Re: Problems with bit-twiddlers

[Nick Mathewson <nickm@alum.mit.edu>]

On Fri, 2002-03-29 at 12:21, George Danezis wrote:
> 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.

Cool!  I had a suspicion that this might be the case, but I didn't know
for sure.

> 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).

Hm.  Isn't it also a problem for SURBs that we require that E(x) and
D(x) both provide equivalent security?  Do any of the transforms you're
looking at provide this?

As for the issue you mention, perhaps there could be one pass on the
payload, and one on the headers...

> 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))

Hm.  This is probably a good idea, and it is (I believe) what Mixmaster
3 (and possibly 2) do as well.  Now we know why they do it. :)

> - 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.

If garbage is dropped at each stage, we're fine.  If not, a hostile
adversary who owns 3 nodes of a 4-node cascade can use the 1 bit of
information to trace particular messages at will.

I'm not totally sure how this step works in the forward and reply
directions.  Could you sketch out a brief example?

> - Disadvantages
 [...]

I think that this direction is a good one to follow.
-N