mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-02-15, 22:01   #1
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7×167 Posts
Default RSA Key Generation Flaws

Has anyone taken a look at Lenstra's paper on key generation problems, titled "Ron was wrong, Whit is right"?
http://eprint.iacr.org/2012/064.pdf

There is also a news article that summarizes things:
http://www.nytimes.com/2012/02/15/te...method.html?hp

Last fiddled with by Jeff Gilchrist on 2012-02-15 at 22:04
Jeff Gilchrist is offline   Reply With Quote
Old 2012-02-15, 22:18   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

In the science news thread, the discussion right above the Venus post was about that paper. xilman took a rather blackly humorous view of it, but I personally do not know enough of the specifics of how RSA works to put my own thoughts down about it.
Dubslow is offline   Reply With Quote
Old 2012-02-15, 23:18   #3
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·4,643 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
There is also a news article that summarizes things
Meta summation: if you don't have access to (or don't use) a truly random data stream during your key creation you might generate a reversable RSA pair.

Really? Never would have thought of that....
chalsall is offline   Reply With Quote
Old 2012-02-16, 00:00   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by chalsall View Post
Meta summation: if you don't have access to (or don't use) a truly random data stream during your key creation you might generate a reversable RSA pair.
No. Well, almost. It depends on what you mean by "pair".

It does not produce a reversible key. It does produce a key with a non-negligible chance of duplicating someone else's key (or single prime within a key which is even worse).

OTOH, if by 'pair' you mean a single public/private key pair your statement
is not correct.

And one need not have a 'truly random' generator.

What is needed is a generator that is not likely to produce a collision.

This, in turn, depends not only on the generator, but how widely it is used.
The OPEN-SSL generator is VERY widely used. And flawed. And the
circumstances when it is used (e.g. at (say) system boot time)
have a reasonable probability of producing duplicates in widely scattered systems.
R.D. Silverman is offline   Reply With Quote
Old 2012-02-16, 00:50   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2×4,643 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This, in turn, depends not only on the generator, but how widely it is used. The OPEN-SSL generator is VERY widely used. And flawed. And the circumstances when it is used (e.g. at (say) system boot time) have a reasonable probability of producing duplicates in widely scattered systems.
Please note that under modern versions of Linux, /dev/random is a true source of entropy, even immediately after boot time. The down-side is this source can easily be exhausted, which is why hardware entropy devices exist for those servers which need a lot of it.

And I'm not just talking about a web-cam pointed at a lava-lamp or with its lens cover on, or an audio card digitizing an untuned radio channel. Although these techniques work rather well as well...

Coming back to the issue at hand, in your opinion is this "discovery" really worth the fear being attached to it? In my opinion this risk has been known for many, many years.
chalsall is offline   Reply With Quote
Old 2012-02-16, 02:38   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66378 Posts
Default

Some references from a previous post of mine.
jasonp is offline   Reply With Quote
Old 2012-02-16, 02:51   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

882610 Posts
Default

What I understood from that papers is that if you have enough big collection of keys and enough big computing power, then you can decrypt my shit in enough many years. Quite interesting (and I appreciate the material, no sarcasm!), but not really scary. If you take my encrypted shit and decrypt it, you will have some decrypted stuff, but still shit... So, who cares?

Years ago we made a nice processor card (pxa2xx, that time it was intel, now is marvell), the initial PCB had a mechanical defect: a hole in the wrong place make it very difficult to insert the card in the sodim200 socket. We never made any efforts to "hide" the "intelligence". Some chinese company hacked our board and they made their own, cheaper then our board of course. It took them six months or one year. The result is that in this time we, from the experience accumulated, were able to create a new board, with a new processor pxa320 which is much better, at the same price, and the chinese company has a board with an old processor, that is still VERY difficult to insert in the socket. They were so idiots they copied inclusive the wrong-positioned hole.
LaurV is offline   Reply With Quote
Old 2012-02-16, 04:04   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

132338 Posts
Default

