[messaging] Mixmaster Protocol Design

Tom Ritter tom at ritter.vg
Mon Jul 14 12:39:38 PDT 2014

Hi all,

My friend Zax (cc-ed) emailed me with some comments about the new,
proposed, Mixmaster protocol design.  I'd like to reproduce his email
with my comments inline, and I'd love to have people discuss and see
if they agree with me. I believe Zax has his own proposal for altering

Some of the questions I turned into a more generic discussion, but the
overall topic is Mixmaster...

On 7/11/14, 10:39 AM, Steve Crook wrote:
> Hi Tom,
> I was wondering if you've been involved at all in the recent work to
> produce a mixmaster version with support for larger keys?  I don't
> believe a spec exists for it so I've been digging through the code,
> trying to piece it together.
> 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]
> There are some aspects of this I either don't like, or perhaps don't
> understand.  I'd appreciate your thoughts.
> Why use RSA to encrypt anything more than the session key?  All the new
> fields could go in the Encrypted header or maybe, for backwards
> compatibility, in a second encrypted header.  I don't think it's good
> practice to use RSA to encrypt anything beyond the session key.

I don't think it is either.  You shouldn't concat a bunch of stuff
together and then RSA encrypt it - encrypt one thing and then
symmetrically encrypt the rest.

So here's what I'm thinking.  The RSA-encrypted data is N bytes of key
material, that is used to derive both a TDES Key and an HMAC Key.  Put
an HMAC value after the Encrypted Header in the Padding.  Upon receipt,
decrypt the key material, derive your keys.  Authenticate the cipher
text, and then decrypt it.

You would stick the HMAC of the Anti-Tag (this is authentication of the
next Mix Header, preventing the tagging attack, right?) and the HMAC of
the Body into the Encrypted Header, which is decrypted after you derive
the HMAC & TDES key.  Those could be hashes though, as they are
protected by the cipher text's HMAC.  But, it 'feels right' to
authenticate the data with an HMAC instead of a plain hash.

> What's the benefit of using HMAC rather than simple hashes?  As the HMAC
> key is transported in the same block as the hashes, it doesn't appear to
> provide any authentication.

HMAC protects against Length Extension, but one would not be able to
manipulate the RSA cipher text to modify the hash in any predictable
manner, and the lengths of fields are fixed.  I cannot see a benefit.
You could replace those with hashes to the same effect.

> Why have three hashes at all?  One hash could validate the anti-tag,
> body and encrypted header.

This seems to be a general question.  If I have 3 fields of data,
perhaps encrypted to different keys, and I want to authenticate them
all, is there a benefit or disadvantage of constructing a ?pseudo
format? where I concat the fields together and then authenticate the
whole thing vs having three hashes authenticating them individually.

I?m reminded of the PGP V3 Key Format Fingerprint Vuln.  It concatted E
to N and then used that to generate the fingerprint. By creating a key
with a large E composed of the top bits of N, and a small N composed of
the low bits, you could construct a match.  The solution was the add the
length bytes before E and N.

So my conclusion is that it IS safe to construct a pseudo format as long
as you preface all fields with the length of the field.  But even with
that safety feature, if saving every single byte on the wire is not a
priority, I would probably say to separate them.

> Last of all, why add AES but retain 3DES?  As this is new remailer
> functionality, it would seem more logical to just use AES for
> everything.

Probably minimizing the amount of code that changes.


More information about the Messaging mailing list