RNG bug in GnuPG/Libgcrypt

[Werner Koch]

On Sat, 20 Aug 2016 03:20, calestyo at scientia.net said:

> I guess people should be also confirmed whether the main use cases
> (signing/encrypting) could be anyhow affected, and also whether 3rd

Let's see by encrypting to 4 keys (1 4k and 3 2k RSA keys)

  #RNG(11973) stats: bytes: 32 (32 + 0) (1 + 0) #

  The session key.

  #RNG(11973) stats: bytes: 506 (506 + 0) (2 + 0) #

  474 bytes for the RSA padding of a 4096 bit key.

  #RNG(11973) stats: bytes: 514 (514 + 0) (3 + 0) #
 
  5 extra bytes to replace the zero bytes in the padding.

  gpg: RSA/AES256 encrypted for: "3C1CFCC2 test 4096"
  #RNG(11973) stats: bytes: 732 (732 + 0) (4 + 0) #

  218 bytes for the RSA padding of a 2048 bit key.

  gpg: RSA/AES256 encrypted for: "0C8AAAF8 zzzzzzzzzzzzzzzzzzzzzzzzzzz"
  #RNG(11973) stats: bytes: 950 (950 + 0) (5 + 0) #
  #RNG(11973) stats: bytes: 954 (954 + 0) (6 + 0) #

  218 + 4 bytes for the RSA padding of a 2048 bit key.

  gpg: RSA/AES256 encrypted for: "0E443FF2 yyyyyyyyyyyyyyyyyyyyyyyyyyy"
  #RNG(11973) stats: bytes: 1172 (1172 + 0) (7 + 0) #

  218 bytes for the RSA padding of a 2048 bit key.

  gpg: RSA/AES256 encrypted for: "D44EF6F6 xxxxxxxxxxxxxxxxxxxxxxxxxxx"
  #RNG(11973) stats: bytes: 1188 (1188 + 0) (8 + 0) #

  16 bytes for the IV.

Now, if two recipients work together they can predict 20 bytes of the
padding used for another key.  I doubt that 20 known bytes out of 218 of
the padding puts the message in danger - in particilar not because they
all received the same message.

More important is the case where we sign and an encrypt a message.
Let's do that by sending a 2048 bit key signed message to a 4096 bit
key:

  #RNG(12472) stats: bytes: 32 (32 + 0) (1 + 0) #
 
  The session key.

  #RNG(12472) stats: bytes: 506 (506 + 0) (2 + 0) #

  474 bytes for the padding.

  gpg: RSA/AES256 encrypted for: "3C1CFCC2 test 4096"
  #RNG(12472) stats: bytes: 514 (514 + 0) (3 + 0) #

  8 bytes to initialize the nonce generator used for RSA blinding.

  gpg: RSA/SHA256 signature from: "72E20749 zzzzzzzzzzzzzzzzzzzzzzzzzzz"
  #RNG(12472) stats: bytes: 530 (530 + 0) (4 + 0) #

  16 bytes for the IV.

We do not access bytes 580..599.  Even if we would do no sensitive data
is leaked: As described above the padding is not relevant.  The RSA
blinding does not require stroing random and that random number is not
leaked anyway.  The IV does not matter because it is the same for all
recipients.

> party programs using libgcrypt need to do their own analysis on whether
> their stuff could be affected or not.

Yes.  For example if an application sends a random challenge of 20 bytes
using the real RNG and not the nonce generator to 30 recipients,
recipient 1,3, and 29 are able to reconstruct the challenge sent to 30.
This needs to be done in one process.


Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.
 /* Join us at OpenPGP.conf  <https://openpgp-conf.org> */