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

[Tom Ritter]

I'd like to revive this thread, sorry.  Originally it was about the
anti-tagging mechanism and moving to 4096 bit keys.  Originally, I
thought that the anti-tagging mechanism was valid, but after
discussing it with some other folks [0], I don't think it is.

Specifically: If I'm correct the anti-tagging mechanism asserts the
validity of the _next_ hop, and the payload.  But it only asserts the
validity of the next hop, not the hops after the next hop.

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.

(I'm not writing a paper here, so I haven't thought about how he could
tag it in such a way that he could undo the tag and be certain it was
his tag, I'm just looking at it from an error perspective.  )

Looking at the code, I don't think one would be able to tag a 3-hop
chain, because one would need to tag Hop #4 (which doesn't have a
valid antitag) OR one would need to tag the payload (which is
protected at Hop #2).  Likewise, one is not able to tag to determine
if you're the exit remailer (because of the same Hop#4 problem).

-tom

[0] http://moderncrypto.org/mail-archive/messaging/2014/000527.html