We examine covert channels in privacy-enhanced mobile identification devices where the devices uniquely identify themselves to an authorized verifier. Such devices (e.g. RFID tags) are increasingly commonplace in hospitals and many other environments. For privacy, the device outputs used for identification should "appear random" to any entity other than the verifier, and should not allow physical tracking of device bearers. Worryingly, there already exist privacy breaches for some devices [28] that allow adversaries to physically track users. Ideally, such devices should allow anyone to publicly determine that the device outputs are covert-channel free (CCF); we say that such devices are CCF-checkable.

Privacy-preserving protocols allow multiple parties with private inputs to perform joint computation while preserving the privacy of their respective inputs. An important cryptographic primitive for designing privacy-preserving protocols is secure function evaluation (SFE). The classic solution for SFE by Yao uses a gate representation of the function that the two parties want to jointly compute. Fairplay is a system that implements the classic solution for SFE. In this paper, we present a new protocol for SFE that uses a graph-based representation of the function. Specifically we use the graph-based representation called ordered binary decision diagrams (OBDDs). For a large number of Boolean functions, OBDDs are more succinct than the gate-based representation. Preliminary experimental results based on a prototype implementation shows that for several functions, our protocol results in a smaller bandwidth than Fairplay. For example, for the classic millionaire's problem, our new protocol results in a approximately $45$\% bandwidth reduction over Fairplay. Therefore, our protocols will be particularly useful for applications for environments with limited bandwidth, such as applications for wireless and sensor networks.

Address-space randomization is a technique used to fortify systems against buffer overflow attacks. The idea is to introduce artificial diversity by randomizing the memory location of certain system components. This mechanism is available for both Linux (via PaX ASLR) and OpenBSD. We study the effectiveness of address-space randomization and find that its utility on 32-bit architectures is limited by the number of bits available for address randomization. In particular, we demonstrate a derandomization attack that will convert any standard buffer-overflow exploit into an exploit that works against systems protected by address-space randomization. The resulting exploit is as effective as the original exploit, although it takes a little longer to compromise a target machine: on average 216 seconds to compromise Apache running on a Linux PaX ASLR system. The attack does not require running code on the stack.