weak key check?

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

weak key check?

"Magosányi, Árpád"
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?

Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Jakob Bohm-7
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Richard Könning
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Dr. Stephen Henson
In reply to this post by Jakob Bohm-7
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

John Hascall
In reply to this post by Richard Könning



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, [hidden email]
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Ken Goldman-2
> From: John Hascall <[hidden email]>
> To: [hidden email],
> 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.
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Wim Lewis-3

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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

aberglas
In reply to this post by Richard Könning
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 <[hidden email]>
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 List                    [hidden email]
Automated List Manager                           [hidden email]



--

Dr Anthony Berglas, [hidden email]       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.


Reply | Threaded
Open this post in threaded view
|

RE: weak key check?

Edward Ned Harvey (openssl)
> From: [hidden email] [mailto:owner-openssl-
> [hidden email]] 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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Dr. Stephen Henson
On Sat, Feb 18, 2012, Edward Ned Harvey wrote:

> > From: [hidden email] [mailto:owner-openssl-
> > [hidden email]] 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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

aberglas
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 <[hidden email]> wrote:
On Sat, Feb 18, 2012, Edward Ned Harvey wrote:

> > From: [hidden email] [mailto:[hidden email]
> > [hidden email]] 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 List                    [hidden email]
Automated List Manager                           [hidden email]



--

Dr Anthony Berglas, [hidden email]       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.


Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Dr. Stephen Henson
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Jakob Bohm-7
In reply to this post by Wim Lewis-3
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Wim Lewis-3
In reply to this post by aberglas

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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Wim Lewis-3
In reply to this post by Jakob Bohm-7
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

aberglas
In reply to this post by Wim Lewis-3
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 <[hidden email]> 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 List                    [hidden email]
Automated List Manager                           [hidden email]



--

Dr Anthony Berglas, [hidden email]       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.


Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Chris Dodd-2
In reply to this post by aberglas
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
[hidden email]

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Ben Laurie-2
On Tue, Feb 21, 2012 at 5:47 PM, Chris Dodd <[hidden email]> 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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: weak key check?

Ben Laurie-2
On Tue, Feb 21, 2012 at 7:04 PM, Ben Laurie <[hidden email]> wrote:

> On Tue, Feb 21, 2012 at 5:47 PM, Chris Dodd <[hidden email]> 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 List                    [hidden email]
Automated List Manager                           [hidden email]