tagging attacks and forward-message/reply-message distinction

[Zooko <zooko@zooko.com>]

[Cc: my consultant, Amber O'Whielacronx]

Hi folks:

I talked to Roger on the phone last night and I've read all the messages about 
tagging/twiddling attacks.  (I still haven't carefully read the new messages 
about "API", "comments on latest draft", and "daystamp attacks", although I've 
scanned them.)

I'm going to restate what I think we all agree on and then propose an 
improvement.

 --- stuff we agree on

1.  We don't want a node to learn anything by forwarding a modified message.  
There are only two ways that we know to ensure this:

1.a.  The next node detects that the message has been modified and drops it.  
(Idea: if a node detects the modification but it isn't the next node after the 
modifier, and thus cannot safely drop it without revealing path information, 
then the detecting node could instead replace it with dummy traffic.  :-)  But 
my proposed improvement below obviates the need for this trick.)

1.b.  The modification cannot be detected by anyone other than the anonymous 
party (the original sender).  That is: if node N attempts to tag a message by 
twiddling a bit, and then node N+1 re-whitens it by XOR'ing with with CTR mode, 
and then nobody other than the anonymous party ever sees the decrypted 
plaintext, nobody can "read" the tag that node N attempted to "write".  The 
XOR'ing erases it from the ciphertext, and no potential attackers see the 
decrypted plaintext.

2.  We can implement these using straightforward techniques, but unfortunately 
they are different techniques for forward-travelling messages versus reply 
messages:

2.a.  We can implement 1.a. for forward-travelling messages, both headers and 
payload, by having the original sender include MACs of both header and payload 
in each layer.  (Or an equivalent integrity guarantee such as all-or-nothing or 
an integrity-plus-encryption mode.)

2.b.  We can implement 1.a. for reply-message headers and 1.b. for reply-message 
payload by having the original sender include MACs, only for headers, in the 
reply block, and having the payload be {en,de}crypted at every hop and never 
visible as decrypted plaintext except to the original sender.  (This means that 
the padding has to be appended to the headers instead of the payload so that the 
node can MAC over the headers without knowing how many layers are left to be 
processed.  It also means that the padding has to be deterministically generated 
from a secret know to the original sender and to the generating node but not to 
anyone else.)

3.  It isn't good for forward-travelling and reply messages to be distinguishable
(although I haven't seen any explanation about how *bad* it might be).


 --- proposed improvement

At a cost of two times message expansion, we can combine both kinds of messages 
in such a way that each node in the chain cannot tell whether it is processing a 
forward-travelling or reply message.

Each message has three parts: header, "forward" payload (which I'll call an 
A-payload), and "reply" payload (which I'll call a B-payload).

The node that is processing a message decrypts his header, checks MACs on the 
headers and on the A-payload but not on the B-payload, applies the CTR-mode 
{en,de}-cryption to both payloads, and forwards.

When the message is a forward-travelling message, then the actual message (and 
reply block) are hidden inside the encrypted A-payload.  When the message is 
a reply message, then the message is hidden inside the encrypted B-payload.  But 
what is the contents of the A-payload when the message is actually a reply?  It 
is dummy garbage which looks like an encrypted payload, and which matches the 
MACs that the original sender included in the reply block!

Where did the replier gets this dummy A-payload?  It is generated 
deterministically by the replier from a secret that the original sender included 
along with the reply block in the original A-payload.

Now for every part of the message we have one or other the guarantee: either it 
comes with a MAC and it gets verified at every hop, or it gets re-encrypted at 
every hop and nobody ever sees the resulting decrypted plaintext except for the 
original sender.

The dummy B-payload in forward-travelling messages is random garbage which is 
redirected to /dev/null by the receiver.  In order to get our 1.b. guarantee 
against tagging attacks, we cannot use this data for anything.

Regards,

Zooko

---
                 zooko.com
Security and Distributed Systems Engineering
---