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
participants (4)
-
Adam Back -
Germano Caronni -
ghio＠c2.net -
Lance Cottrell