Double headers to protect against tagging

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

Dear All,

After having read properly Zooko's proposal I got the idea that we can use 
two headers to avoid tagging attacks all together. It also follows from my 
last email exchange with Nick.

The intuition is the following:

We have two routing headers H1 and H2 and a payload M.
Both H1 and H2 have their integrity protected by Hashes and are discarded 
is changed.

Both H2 and M are encrypted using BEAR (or other all or nothing transform) 
by the keys contained in H1. Additionally H2 is encrypted using H(M') as a 
key to a BEAR transform.

The processing is muxh as before: The first routing header is decrypted 
and checked as it goes along, and the inverse BEAR transform is applied to 
the second header and the payload. 

The only difference is that the last hop of the first routing header is 
also doing the following: it Hashes the payload M and uses it to decrypt 
the second header. Then the second header has its position exchanged with 
the first on and is now in front of the packet.

The packet is passed along to the next mix which treats it as any other 
packet. 

Why does that help? If someone tags the first header at any point the 
packet is rejected at the next hop. So the header tagging attack is not 
possible.

Now if someone tries to tag the second header or the body of the message 
is will be impossible to retrieve any of these (H2 depends on the body and 
the body depends on secrets inside H2, creating effectively a ladder 
structure). Therefore the packet will have to be dropped at the end of the 
first Header. 

It is still possible to run the tagging attack after the special step, but 
by then the message has already traveled through the network securely 
(using the first header) and the attacker cannot therefore link it back to 
the original sender (although the anonymity set is reduced).

This approach has the advantages to only waste an additional header, which 
is used anyway. It provides undistinguishability between forward and 
return mechanisms, and is resistant against all tagging attacks.

The technical details are not yet completely worked out but I have a pretty 
picture (in pdf) that shows the standard processing both conceptually and 
in terms of cryptography. You can find it at:

http://www.cl.cam.ac.uk/~gd216/MixMinBEAR.pdf

(I am not sure how happy CVS is receiving PDF files, so I have not checked 
it in yet)

I am looking forward to hear what you think

Yours,

George

PS: I also have some techical specs:

We redefine the header to contain the following:

Major Version, Minor Version: V [2 bytes]
Master Secret: MS [16 bytes]
Timestamp: T [2 bytes] (is that correct?)
Size: S [2 bytes]
Type: Tp [1 bit] * Note the 1bit*
Transform: Tr [1 bit] * Note the 1bit*
Hash: H [10byte]
Address Type, Next Address, Dest. Port, Expected Key: A [40bytes]

We denote a particular header composed of the above elements as:

MH(V, MS, T, S, Tp, Tr, H, A)

Define:
- if B is a byte array, B[i:j] (j bytes) is sub array starting at 
  byte i with length j.
- R(n) (n bytes) Generates n random bytes. Only used by client.
- Z(n) (n bytes) Generates n zero bytes
- Len(M) (2 bytes) is the length of message M (* bytes)
- x|y (Len(x)+Len(y) bytes) denotes x concatenated with y.
- PAD(M,L) (L bytes) pads the message M (Len(M) <= L) to length L
[Q Pads it with what? -RD]

- H(M) (20 bytes) is the SHA-1 hash of M (* bytes)

- RSA_OAEP_Encrypt(K,M) (128 bytes): the encryption of M (73
  bytes) using the public key K as described in PKCS\#1.
- RSA_OAEP_Decrypt(K,M) (73 bytes) Gives the decryption of the
  message M (128 bytes) under the private key corresponding to K.
- Encrypt(K,M) (Len(M) bytes) Rijndael in Counter mode encryption 
  of message M using key K. 
- Decrypt(K,M,i,j) (j bytes) Rijndael counter mode decryption 
  using the key material byte i to j. Len(M) = j.

The encoding of apacket is now:

Input: K1...Kn keys of M1...Mn
Input: Kn+1...Km keys of Mn+1...Mm

where n and m-n have to be smaller than some constant.
(The maximum for each header "Max")

Then we construct 2 headers: 

The prevJunkBlock procedure constructs the encrypted junk that a mix would
expect to see for the purpose of calculating the correct hash.

Header 1: H1
- S[1..n] = R(16) // Think of n master secrets
- J = R(128* (Max - n)) // Junk to fill the routing header.
- M = J

- for i = n to 1
  H = H(M | PrevJunkBlock(i))
  if i = n then tr = 1 else tr = 0
  Ma = RSA_OAEP_Encrypt(Kn, MH(V, Si, T, 62k, 0, Tr, H, Mi)) 
  Mb = Encrypt(H(Si,"SECRECY_MODE")[0:16], M)
  M = Ma | Mb

Header 2: H2
- S[1..n] = R(16) // Think of n master secrets
- J = R(128* (Max - n)) // Junk to fill the routing header.
- M = J

- for i = m to n+1
  H = H(M | PrevJunkBlock(i))
  if i = m then tp = 1 else tp = 0
  Ma = RSA_OAEP_Encrypt(Kn, MH(V, Si, T, 62k, 0, Tr, H, Mi)) 
  Mb = Encrypt(H(Si,"SECRECY_MODE")[0:16], M)
  M = Ma | Mb

Final Message:
input: message "Msg"

for i = m to n+1
   Msg = BEAR(H(Si,"BEAR_BODY_MODE")[0:16],Msg)
end
H2 = BEAR( H(Msg)[0:16], H2)
for i = n to 0
   H2 = BEAR(H(Si,"BEAR_HEAD_MODE")
   Msg = BEAR(H(Si,"BEAR_BODY_MODE")[0:16],Msg)
end

Final message (M0,H1|H2|Msg)

In order to construct a return address the second header H2 is constructed 
using a MasterMasterSecret MMS used to generate all the other Si, which is 
stored 
in the Mm header along with the number of hops. The message is not then 
BEARed using 
any of the keys inside the H2 header.
 
Standard processing:

MMProcess(K_x, M)
- MH(V,MS,T,S,Tp,Rt,Ru,A) = RSA_OAEP_Decrypt(K_x,M[0:128])
- Check that the OAEP structure is intact.
- Check that protocol version V is supported.
- Check T to make sure the message is valid.
- Calculate US = H(M[0:128]) and check that it has not been
  seen before.
- Store US.
- if tp = 0
  o Check that S = 62kb
  o Check the hash H on the rest of the header 
    H == H(M[128:128*Max-128])
  o D = Decrypt(H(MS|"SECRECY_MODE")[0:16],M[128:Max*128])
  o J = Encrypt(H(MS|"JUNK_GENERATION_MODE")[0:16], Z(128))
  o M = M[128:128*Max] | J | M[128*Max:62k-128*Max]
  o if tr = 1
      + H2 = BEAR( H(M[128*Max*2:62k])[0:16], M[128*Max:128*Max])
      + M = M[128*Max:128*Max] | M[0:128*Max] | M[128*2*Max: 62k - 
128*2*Max]
  o Send (K_x, M) to the network
- else
  [The procedure goes on as before taking into account 
  that SURB messages need to be decrypted before it is
  given to the application.]