Does RNG play a role in PGP signing?

Question

We have a Jenkins system that builds and PGP-signs software releases, and we are considering moving the signing component to an isolated VM instead of running it as part of the overall builder infrastructure -- in order to better isolate the private keys from all the other relatively public moving parts.

A few developers are arguing against using a VM, since VMs usually have few sources of good entropy and therefore are not generally well-suited for cryptography. I want to put forth a counter-argument that since we'll be using PGP keys generated elsewhere, the only crypto operations that will be done on that VM will not be relying on RNG at all. My understanding of PGP signing process is that it calculates a sha1/sha2 hash (no RNG used) and then calculates the signature using the private key (no RNG used).

Is that correct? Or am I missing something that would make strong RNG a requirement for a system that only PGP-signs but never PGP-encrypts?

Answer 1

Signing with RSA in OpenPGP is deterministic and thus does not require a source for randomness as you described correctly. Hashing the data to be signed is deterministic as long not padded with a random seed (see @Karol Babioch's answer for details why one might want to do so), signing the hash also is.

Detailed discussion of the parts involved:

• RSA signing does not involve any random input

• OpenPGP defines use of EMSA-PKCS1-v1_5:

  This encoding method is deterministic and only has an encoding operation.

• Finally, OpenPGP signature packets (and also one-pass signature packets) do not involve any non-deterministic input (apart from the system time, but for the same (faked) time, you will receive the same output)

You can try yourself by using faketime to set the time to some fixed time (don't use a date prior to the creation time of your key):

$ faketime '@2147483647' gpg --sign --output - somefile  | gpg --print-md SHA256
93C7E062 151311F2 822FBBBF FC4B061A C8F31A1A 54FDA558 61A9C964 B5107CD4

Without faking the time, you will receive different hash values as the timestamp changes.

For other algorithms, refer to @Karol Babioch's answer. Conclusion of this debate would be: Use RSA for signing in virtual machines or other low-entropy devices (some embedded boxes, routers, ...), as it does not depend on randomness; but better import the key pair from somewhere else.

---

On the other hand, encryption requires random numbers also with RSA: public/private encryption is only used to encrypt the block cipher key, and some padding might be applied.

Obviously creating a new OpenPGP key pair also requires randomness.

Answer 2

Unfortunately the previous answers given to this question, are not only wrong, but also quite dangerous.

While it is certainly true that digital signatures usually involve hash functions, which by its nature are inherently deterministic, you should note that digital signatures are more than just a simple hash. They involve public key cryptography, which is used in a way that guarantees only the legitimate owner of a private key is able to sign something. There are quite a few digital signature algorithms, with the following being used widely in practice:

• RSA
• DSA and its elliptic curve equivalent ECDSA
• ElGamal

At least DSA, ECDSA and ElGamal do absolutely require random numbers by design. Reusing a random number, can lead to the recovery of the private key. This is trivially easy and can be understood by anyone interested in the topic with only a few very basic equations.

There have been all sorts of attacks in the past exploting this very fact. Probably the most prevalent example is the hack of the PlayStation 3, which brought us the following xkcd comic:

With RSA on the other hand it is not that easy. "Schoolbook" RSA does not require random numbers. However it is possible for an attacker to perform existential forgery attacks on simple RSA implementations. Therefore in practice modified schemes are used, which might operate in a probabilistic way. The basic idea is that valid signatures have to satisfy a certain form. One such standard is called Probabilistic Signature Protocol (PSS).

GPG has all of the above schemes implemented. By now RSA seems to be the default on most systems. RFC 4880 states that OpenPGP makes use of EMSA-PKCS1-v1_5, which is a deterministic padding scheme and does indeed not require random numbers.

So, in essence: Yes, digital signatures do require random numbers and it might be a bad idea to use virtual machines for such tasks. At least it is something to consciously think about.