Re: forward secrecy in mixmaster

[Lance Cottrell <loki@infonex.com>]

At 10:03 AM -0700 9/6/96, Adam Back wrote:
>Since Peter Allen's discussion of mixmaster, I started doing something
>I'd been thinking of for a while, since noticing that it was on the
>mixmaster to-do list months ago (ie there is unfinished source to do
>this): direct socket connections and diffie-hellman key exchange for
>forward secrecy.

The code is still out there to look at. I warn you though, it is steaming
horse manure.  ;)


>I wrote the socket stuff yesterday evening, didn't take too long as
>socket programming is something I've done lots of.
>
>Now comes what do you actually send down the sockets.
>
>Question for Lance, and any others who were involved in mixmasters
>implementation: what did you have in mind as a way of negotiating the
>DH keys?
>
>I notice that mixmaster generates a DH key and stores it in file
>`DH.mix', but that this is not (as far as I can see from the source)
>included in the remailers public key block.

No, it is not in the key block. It would be passed during the negotiation.

>(A couple of comments as an aside: I think that you should be able to
>have a much smaller generator without loss of security, this should
>reduce the overhead of a DH key exchange.  Using 3 even I think is
>safe, without any extra precautions on prime generation.  You can even
>go to 2, with a few precautions (PGPfone does this).  Comment #2 I
>think 1024 may be a bit small, I don't have any figures handy for
>relative security of DH key lengths, but PGPfone offers 4096 bit DH
>for instance.  Does rsaref have limits on prime lengths for DH, the
>same as it does for RSA?).

Call me paranoid. After asking and reading around I decided I wanted to
cover my bases. It looked like, in the future, it might be easier to break
with small generators. This is not a critical decision though. I too would
have liked it longer, but using RSAREF I am limited. That is one of the
reasons I have each remailer creat its own DH modulus, and allow it to
change it periodically.

>There are lots of options for DH public key negotiation.
>
>First option is whether you have a common prime and generator for all
>remailers or not.  If you have a common prime, accusations of the
>prime being `cooked' (chosen to have a weakness) can be mitigated by
>using a deterministic generation method based on the hash of a known
>phrase (a Jefferson quote perhaps), or PI or whatever.
>
>A common modulus may offer a fatter target for attack (for some
>precomputation attacks), but with large enough keys this probably
>isn't that bad, as there aren't that many mixmasters anyway.
>
>With a common modulus there is DH key negotiation needed, just include
>it with the source.

You have spelled out why I like having each remailer use its own modulus.

>For different modulii for each remailer, there are more options:
>
>a) include the DH key signed by the RSA key in the remailers public key
>   (may break backwards compatibility with existing versions of
>   mixmaster)
>
>b) send the DH public key at the start of each session
>
>c) send the DH public key on request

I chose C. The in protocol I developed the sending remailer (A) sends a
hash of the DH modulus to the receiving remailer (B). If B has it, they use
it. If not, A sends it. I use the modulus from A because it has the stake
in privacy. B will take messages from anyone, but A wants to know the
messages it has goes to the correct other remailer B.

>There is also a question of which key do you use, the sender remailers
>or the recipient remailers.
>
>Negotiating DH public keys during execution also opens the possibility
>for periodic re-keying.
>
>Thats the end of my thoughts on direct socket mixmaster.
>
>Next message is some thoughts on non-interactive forward secrecy
>protocols.
>
>Adam

Here is a description of the protocol I wrote many months ago. The message
assumed the above discussion of distributing the DH modulus.

--------------Start Old Message--------------

It is too bad that I was never able to debug my socket code. It is more or
less all done. The advantage of the socket code is that it allows the
message to be super-encrypted with a DH negotiated key which provides
forward security for intercepted messages. There is a built in
authentication for the DH (against MITM attacks) in the RSA key used to
encrypt the remailer message to the next remailer. I can send the code I
wrote to anyone on demand (within the US of course).

This basically pushes the key authentication job onto the original sender
where it belongs. The key ID (16 byte fingerprint) is visible in the clear
in the header of the message remailer A is about to send to remailer B.
Remailer A either has the key corresponding to that fingerprint, or it
requires remailer B to send it the key. Remailer B must have the key or it
would not be able to read the message any way. A different RSA key can not
be sent because of the strength of the MD5 fingerprint.

Remailer A sends its DH key half to B along with a challenge number, all
encrypted under B's RSA key. Return of the challenge number along with B's
DH key half, completes the authenticated exchange. The second half could
also be encrypted with a 3DES key provided along with the challenge number
if desired.

The whole point of all this is that if the message is intercepted and
presented to B with a demand to decrypt it, B will be unable to comply,
even if it wished to.

        -Lance

--------------End Old Message--------------

----------------------------------------------------------
Lance Cottrell   loki@obscura.com
PGP 2.6 key available by finger or server.
Mixmaster, the next generation remailer, is now available!
http://www.obscura.com/~loki/Welcome.html or FTP to obscura.com

"Love is a snowmobile racing across the tundra.  Suddenly
it flips over, pinning you underneath.  At night the ice
weasels come."
                        --Nietzsche
----------------------------------------------------------