Quick links

Buffer Overflows and Group Signatures: Recent Results in Security and Cryptography

Date and Time
Wednesday, April 11, 2007 - 4:15pm to 5:45pm
Computer Science Small Auditorium (Room 105)
Hovav Shacham, from Weizmann Institute
Edward Felten
We analyze the effectiveness of two techniques intended to make it harder for attackers to exploit vulnerable programs: W-xor-X and ASLR. W-xor-X marks all writable locations in a process' address space nonexecutable. ASLR randomizes the locations of the stack, heap, and executable code in an address space. Intel recently added hardware to its processors (the "XD bit") to ease W-xor-X implementation. Microsoft Windows Vista ships with W-xor-X and ASLR. Linux (via the PaX project) and OpenBSD also include support for both.

We find that both measures are less effective than previously thought, on the x86 at least. A new way of organizing exploits allows the attacker to perform arbitrary computation using only code already present in the attacked process' address space, so code injection is unnecessary. Exploits organized in the new way chain together dozens of short instruction sequences, each just two or three instructions long. Because of the properties of the x86 instruction set, these sequences might not have been intentionally compiled into the binary; we find them by means of static analysis. Furthermore, the effective entropy of PaX ASLR can be searched by brute force. The attack takes just a few minutes to mount over the network.

Group signatures are a variant of digital signatures that provides anonymity for signers. Any member of a group can sign messages, but the resulting signature keeps the identity of the signer secret. In some systems there is a third party that can undo the signature anonymity (trace) using a special trapdoor. New applications for group signatures include the trusted computing initiative (TCPA) and vehicle safety ad-hoc networks (DSRC). In each case, group signatures provide privacy guarantees for tamper-resistant embedded devices.

We describe a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. The mathematical setting for our scheme is certain elliptic curves featuring an efficiently computable bilinear map, a setting that has proved fruitful in recent years. We also consider two choices for handling revocation in our scheme.

Follow us: Facebook Twitter Linkedin