Re: weak key check?
On Tue, Feb 21, 2012 at 5:47 PM, Chris Dodd d...@csl.sri.com wrote: On 02/19/2012 07:36 PM, anthony berglas wrote: Exactly. So you need about 112 bits of entropy / Pass Phrase to generate a good 2048 bit key. Remember that the vast majority of 2048 bit numbers are not valid key pairs. My question is, has this been done, or would it be easy to do given the existing structure. No, this is NOT true. While it is the case that a good 2048 bit RSA key gives you only about 112 bits of security, its not at all clear that you can generate such a good key from less than 2048 bits of entropy. Indeed, from the recently published Lenstra/Hughes attack, its clear that using 112 bits of entropy to generate an RSA key (of any length) cannot possibly give you more that 56 bits of security, and probably far less. Surely not. What is the attack, given my 112 bits of entropy and my single RSA key generated from it, that reduces security down to 56 bits? An upper bound for the amount of entropy used by the colliding devices could be derived, though. Very crudely, 2.3% of self-signed certs were colliding. So, it takes about 44 certs to produce a collision, so the total entropy is ~44^2 = ~2^11. In fact, I'm sure the pool for potential collisions is actually smaller, so we can be reasonably confident the devices had significantly less than 11 bits of entropy. That seems like a curable problem!!! __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Tue, Feb 21, 2012 at 7:04 PM, Ben Laurie b...@links.org wrote: On Tue, Feb 21, 2012 at 5:47 PM, Chris Dodd d...@csl.sri.com wrote: On 02/19/2012 07:36 PM, anthony berglas wrote: Exactly. So you need about 112 bits of entropy / Pass Phrase to generate a good 2048 bit key. Remember that the vast majority of 2048 bit numbers are not valid key pairs. My question is, has this been done, or would it be easy to do given the existing structure. No, this is NOT true. While it is the case that a good 2048 bit RSA key gives you only about 112 bits of security, its not at all clear that you can generate such a good key from less than 2048 bits of entropy. Indeed, from the recently published Lenstra/Hughes attack, its clear that using 112 bits of entropy to generate an RSA key (of any length) cannot possibly give you more that 56 bits of security, and probably far less. Surely not. What is the attack, given my 112 bits of entropy and my single RSA key generated from it, that reduces security down to 56 bits? An upper bound for the amount of entropy used by the colliding devices could be derived, though. Very crudely, 2.3% of self-signed certs were colliding. So, it takes about 44 certs to produce a collision, so the total entropy is ~44^2 = ~2^11. In fact, I'm sure the pool for potential collisions is actually smaller, so we can be reasonably confident the devices had significantly less than 11 bits of entropy. Sigh. Sorry, this is not an upper bound - the 2.3% approximation yields a lower bound. So, bad calculation. I'm sure it can be done better, though! __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On 02/19/2012 07:36 PM, anthony berglas wrote: Exactly. So you need about 112 bits of entropy / Pass Phrase to generate a good 2048 bit key. Remember that the vast majority of 2048 bit numbers are not valid key pairs. My question is, has this been done, or would it be easy to do given the existing structure. No, this is NOT true. While it is the case that a good 2048 bit RSA key gives you only about 112 bits of security, its not at all clear that you can generate such a good key from less than 2048 bits of entropy. Indeed, from the recently published Lenstra/Hughes attack, its clear that using 112 bits of entropy to generate an RSA key (of any length) cannot possibly give you more that 56 bits of security, and probably far less. Chris Dodd d...@csl.sri.com __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Mon, Feb 20, 2012, anthony berglas wrote: Exactly. So you need about 112 bits of entropy / Pass Phrase to generate a good 2048 bit key. Remember that the vast majority of 2048 bit numbers are not valid key pairs. My question is, has this been done, or would it be easy to do given the existing structure. It hasn't been done AFAIK. Doing it is not trivial as OpenSSL includes additional entropy at various points (low level stuff like the current time) in addition to the initial seed. You could write a new default PRNG method and use that or your own key generation method. Is there a reason why you can't use a derive symmetric key instead? There are several ways to do that. Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On 2/17/2012 10:16 PM, Wim Lewis wrote: On Feb 16, 2012, at 9:22 AM, Kenneth Goldman wrote: Many laptops and desktops and some servers now come with a TPM chip, a free source of hardware random numbers. Even aside from TPM or other HSMs, hardware random number generators have been a common feature of PC motherboard chipsets for a decade or so. I assume, perhaps optimistically, that the /dev/?random devices that modern OSs provide make use of these RNGs as well as other system entropy sources (interrupt timing and so on). Unfortunately not! Intel made a big splash when they put a hardware RNG in one of the flash EEPROM chip models for storing the BIOS, then silently omitted the feature from all later models and even some chips of the same model (!). Later various other motherboard chip makers have been adding and removing this feature from various chip models at various time. Thus only a somewhat small minority of PC motherboards from the last 10 years actually have the feature, and a specific driver is needed for each family of hardware implementations within that minority. As for the standard /dev/random devices and motherboards with this feature, the situation varies with the OS: For Linux, the motherboard or CPU hardware random source will be available as an extra character device which may be named /dev/hwrandom or a hardware specific name (varies with the Linux dist). A user mode daemon reads this device and feeds the random bits into /dev/random for use by /dev/random and /dev/urandom. For BSD and other UNIX variants, I have no information at this time. For NT based MS Windows, support for the Intel RNG apparently never got integrated into the CryptoAPI system PRNG (which servers the same purpose as /dev/random). It is unclear if recent Windows versions, with their general focus on integration with TPM chips, also use the TPM chip (if present) as an RNG input to the system PRNG, and if so, which of the multiple current System PRNG APIs that use it. It sounds like most of the low-entropy keys discovered by Lenstra+co belong not to desktop/server machines but to embedded devices such as firewalls or VPN boxes; it's easy to imagine that such a device, without a hardware RNG and generating its secret key immediately after its first boot, fresh from factory initialization, could have a hard time getting enough entropy. Some could also be from the Debian/Ubuntu bug I mentioned in an earlier post. In the past few years I have also come across some semi-embedded devices that won't let the user regenerate or change the built-in https-management X.509 certificate and its key. Enjoy Jakob -- Jakob Bohm, CIO, Partner, WiseMo A/S. http://www.wisemo.com Transformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10 This public discussion message is non-binding and may contain errors. WiseMo - Remote Service Management for PCs, Phones and Embedded __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Feb 17, 2012, at 5:05 PM, anthony berglas wrote: Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? I dimly remember seeing schemes and specifications for doing roughly that, although I can't find a reference for one offhand[1]. All the entropy is provided upfront and the secret key parameters are derived from it in a well-defined deterministic way. AIUI the intent is to allow the RNG and PKC implementations to be validated independently (with published test vectors for the deterministic key-generation step) but presumably you could use it to derive RSA keys from a password as well. (I might be remembering DSA key generation; the secret parameter of a DSA key doesn't have to have special properties, so you could if you wanted simply use the output of a PBKDF-like algorithm there?) My question is, has this been done, or would it be easy to do given the existing structure. I don't think it would be hard to do; OpenSSL's rsa_builtin_keygen() is pretty straightforward and I don't think it relies on any internals not exposed to users of the library. You could write a version of it that calls an equivalent of BN_generate_prime_ex() that works deterministically based on the passphrase. Like others, I'm skeptical that this is actually a good idea, but I could be wrong... [1] Some places suggest that X9.31 and/or X9.44 might contain deterministic algorithms for RSA secret key generation in their appendices, but I don't have easy access to those. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Feb 20, 2012, at 8:38 AM, Jakob Bohm wrote: On 2/17/2012 10:16 PM, Wim Lewis wrote: Even aside from TPM or other HSMs, hardware random number generators have been a common feature of PC motherboard chipsets for a decade or so. I assume, perhaps optimistically, that the /dev/?random devices that modern OSs provide make use of these RNGs as well as other system entropy sources (interrupt timing and so on). Unfortunately not! [] How disappointing. :( Good to know, though. Some [low-entropy keys] could also be from the Debian/Ubuntu bug I mentioned in an earlier post. The paper mentions that they found some keys that were on the Debian/Ubuntu blacklist, but it sounds like these do not account for the weak keys they found: 21419 X.509 certificates and PGP keys are affected [factorable due to shared factors]. Note that affected moduli are much more frequently shared than non-affected ones. None of the affected moduli are blacklisted. (With more data, that number went up to 26965.) Their other numbers: 30099 n-values were found on the Debian/Ubuntu blacklist, but only 2 immediately factorable; 71024 n-values are shared by more than one certificate, but many of those instances are intentional/benign. Nadia Heninger has a post on Freedom-to-Tinker ( https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs ). She's not one of the authors of the Lenstra paper but is part of a different group that was doing similar research and finding similar results. From that post: this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown web servers. [] So which systems are vulnerable? Almost all of the vulnerable keys were generated by and are used to secure embedded hardware devices such as routers and firewalls, not to secure popular web sites such as your bank or email provider. Only one of the factorable SSL keys was signed by a trusted certificate authority and it has already expired. [] Embedded devices are well known to have entropy problems. However, until now it wasn't apparent how widespread these problems were in real, Internet-connected devices. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
Thanks for that. As to why it is a good idea, consider for example encrypted zip files sent to various people. The big danger with encryption is that keys will be lost, and thus the data. So as well as encrypting with a symmetric pass phrase, that phrase can be wrapped in a public key (which requires a cert). But now we have the problem of the private key, key stores etc. Easy for an PKI expert, but not for a simple user. How much simpler a public key pass phrase that can be remembered, written down etc. No Key store to mismanage or loose. Anthony On Tue, Feb 21, 2012 at 8:47 AM, Wim Lewis w...@omnigroup.com wrote: On Feb 17, 2012, at 5:05 PM, anthony berglas wrote: Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? I dimly remember seeing schemes and specifications for doing roughly that, although I can't find a reference for one offhand[1]. All the entropy is provided upfront and the secret key parameters are derived from it in a well-defined deterministic way. AIUI the intent is to allow the RNG and PKC implementations to be validated independently (with published test vectors for the deterministic key-generation step) but presumably you could use it to derive RSA keys from a password as well. (I might be remembering DSA key generation; the secret parameter of a DSA key doesn't have to have special properties, so you could if you wanted simply use the output of a PBKDF-like algorithm there?) My question is, has this been done, or would it be easy to do given the existing structure. I don't think it would be hard to do; OpenSSL's rsa_builtin_keygen() is pretty straightforward and I don't think it relies on any internals not exposed to users of the library. You could write a version of it that calls an equivalent of BN_generate_prime_ex() that works deterministically based on the passphrase. Like others, I'm skeptical that this is actually a good idea, but I could be wrong... [1] Some places suggest that X9.31 and/or X9.44 might contain deterministic algorithms for RSA secret key generation in their appendices, but I don't have easy access to those. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org -- Dr Anthony Berglas, anth...@berglas.org Mobile: +61 4 4838 8874 Just because it is possible to push twigs along the ground with ones nose does not necessarily mean that that is the best way to collect firewood.
Re: weak key check?
On Sat, Feb 18, 2012, Edward Ned Harvey wrote: From: owner-openssl-us...@openssl.org [mailto:owner-openssl- us...@openssl.org] On Behalf Of anthony berglas Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? You want at least 2048 bits of entropy. That's a very long passphrase. Also, unless you randomly generate your passphrase in hex or binary, it's bound to be a lot less than 2048 bits of entropy even if it's 2048 bits long. It depends on the key length and the algorithm in question. For example for an 2048 bit RSA key the equivalent comparable security strength is 112 bits (see SP800-57 et al). Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
Exactly. So you need about 112 bits of entropy / Pass Phrase to generate a good 2048 bit key. Remember that the vast majority of 2048 bit numbers are not valid key pairs. My question is, has this been done, or would it be easy to do given the existing structure. Anthony On Mon, Feb 20, 2012 at 2:49 AM, Dr. Stephen Henson st...@openssl.orgwrote: On Sat, Feb 18, 2012, Edward Ned Harvey wrote: From: owner-openssl-us...@openssl.org [mailto:owner-openssl- us...@openssl.org] On Behalf Of anthony berglas Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? You want at least 2048 bits of entropy. That's a very long passphrase. Also, unless you randomly generate your passphrase in hex or binary, it's bound to be a lot less than 2048 bits of entropy even if it's 2048 bits long. It depends on the key length and the algorithm in question. For example for an 2048 bit RSA key the equivalent comparable security strength is 112 bits (see SP800-57 et al). Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org -- Dr Anthony Berglas, anth...@berglas.org Mobile: +61 4 4838 8874 Just because it is possible to push twigs along the ground with ones nose does not necessarily mean that that is the best way to collect firewood.
RE: weak key check?
From: owner-openssl-us...@openssl.org [mailto:owner-openssl- us...@openssl.org] On Behalf Of anthony berglas Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? You want at least 2048 bits of entropy. That's a very long passphrase. Also, unless you randomly generate your passphrase in hex or binary, it's bound to be a lot less than 2048 bits of entropy even if it's 2048 bits long. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Feb 16, 2012, at 9:22 AM, Kenneth Goldman wrote: Many laptops and desktops and some servers now come with a TPM chip, a free source of hardware random numbers. Even aside from TPM or other HSMs, hardware random number generators have been a common feature of PC motherboard chipsets for a decade or so. I assume, perhaps optimistically, that the /dev/?random devices that modern OSs provide make use of these RNGs as well as other system entropy sources (interrupt timing and so on). It sounds like most of the low-entropy keys discovered by Lenstra+co belong not to desktop/server machines but to embedded devices such as firewalls or VPN boxes; it's easy to imagine that such a device, without a hardware RNG and generating its secret key immediately after its first boot, fresh from factory initialization, could have a hard time getting enough entropy. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
Taking a different slant, is it possible to provide the Entropy using a pass phrase. So a given pass phrase will always generate the same key pair. This means that for simple applications no key store is required. Much like password based (symmetric) encryption. Any ideas as to how hard that would be to do with Open SSL? Has anyone else done it? Anthony 2012/2/17 Richard Könning richard.koenn...@ts.fujitsu.com Am 16.02.2012 12:17, schrieb Jakob Bohm: 2. Creating primes starts with high quality random numbers, such that there are a gigantic number of possible primes. If done correctly (like in current OpenSSL versions), the chance of choosing the same prime as somebody else is extremely low (again, I hope someone else on this list can come up with the numbers for general enlightenment). Well, seeding the PRNG correctly seems not to be a trivial task, see e.g. http://eprint.iacr.org/2012/**064.pdfhttp://eprint.iacr.org/2012/064.pdfand https://freedom-to-tinker.com/**blog/nadiah/new-research-** theres-no-need-panic-over-**factorable-keys-just-mind-**your-ps-and-qshttps://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs . Ciao, Richard __**__**__ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org -- Dr Anthony Berglas, anth...@berglas.org Mobile: +61 4 4838 8874 Just because it is possible to push twigs along the ground with ones nose does not necessarily mean that that is the best way to collect firewood.
weak key check?
Hi! Is the sentence It checks that p and q are in fact prime, and that n = p*q in RSA_check_key's documentation mean that it checks for weak primes, like the ones mentioned here?: http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars As I understand there are two cases. One is when the prime is not exactly prime. I would expect RSA_check_key to find this out, but what is the extent of the check? The other cause is a clash with already existing prime factors out there. I guess that checking for this would involve looking up a list of prime factors collected on the net. Is there such tool accessible to mere mortals?
Re: weak key check?
On 2/16/2012 11:36 AM, Magosányi Árpád wrote: Hi! Is the sentence It checks that p and q are in fact prime, and that n = p*q in RSA_check_key's documentation mean that it checks for weak primes, like the ones mentioned here?: http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars As I understand there are two cases. One is when the prime is not exactly prime. I would expect RSA_check_key to find this out, but what is the extent of the check? The other cause is a clash with already existing prime factors out there. I guess that checking for this would involve looking up a list of prime factors collected on the net. Is there such tool accessible to mere mortals? All the practical ways of creating and checking primes for use in crypto have the following features: 1. They are statistical tests, each round of testing that passes increases the probability that this is really a prime, you stop if it says not a prime (an absolute non-statistical rejection) or until the combined probability is big enough for you. Someone else on this list can hopefully give you the number of rounds and resulting probabilities used by OpenSSL. 2. Creating primes starts with high quality random numbers, such that there are a gigantic number of possible primes. If done correctly (like in current OpenSSL versions), the chance of choosing the same prime as somebody else is extremely low (again, I hope someone else on this list can come up with the numbers for general enlightenment). However there is another issue with checking for known bad primes: Some versions of OpenSSL historically packaged by the Debian and Ubuntu Linux distributions from 2006 to 2008 contained a broken non-standard patch which caused those patched versions to frequently choose one of a very few primes and RSA keys. Debian has published a table of the bad keys and code to check existing keys against those blacklists. For more information, see the security advisory at http://www.debian.org/security/2008/dsa-1571 and the blacklist databases from http://packages.debian.org/source/sid/openssl-blacklist Enjoy Jakob -- Jakob Bohm, CIO, Partner, WiseMo A/S. http://www.wisemo.com Transformervej 29, 2730 Herlev, Denmark. Direct +45 31 13 16 10 This public discussion message is non-binding and may contain errors. WiseMo - Remote Service Management for PCs, Phones and Embedded __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
Am 16.02.2012 12:17, schrieb Jakob Bohm: 2. Creating primes starts with high quality random numbers, such that there are a gigantic number of possible primes. If done correctly (like in current OpenSSL versions), the chance of choosing the same prime as somebody else is extremely low (again, I hope someone else on this list can come up with the numbers for general enlightenment). Well, seeding the PRNG correctly seems not to be a trivial task, see e.g. http://eprint.iacr.org/2012/064.pdf and https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs. Ciao, Richard __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
On Thu, Feb 16, 2012, Jakob Bohm wrote: On 2/16/2012 11:36 AM, Magosányi Árpád wrote: Hi! Is the sentence It checks that p and q are in fact prime, and that n = p*q in RSA_check_key's documentation mean that it checks for weak primes, like the ones mentioned here?: http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars As I understand there are two cases. One is when the prime is not exactly prime. I would expect RSA_check_key to find this out, but what is the extent of the check? The other cause is a clash with already existing prime factors out there. I guess that checking for this would involve looking up a list of prime factors collected on the net. Is there such tool accessible to mere mortals? All the practical ways of creating and checking primes for use in crypto have the following features: 1. They are statistical tests, each round of testing that passes increases the probability that this is really a prime, you stop if it says not a prime (an absolute non-statistical rejection) or until the combined probability is big enough for you. Someone else on this list can hopefully give you the number of rounds and resulting probabilities used by OpenSSL. OpenSSL uses trial division and a slight variation of the Miller Rabin algorithm. See the macro BN_prime_checks_for_size and the associated comments in that header file for references. Provable prime schemes do exist such as the Shawe-Taylor algorithm mentioned in FIPS 186-3 et al but OpenSSL doesn't currently use them. Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
Richard writes: Well, seeding the PRNG correctly seems not to be a trivial task, Which is really sad, because you can buy a hardware RNG for diddly-squat these days, for example http://www.entropykey.co.uk/ John --- John Hascall, j...@iastate.edu Team Lead, NIADS (Network Infrastructure, Authentication Directory Services) IT Services, The Iowa State University of Science and Technology __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: weak key check?
From: John Hascall j...@iastate.edu To: openssl-users@openssl.org, Date: 02/16/2012 09:54 AM Richard writes: Well, seeding the PRNG correctly seems not to be a trivial task, Which is really sad, because you can buy a hardware RNG for diddly-squat these days, for example http://www.entropykey.co.uk/ Many laptops and desktops and some servers now come with a TPM chip, a free source of hardware random numbers.
