genrsa question how secure is the random creation

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

genrsa question how secure is the random creation

redpath
When using this command

openssl genrsa -out test.pem  2048

an RSA pair is created. Its not so much I want to know how a pair is randomly selected
but how secure is that random selection. Random number generators are a series
and this selection could be followed for brute force deciphering.

Reply | Threaded
Open this post in threaded view
|

Re: genrsa question how secure is the random creation

Wim Lewis-3

On 11 Dec 2012, at 3:27 PM, redpath wrote:
> an RSA pair is created. Its not so much I want to know how a pair is randomly selected but how secure is that random selection. Random number generators are a series and this selection could be followed for brute force deciphering.


I think the random number source or sources are configured when OpenSSL is built or in openssl.cnf. On the systems I'm familiar with, IIRC, entropy is obtained from /dev/*random and used to seed a CPRNG.


______________________________________________________________________
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: genrsa question how secure is the random creation

Michael Sierchio
In reply to this post by redpath
On Tue, Dec 11, 2012 at 3:27 PM, redpath <[hidden email]> wrote:
> When using this command
>
> openssl genrsa -out test.pem  2048
>
> an RSA pair is created. Its not so much I want to know how a pair is
> randomly selected
> but how secure is that random selection. Random number generators are a
> series
> and this selection could be followed for brute force deciphering.

> Random number generators are a series

This is not invariably true, and in any case most depend for their
security on the availability of a small amount of entropy for seeding
- /dev/random is suitable, esp. on BSD systems that use a Yarrow-based
mixer.

There are side channel attacks against RSA key generation, but
guessing random numbers isn't one of them.

The real question is how the probable primes are selected.

- Select an interval near the desired size
- Sieve out composites divisible by small primes
- Select two probable primes such that (p - q) is reasonably large
(2^100 or so) to defeat the difference-of-squares method
- Perform enough primality tests to convince yourself they're prime ;-)
- other common criteria aren't really helpful - e.g. strong primes
(they were never necessary for RSA), restrictions on p-1 and q-1
(Elliptic Curve Method factoring makes those obsolete)

I can't answer the question about genrsa, I haven't looked at the code
in a very long time.  But I observe that openssl is maintained by a
lot of smart folks who are always responsive to reported exploits and
vulnerabilities.

Maybe Dr. S.H. will chime in...

- M
______________________________________________________________________
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: genrsa question how secure is the random creation

Jeffrey Walton-3
In reply to this post by redpath
On Tue, Dec 11, 2012 at 6:27 PM, redpath <[hidden email]> wrote:
> When using this command
>
> openssl genrsa -out test.pem  2048
>
> an RSA pair is created. Its not so much I want to know how a pair is
> randomly selected
> but how secure is that random selection.
It depends. In theory, the way entropy is gathered and managed is enough.

In practice, there are practical problems:
"Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network
Devices," https://factorable.net/paper.html

The authors then went on to break secure channels between traffic
reporting systems and cell phones:
"Traffic sensor flaw that could allow driver tracking fixed,"
http://www.csoonline.com/article/723229/traffic-sensor-flaw-that-could-allow-driver-tracking-fixed

> Random number generators are a series
> and this selection could be followed for brute force deciphering.
There are ways other than brute forcing. I would bet Nadia Heninger,
Zakir Durumeric, Eric Wustrow, and Alex Halderman did not brute force
their break of the traffic system.

Linux 3.x kernels have entropy starvation issues due to decisions to
stop using IRQ interrupts (removal of the IRQF_SAMPLE_RANDOM flag,
without an alternative to gather entropy). The 2.x kernels start weak,
but improve over time.

Bottom line: use an Entropy Key (http://www.entropykey.co.uk/), HSM or
other hardware to get your RNG/PRNG in good working order quickly. You
can go to random.org and it will likely be an improvement.

Jeff
______________________________________________________________________
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: genrsa question how secure is the random creation

Salz, Rich
Until someone breaks the website, spoofs it, buys out the owner, etc.

Q2.4: Are the numbers available in a secure fashion?

Yes, since April 2007 you can access the server via https://www.random.org/

I should probably note that while fetching the numbers via secure HTTP would protect them from being observed while in transit, anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys.


--  
Principal Security Engineer
Akamai Technology
Cambridge, MA

:��I"Ϯ��r�m���� (���Z+�K�+����1���x ��h���[�z�(���Z+� ��f�y������f���h��)z{,���
Reply | Threaded
Open this post in threaded view
|

Re: genrsa question how secure is the random creation

David Johnston
In reply to this post by Jeffrey Walton-3
> On Tue, Dec 11, 2012 at 6:27 PM, redpath <[hidden email]> wrote:
>> When using this command
>>
>> openssl genrsa -out test.pem  2048
>>
>> an RSA pair is created. Its not so much I want to know how a pair is
>> randomly selected
>> but how secure is that random selection.
> It depends. In theory, the way entropy is gathered and managed is enough.
>

Current versions of openssl take advantage of RdRand when present in the
CPU. So on intel gen3 and beyond (Ivy Bridge i5, i7 and every later chip)
openssl will have and use a robust source of entropy on chip.

______________________________________________________________________
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: genrsa question how secure is the random creation

Jeffrey Walton-3
In reply to this post by Salz, Rich
On Wed, Dec 12, 2012 at 12:39 PM, Salz, Rich <[hidden email]> wrote:
> Until someone breaks the website, spoofs it, buys out the owner, etc.
>
> Q2.4: Are the numbers available in a secure fashion?
>
> Yes, since April 2007 you can access the server via https://www.random.org/
>
> I should probably note that while fetching the numbers via secure HTTP would protect them from being observed while in transit, anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys.
>
Yeah, we need a fingerpaint program for all those mobile devices
(seriously!). Upon first boot (or after reset), the user has to finger
paint something to get the RNG/PRNG some entropy.
(http://groups.google.com/group/android-security-discuss/browse_thread/thread/71c6ab0081c70e9c)

Also relevant: "When Good Randomness Goes Bad: Virtual Machine Reset
Vulnerabilities and Hedging Deployed Cryptography,"
www.isoc.org/isoc/conferences/ndss/10/pdf/15.pdf. Hedging extracts
entropy from the peer during key exchange and uses the extracted
entropy to improve the localhost's state.

Jeff
______________________________________________________________________
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: genrsa question how secure is the random creation

Michael Sierchio
In reply to this post by Michael Sierchio
On Tue, Dec 11, 2012 at 8:06 PM, Michael Sierchio <[hidden email]> wrote:

> - Select an interval near the desired size

[ 2^1023 + 1^1022 + 1 , 2^1024 - 1 ]

> - Sieve out composites divisible by small primes
> - Select two probable primes such that (p - q) is reasonably large
> (2^100 or so) to defeat the difference-of-squares method

Before testing for primality, make sure that p mod e != 1, where e is
the public exponent

> - Perform enough primality tests to convince yourself they're prime ;-)
> - other common criteria aren't really helpful - e.g. strong primes
> (they were never necessary for RSA), restrictions on p-1 and q-1
> (Elliptic Curve Method factoring makes those obsolete)
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]