Quote:
Originally Posted by LaurV View Post
If you take my encrypted shit and decrypt it, you will have some decrypted stuff, but still shit... So, who cares?
Did you encrypt purely as a decoy? I can't imagine any other reason why you would encrypt something if you really don't care about non-authorised people decrypting it. For more normal usage where people do care that others don't have access to the data then this is a concern. Do you ever log into your bank online over SSL? If so then you should be concerned that your bank does not have a weak key.
retina is online now   Reply With Quote
Old 2012-02-16, 09:19   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

227A16 Posts
Default

You got me wrong. I am for an open society where people should concentrate to make better stuff, and not to replicate old shit. Imagine you want now to copy the iPad or some hightech brand new things. The time you need to hack into the stuff I already did, that time I can use to make better stuff. At the end, you will have a functional design, but older. People spend billions in methods and rules to protect things that don't need any protection. Such activity is not profitable. Nobody got rich by reinventing the wheel... Of course, my universe is limited to trying to protect technical stuff and intellectual property only. Excluding banking communications or governments whose the only goal is to keep you in line and keep you in the the dark. For them too, the "secret key" is not in encryption... In an ideal society, I don't see where the encryption is need, beside of "show offs" (I am better then you, and look here, I know something you don't! And? So what?), industrial showoffs, governmental showoffs, individual showoffs, etc. As I said already here on the forum, the locks are for honest people (the thief knows how to pass the locks). Taking advantages of honest people is not really nice, you know...

If it would be up to me I would make everything public, open source software, open plans of spaceships, open government and banks activity, open pharmaceutical recipes. We would get rid of many headaches and the progress would be faster (see the open sources, as an example, where lots of people help with the design), the conspirationists won't say anymore that the doctors can cure diseases but they prefer to maintain them running because they can make more money, etc, because they (the doctors) won't... And I don't mind if someone can see what I am doing when I am into the toilet... It would be his wasting of time, not mine...

And I could argue centuries, related to this aspects. I come from a former communist country and I was raised in a secrecy-mania atmosphere, I hated that all my life, and honestly I never found a lock which I could not open if I was really interested to. I struggled 30 years of my life to find out that we are much better doing new wonderful things properly, than scratching through the piles of dung...

You want to encrypt your data? Be my guest. I won't try to decrypt them unless I could get a good profit from that, and unless decrypting them would be the only way to make that profit. Unfortunately you, and all your relatives and ancestors, will not be able to convince me that there are no easier ways to get your data, or more easier and clever ways to make that profit... And I feel pity for the guy who thinks differently. His universe is quite limited if everything he see is that encrypted data.

Last fiddled with by LaurV on 2012-02-16 at 09:27
LaurV is offline   Reply With Quote
Old 2012-02-16, 10:31   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

169B16 Posts
Default

Quote:
Originally Posted by LaurV View Post
I won't try to decrypt them unless I could get a good profit from that ...
I'm not sure I understand you completely, but nevermind. The quote above is kind of the point, I encrypt things (like bank logins/transactions) precisely because I don't wish others (free-loaders or hackers) to benefit from my labours. And I expect many other people also think the same else banks would never have had to bother with implementing SSL.
retina is online now   Reply With Quote
Old 2012-02-16, 11:28   #11
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

232 Posts
Default

Quote:
Originally Posted by jasonp View Post
Some references from a previous post of mine.
Updated link.
ckdo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Next generation NFS sieving R.D. Silverman Factoring 14 2013-03-16 00:38
Next-generation heatsink has no fan at all Jeff Gilchrist Hardware 9 2012-10-18 10:49
Respect for the old generation Kees Lounge 27 2006-12-12 08:04
Next Generation? R.D. Silverman Hardware 11 2005-08-08 19:09
Next Generation : 62 bit+ hbock Lone Mersenne Hunters 40 2004-09-08 18:59

All times are UTC. The time now is 09:10.

Tue Oct 20 09:10:20 UTC 2020 up 40 days, 6:21, 0 users, load averages: 2.05, 1.88, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.