mersenneforum.org > Math RSA Key Generation Flaws
 Register FAQ Search Today's Posts Mark Forums Read

 2012-02-15, 22:01 #1 Jeff Gilchrist     Jun 2003 Ottawa, Canada 7×167 Posts 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
 2012-02-15, 22:18 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-02-15, 23:18   #3
chalsall
If I May

"Chris Halsall"
Sep 2002

2·4,643 Posts

Quote:
 Originally Posted by Jeff Gilchrist 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....

2012-02-16, 00:00   #4
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by chalsall 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.

2012-02-16, 00:50   #5
chalsall
If I May

"Chris Halsall"
Sep 2002

2×4,643 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

 2012-02-16, 02:38 #6 jasonp Tribal Bullet     Oct 2004 66378 Posts Some references from a previous post of mine.
 2012-02-16, 02:51 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 882610 Posts 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.
2012-02-16, 04:04   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

132338 Posts

Quote:
 Originally Posted by LaurV 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.

 2012-02-16, 09:19 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 227A16 Posts 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
2012-02-16, 10:31   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

169B16 Posts

Quote:
 Originally Posted by LaurV 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.

2012-02-16, 11:28   #11
ckdo

Dec 2007
Cleves, Germany

232 Posts

Quote:
 Originally Posted by jasonp Some references from a previous post of mine.

 Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Factoring 14 2013-03-16 00:38 Jeff Gilchrist Hardware 9 2012-10-18 10:49 Kees Lounge 27 2006-12-12 08:04 R.D. Silverman Hardware 11 2005-08-08 19:09 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

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.