[messaging] Mixmaster Protocol Design

[Trevor Perrin]

On Mon, Jul 14, 2014 at 12:39 PM, Tom Ritter <tom at ritter.vg> wrote:
>>
>> The original header spec was:
>>
>> Public key ID                [   16 bytes]
>> Length of RSA-encrypted data [    1 byte ]
>> RSA-encrypted session key    [  128 bytes]
>> Initialization vector        [    8 bytes]
>> Encrypted header part        [  328 bytes]
>> Padding                      [   31 bytes]
>> -----------------------------------------
>> Total                        [  512 bytes]
>>
>> The new spec appears to be:
>>
>> Public key ID                [   16 bytes]
>> Length of RSA-encrypted data [    1 byte ]
>> RSA-encrypted data           [  512 bytes]
>>     3DES Session Key              [  24 bytes ]
>>     Random HMAC Key               [  64 bytes ]
>>     HMAC hash (Anti-tag)          [  32 bytes ]
>>     HMAC hash (Body)              [  32 bytes ]
>>     HMAC hash (328 Byte Enc Head) [  32 bytes ]
>>     AES Key                       [  32 bytes ]
>> Initialization vector        [    8 bytes]
>> Encrypted header part        [  328 bytes]
>> Padding                      [    n bytes]
>> -----------------------------------------
>> Total                        [ 1024 bytes]


Looks pretty hack-ish:

 * Compared to Sphinx [1] which can use curve25519 to encode headers
for 10 mixes in 384 bytes total, this format would use 10 KB, i.e.
it's about 30x less space efficient than it could be.

 * My guess is the "Anti-tag" hash only covers the next header, as you
mention and as described at [2], so fails to prevent tagging attacks
against later headers (e.g. see Sphinx and Mixminion which
integrity-protect all headers).

 * I assume this is RSA PKCS#1 encryption as per Mixmaster, which
should be avoided in new protocols.

 * The use of HMAC side-by-side with the HMAC key doesn't accomplish
anything vs a straightforward hash.

 * The presence of AES side-by-side with 3DES is weird.

Side question, for you or anyone:  Is this really the
"state-of-the-art" in real-world remailers?  Is no-one working on
anything better?

Trevor

[1] https://eprint.iacr.org/2008/475.pdf
[2] https://github.com/merkinmuffley/mixmaster4096/blob/master/doc/README_302