Re: questions on RFC2631 and DH key agreement
- Original Message - From: Hal Finney [EMAIL PROTECTED] To: [EMAIL PROTECTED]; cryptography@metzdowd.com Sent: Sunday, February 10, 2008 9:27 AM Subject: Re: questions on RFC2631 and DH key agreement Joseph Ashwood writes: From: Hal Finney [EMAIL PROTECTED] Joseph Ashwood writes, regarding unauthenticated DH: if b uses the same private key to generate multiple yb the value of b will slowly leak. I'm not familiar with this last claim, that the value of b's private key (presuming that is what you mean) would slowly leak if it were reused for many DH exchanges. Can you explain what you mean? Are you talking about LimLee style attacks where the recipient does not check the parameters for validity? In that case I would say the private exponent would leak quickly rather than slowly. But if the parameters are checked, I don't see how that would leak a reused exponent. I am not immediately aware of any known attacks that have been published about it, but it is fairly obvious that Eve has more information about the private key by having a second key set with the same unknown. With only a single pair Eve's information set is: g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 By adding the second key set Eve now has g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 g_2,p_2,q_2,y_2 where y_2 = g_2^x mod p_2 This is obviously additional information, and with addition key set _i eventually Eve has the information to guess x with improves probability. That's hardly grounds for saying that the value of the secret will slowly leak. You have given no reason to believe that this information will be of any practical value to Eve. We obviously disagree. Security is alway about information control, and disclosing additional information for no gain is always a bad idea. Expressing the equations differently: Y_i = g_i^X - k_i*p_i is equivalent to Y_i = g_i^X mod p_i Since Y_i, g_i, and p_i are known, k_i is irrelevant, and g_i and p_i can even be chosen, simple algebra shows that not all Xs can be discovered from a given set, but it also says that sets of possible X can be determined from each triple, and by choosing g,p the overlap of the sets can be reduced. Creating an oracle for Y,g,p triples out of the client is begging for an adaptive attack. After all, exactly the same observation might be made about a digital signature, that each signature gives additional information about the private exponent. Actually there is an additional random variable in the signature, and 3 additional k_i so the algebra says that the sets will overlap simply too much for a similar set-based attack to work. This is a largely fuzzy-logic based attack. And while I obviously haven't sorted it through that far should allow for a probability sorting of values for X. Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Jeff Hodges wrote: It turns out the supplied default for p is 1024 bit -- I'd previously goofed when using wc on it.. DCF93A0B883972EC0E19989AC5A2CE310E1D37717E8D9571BB7623731866E61EF75A2E27898B057 F9891C2E27A639C3F29B60814581CD3B2CA3986D2683705577D45C2E7E52DC81C7A171876E5CEA7 4B1448BFDFAF18828EFD2519F14E45E3826634AF1949E5B535CC829A483B8A76223E5D490A257F0 5BDFF16F2FB22C583AB This p is a strong prime, one where (p-1)/2 is also a prime, a good property for a DH modulus. The generator g=2 generates the entire group, which is an OK choice. It means that one bit of the shared secret is leaked (whether or not it is a quadratic residue, i.e. whether the discrete log of the number is even or odd). But that shouldn't matter, the shared secret should be hashed and/or used as the seed of a PRNG to generate further keys. The main problem as I said is that 1024 bit moduli are no longer considered sufficiently safe for more than casual purposes. Particularly with discrete logs that use a widely-shared modulus like the one above, it would not be surprising to see it publicly broken in the next 5-10 years, or perhaps even sooner. And if a public effort can accomplish it in a few years, conservatively we should assume that well funded secret efforts could already succeed today. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Thanks for your thoughts on this Hal. Quite educational. Jeff Hodges wrote: It turns out the supplied default for p is 1024 bit -- I'd previously goofed when using wc on it.. DCF93A0B883972EC0E19989AC5A2CE310E1D37717E8D9571BB7623731866E61EF75A2E27898B057 F9891C2E27A639C3F29B60814581CD3B2CA3986D2683705577D45C2E7E52DC81C7A171876E5CEA7 4B1448BFDFAF18828EFD2519F14E45E3826634AF1949E5B535CC829A483B8A76223E5D490A257F0 5BDFF16F2FB22C583AB This p is a strong prime, one where (p-1)/2 is also a prime, a good property for a DH modulus. Ok, so what tools did you use to ascertain that? I'm curious. The generator g=2 generates the entire group, which is an OK choice. Same here. But that shouldn't matter, the shared secret should be hashed and/or used as the seed of a PRNG to generate further keys. It is hashed, but isn't used to gen further keys. I'm crafting a review of the full DH exchange in the target spec that I'll post to the list today. The main problem as I said is that 1024 bit moduli are no longer considered sufficiently safe for more than casual purposes. That's what I thought. Particularly with discrete logs that use a widely-shared modulus like the one above, it would not be surprising to see it publicly broken in the next 5-10 years, or perhaps even sooner. And if a public effort can accomplish it in a few years, conservatively we should assume that well funded secret efforts could already succeed today. Yep. thanks again, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
I think I already know the answer to this question, but I just want to test my understanding... How wise (in a real-world sense) is it, in a protocol specification, to specify that one simply obtain an ostensibly random value, and then use that value directly as the signature key in, say, an HMAC-based signature, without any further stipulated checking and/or massaging of the value before such use? E.g., here's such a specfication excerpt and is absolutely everything said in the spec wrt obtaining said signature keys: When generating MAC keys, the recommendations in [RFC1750] SHOULD be followed. ... The quality of the protection provided by the MAC depends on the randomness of the shared MAC key, so it is important that an unguessable value be used. How (un)wise is this, in a real-world sense? [yes, I'm aware that using a only a SHOULD here leaves a huge door open compliance-wise, but that's a different issue] thanks, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Hi Jeff - How wise (in a real-world sense) is it, in a protocol specification, to specify that one simply obtain an ostensibly random value, and then use that value directly as the signature key in, say, an HMAC-based signature, without any further stipulated checking and/or massaging of the value before such use? I think it's OK, as long as it is understood that the random number generator should be of good quality. If it is not, I don't know that checking and/or massaging will help much. E.g., here's such a specfication excerpt and is absolutely everything said in the spec wrt obtaining said signature keys: When generating MAC keys, the recommendations in [RFC1750] SHOULD be followed. One point, RFC1750 has been superceded by RFC4086. ... The quality of the protection provided by the MAC depends on the randomness of the shared MAC key, so it is important that an unguessable value be used. How (un)wise is this, in a real-world sense? It seems pretty reasonable to me. They are referring to an RFC with lots of good advice about random number generators, and they emphasize that the key value should be unguessable. It's probably out of scope to go into a lot more detail than that. Referring to other standards like RFC1750/4086 is the right way to handle this kind of issue. [yes, I'm aware that using a only a SHOULD here leaves a huge door open compliance-wise, but that's a different issue] I am the co-author of the OpenPGP Standard, RFC4880. All we say is: The sending OpenPGP generates a random number to be used as a session key for this message only. and * Certain operations in this specification involve the use of random numbers. An appropriate entropy source should be used to generate these numbers (see [RFC4086]). Not all that different in thrust than the spec you are looking at. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
- Original Message - From: Hal Finney [EMAIL PROTECTED] To: [EMAIL PROTECTED]; cryptography@metzdowd.com Sent: Wednesday, February 06, 2008 8:54 AM Subject: Re: questions on RFC2631 and DH key agreement Joseph Ashwood writes, regarding unauthenticated DH: I would actually recommend sending all the public data. This does not take significant additional space and allows more verification to be performed. I would also suggest looking at what exactly the goal is. As written this provides no authentication just privacy, and if b uses the same private key to generate multiple yb the value of b will slowly leak. I'm not familiar with this last claim, that the value of b's private key (presuming that is what you mean) would slowly leak if it were reused for many DH exchanges. Can you explain what you mean? Are you talking about LimLee style attacks where the recipient does not check the parameters for validity? In that case I would say the private exponent would leak quickly rather than slowly. But if the parameters are checked, I don't see how that would leak a reused exponent. I am not immediately aware of any known attacks that have been published about it, but it is fairly obvious that Eve has more information about the private key by having a second key set with the same unknown. With only a single pair Eve's information set is: g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 By adding the second key set Eve now has g_1,p_1,q_1,y_1 where y_1 = g_1^x mod p_1 g_2,p_2,q_2,y_2 where y_2 = g_2^x mod p_2 This is obviously additional information, and with addition key set _i eventually Eve has the information to guess x with improves probability. You can then use the gpb trio for DSA, leveraging the key set for more capabilities. Presuming here you mean (g,p,q) as suitable for reuse. This raises the question, is the same set of (g,p,q) parameters suitable for use in both DH exchange and DSA signatures? From the security engineering perspective, I'd suggest that the goals and threat models for encryption vs signatures are different enough that one would prefer different parameters for the two. I agree with that, presuming that the private key values are different, there is at least no harm in using different parameters, and it avoids some possible avenues of attack. For DSA signatures, we'd like small subgroups, since the subgroup size determines the signature size. This constraint is not present with DH encryption, where a large subgroup will work as well as a small one. Large subgroups can then support larger private exponents in the DH exchange. Actually there is nothing stopping parameters for DSA from being prime(160 bit)*prime(5 bit)*2+1 which would have a large enough subgroup as to be effectively unbreakable. Now obviously 5 bits is excessive, but my point is that finding p with a moderately sized subgroup q and a large additional subgroup is entirely possible, even though it is arguably unnecessary. Now it may be argued that large subgroups do not actually increase security in the DH exchange, because index calculus methods are independent of subgroup size. In fact, parameters for DSA signatures are typically chosen so that subgroup based methods such as Shanks that take sqrt(q) cost are balanced against estimates of index calculus work to break p. However, this balancing is inherently uncertain and it's possible that p-based attacks will turn out to be harder than ones based on q. Hence one would prefer to use a larger q to provide a margin of safety if the costs are not too high. I would consider that except for (semi)ephemeral parameters the cost of finding an appropriate prime are minor relative to the other considerations. This is especially true with signature parameters where a signing pair can be worth more than all the data authenticated by it. While there is a computational cost to using a larger subgroup for DH exchange, there is no data cost, while for DSA there are both computational and data costs. Therefore the tradeoffs for DH would tend to be different than for DSA, and a larger q would be preferred for DH, all else equal. In fact it is rather common in DH parameter sets to use Sophie-Germain primes for q. I don't know if they are common but they are definitely a good idea, or at the very least using parameters with very large factors of p-1. Primes of the form q*k+1 for small k are certainly a good idea. We may also consider that breaking encryption keys is a passive attack which can be mounted over a larger period of time (potentially providing useful information even years after the keys were retired) and is largely undetectable; while breaking signatures, to be useful, must be performed actively, carries risks of detection, and must be completed within a limited time frame. All these considerations motivate using larger parameter sets for DH encryption than for DSA signatures. I'm not as certain about that last
Re: questions on RFC2631 and DH key agreement
E.g., here's such a specfication excerpt and is absolutely everything said in the spec wrt obtaining said signature keys: When generating MAC keys, the recommendations in [RFC1750] SHOULD be followed. One point, RFC1750 has been superceded by RFC4086. I'll point that out, thanks. ... The quality of the protection provided by the MAC depends on the randomness of the shared MAC key, so it is important that an unguessable value be used. How (un)wise is this, in a real-world sense? It seems pretty reasonable to me. They are referring to an RFC with lots of good advice about random number generators, and they emphasize that the key value should be unguessable. It's probably out of scope to go into a lot more detail than that. Referring to other standards like RFC1750/4086 is the right way to handle this kind of issue. agreed (thx for the ptr to RFC4880) after doing some further reading and such. RFC4086 covers the notion of mixing functions etc, so the above-quoted SHOULD statement covers those bases. I am the co-author of the OpenPGP Standard, RFC4880. All we say is: The sending OpenPGP generates a random number to be used as a session key for this message only. and * Certain operations in this specification involve the use of random numbers. An appropriate entropy source should be used to generate these numbers (see [RFC4086]). Not all that different in thrust than the spec you are looking at. agreed, thanks again. =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
[to and CC trimmed] - Original Message - From: ' =JeffH ' [EMAIL PROTECTED] To: Hal Finney [EMAIL PROTECTED]; Eric Rescorla [EMAIL PROTECTED]; [EMAIL PROTECTED]; Joseph Ashwood [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; cryptography@metzdowd.com Sent: Thursday, February 07, 2008 2:17 PM Subject: Re: questions on RFC2631 and DH key agreement I think I already know the answer to this question, but I just want to test my understanding... How wise (in a real-world sense) is it, in a protocol specification, to specify that one simply obtain an ostensibly random value, and then use that value directly as the signature key in, say, an HMAC-based signature, without any further stipulated checking and/or massaging of the value before such use? With any authentication the biggest consideration is to examine what the intention is. Using a single-use one time key for a symmetric MAC works for local authenticity, but not for remote authenticity. That is to say that the local process knows that it didn't generate the MAC, and the MAC is shared with only one other, so the authenticity is known, but any external source can only say that an entity knowing the key generated it. This may or may not be the intended condition, in that auditing this is very, very difficult. E.g., here's such a specfication excerpt and is absolutely everything said in the spec wrt obtaining said signature keys: When generating MAC keys, the recommendations in [RFC1750] SHOULD be followed. ... The quality of the protection provided by the MAC depends on the randomness This should be entropy. of the shared MAC key, so it is important that an unguessable value be used. How (un)wise is this, in a real-world sense? It all depends on the intended meaning. If this is intended to authenticate to a third party, it fails completely. If it is specifically intended NOT to authenticate to a third party it may be exactly what is needed. Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
' =JeffH ' [EMAIL PROTECTED] writes: [EMAIL PROTECTED] said: http://www.xml-dev.com/blog/index.php?action=viewtopicid=196 thanks, but that doesn't actually answer my first question. It only documents that a and b (alice and bob) arrive at the ZZ value independently. My question is actually concerning section 2.1.2 Generation of Keying Material in RFC2631. I'm going to approach the answer somewhat differently: Why are you using this mechanism? The only reason that it's present in the spec is politics, it being an attempt to avoid the RSA patent. Its adoption was severely hampered by the fact that US vendors already had RSA licenses, non-US vendors didn't care (and in any case the patent has now expired, so they care even less), no CA's of note will issue X9.42 certificates, and even if they did almost no S/MIME implementations support it. Although X9.42 was at one point listed as mandatory to implement for S/MIME v3, the approach that was taken by most vendors was to vaguely pretend to support X9.42 while actually concentrating on RSA, knowing that noone else supported it either (AFAIK only two vendors ever really supported it, Microsoft had a receive-only implementation so that no-one could accuse them of not being compliant with the spec, and the S/MIME Freeware Library (which was the reference implementation and therefore had no choice in supporting it) supported it because it had to). A few years after the expiry of the RSA patent, the matter was corrected by changing the standard so that vendors were no longer required to even pretend to support X9.42. My comments at the time were: -- Snip -- How about trying to make the spec at least vaguely approximate reality in the choice of algorithms? It doesn't really matter if you include requirements like MUST DSA OR WE WILL KILL YOU[0], SHOULD NOT RSA, in practice the world will interpret it as MUST RSA, MAY DSA, SHOULD NOT X9.42 DH, BWAHAHAHAHAHA X9.31 RSA no matter what it says in the RFC. I've been sitting here watching this debate go on and on, but since no matter what you put in the RFC the market will interpret it as MUST RSA and various levels of deprecation for anything else maybe we could get Markov Chaney to continue the debate for a while just for forms sake and then after enough messages have been exchanged to satisfy everyone either put text in the RFC which accepts what everyone's going to do anyway or which specifies all sorts of options and alternatives secure in the knowledge that implementors will ignore it and do what the market wants/expects, which ain't DSA or X9.42 or X9.31 RSA. Peter. [0] RFC 2026bis, When MUST just isn't enough. -- Snip -- So by implementing this you're getting an unwanted orphan crypto mechanism that was only added for political reasons. Are you sure you don't want to use RSA instead? Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Ok thanks, I'm going to risk pedanticism in order to nail things down a bit more rigorously.. ' =JeffH ' [EMAIL PROTECTED] writes: [EMAIL PROTECTED] said: http://www.xml-dev.com/blog/index.php?action=viewtopicid=196 thanks, but that doesn't actually answer my first question. It only documents that a and b (alice and bob) arrive at the ZZ value independently. My question is actually concerning section 2.1.2 Generation of Keying Material in RFC2631. [EMAIL PROTECTED] said: I'm going to approach the answer somewhat differently: Why are you using this mechanism? Are you referring to the above mentioned mechanism of arriving at the ZZ value independently, which is implied in RFC2631? (btw, I am not myself designing anything at this time that uses DH, I'm reviewing/analyzing. I am _not_ reviewing RFC2630/2631 themselves, rather it's a (non-IETF) spec that references 2631) The only reason that it's present in the spec is politics, it being an attempt to avoid the RSA patent. So by the spec you're referring to RFC2631 here? Or are you referring to X9.42? Or something else? Its adoption was severely hampered by the fact that US vendors already had RSA licenses, non-US vendors didn't care (and in any case the patent has now expired, so they care even less), no CA's of note will issue X9.42 certificates, and even if they did almost no S/MIME implementations support it. snippage/ So here, and in the snippage, are you referring to X9.42 itself, or CMS (Cryptographic Message Syntax) ? A few years after the expiry of the RSA patent, the matter was corrected by changing the standard so that vendors were no longer required to even pretend to support X9.42. My comments at the time were: Exactly which standard ? From grepping all RFCs, it seems you're referring to CMS when you say the standard, which has indeed been revised a few times since RFC2630. thanks, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
- Original Message - From: ' =JeffH ' [EMAIL PROTECTED] Sent: Saturday, February 02, 2008 12:56 PM Subject: Re: questions on RFC2631 and DH key agreement If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? It is assuming that the total value of the data protected by those parameters never crosses the cost to break in the information value lifetime. For 1040 bits this is highly questionable for any data with a lifetime longer than 6 months. I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, Very bad idea, for two reasons, the rand() function does not have sufficient internal state, and the rand() function is far from cryptographically strong. and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? All flaws in the private key generator will show in the public key selection, do yes. Additionally there's the previously noted issue with the values of static private keys slowly leaking. Only if the value of p changes, if the value of p remains static, then the private key doesn't leak. A simple proof of this is simple, Eve can easily, and trivially generate any number of public/private key pairs and thereby generate any number of viewable sets to determine the unknown private key. Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
I'd scrawled: If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? Joseph Ashwood graciously replied: It is assuming that the total value of the data protected by those parameters never crosses the cost to break in the information value lifetime. yes. I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, Very bad idea, for two reasons, the rand() function does not have sufficient internal state, and the rand() function is far from cryptographically strong. what about just using bytes from /dev/urandom on *nix? and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? All flaws in the private key generator will show in the public key selection, do yes. ^^ so? Additionally there's the previously noted issue with the values of static private keys slowly leaking. Only if the value of p changes, if the value of p remains static, then the private key doesn't leak. Ok, I can see that from ya = g ^ xa mod p ... ya doesn't change if g, xa, and p don't change. A simple proof of this is simple, Eve can easily, and trivially generate any number of public/private key pairs and thereby generate any number of viewable sets to determine the unknown private key. Are you saying here that if p (and g) are static, then one has some opportunity to brute-force guess the private key that some long-running instance is using, if it doesn't otherwise re-allocate said private key from time to time? thanks again, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
' =JeffH ' [EMAIL PROTECTED] [EMAIL PROTECTED] said: I'm going to approach the answer somewhat differently: Why are you using this mechanism? Are you referring to the above mentioned mechanism of arriving at the ZZ value independently, which is implied in RFC2631? I'm referring to the X9.42 mechanism (as used in CMS) as a whole (see below for the reason why this is in quotes). (btw, I am not myself designing anything at this time that uses DH, I'm reviewing/analyzing. I am _not_ reviewing RFC2630/2631 themselves, rather it's a (non-IETF) spec that references 2631) Oh. In that case you have my sympathy :-). So by the spec you're referring to RFC2631 here? Or are you referring to X9.42? I'm referring to the (old) CMS RFCs. Even the RFCs themselves don't use proper X9.42, they were based on an old draft that floated around for awhile and was subsequently changed and updated. You can see this if you look at the order of the DLP key parameters, everything else (e.g. FIPS 186) uses { p, q, g }, while the old CMS RFCs flip the second two values to use { p, g, q }. I think the definitive comment on this (which also talks about differences between FIPS 186, various X9.42 drafts, and the CMS use of those drafts) is by the former editor of X9.42, and is archived at http://www.vpnc.org/ietf-ipsec/99.ipsec/msg02018.html. So here, and in the snippage, are you referring to X9.42 itself, or CMS (Cryptographic Message Syntax) ? Specifically CMS, since X9.42 isn't necessarily what's used in CMS. Peter. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
- Original Message - From: ' =JeffH ' [EMAIL PROTECTED] To: Joseph Ashwood [EMAIL PROTECTED] Cc: cryptography@metzdowd.com Sent: Monday, February 04, 2008 5:18 PM Subject: Re: questions on RFC2631 and DH key agreement I'd scrawled: If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? Joseph Ashwood graciously replied: It is assuming that the total value of the data protected by those parameters never crosses the cost to break in the information value lifetime. yes. I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, Very bad idea, for two reasons, the rand() function does not have sufficient internal state, and the rand() function is far from cryptographically strong. what about just using bytes from /dev/urandom on *nix? *nix /dev/urandom should work well, the entropy harvesting is reasonably good, and the mixing/generating are sufficient to keep it from being the weak link. and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? All flaws in the private key generator will show in the public key selection, do yes. ^^ so? Yep, my typos show I'm far from perfect. I meant so. Additionally there's the previously noted issue with the values of static private keys slowly leaking. Only if the value of p changes, if the value of p remains static, then the private key doesn't leak. Ok, I can see that from ya = g ^ xa mod p ... ya doesn't change if g, xa, and p don't change. A simple proof of this is simple, Eve can easily, and trivially generate any number of public/private key pairs and thereby generate any number of viewable sets to determine the unknown private key. Are you saying here that if p (and g) are static, then one has some opportunity to brute-force guess the private key that some long-running instance is using, if it doesn't otherwise re-allocate said private key from time to time? Actually I'm saying that if p and g do not change, then there is no additional leakage of the private key beyond what Eve can compute anyway. There are many, many factors involved in any deep security examination, making it truly a business decision with all the complexities involved in that, and very easy to get wrong. Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
[EMAIL PROTECTED] said: *nix /dev/urandom should work well, the entropy harvesting is reasonably good, and the mixing/generating are sufficient to keep it from being the weak link. yeah, that's the way it sounds from the man page (on linux). thx. Actually I'm saying that if p and g do not change, then there is no additional leakage of the private key beyond what Eve can compute anyway. ok, gotcha. thanks again, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Thanks Hal. It turns out the supplied default for p is 1024 bit -- I'd previously goofed when using wc on it.. DCF93A0B883972EC0E19989AC5A2CE310E1D37717E8D9571BB7623731866E61EF75A2E27898B057 F9891C2E27A639C3F29B60814581CD3B2CA3986D2683705577D45C2E7E52DC81C7A171876E5CEA7 4B1448BFDFAF18828EFD2519F14E45E3826634AF1949E5B535CC829A483B8A76223E5D490A257F0 5BDFF16F2FB22C583AB =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Jeff Hodges writes: If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? This can be reasonably safe, if p is chosen properly. There is no problem with using g=2, with the right p. The main issue is that with current technology, a 1040 bit p stands a substantial chance of being broken. A 1024 bit special-form number was factored last year, with claims that the technique might apply to general RSA moduli of that size. Finding discrete logs takes similar work. A widely reused p value would be a fat target for such an effort. I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? Additionally there's the previously noted issue with the values of static private keys slowly leaking. I'm not sure about this leaking, I asked Ashwood for clarification. Certainly if the secret exponents are poorly chosen, the system will be insecure. I would not necessarily assume that rand() is being used; I would hope in this day and age that people would know better than that. /dev/random on LinuxMac and CryptGenRandom on Windows should provide adequate security for this use, and hopefully the implementors would be aware of the need for secure random numbers. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Joseph Ashwood writes, regarding unauthenticated DH: I would actually recommend sending all the public data. This does not take significant additional space and allows more verification to be performed. I would also suggest looking at what exactly the goal is. As written this provides no authentication just privacy, and if b uses the same private key to generate multiple yb the value of b will slowly leak. I'm not familiar with this last claim, that the value of b's private key (presuming that is what you mean) would slowly leak if it were reused for many DH exchanges. Can you explain what you mean? Are you talking about LimLee style attacks where the recipient does not check the parameters for validity? In that case I would say the private exponent would leak quickly rather than slowly. But if the parameters are checked, I don't see how that would leak a reused exponent. You can then use the gpb trio for DSA, leveraging the key set for more capabilities. Presuming here you mean (g,p,q) as suitable for reuse. This raises the question, is the same set of (g,p,q) parameters suitable for use in both DH exchange and DSA signatures? From the security engineering perspective, I'd suggest that the goals and threat models for encryption vs signatures are different enough that one would prefer different parameters for the two. For DSA signatures, we'd like small subgroups, since the subgroup size determines the signature size. This constraint is not present with DH encryption, where a large subgroup will work as well as a small one. Large subgroups can then support larger private exponents in the DH exchange. Now it may be argued that large subgroups do not actually increase security in the DH exchange, because index calculus methods are independent of subgroup size. In fact, parameters for DSA signatures are typically chosen so that subgroup based methods such as Shanks that take sqrt(q) cost are balanced against estimates of index calculus work to break p. However, this balancing is inherently uncertain and it's possible that p-based attacks will turn out to be harder than ones based on q. Hence one would prefer to use a larger q to provide a margin of safety if the costs are not too high. While there is a computational cost to using a larger subgroup for DH exchange, there is no data cost, while for DSA there are both computational and data costs. Therefore the tradeoffs for DH would tend to be different than for DSA, and a larger q would be preferred for DH, all else equal. In fact it is rather common in DH parameter sets to use Sophie-Germain primes for q. We may also consider that breaking encryption keys is a passive attack which can be mounted over a larger period of time (potentially providing useful information even years after the keys were retired) and is largely undetectable; while breaking signatures, to be useful, must be performed actively, carries risks of detection, and must be completed within a limited time frame. All these considerations motivate using larger parameter sets for DH encryption than for DSA signatures. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
I'd scrawled.. Other than for b perhaps wanting to verify the correctness of { p, q, g, j } (group parameter validation), is there any reason to send q ? [EMAIL PROTECTED] replied: I would actually recommend sending all the public data. This does not take significant additional space and allows more verification to be performed. That's what I thought. BTW, I'm not myself working on something employing a DH exchange -- I'm analyzing/reviewing something that does. I would also suggest looking at what exactly the goal is. As written this provides no authentication just privacy, Indeed, b could be any entity because it isn't proving possession of any known-only-to-it information. and if b uses the same private key to generate multiple yb the value of b['s private key?] will slowly leak. Yep, I suspected that too. Thanks. So, another question or two: If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? Additionally there's the previously noted issue with the values of static private keys slowly leaking. thanks again, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Oh, yeah, sorry, your diagram (or whoever drew it) does in fact answer my second question wrt what one needs to send over the wire wrt a simplistic DH profile. Just g, p, and a public key (y). thanks again, =JeffH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
- Original Message - From: ' =JeffH ' [EMAIL PROTECTED] To: cryptography@metzdowd.com Cc: ' =JeffH ' [EMAIL PROTECTED] Sent: Friday, February 01, 2008 1:53 PM Subject: questions on RFC2631 and DH key agreement (ya and yb) if { p, q, g, j } are known to both parties. So if p, q, g are not static, then a simplistic, nominally valid, DH profile would be to.. a b -- -- g, p, ya --- yb ..yes? I would actually recommend sending all the public data. This does not take significant additional space and allows more verification to be performed. I would also suggest looking at what exactly the goal is. As written this provides no authentication just privacy, and if b uses the same private key to generate multiple yb the value of b will slowly leak. Other than for b perhaps wanting to verify the correctness of { p, q, g, j } (group parameter validation), is there any reason to send q ? You can then use the gpb trio for DSA, leveraging the key set for more capabilities. Joe - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]