2

So with all of the FUDD (fear/uncertainty/doubt/disinformation) going around about RSA in light of Snowden leaks and other discoveries about backdoors into PRNG, I'm uncertain what this means to me...

I'm currently working with many systems that use RSA to digitally sign things … license files, tokens, etc.

Assuming I've followed all best practices set forth for RSA digital signatures, are those now "insecure" if the right (or wrong) people get ahold of them? Because of these "backdoors" to PRNG, can someone effectively "divine" the private key from the data and signature they have and then create their own signed data and fool my system?

(x-post from: https://softwareengineering.stackexchange.com/questions/214625/is-my-rsa-signed-data-secure)

Improve this question
4
  • 1
    If you generated your keys using a broken PRNG you're doomed. But we don't have a concrete reason to suspect properly used RSA signatures with 2048+ bit keys.
    – CodesInChaos
    Oct 16, 2013 at 17:58
  • 1
    Perhaps you used a weak hash function (MD5, SHA-1), in that case an active attacker might have managed to exploit hash collisions. This only applies if you signed attacker influenced data, but there have been practical attacks against CAs using MD5 collisions. It's very well possible that the NSA can do similar attacks with SHA-1 considering its collision weakness.
    – CodesInChaos
    Oct 16, 2013 at 18:00
  • Yikes, I supposed my next question is whether or not the key generation built into .NET RSA provider is "broken" or not...
    – blesh
    Oct 16, 2013 at 18:00
  • 2
    We have no concrete reason to believe it's broken. But since the windows PRNG is closed source, and I'm not aware of any independent review, we can't really be sure. PRNGs are notorious for failing in non obvious ways even without malice.
    – CodesInChaos
    Oct 16, 2013 at 18:02

1 Answer 1

Reset to default
6

All the recent fuss is not at all about RSA. It is about Dual_EC_DRBG, a PRNG which has no relation whatsoever with RSA.

Some wild speculation has been made about other usages of elliptic curves, for other algorithms, which again have no relation with RSA, except that some EC-based algorithm may be used as replacements for RSA.

Now there is a relation not with RSA, the algorithm, but with RSA, the company, which edits a number of cryptography solutions, including one, called BSAFE, which implements both RSA (the algorithm)(actually the algorithmS, since there are RSA signature and RSA encryption, which are not the same kind of thing), and the Dual_EC_DRBG PRNG. Any software which was using BSAFE for random numbers may be at risk, depending on what kind of randomness they needed.

It so happens that "normal" RSA signatures (technically called RSASSA-PKCS1-v1_5, or "PKCS#1 v1.5") are deterministic: they don't use randomness at all. In particular, they cannot be put at risk by flawed randomness.

The newer "PSS" padding scheme for RSA uses random numbers, but not in a way which is critical to security. As PKCS#1 puts it:

RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a "tighter" security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [4] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [12].

(emphasis is mine)

Improve this answer
4
  • "they cannot be put at risk by flawed randomness." .. So the definitive answer is RSA signatures are not at risk from broken PRNG implementations, because RSA signature generation doesn't rely on PRNG?
    – blesh
    Oct 16, 2013 at 18:07
  • 1
    That's a summary, but yes. No PRNG is used on v1.5 RSA signatures.
    – Tom Leek
    Oct 16, 2013 at 18:17
  • 3
    However, I must add that this is for generating signatures. For the private key itself, a PRNG must have been used at some point, to create that key; and there, a flawed PRNG would be a big issue.
    – Tom Leek
    Oct 16, 2013 at 18:18
  • 1
    Sadly, working in .NET, I dug and dug through decompiled source for RSACryptoServiceProvider, and the RNG used for key generation is hidden in native calls I can't find documenation for. Perhaps getting to that is just beyond my skill level at the moment.
    – blesh
    Oct 16, 2013 at 19:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .