forward secrecy in mixmaster

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.

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.

(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?).

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.

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

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
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

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
----------------------------------------------------------

Lance Cottrell <loki@infonex.com> writes on several lists:
> >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.

Well the first DH parameter set (in a series of re-keyed DH
parameters) could just as easily go in the public key block.  If you
were not doing rekeying, it would make sense to put the public DH
parameters in the key block, as it would remove the need to negotiate
these parameters, and simplify the protocol.  As you're doing
rekeying, putting the parameters in the public key block makes a less
orthogonal protocol, adds nothing, and has the negative effect of
breaking compatibility with previous public key blocks.  In short for
a rekeying protocol I agree :-)

> >[bigger keys!]
> 
> 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. 

Fair enough.

> This is not a critical decision though. I too would have liked it
> longer, but using RSAREF I am limited. 

I suspected RSAs weird license might be the problem.  (Given the
situation with PGP 2.x, I presume that the license does not permit you
to increase the max arithmetic precision.)

> That is one of the reasons I have each remailer creat its own DH
> modulus, and allow it to change it periodically.

Each remailer with it's own prime doesn't buy you a whole lot of
entropy because there aren't many mixmaster remailers, 4 bits
currently?.  The entropy from having rekeying every day instead of say
every year, another 9 bits, 13 bits tops?  I'm not sure what the
precise entropy increase is from going to 1024 to 4096, but it's got
to be many orders of magnitude better than 13 bits.

