Re: questions on RFC2631 and DH key agreement

2008-02-13 Thread Joseph Ashwood
- 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

2008-02-09 Thread Hal Finney
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

2008-02-09 Thread ' =JeffH '
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

2008-02-09 Thread ' =JeffH '
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

2008-02-09 Thread Hal Finney
Jeff Hodges wrote:
 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. 

I copied and pasted it into Python as p, set p1 = (p-1)/2, and did
pow(2L,p1-1,p1), pow(3L,p1-1,p1) and a few such Fermat tests, always
getting 1 as the result, to confirm that p1 is prime. I then did
pow(2L,p1,p) and got p-1 rather than 1, which tells me that 2 generates
the whole group rather than the subgroup of order p1.

Hal

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: questions on RFC2631 and DH key agreement

2008-02-09 Thread Hal Finney
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

2008-02-09 Thread Joseph Ashwood
- 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

2008-02-09 Thread ' =JeffH '
  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

2008-02-09 Thread Joseph Ashwood

[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

2008-02-06 Thread Peter Gutmann
' =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

2008-02-06 Thread ' =JeffH '
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

2008-02-06 Thread Joseph Ashwood
- 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

2008-02-06 Thread ' =JeffH '
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

2008-02-06 Thread Peter Gutmann
' =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

2008-02-06 Thread Joseph Ashwood
- 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

2008-02-06 Thread ' =JeffH '

[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

2008-02-06 Thread ' =JeffH '
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

2008-02-06 Thread Hal Finney
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

2008-02-06 Thread Hal Finney
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

2008-02-03 Thread ' =JeffH '
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

2008-02-02 Thread ' =JeffH '
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

2008-02-02 Thread Joseph Ashwood
- 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]