Ben Laurie blathering

Two Anonymity Papers

I just posted two old papers that I’d somehow managed to not put up before.

The first is on Apres, a system for anonymous presence and the second is Minx, an anonymous packet format that defeats traffic marking attacks by making all packets valid (even corrupt ones), which I wrote with George Danezis.

I also have an implementation of Apres, as a Perl library, and two instantiations of it. The first is a pair of command-line tools that communicate using TCP/IP (over something like Tor, of course) and the second is an IRC bot that acts as the server and an xchat plugin that is the client. I have not bundled those up and put them somewhere yet, but I will someday (sooner if anyone actually wants to play with them: nag me).


  1. I have a couple of comments on your Minx design. In the encryption step, what if the input to the RSA operation is bigger than the RSA modulus? Then it will not decrypt correctly.

    In section 7 you describe a measure to prevent this, but it is to fix a different problem, one that is unclear to me: “it is possible in some cases to identify a subset of keys which the creator of a ciphertext must be amongst.” This was confusing at first because keys don’t create ciphertext. However in this context I think you mean that inspection of the ciphertext input to a mix node might reveal which mix node it came from, because the output from that predecessor node has to be less than its RSA modulus.

    Your fix for this is for the message creator to ensure that all outputs are 1023 bits (not 1024), and then pad the highest bit randomly. Presumably this high bit is discarded before decryption.

    I don’t see why this is even a security requirement. It should be no secret which mix was the predecessor. The assumed adversary is able to track all messages through the network. For each message input to a given mix node, it is assumed to be known which node it came from. What we want to prevent is linkage between the input and output of a given node, not linkage from the output of one node to the input of the next.

    I am a little confused by the role of the “tag” or directory-index number “i”. Apparently this is supposed to be a uniform random bit pattern. Your description first says that Alice chooses her mix servers i_1 through i_n and sets up the message. The it says that “if” Alice creates her route using random values then the average route length will be 8. Does your security analysis depend on Alice creating routes in this way?

    If most users don’t do this, and non-random values are present in this field, then there might be a tagging attack. Randomly alter one message going into mix X, and corrupt mix Y. Decrypt the messages in Y that came from X and see if one of them has an unusual value in the tag field. This would be the one that was tagged.

    Alternatively, do the same thing and in mix Y look for messages that are “Final” but which are malformed. Such a message has been corrupted earlier, hence it was one which was tagged.

    What is the security requirement here? Is it OK to be able to trace messages in this way, as long as they turn to garbage? Does that not reveal anything of interest? What if some users consistently use the same paths? I am worried that it might be possible to put together small pieces of information like this and deduce something about usage patterns. I gather that mixminion uses authentication to prevent this kind of tracing.

    Comment by cyphrpunk — 7 Nov 2005 @ 22:05

  2. To follow up on that, a simpler attack might occur if Alice typically uses a particular exit node, perhaps one controlled by the attacker, and he wants to verify that fact. He can corrupt some data in the tail of the message as it leaves Alice’s computer, and then see if he receives a corrupted message in his exit node. Assuming that corrupted messages are rare, he could soon determine that only when he corrupts one of Alice’s messages he shortly gets a garbage message. This would be strong evidence that Alice was using his node as her exit node.

    Comment by cyphrpunk — 10 Nov 2005 @ 5:00

  3. […] Another is Minx, a system for anonymising Internet traffic which defeats traffic marking attacks by making all packets valid, and all damage to packets comprehensive. Minx uses a variant on IGE, bi-directional IGE (biIGE), which spreads damage to the ciphertext over the whole plaintext. This is also implemented in OpenSSL. […]

    Pingback by Links » Infinite Garble Extension — 29 Aug 2006 @ 22:26

  4. […] Erik Shimshock, Matthew Staats, and Nicholas Hopper, that shows an attack against the Minx scheme Ben Laurieand myself had proposed back in 2004. Minx is a cryptographic packet format to be used by anonymous […]

    Pingback by A quick fix for Minx « Conspicuous Chatter — 18 Aug 2008 @ 13:54

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress