Re: Wider fallout from Debian issue?
Yves Rutschle wrote: On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote: Finally - how real is this concern? What is the probability that say a 2048bit generated key could fall into the 32,767 keys in the metasploit SSH example on unaffected systems? 32,768 = 2^15 number of 2048 bit keys: 2^2048 I think that's really oversimplified. If you look at the OpenSSL RSA key generator, you'll notice that RSA keys are built from 2 prime numbers of 1024 bits. Well not really 1024 bits but 1022 bits because top and bottom bit are always set. Also not all 2^1022 odd numbers between 2^1023 + 1 and 2^1024 - 1 are prime numbers. Also those prime numbers are generated using the output of the OpenSSL RNG which is commonly (assuming no entropy from uninitialized memory, which should be the case on Linux, and no .rnd file) seeded only with the 2^15 bit PID and ENTROPY_NEEDED (32) bytes from urandom. This would mean an upper limit 2^(15+256) = 2^271 keys that can be generated from OpenSSL (within those parameters). Probability that a "proper" key falls in the space of the "bad debian" keys: 2^15 / 2^2048 = 1 / 2^2033. That's a lot of zeros before the first non-zero digit. I get 2^15 / 2^271 = 1 / 2^256 which is a lot less impressive than your figure but still a very small probability. Sincerely, -- Mathias Brossard begin:vcard fn:Mathias Brossard n:Brossard;Mathias org:OpenTrust;R&D email;internet:[EMAIL PROTECTED] title:Senior Architect x-mozilla-html:FALSE version:2.1 end:vcard
Re: Wider fallout from Debian issue?
On Thu, May 29, 2008 at 10:14:12AM -0400, Victor Duchovni wrote: > And then knowing that attackers never choose these keys, users start > using these keys because attakers avoid them, and then attackers start > checking these first again, ... This way lies madness. Fix your premise > and don't change it in flight. Agreed. Let's assume that users tend to pick the password "password" when given a choice. Now adversaries try the most common password, namely "password", first. Security conscious admins ban the word "password" as a password. Yes, this does reduce the keyspace a tiny bit. Do adversaries generally stop trying the password "password"? Not generally. For every security-conscious admin or user, there are 99 who are not. For every cutting-edge security expert, there are 99 bottom-feeders who will only get this information years later. I still hear of people trying to tftp /etc/passwd. I think that people will still be trying to brute-force their way in with these keys for ten years. I would ban the use of these keys to gain entry to anything, much like security-conscious admins ban easily-guessed passwords. Only the key space here is much, much larger than typical 8-character passwords, so this loss will be unnoticeable. I personally don't like the idea of generating keys that people will try, or using a weak/known key with small probability, but in this case I think it's so small that simply scanning for and banning such keys is good enough. I was hoping someone would release a tool to search for them in the authorized_keys files on any OS (e.g. my OpenBSD box), but AFAIK, nobody has. I certainly don't want a kluge to the RNG. -- Crypto ergo sum. https://www.subspacefield.org/~travis/ Truth does not fear scrutiny or competition, only lies do. If you are a spammer, please email [EMAIL PROTECTED] to get blacklisted. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
* John Parker wrote on Sat, May 31, 2008 at 15:35 -0500: > > Probability that a "proper" key falls in the space of the > > "bad debian" keys: 2^15 / 2^2048 = 1 / 2^2033. > > > > That's a lot of zeros before the first non-zero digit. > > Put differently, if you were to start generating keys now at a rate > of, say, 1000/s, how long would you have to wait before you got one of > the Debian keys? This is a fun math problem for probability theory > students. wow, big numbers, John! Cool idea to make such a time estimation :) Maybe we should say `a million keys per second', sounds much more but just are three digits less in the result :) Is the calculation that complicated? Aren't the keys independent of each other, so that each key always have the same probability, since we are not `searching' but `guessing' when generating? (beside, that all those values are so horrible big that practically it does not matter of course :-)) With Victor's number of 2013 bits probablility, couldn't we statistically expect half of that? With a million per second does this give (2^2012) / 10^6 / 60 / 60 / 24 / 365.25 years which the 593 digit number 14902094353953870165214353410981143707238235188212334084836694330488\ 81602740116106914618746657670317636941551690018457525299578948872878\ 36765806488289940028625838604817603080995646449473721456572544453618\ 55782431446798772374819591436871325406930507575507226972337350924070\ 18286766525605611643878663746554436287030227901811414516143083673080\ 28892637223535933402770689260083725677906317276399679998875094201786\ 41124284757024653658707346461288521262653417342296719918707161098486\ 04762949019240046008945125630714069482285597143371578237868834348990\ 3212246280855279993597997641265155474006217516831 of years? Seems there even is a number word[1], so are that around a hundred quintillion nonagintacentillions? lol Assuming the age of the universe beeing 13.73 * 10^9 year (http://en.wikipedia.org/wiki/Age_of_the_universe), (2^2012) / 10^6 / 60 / 60 / 24 / 365.25 / (13.73 * 10^9) or `in short': 10853673965006460426230410350314015810078831164029376609495043212300\ 66717217855868109700470981551578759607830801178774599635527275216954\ 38285365250029089605699809617492791756005569154751435875143877970588\ 89863387798105442370589651447102203501041884614353406389175055297938\ 95329036071089301998454962670469363646780938020255946479346747030648\ 42602066441031269776235024952719392336421207047632687544701452441213\ 70083237259304190574440893271149687736819677598176780712823860960295\ 73753058280582699205349690918218550242014273228966917871718014820823\ 249253188700311725680844693464323049818 universe ages would be needed, slighty more than 10^582, which is a funny big number... Even when using `googols' (10^100) as factor it remains terrible... lol SCNR. oki, Steffen [1] http://en.wikipedia.org/wiki/Names_of_large_numbers#Extensions_of_the_standard_dictionary_numbers About Ingenico Throughout the world businesses rely on Ingenico for secure and expedient electronic transaction acceptance. Ingenico products leverage proven technology, established standards and unparalleled ergonomics to provide optimal reliability, versatility and usability. This comprehensive range of products is complemented by a global array of services and partnerships, enabling businesses in a number of vertical sectors to accept transactions anywhere their business takes them. www.ingenico.com This message may contain confidential and/or privileged information. If you are not the addressee or authorized to receive this for the addressee, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by reply e-mail and delete this message. Thank you for your cooperation. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
* [EMAIL PROTECTED] wrote on Fri, May 30, 2008 at 06:51 -0500: > Back in the day, DES was the de facto encryption algorithm. [...] > In an ideal world, I think the system should throw an exception > then and let the calling application feed it another key. > However, I think the general consensus was that we should just > ignore it. I don't know what the general consensus was, but applications I know do not ignore this situation but handle it by actively rejecting it. Do you meant this by `ignore'? I think best is to consider a weak or semi-weak [3-]DES[1] key as a [3-]DES key acceptable and thus refuse to generate, store or use it[2]. In practice usually it shouldn't be a big deal to iterate a 16 elements table at key generation, which probably usually is much more expensive. So to say that DES is not defined / allowed for those numbers (keys). I think it is a little like division by zero: it simply cannot be done. BTW, testing that can be difficult and probably needs special considerations (e.g. some test driver with special `PRNG without random' generating bits that lead to a weak key to check if the generator correctly detects and refuses it). oki, Steffen [1] A 3DES key with one weak or semi-weak key half should be considered weak (not essentially stronger than single DES). [2] http://en.wikipedia.org/wiki/Weak_key tells as a main countermeasure: `Checking generated keys against a list of known weak keys, or building rejection of weak keys into the key scheduling.' About Ingenico Throughout the world businesses rely on Ingenico for secure and expedient electronic transaction acceptance. Ingenico products leverage proven technology, established standards and unparalleled ergonomics to provide optimal reliability, versatility and usability. This comprehensive range of products is complemented by a global array of services and partnerships, enabling businesses in a number of vertical sectors to accept transactions anywhere their business takes them. www.ingenico.com This message may contain confidential and/or privileged information. If you are not the addressee or authorized to receive this for the addressee, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by reply e-mail and delete this message. Thank you for your cooperation. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Sat, May 31, 2008 at 09:32:54PM +0200, Yves Rutschle wrote: > On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote: > > Finally - how real is this concern? What is the probability that say a > > 2048bit generated key could fall into the 32,767 keys in the metasploit > > SSH example on unaffected systems? > > 32,768 = 2^15 > > number of 2048 bit keys: 2^2048 No, not all possible 2048 bit numbers are sensible RSA moduli. The modulus is a product of 2 1024-bit primes, whose density can be estimated via the Prime Number Theorem. Don't recall whether the primes used in practice have additional properties that further reduce their density. In any case the prime density is ~1/ln(N) and if estimate e ~= 2, only one in 1000 numbers of that size is prime, so there are ~20 bits fewer RSA moduli (crude estimate ~2028 bits). And subtracting 15 from that, we now get down to 2013 bits, which is still absurdly large. How many bits of random data are taken from the RNG to generate the two primes? If it is less that ~1000 bits each, the key-space bit count is the number of bits random data used, not the size of the primes. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Sat, May 31, 2008 at 2:32 PM, Yves Rutschle <[EMAIL PROTECTED]> wrote:
> On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote:
>> Finally - how real is this concern? What is the probability that say a
>> 2048bit generated key could fall into the 32,767 keys in the metasploit
>> SSH example on unaffected systems?
>
> 32,768 = 2^15
>
> number of 2048 bit keys: 2^2048
>
> Probability that a "proper" key falls in the space of the
> "bad debian" keys: 2^15 / 2^2048 = 1 / 2^2033.
>
> That's a lot of zeros before the first non-zero digit.
Put differently, if you were to start generating keys now at a rate
of, say, 1000/s, how long would you have to wait before you got one of
the Debian keys? This is a fun math problem for probability theory
students.
The probability that the first key you generate is from the Debian set
is the probability shown above, call it p.
The probability that the second key you generate is known is (1-p)p,
the probability that the first one generated isn't known but the
second one is. Similarly, the third: p(1-p)^2. In general,
p(1-p)^(n-1) that it's the nth key.
The expected value is sum(xP(x)) for all values of x: sum_{x=1..inf}
(xp(1-p)^(x-1)).
Expanded:
1p(1-p)^0 + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3...
For simplicity, let's define q to be 1-p: the probability that a
randomly generated key isn't known. The series becomes:
1(1-q)+2(1-q)q+3(1-q)q^2+4(1-q)q^3...
which is the same as
1-q + 2q-2q^2 + 3q^2+3q^3 + 4q^3-4q^4...
This reduces to
1+q+q^2+q^3...
This is the Maclaurin series for 1/(1-q) or 1/p:
http://en.wikipedia.org/wiki/Maclaurin_series
So the expected or average number of keys that will need to be
generated to get a single compromised key is 2^2033.
If we generate 1000 keys per second, every minute of every hour of
every day, python can tell us how many years this should take:
>>> 2**2033/1000/60/60/24/365
31273362428568397592339282651453150725927505483211674133457883903086002935187835628713902368959626676044355690433939619266697318127399331450487165278264227276952422607302843373297384824699247125847270814985691932082882361644413681612675805034740192979033275985559364836461601752345605100835466698544385055087087441932283729948709580608277506656401101528311256762947115091869664100469360191068701154131313187262849700051439632063137802627522490247771629992729670120799681243732768067704095846963793730355643106032512997622948135372447337202554569376369649862450650606037557559006417097486452568315050050L
-JP
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote: > Finally - how real is this concern? What is the probability that say a > 2048bit generated key could fall into the 32,767 keys in the metasploit > SSH example on unaffected systems? 32,768 = 2^15 number of 2048 bit keys: 2^2048 Probability that a "proper" key falls in the space of the "bad debian" keys: 2^15 / 2^2048 = 1 / 2^2033. That's a lot of zeros before the first non-zero digit. Y. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
Travis wrote: > Agreed. > > Let's assume that users tend to pick the password "password" when > given a choice. > > Now adversaries try the most common password, namely "password", first. > > Security conscious admins ban the word "password" as a password. > Yes, this does reduce the keyspace a tiny bit. > > Do adversaries generally stop trying the password "password"? > Not generally. Of course, but this is to catch people who do not follow proper security protocols. It's not designed to catch someone who actually chooses the password "password" using some valid password-generating method. To make this analogy apply, you would have to argue that an automated password generator that selects 8 random letters or numbers should specifically test its output for the string 'password' and try again if it just happens to get it by pure chance. > For every security-conscious admin or user, there are 99 who are not. > > For every cutting-edge security expert, there are 99 bottom-feeders > who will only get this information years later. > > I still hear of people trying to tftp /etc/passwd. > > I think that people will still be trying to brute-force their way in > with these keys for ten years. > > I would ban the use of these keys to gain entry to anything, much like > security-conscious admins ban easily-guessed passwords. Of course, but not because security-conscious users might happen to choose these keys by pure chance. You would ban them because someone might use software that has the bug to generate their keys. > Only the key space here is much, much larger than typical 8-character > passwords, so this loss will be unnoticeable. And that is the reason why you would *NOT* add a 'password' detector to your random password generator, which is essentially what was suggested here. > I personally don't like the idea of generating keys that people will > try, or using a weak/known key with small probability, but in this > case I think it's so small that simply scanning for and banning such > keys is good enough. Right, but you do that in case someone uses a broken RNG to generate them. > I was hoping someone would release a tool to search for them in the > authorized_keys files on any OS (e.g. my OpenBSD box), but AFAIK, > nobody has. > > I certainly don't want a kluge to the RNG... Exactly. You can't fix what isn't broken. By the way, while I disagree with most of the arguments made, I am not saying that I disagree with their conclusion. Here's how I would make the argument: 1) Broken code is going to be out there. We are going to see broken keys used for access, authentication, and signing. 2) We don't want to accept a signature from a broken key. We don't want to allow someone to access our machine with a compromised key. 3) So we probably will really want a blacklist of these keys, and we'll probably need to check every foreign key against this blacklist before we trust it forever. 4) If we have a list of keys we refuse to trust, we should probably make sure we don't generate keys we don't trust. (Though the probability is so, so low that I would argue that's what needed to ensure this is nothing.) DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
On Friday 30 May 2008 07:39:08 [EMAIL PROTECTED] wrote: > I personally don't like the idea of generating keys that people will > try, or using a weak/known key with small probability, but in this > case I think it's so small that simply scanning for and banning such > keys is good enough. What about in a digital signing example, where the point at which you receive a signed instrument (say by email) it might be considered legally binding? A specific example I have here in New Zealand is The Electronic Transactions Act where an electronic signature is, amongst other requirements, to be as reliable as is appropriate and adequately identify the signatory. One could argue (and I'm not a lawyer) that if the digital signature was created by a key in the "Debian" keyspace, the signature *may* no longer meet these two requirements and therefore the instrument could be invalid. The signatory and/or receiver however may not be aware of the contestability of the signature - which could result in all kinds of issues including abuse of the situation (e.g. one party is aware that the signature could be contested however chooses not to divulge until/if they decide that they want to try and exit the arrangement). It is clear by the posts thus far that checking for such keys on creation (on an unaffected system) seems unwarranted. There also seems to be some question about the validity of blacklisting of these keys. Relying on the system using the key (say for signing) being unaffected doesn't remove the possibility of the key having originated from an affected system. I'm therefore left wondering - is blacklisting the affected keys in all forms of *usage* on all systems a prudent option? If so: is this functionality something that may be featured in a future OpenSSL release, or something that should be undertaken by an end-user of OpenSSL? Thanks again, Deane __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Friday 30 May 2008 07:39:08 [EMAIL PROTECTED] wrote: > I personally don't like the idea of generating keys that people will > try, or using a weak/known key with small probability, but in this > case I think it's so small that simply scanning for and banning such > keys is good enough. > > I was hoping someone would release a tool to search for them in the > authorized_keys files on any OS (e.g. my OpenBSD box), but AFAIK, > nobody has. In the debian (+ubuntu+...) case, their package updating machinery now brings in a black-listing package that essentially blocks the use of host keys or user keys that match the "Debian Weak Key Space"(tm). I believe there's also a tool in there to scan - ah, found it. This is from the blacklist README; To check all keys on your system: sudo ssh-vulnkey -a To check a key in a non-standard location: ssh-vulnkey /path/to/key Though there is some note in their README to the effect that this isn't 100% bullet-proof, ie. a weak key might not be detected as such. I'm not sure why though, if they were really only hashing the PID then you have to figure that the affected keys are a distinctly finite set. Perhaps the issue is 64bit-vs-32bit and endianness platform variations. In any case, if in doubt, regenerate, grumble, and move on. > I certainly don't want a kluge to the RNG... Indeed, I've seen one RNG kludge so far this year, and that was one too many ... Cheers, Geoff __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 10:55:18PM -0700, David Schwartz wrote: > Okay, I guess I give up. I now realize that I had no idea what > you meant in your past few comments. What relevance do you think > this notion of weak keys has to do with this issue, since you > were the one who brought it up? > > The only issue here is known keys. The keys the Debian bug > causes OpenSSL to choose are not weak in this sense. I know exactly what he's getting at. Back in the day, DES was the de facto encryption algorithm. Later, we found that some of the keys in the keyspace were weak, using the cryptographic meaning of "weak". For example, if one key caused the encryption to be a no-op, that would be ultimately weak. These were actually significantly less weak then that, classified into two groups known as "weak" and "semi-weak"... http://en.wikipedia.org/wiki/Weak_key Of course, you'd generate these keys randomly n/2^56 (note: not 2^64) of the time, for a small integer n. The question was what to do about it. In an ideal world, I think the system should throw an exception then and let the calling application feed it another key. However, I think the general consensus was that we should just ignore it. I suppose in retrospect, that the chance of picking any single weak key was equal to the chance that the adversary simply guessed your key... in this case one in 2^56... so as long as there aren't too many, it's still O(brute force). -- Crypto ergo sum. https://www.subspacefield.org/~travis/ Truth does not fear scrutiny or competition, only lies do. If you are a spammer, please email [EMAIL PROTECTED] to get blacklisted. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Thu, May 29, 2008 at 10:14:12AM -0400, Victor Duchovni wrote: > And then knowing that attackers never choose these keys, users start > using these keys because attakers avoid them, and then attackers start > checking these first again, ... This way lies madness. Fix your premise > and don't change it in flight. Agreed. Let's assume that users tend to pick the password "password" when given a choice. Now adversaries try the most common password, namely "password", first. Security conscious admins ban the word "password" as a password. Yes, this does reduce the keyspace a tiny bit. Do adversaries generally stop trying the password "password"? Not generally. For every security-conscious admin or user, there are 99 who are not. For every cutting-edge security expert, there are 99 bottom-feeders who will only get this information years later. I still hear of people trying to tftp /etc/passwd. I think that people will still be trying to brute-force their way in with these keys for ten years. I would ban the use of these keys to gain entry to anything, much like security-conscious admins ban easily-guessed passwords. Only the key space here is much, much larger than typical 8-character passwords, so this loss will be unnoticeable. I personally don't like the idea of generating keys that people will try, or using a weak/known key with small probability, but in this case I think it's so small that simply scanning for and banning such keys is good enough. I was hoping someone would release a tool to search for them in the authorized_keys files on any OS (e.g. my OpenBSD box), but AFAIK, nobody has. I certainly don't want a kluge to the RNG... -- Crypto ergo sum. https://www.subspacefield.org/~travis/ Truth does not fear scrutiny or competition, only lies do. If you are a spammer, please email [EMAIL PROTECTED] to get blacklisted. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 08:01:11PM +0200, Ger Hobbelt wrote: > Anything (such as passwords) which has been used on an *actual* > 'compromized box' (be it one of 'those Debian' releases or otherwise) > to _generate_ keys plus any keys _produced_ on such a compromised box > must be eradicated and are not allowed entry. Anything derived from > them will be lost or must be re-encrypted/re-created on a 'good > system'. > [...] That's a pretty interesting thought process. I should probably write about some of those scenarios. For those who are interested in a discussion of proper RNG behavior, see the section in my online book, here: http://www.subspacefield.org/security/security_concepts.html#tth_sEc21 -- Crypto ergo sum. https://www.subspacefield.org/~travis/ Truth does not fear scrutiny or competition, only lies do. If you are a spammer, please email [EMAIL PROTECTED] to get blacklisted. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
Only against random attacks of course, if all attackers first check these keys, then removing them strengthens the algorithm against (non-random) brute-force attack. This said, the effort of explicitly avoiding these is probably wasted (unless one suspects one has a identically weak RNG). -- Viktor. I realize it's counter-intuitive, but even this is wrong. Suppose that there's an attack tool that everyone uses to attack a particular algorithm. It brute-forces passwords and follows a particular pattern. If you use an implementation that is known to not use the first 10,000 keys this algorithm tests, attackers will respond by skipping those 10,000 keys. The net result will only be a reduction in the keyspace. Even if every attacker tests a particular key first, it is a net loss in security to specifically avoid that key if you randomly chose it. Really. If you honestly and truly randomly selected the key, you should go with it. Otherwise, there's one less key for an attacker to test. DS You are afraid of somebody DoS'ing RSA algorithm out of existense by repeating the Debian-style mistakes a couple more times? __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Thu, May 29, 2008 at 09:48:38AM +0200, Steffen DETTMER wrote: > On the other hand, someone else could assume that all potentially > weak keys are regenerated and the concerned (boxes, > systems, admins, security professionals, ...) now are more > sensitive, carefully exchanged all keys against, installed IDSes > scanning the network traffic for traces of weak keys and this > time double-verified everything, including exhaustive use of all > the black-hat attack tools to test themselfs, and from that > conclude that it makes no sense to check that keys at all because > noone will ever use them and if someone accidently created one, > security test tools will alert `potential valgrind-SSL key' or > alike. > >(I would start searching those `frequently existing' keys :-)) > > Does this make sense or am I wrong? A complicate topic I think, > and very interesting :) And then knowing that attackers never choose these keys, users start using these keys because attakers avoid them, and then attackers start checking these first again, ... This way lies madness. Fix your premise and don't change it in flight. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
* Victor Duchovni wrote on Wed, May 28, 2008 at 21:10 -0400: > > > Only against random attacks of course, if all attackers > > > first check these keys, then removing them strengthens the > > > algorithm against (non-random) brute-force attack. This > > > said, the effort of explicitly avoiding these is probably > > > wasted (unless one suspects one has a identically weak > > > RNG). I think blacklisting those keys on a strong system reduces the key space (even if it just the smallest bit of a bit) and thus helps the attacker, because she don't need to try those keys. In this particular case I would expect an attacker testing those `frequently existing' keys first (in the hope/expectation to hit from time to time a key generated with such a valgrind-SSL :-)). Noone requires brute-force to use a random probe order :-) If assuming that because of this all RSA brute force attacks try those keys first in all future, someone may wish to avoid such keys (accepting a small decrease of key space). On the other hand, someone else could assume that all potentially weak keys are regenerated and the concerned (boxes, systems, admins, security professionals, ...) now are more sensitive, carefully exchanged all keys against, installed IDSes scanning the network traffic for traces of weak keys and this time double-verified everything, including exhaustive use of all the black-hat attack tools to test themselfs, and from that conclude that it makes no sense to check that keys at all because noone will ever use them and if someone accidently created one, security test tools will alert `potential valgrind-SSL key' or alike. (I would start searching those `frequently existing' keys :-)) Does this make sense or am I wrong? A complicate topic I think, and very interesting :) oki, Steffen About Ingenico Throughout the world businesses rely on Ingenico for secure and expedient electronic transaction acceptance. Ingenico products leverage proven technology, established standards and unparalleled ergonomics to provide optimal reliability, versatility and usability. This comprehensive range of products is complemented by a global array of services and partnerships, enabling businesses in a number of vertical sectors to accept transactions anywhere their business takes them. www.ingenico.com This message may contain confidential and/or privileged information. If you are not the addressee or authorized to receive this for the addressee, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by reply e-mail and delete this message. Thank you for your cooperation. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 6:47 PM, Deane Sloan <[EMAIL PROTECTED]> wrote: > To tie this off - is it fair to say that the impact of say 2048bit RSA > SSL(etc) using a private key in the affected range is a valid > consideration/concern, however in combination with the likelihood > stated, the overall risk of generating such a key on an unaffected > system is (extremely?) small for the security that a 2048bit RSA private > key is intended for? > > Chuckle - so I'm basically worried about getting struck by lightening > with this concern, whilst at the same time I'm playing with matches and > kerosene... I'd say: extremely small. Despite all the collected entropy on a good box, it has to produce the _exact_ same state as such a Debian box. This is _very_ highly unlikely. So play on, just watch the weather and most importantly: your matches. ;-) I use a simple rule for my own dealings regarding this, given my security paranoia mixed with a sufficiently painful lack of cryptography-oriented math to be sure of anything more than this: Anything (such as passwords) which has been used on an *actual* 'compromized box' (be it one of 'those Debian' releases or otherwise) to _generate_ keys plus any keys _produced_ on such a compromised box must be eradicated and are not allowed entry. Anything derived from them will be lost or must be re-encrypted/re-created on a 'good system'. Given the behaviour of a proper OpenSSL installation (which collects sufficient entropy before generating anything that's cryptographically sensitive), anything coming from somewhere else is a-okay. Assuming I'm 'safe' using the rule described above (and over the years I've used it, it seems to do), it comes down to this: - if you can prove (e.g. by creating them yourself) that the private keys you are using do not originate from a compromized [Debian?] system, you can do anything and will be fine. (this is another way of saying: no need to check any keys generated by yourself on non-compromised systems; keys are independent, so they may /look/ like the others but they are not, thanks to the different entropy/random state that led to these keys.) - if you use passwords to protect keys, etc. and have not used them on a compromized system, again, you are fine. (and if you used a password on a compromized system: if you did not send anything derived from those through keygeneration+communications or otherwise on such a box, and destroyed the box (e.g. by replacing the compromized software) before anything could get out, you're still fine. An 'invisible mistake' is a mistake never made.) Hope this helps. Please correct me if I made mistakes. -- Met vriendelijke groeten / Best regards, Ger Hobbelt -- web: http://www.hobbelt.com/ http://www.hebbut.net/ mail: [EMAIL PROTECTED] mobile: +31-6-11 120 978 -- __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
> David Schwartz wrote: > > > Every known key, provided there are not too many known keys, is weak. > > Once again, you have a very idiosyncratic lexicon of cryptographic > terms. How about if we use these words the way cryptographers do? > > A weak key is one that causes a cipher to leak private data in the > ciphertext, or reveal key structure in a timing attack, or makes > the implementation vulnerable to an adaptive chosen-plaintext attack, > etc. A diminished keyspace reduces the number of keys to be attempted > in a brute force attack. This may or may not be significant. If the > reduction in keyspace means a brute force attack effort is reduced by > half to merely half the life of the universe, that might be a worthwhile > tradeoff. Okay, I guess I give up. I now realize that I had no idea what you meant in your past few comments. What relevance do you think this notion of weak keys has to do with this issue, since you were the one who brought it up? The only issue here is known keys. The keys the Debian bug causes OpenSSL to choose are not weak in this sense. DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
David Schwartz wrote: Every known key, provided there are not too many known keys, is weak. Once again, you have a very idiosyncratic lexicon of cryptographic terms. How about if we use these words the way cryptographers do? A weak key is one that causes a cipher to leak private data in the ciphertext, or reveal key structure in a timing attack, or makes the implementation vulnerable to an adaptive chosen-plaintext attack, etc. A diminished keyspace reduces the number of keys to be attempted in a brute force attack. This may or may not be significant. If the reduction in keyspace means a brute force attack effort is reduced by half to merely half the life of the universe, that might be a worthwhile tradeoff. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 04:31:20PM -0700, David Schwartz wrote: > > Only against random attacks of course, if all attackers first check these > > keys, then removing them strengthens the algorithm against (non-random) > > brute-force attack. This said, the effort of explicitly avoiding these > > is probably wasted (unless one suspects one has a identically weak RNG). > > I realize it's counter-intuitive, but even this is wrong. Suppose that > there's an attack tool that everyone uses to attack a particular algorithm. > It brute-forces passwords and follows a particular pattern. > > If you use an implementation that is known to not use the first 10,000 keys > this algorithm tests, attackers will respond by skipping those 10,000 keys. > The net result will only be a reduction in the keyspace. You are changing the premise. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
> On Wed, May 28, 2008 at 03:38:47PM -0700, David Schwartz wrote: > > In principle, specifically avoiding these keys weakens the > > algorithm by reducing the keyspace. > > > Only against random attacks of course, if all attackers first check these > keys, then removing them strengthens the algorithm against (non-random) > brute-force attack. This said, the effort of explicitly avoiding these > is probably wasted (unless one suspects one has a identically weak RNG). > > -- > Viktor. I realize it's counter-intuitive, but even this is wrong. Suppose that there's an attack tool that everyone uses to attack a particular algorithm. It brute-forces passwords and follows a particular pattern. If you use an implementation that is known to not use the first 10,000 keys this algorithm tests, attackers will respond by skipping those 10,000 keys. The net result will only be a reduction in the keyspace. Even if every attacker tests a particular key first, it is a net loss in security to specifically avoid that key if you randomly chose it. Really. If you honestly and truly randomly selected the key, you should go with it. Otherwise, there's one less key for an attacker to test. DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 03:38:47PM -0700, David Schwartz wrote: > In principle, specifically avoiding these keys weakens the algorithm by > reducing the keyspace. > Only against random attacks of course, if all attackers first check these keys, then removing them strengthens the algorithm against (non-random) brute-force attack. This said, the effort of explicitly avoiding these is probably wasted (unless one suspects one has a identically weak RNG). -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
> David Schwartz wrote: > > ... Suppose I include a randomish > > string in my message "46e8bd8ceae57f8b7af66536e7859bad". Any > > attacker might > > see this message -- it's public. So he can certainly try that > > string as your > > password. So will you now run off and add it to a blacklist, since it's > > clearly now a weak password? > I suppose the distinction between "known" and "weak" is too fine > a semantic point for you? Every known key, provided there are not too many known keys, is weak. If it's possible for there to be so many known keys that an algorithm is compromised, something would have to be seriously broken with that algorithm in the first place. If a key is made known randomly, it is not longer any weaker than any other key. These keys are not any weaker than any other key unless you choose them because of the bug. If someone makes a buggy random number generator that always outputs 4, you don't modify your random number generator to never produce 4. Whether 4 is strong or weak depends upon whether you chose it randomly or not. In principle, specifically avoiding these keys weakens the algorithm by reducing the keyspace. DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
* Deane Sloan wrote on Thu, May 29, 2008 at 04:47 +1200: > stated, the overall risk of generating such a key on an unaffected > system is (extremely?) small for the security that a 2048bit RSA private > key is intended for? The risk to generate one specific key of 2^16 (or how small was the key space?) should be `roughly the same' compared to 2048 Bit RSA, as to generate one specific key (when assuming perfect strong generation). That means, the risk that you accidently generate exactly the same key as I generated is of almost the same order of magnitude. This also was acceptable before the debian issue :) Of course you are right, this probably happens all few billion years in one of the known universes and theoretically it could even happen with the key you are generating right now :-) If someone would not accept the risk of randomness / entropy with their properties, using cryptography in this case probably would be no option, but I think in all `practical situations' such extremely unbelievable rare events (as strong key generation producing collisions) should not be overstated. oki, Steffen About Ingenico Throughout the world businesses rely on Ingenico for secure and expedient electronic transaction acceptance. Ingenico products leverage proven technology, established standards and unparalleled ergonomics to provide optimal reliability, versatility and usability. This comprehensive range of products is complemented by a global array of services and partnerships, enabling businesses in a number of vertical sectors to accept transactions anywhere their business takes them. www.ingenico.com This message may contain confidential and/or privileged information. If you are not the addressee or authorized to receive this for the addressee, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by reply e-mail and delete this message. Thank you for your cooperation. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
Thank you Victor for your succinct clarification and to David and Michael for their responses. To tie this off - is it fair to say that the impact of say 2048bit RSA SSL(etc) using a private key in the affected range is a valid consideration/concern, however in combination with the likelihood stated, the overall risk of generating such a key on an unaffected system is (extremely?) small for the security that a 2048bit RSA private key is intended for? Chuckle - so I'm basically worried about getting struck by lightening with this concern, whilst at the same time I'm playing with matches and kerosene... Thanks again, Deane -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Victor Duchovni Sent: Thursday, May 29, 2008 3:37 AM To: openssl-users@openssl.org Subject: Re: Wider fallout from Debian issue? On Wed, May 28, 2008 at 08:09:16AM -0700, Michael Sierchio wrote: > David Schwartz wrote: > > > ... Suppose I include a randomish > >string in my message "46e8bd8ceae57f8b7af66536e7859bad". Any attacker > >might see this message -- it's public. So he can certainly try that > >string as your password. So will you now run off and add it to a > >blacklist, since it's clearly now a weak password? > > I suppose the distinction between "known" and "weak" is too fine a > semantic point for you? If there exists a known subset of keys large enough for random keys to have appreciable probability of being a member of that set, the keyspace is too small. The RSA keyspace is not "small" in this sense, in fact because it succumbs to *analytic* attacks long before exhaustive key-space search brute-force attacks, the odds of a random RSA key being in a small set of keys are rediculously low. The OP's concern is unwarranted. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 08:09:16AM -0700, Michael Sierchio wrote: > David Schwartz wrote: > > > ... Suppose I include a randomish > >string in my message "46e8bd8ceae57f8b7af66536e7859bad". Any attacker might > >see this message -- it's public. So he can certainly try that string as > >your > >password. So will you now run off and add it to a blacklist, since it's > >clearly now a weak password? > > I suppose the distinction between "known" and "weak" is too fine > a semantic point for you? If there exists a known subset of keys large enough for random keys to have appreciable probability of being a member of that set, the keyspace is too small. The RSA keyspace is not "small" in this sense, in fact because it succumbs to *analytic* attacks long before exhaustive key-space search brute-force attacks, the odds of a random RSA key being in a small set of keys are rediculously low. The OP's concern is unwarranted. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
David Schwartz wrote: > ... Suppose I include a randomish string in my message "46e8bd8ceae57f8b7af66536e7859bad". Any attacker might see this message -- it's public. So he can certainly try that string as your password. So will you now run off and add it to a blacklist, since it's clearly now a weak password? I suppose the distinction between "known" and "weak" is too fine a semantic point for you? __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
RE: Wider fallout from Debian issue?
> Finally - how real is this concern? What is the probability that say a > 2048bit generated key could fall into the 32,767 keys in the metasploit > SSH example on unaffected systems? > > Best Regards, > > Deane If you think about it, it doesn't make sense. Suppose I include a randomish string in my message "46e8bd8ceae57f8b7af66536e7859bad". Any attacker might see this message -- it's public. So he can certainly try that string as your password. So will you now run off and add it to a blacklist, since it's clearly now a weak password? DS __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: Wider fallout from Debian issue?
On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote: > Finally - how real is this concern? What is the probability that say a > 2048bit generated key could fall into the 32,767 keys in the metasploit > SSH example on unaffected systems? This concern is unwarranted. -- Viktor. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
Wider fallout from Debian issue?
Hi, Regarding the recently reported Debian patch of OpenSSL issue, the affected keys would seem to be well known and with the metasploit site hosting pre-computed keys and a number of scripts around various sites available to take advantage of the specific problem, it would seem like just a matter of time before these keys become the first port of call for a malicious user looking to compromise any arbitrary key (in the hope that it's from an affected system). Should these compromisable keys now be considered in the same light as a password of "password" on otherwise unaffected systems? In other words - if these keys could now form the base of a dictionary (of sorts) for an attack, should we consider also checking generated private keys (by OpenSSL in this instance) much as some systems check for silly passwords? If so: Would the key space be narrowed materially if these keys were removed from the "allowable" private keys in 2048 RSA for example? Could a 128bit MAC of the keys be used (or the like) instead of actually looking up against the full keys? From a runtime perspective, distributing the full pre-computed keys and checking could be prohibitive for some solutions, vs. say a binary tree of 128bit hashes. How significantly would a 128 bit MAC of the key reduce the allowable key space? Is there any intention that OpenSSL do such a "bad key" check (much as the OpenSSL-blacklist for Ubuntu presumably does), or would it be something that users concerned enough would look to do themselves? With all the posts around why the Debian issue may have occurred, I'd hate to be trail blazing... Finally - how real is this concern? What is the probability that say a 2048bit generated key could fall into the 32,767 keys in the metasploit SSH example on unaffected systems? Best Regards, Deane __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager [EMAIL PROTECTED]
