RSA Key Generation Flaws
 

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

There is also a news article that summarizes things:
[url]http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html?hp[/url]

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.

[QUOTE=Jeff Gilchrist;289498]There is also a news article that summarizes things[/QUOTE]

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....

[QUOTE=chalsall;289513]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.

[/QUOTE]

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 [i]collision[/i].

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 [b]when[/b] it is used (e.g. at (say) system boot time)
have a reasonable probability of producing duplicates in widely scattered systems.

[QUOTE=R.D. Silverman;289518]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 [b]when[/b] it is used (e.g. at (say) system boot time) have a reasonable probability of producing duplicates in widely scattered systems.[/QUOTE]

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... :smile:

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.

[url="http://mersenneforum.org/showpost.php?p=222216&postcount=150"]Some references[/url] from a previous post of mine.

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 ([URL="http://images.search.yahoo.com/search/images?_adv_prop=image&fr=moz35&va=marvell+pxa270"]pxa2xx[/URL], 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.

[QUOTE=LaurV;289532]If you take my encrypted shit and decrypt it, you will have some decrypted stuff, but still shit... So, who cares?[/QUOTE]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 [i]do[/i] care that others don't have access to the data then this [i]is[/i] 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.

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... :smile:

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.

[QUOTE=LaurV;289559]I won't try to decrypt them unless I could get a good profit from that ...[/QUOTE]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.

[QUOTE=jasonp;289530][URL="http://mersenneforum.org/showpost.php?p=222216&postcount=150"]Some references[/URL] from a previous post of mine.[/QUOTE]

Updated [URL="http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf"]link[/URL].