Re: [Cryptography] A Likely Story!

2013-09-09 Thread Alexander Klimov
On Sun, 8 Sep 2013, Peter Fairbrother wrote:
 On the one hand, if they continued to recommend that government people use
 1024-bit RSA they could be accused of failing their mission to protect
 government communications.
 
 On the other hand, if they told ordinary people not to use 1024-bit RSA, they
 could be accused of failing their mission to spy on people.
 
 What to do?

NIST recommends at least RSA-2048 for a long time, for example NIST 
Special Publication 800-57, back in August, 2005 said:

 [...] for Federal Government unclassified applications. A minimum of 
 eighty bits of security shall be provided until 2010. Between 2011 
 and 2030, a minimum of 112 bits of security shall be provided. 
 Thereafter, at least 128 bits of security shall be provided.

Note that

 RSA-1024 ~ 80 bits of security; 
 RSA-2048 ~ 112 bits; 
 RSA-3072 ~ 128 bits 

So if anyone to blame for using 1024-bit RSA, it is not NIST.

BTW, once you realize that 256 bits of security requires RSA with 
15360 bits, you will believe conspiracy theories about ECC much less. 
Here exponentiation with 15360 bits takes 15^3=3375 times more CPU 
time than a 1024-bit exponentiation, thus using RSA for 256-bit 
security is impractical.

 You can use any one of trillions of different elliptic curves,which should be
 chosen partly at random and partly so they are the right size and so on; but
 you can also start with some randomly-chosen numbers then work out a curve
 from those numbers. and you can use those random numbers to break the session
 key setup.

Can you elaborate on how knowing the seed for curve generation can be 
used to break the encryption? (BTW, the seeds for randomly generated 
curves are actually published.)

-- 
Regards,
ASK
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] A Likely Story!

2013-09-09 Thread Peter Fairbrother

On 09/09/13 12:53, Alexander Klimov wrote:

On Sun, 8 Sep 2013, Peter Fairbrother wrote:


You can use any one of trillions of different elliptic curves,which should be
chosen partly at random and partly so they are the right size and so on; but
you can also start with some randomly-chosen numbers then work out a curve
from those numbers. and you can use those random numbers to break the session
key setup.


Can you elaborate on how knowing the seed for curve generation can be
used to break the encryption? (BTW, the seeds for randomly generated
curves are actually published.)




Move along please, there is nothing to see here.

This is just a wild and disturbing story. It may upset you to read it, 
so please stop reading now.


You may have read a bit about the story in the papers or internet or 
elsewhere, but isn't actually true. Government Agencies do not try to 
break the internet's encryption, as used by Banks and Doctors and 
Commerce and Government Departments and even Government Agencies 
themselves - that wouldn't be sensible.


Besides which, there is no such agency as the NSA.


But ..

Take FIPS P-256 as an example. The only seed which has been published is 
s=  c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 (the string they hashed 
and mashed in the process of deriving c).


I don't think they could reverse the perhaps rather overly-complicated 
hashing/mashing process, but they could certainly cherry-pick the s 
until they found one which gave a c which they could use.


c not being one of the usual parameters for an elliptic curve, I should 
explain that it was then used as c = a^3/b^2 mod p.


However the choice of p, r, a and G was not seeded, and the methods by 
which those were chosen are opaque.



I don't really know enough about ECC to say whether a perhaps 
cherry-picked c = a^3/b^2 mod p is enough that the resulting curve is 
secure against chosen curve attacks - but it does seem to me that there 
is a whole lot of legroom between a cherry-picked c and the final curve.




And as I said, it's only a story. We don't know much about what the NSA 
knows about chosen curve attacks, although we do know that they are 
possible. Don't go believing it, it will just upset you.


They wouldn't do that.


-- Peter Fairbrother

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography