RNG bug in GnuPG/Libgcrypt

[Werner Koch]

On Fri, 19 Aug 2016 01:44, calestyo at scientia.net said:

> Is more information respectively an in-depth-analysis already available
> on how this issue might have impacted security of all types of
> keys/etc. pp.?

I tried to analyze the impact in key generation and I am pretty sure
that RSA keys generated with GnuPG < 2.1 are not affected.  The reasons
are:

For GnuPG < 2.1 the state of the pool is not preserved over gpg
invocations.  A single gpg process creates at max two keys.  The default
is to create two 2048 bit RSA keys.  A single 2048 bit RSA key requires
256 byte of random.  I instrumented the RNG code of Libgcrypt 1.7.3 and
with this

  if (getenv ("DBG_GCRYPT"))
    log_info ("#RNG(%lu) stats: bytes: %lu (%lu + %lu) (%lu + %lu) #\n",
              (unsigned long)getpid (),
              rndstats.getbytes1 + rndstats.getbytes2,
              rndstats.getbytes1, rndstats.getbytes2,
              rndstats.ngetbytes1, rndstats.ngetbytes2);

and started

1) a default key generation with GnuPG 2.0.30-beta to create two
   2048 bit RSA keys:

    #RNG(14052) stats: bytes: 8 (8 + 0) (1 + 0) #

  8 bytes read from the pool for the salting the passphrase.

    #RNG(14052) stats: bytes: 136 (8 + 128) (1 + 1) #

  128 bytes extracted to find the first RSA prime for the primary key

    #RNG(14052) stats: bytes: 144 (16 + 128) (2 + 1) #

  8 bytes read from the pool to seed Libgcrypt's nonce generator.

    #RNG(14052) stats: bytes: 272 (16 + 256) (2 + 2) #

  128 bytes extracted to find the second RSA prime for the primary key

    gpg: writing self signature

    #RNG(14052) stats: bytes: 400 (16 + 384) (2 + 3) #

  128 bytes extracted to find the first RSA prime for the subkey

    #RNG(14052) stats: bytes: 528 (16 + 512) (2 + 4) #

  128 bytes extracted to find the second RSA prime for the subkey

  Thus we extracted 528 bytes in total; we didn't even extract the
  dangerous bytes 580..599.


2) Now let's create two 4096 bit keys:

    #RNG(14384) stats: bytes: 8 (8 + 0) (1 + 0) #

  8 bytes read from the pool for the salting the passphrase.

    #RNG(14384) stats: bytes: 264 (8 + 256) (1 + 1) #

  256 bytes extracted to find the first RSA prime for the primary key

    #RNG(14384) stats: bytes: 272 (16 + 256) (2 + 1) #

  8 bytes read from the pool to seed Libgcrypt's nonce generator.

    #RNG(14384) stats: bytes: 528 (16 + 512) (2 + 2) #

  256 bytes extracted to find the second RSA prime for the primary key

    #RNG(14384) stats: bytes: 784 (16 + 768) (2 + 3) #

  256 bytes extracted to find the first RSA prime for the subkey.  Now
  this is interesting.  This prime has been taken from bytes 528..599
  and 0..183 including the dangerous range from 580 to 599.  However, we
  are pretty safe because almost the entire range is part of the secret
  prime:

  To predict bytes 580..599 an attacker needs to know the bytes in the
  range 0..44 and 560..579.  From these bytes 0..7 are available as the
  salt used to protect the _secret key_; thus only 64 of 2048 bit.  Even
  if that would help to guess the prime, an attacker arriving at that
  point could more easily guess the passphrase.

    #RNG(14384) stats: bytes: 1040 (16 + 1024) (2 + 4) #

  256 bytes extracted to find the second RSA prime for the subkey.
  These random bytes are taken from bytes 184..439.  Thus entirely safe.

More analysis is required for other key types, but we can see that generated
RSA keys are not really affected.

For GnuPG 2.1 things are different because there is a long running
process (gpg-agent) which creates all keys.  The case for RSA keys is
similar for above and large keys should never be in danger. 

This is a pretty short answer but I hope it clarifies the common use
cases.  Again, please to not revoke your keys before we have hard facts
that there might be a real problem for DSA, Elgamal or ECC keys.



Salam-Shalom,

   Werner


--
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
 /* Join us at OpenPGP.conf  <https://openpgp-conf.org> */
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 162 bytes
Desc: not available
URL: </pipermail/attachments/20160819/e3e9a80e/attachment-0001.sig>