Re: Problems with bit-twiddlers

[George Danezis <gd@theory.lcs.mit.edu>]

On 28 Mar 2002, Nick Mathewson wrote:
> 4) We discover a magical, efficient, symmetric whitening process, such
> that changes to X have no predictable effect on W(X), and so that
> W(W(X))=X.  This would solve all our problems, but seems unlikely to
> turn up. ;)
> 

I am looking into this kind of magic for the moment. There is a family of 
algorithms that are called "all-or-noting" transforms, or variable-size 
block ciphers, that have the property you describe. The main problem is 
that you cannot perform the operation in one go on the rest of the headers 
and the payload if you do not know the payload in advance (the case for 
SURBs).

So my thoughts are moving in the following direction:
- Have a fixed size header that contains all the routing information. Each 
intermediate mix reads the first 126 bytes and decrypts them. Then it can 
decrypt the rest of the fixed size headers and check that it hashes to 
something known (to avoid the header tagging attacks (No 2))

- Then the payload at each stage is whitened by an all or nothing 
transform (call it BEAR - see paper by Anderson). This makes sure that a 
modification at any step will result in the next BEAR operation giving out 
complete garbage. In that way only 1 bit of information can be leaked: is 
the decryption meaningful or just garbage? It is not possible to perform 
any more sophisticated tagging, to associate particular messages with 
particular senders.

- Disadvantages: There is a smaller limit to the number of hops (if we 
decide to have a 2kb header that gives us 16 hops maximum, which should 
not be too insecure).
- Advantages: Limit the information gained by traffic tagging. (that was 
the point)
  Since the header size is fixed it is not possible for even the last node 
to be aware of how many hops the message has gone through (that is new).
  We can protect the integrity of the message header, so that any 
modification is noticed, and makes it invalid.

Let me know,

G.