A quick fix for Minx
18 August 2008
Last month I attended the Privacy Enhancing Technologies ( PET 2008 ) Symposium in Leuven, Belgium. The programwas fantastic, with a strong focus on anonymous communications, and many papers on traffic analysis. The associated HotPETS event, was also very fun, with plenty of time for discussion, and the added advantage that all the papers are on-line.
A paper that had to catch my attention was entitled “Breaking and Provably Fixing Minx” by Erik Shimshock, Matthew Staats, and Nicholas Hopper, that shows an attack against the Minx scheme Ben Laurie and myself had proposed back in 2004. Minx is a cryptographic packet format to be used by anonymous remailers (or mixes) for high-latency, email like, communication. It was designed to be space efficient, meaning that we radically cut down on the padding and redundancy within the packet, and used raw RSA.
That last use of raw RSA proved to be a bridge too far: recent results show that all bits of RSA are hardcore, meaning that if you do not know the key you cannot guess them. Sadly the inverse is also true, and if you can know even a single bit of the plaintext with non-negligible advantage, there is a polynomial time algorithm to extract the key.
Minx does leaks sufficient information about the plaintext to the adversary to use this algorithm. It is a theoretical attack, that poses no danger to those using Minx for the moment (is anyone?), but goes to show that there cannot be a security proof for Minx. The leakage is subtle: Minx effectively encrypts a session key and the address of the next hop, as well as the symmetrically encrypted message to be relayed under the RSA key of the intermediate mix. We can denote the message as: E_RSAi(Ki, Next, E_Ki(M)), where E_x(.) denotes encryption under a key x. The adversary observes the message going into the Mix i and then at some later time observes a bunch of messages leaving the mix, including a message Mix i -> Next: M. It know knows that the the string “Next”, which is the address of the next hop must have figured verbatim within one of the input ciphertexts and can use this to extract the RSA key (after a lot of computation.)
The paper exhibits really solid scholarship, when it comes to the attack, and also provides a fix that yields a provable mix packet format. Sadly the proposed mix packet format is very verbose, and requires a separate RSA ciphertext for each intermediate mix the message is relayed through (the original Minx header is as long as a single RSA encryption plus the routing and symmetric key information for each hop.)
A simpler fix for Minx, against this particular attack, could be to include the “Next” address (which is just a single byte in the original proposal) inside the symmetrically encrypted shell of the message. The modification would result in a message with the conceptual format: E_RSAi(Ki, E_Ki(Next, M)). Through this modification every single bit within the RSA ciphertext cannot be predicted with probability better than 1/2, based on the security of the symmetric encryption scheme and the secrecy of Ki. It is an open exercise to take this modified scheme and prove formally that there are not other applicable attacks.