[Remops] mixmaster's 1024-bit RSA is getting old (Take 2)

[lists at notatla.org.uk]

> Trevor points out that I can simply tag the subsequent hop and detect
> it.  It would look like this:
> 
> Mix #1 (Attacker) wants to see if he is Hop #3 for this message.  He
> tags Header #4 (or if you're not counting the header encrypted to him,
> Header #3)
> Mix #2 (Honest) decrypts his header fine.
> Mix #3 (Attacker) decrypts his header fine, but upon checking the
> antitag for Header #4 sees that it's invalid.  He knows he tagged the
> message, so he's fairly sure that this is his tagged message.
> 
> -tom
> 
> [0] http://moderncrypto.org/mail-archive/messaging/2014/000527.html


> 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


My aims in extending mixmaster last year were:
- increase RSA key size and actually get it deployed
- protect against the tagging attack described by Tom Ritter
- add AES encryption
- delete private keys after they have expired

Since deployment only works if done gradually I catered for RSA
key sizes of 1k, 2k, 3k and 4k - where the 1k behaviour is unchanged
from the legacy code.  I enabled a remailer to have multiple
keys at once expecting a changeover period when a remailer might
have a 1k and a 4k key.

The 2k and 3k sizes were in case a lot of people wanted them and
thought 4k was unnecessary.  The legacy 3DES was left in because
the code had to be there for the 1k case and adding AES over the
unchanged 3DES should avoid arguments over whether the new version
was stronger or weaker.

The tagging defence was a response to
  https://crypto.is/blog/tagging_attack_on_mixmaster
and I believe it works for that specific attack.  I didn't look into
the possibilities of tagging further into the chain - perhaps I should
have but the work to deal with that is more because of the way it
involves the position in the chain.

HMAC involves running a hash twice similar to
    Practical Cryptography section 6.4.1
    Cryptography Engineering section 5.4.1
and the sha256 now in use is better than the legacy MD5.

That may be hackish but it's aimed at making mixmaster usable
for longer - so no radical changes.