I'd say junk RSAREF for the DH operations, use one of the other libs.
(You can do this for DH, without violating patents, right?  But not
for RSA, so I guess if you care about the patent/license agreement
mess, you've got to use RSAREF for RSA signatures at least).  Or maybe
you could just wait for PGP 3.0 which uses El Gamal, for sigs and pk
encryption, and presumably will have less restrictive key sizes.

So as well as having bigger signing keys, for the sake of paranoia
(it's contagious), as you were saying, I guess you may gain some
security by not having a common modulus, and making the protocol allow
re-keying.

If you used a different password for RSA and DH keys, and your machine
is compromised, you can sign a new DH key with RSA, and use El Gamal
signatures with the DH key normally.  Hows that for paranoid :-)

(Or another temporary RSA key, and RSA sigs, rather than El Gamal
sigs, whatever.  You sign by proxy, that is the receiver mixmaster
gets a the temporary key signed by the long term RSA key, checks the
signature on the temporary key, and then checks the signature made by
the temporary key on the object in question).

Greatly reduces the risk of having the password in the binary.  You'd
need to manually type the RSA keys password to rekey, or if you were
real paranoid, you could keep the RSA key on your laptop, and copy the
new signed DH public key on to the remailer.  Do this once a month, or
as often as you wish.

This is a similar approach to that taken by people who have a huge
signing only PGP key, which they are careful to keep only on machines
they physically control, and have smaller keys which they use on
multi-user systems.

This also formalizes the situation where remailers have been
compromised, or suffered disk crashes.  The operator says, "sorry
folks new type2 key for mixmaster@xyz.org", and if you're lucky signs
his post, and also his post of the original key, so that you know it's
not a hijacker, and if you're even more lucky, the user was around
when the first post was made, or searches through the archives for it,
and checks that the sigs show a persistent identity for the operator.
An improvement right?  The remailers keep both their signing keys, and
their temporary signing keys available by request, the signing key
should not change through the remailers life-time.

> >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.

yeah, ok, I agree no common modulus.  And rekeying.

> >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.

sounds fine.

Also, you might want to migrate to SHA1 in place of MD5, at some
point.  Or to one of those megahashes like

	SHA1(MD5(x))||MD5(SHA1(x))

Also mixmaster has capabilities like type 1 remailers right?  If so
you would presumably add a capability indicating that the remailer
supports direct socket delivery.  And another capability for forward
secrecy (the other thread "non-interactive forward secrecy" discusses
ways to retro-fit a less interactive forward secrecy mechanism into
email delivered mixmaster packets).

The socket capability presumably would be useful to know that it is
likely to react more quickly.  Forward secrecy is obviously nice to
know about for other reasons.

Adam
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

At 11:29 AM -0700 9/8/96, Adam Back wrote:
>Lance Cottrell <loki@infonex.com> writes on several lists:

>I suspected RSAs weird license might be the problem.  (Given the
>situation with PGP 2.x, I presume that the license does not permit you
>to increase the max arithmetic precision.)

Our options will open up alot when the patent expires next year.

>> That is one of the reasons I have each remailer creat its own DH
>> modulus, and allow it to change it periodically.
>
>Each remailer with it's own prime doesn't buy you a whole lot of
>entropy because there aren't many mixmaster remailers, 4 bits
>currently?.  The entropy from having rekeying every day instead of say
>every year, another 9 bits, 13 bits tops?  I'm not sure what the
>precise entropy increase is from going to 1024 to 4096, but it's got
>to be many orders of magnitude better than 13 bits.
>
>I'd say junk RSAREF for the DH operations, use one of the other libs.
>(You can do this for DH, without violating patents, right?  But not
>for RSA, so I guess if you care about the patent/license agreement
>mess, you've got to use RSAREF for RSA signatures at least).  Or maybe
>you could just wait for PGP 3.0 which uses El Gamal, for sigs and pk
>encryption, and presumably will have less restrictive key sizes.

I agree it does not make much difference mathematically, but one DH modulus
always makes me uneasy. DH is still patented though. I think I will continue
to use RSAREF, but compose the standard so the protocol supports unlimited
key sizes.

>So as well as having bigger signing keys, for the sake of paranoia
>(it's contagious), as you were saying, I guess you may gain some
>security by not having a common modulus, and making the protocol allow
>re-keying.
>
>If you used a different password for RSA and DH keys, and your machine
>is compromised, you can sign a new DH key with RSA, and use El Gamal
>signatures with the DH key normally.  Hows that for paranoid :-)
>
>(Or another temporary RSA key, and RSA sigs, rather than El Gamal
>sigs, whatever.  You sign by proxy, that is the receiver mixmaster
>gets a the temporary key signed by the long term RSA key, checks the
>signature on the temporary key, and then checks the signature made by
>the temporary key on the object in question).
>
>Greatly reduces the risk of having the password in the binary.  You'd
>need to manually type the RSA keys password to rekey, or if you were
>real paranoid, you could keep the RSA key on your laptop, and copy the
>new signed DH public key on to the remailer.  Do this once a month, or
>as often as you wish.
>
>This is a similar approach to that taken by people who have a huge
>signing only PGP key, which they are careful to keep only on machines
>they physically control, and have smaller keys which they use on
>multi-user systems.

For now I think we might just suggest that the operator keep a big PGP key
to sign new key releases with. Key management is a whole nother thorny
issue. I would love to see that whole part of Mixmaster reworked. Some deep
thought should go into managing and distributing keys (it was almost an
afterthought in my design).

<SNIP>
>> >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.
>
>sounds fine.
>
>Also, you might want to migrate to SHA1 in place of MD5, at some
>point.  Or to one of those megahashes like
>
>	SHA1(MD5(x))||MD5(SHA1(x))

It is something to consider. Right now the software is not that flexible,
but it should be in the next major revision. I too would like to move from
total MD5 dependence.

>Also mixmaster has capabilities like type 1 remailers right?  If so
>you would presumably add a capability indicating that the remailer
>supports direct socket delivery.  And another capability for forward
>secrecy (the other thread "non-interactive forward secrecy" discusses
>ways to retro-fit a less interactive forward secrecy mechanism into
>email delivered mixmaster packets).

Mixmaster recognizes type 1 messages, and passes them to a type 1 remailer.

>The socket capability presumably would be useful to know that it is
>likely to react more quickly.  Forward secrecy is obviously nice to
>know about for other reasons.
>
>Adam

Socket support for type 1 is more complicated. The known RSA key is now the
PGP key which encrypted the message. It is going to be a lot more
complicated to go in a get all the info needed using PGP. Given a PGP
library it could be done within Mixmaster, but it seems outside the scope
of the program. My personal feeling is that as Mixmaster improves and gets
more widely ported, type 1 should phase out.

	-Lance

----------------------------------------------------------
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
----------------------------------------------------------

Lance Cottrell <loki@infonex.com> wrote:

> Our options will open up alot when the patent expires next year.

> I agree it does not make much difference mathematically, but one DH modulus
> always makes me uneasy. DH is still patented though. I think I will continue
> to use RSAREF, but compose the standard so the protocol supports unlimited
> key sizes.

RSAREF does not give you a license to use DH because RSA does not have a
licence to use DH.  So basically you can use whatever library you want and
it doesn't change your position legally.  I believe I read that in the
Schafly-RSA-Cylink lawsuit, the judge issued an injunction barring Cylink
from suing anyone else for patent infringement until the current case is
resolved.  The judge will probably throw out the patent - Anyone know when
the next hearing in this case is?

Mathematically, a common modulus does make a difference, because you can
do precomputations on the modulus.  This generally involves finding the
discrete logarithms of many small primes modulo p.  For example, if you
solved (by exhaustive search) the values of a,b,c,d,e... such that, mod p,
g^a=2, g^b=3, g^c=5, g^d=7, g^e=11, and so on, then you could compute the
discrete logs of larger numbers by factoring them into small primes.  For
example, if you wanted to take the discrete log of, oh, say, 339570, that
would be a+2b+c+3d+e, since 339570=2*(3^2)*5*(7^3)*11.  The logarithm of a
product is the sum of the logarithms of the factors.  What happens if you
want to take the discrete log of a number you can't factor?  Let's suppose
you want the discrete log of 257.  Well, you can't factor that because
it's prime.  But, since we're working modulo p, 257=p+257.  So you can
try factoring p+257, or 2p+257, or 3p+257, etc. until you find a number
that factors nicely into some combination of the primes that you do have.
Of course, the more small primes you collect, the easier it is to find
such numbers, thus the more small primes you collect, the easier it is to
find more small primes. :)

In light of the above, it should be apparent that users should not share
a common modulus, even if they use different generators (you can take the
discrete log of one generator to the other, once you crack one of them).
Thus it is wise for each user to create their own prime number modulus
before they generate their key.

Oh, one final thing - (actually two final things) - If the modulus is not
prime, and the attacker can factor the modulus, then the discrete log
problem becomes somewhat easier because of the Chinese Remainder Theorem.
Also, the ability to do arbitrary discrete logs modulo p, where p is a
product and not prime, implies the ability to factor p.  (Think about it
for awhile. ;-)  Overall tho, the discrete log problem is believed to be
slightly harder than factoring.

Matthew Ghio wrote:
> > I agree it does not make much difference mathematically, but one DH modulus
> > always makes me uneasy. DH is still patented though. I think I will continue
> > to use RSAREF, but compose the standard so the protocol supports unlimited
> > key sizes.
  
Just a short note. The DH patent (#4200770), as held by Cylink expires at
the 29th of april '97. Afterwards DH enters the public domain. That's a
certain argument for using DH key exchange. RSA will go into the public
domain somewhen in 2002, if I remember correctly.

Germano