5

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?

4

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:

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.

  • 2
    Sorry, but this is simply not true. There are a lot of signing algorithms that absolutely do require random numbers to be generated, e.g. DSA and its elliptic curve equivalent ECDSA. Reusing the same random number more than once in these schemes might enable the attacker to recover the private key. This is what the famous PlayStation 3 hack was all about. So your statement is wrong and dangerous! – Karol Babioch Mar 24 '14 at 23:50
  • I should have limited the answer to RSA, which currently is most commonly used and recommended. I updated the answer to restrict to RSA in OpenPGP, where it is valid. Thank you for pointing out the issue with DSA. – Jens Erat Mar 25 '14 at 13:30
  • 1
    I think your edited version is really good now and much more valuable than it was before. – Karol Babioch Mar 25 '14 at 15:10
6

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:

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:

https://xkcd.com/221/

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.

  • Traditional implementations of (EC)DSA need randomness. But it's possible to implement them in a deterministic way or in a way that's randomized but doesn't fail even when the RNG sucks. OpenSSL recently switched to a failsafe randomized implementation. I don't know if GPG contains a risky/low quality implementation of DSA. – CodesInChaos Mar 25 '14 at 11:33
  • I have not been able to reproduce different signatures with GnuPG and a RSA key when using a fixed (faked) system time (the signature package includes a timestamp). All that seems different is this time. I also cannot find any hint on GnuPG implementing PSS, nor anything in RFC 4880. Could you elaborate this a little bit further? – Jens Erat Mar 25 '14 at 11:46
  • @JensErat: You are of course right. I was fooled by different system times. Shame on me. RFC 4880 states that OpenPGP uses a padding scheme called EMSA-PKCS1-v1_5, which is deterministic. I've edited my answer accordingly, so thanks for your input. – Karol Babioch Mar 25 '14 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.