4
$\begingroup$

Given that some signature schemes (for instance Elgamal) use an ephemeral key that cannot be reused ever. How do people usually protect against this?

I'll elaborate more: if you reuse the ephemeral key in Elgamal for two different signatures you have (AFAIK) effectively given away your secret key. If the same public/private key pairs are normally used for long periods of time (sometimes years), how can you be sure that you never repeat the ephemeral key?

I know this key should be chosen randomly and given its length the probability of reuse is very tiny. But the risk is so big that I think it's worth taking some countermeasure.

Is there any standard way of dealing with this or am I totally missing something?

$\endgroup$
3
  • $\begingroup$ The risk of your counter measure having a bug that causes trouble is bigger than the change of repeated nonces with a perfect PRNG. Even the risk of random hardware errors is much bigger. $2^{-200}$ is really really small. $\endgroup$ Jan 24, 2014 at 9:26
  • 2
    $\begingroup$ There is one risk worth guarding against though: A failing PRNG. That's why I recommend deterministic nonce generation like EdDSA or RFC6979 - Deterministic Usage of the Digital Signature Algorithm. $\endgroup$ Jan 24, 2014 at 9:28
  • $\begingroup$ RFC6979 looks quite good to use if you don't have access to a good quality entropy source. I would have a look at it in more detail. Thanks for the link :-). $\endgroup$
    – xxxxxxxxx
    Jan 24, 2014 at 12:13

1 Answer 1

3
$\begingroup$

Would you say: the probability of mass life extinction on earth caused by asteroid impact is like $2^{-28}$/year; but the risk is so big that I think it's worth taking some countermeasure?

The applied cryptographer's position is that below a certain probability, like $2^{-40}$ lower than mass life extinction on earth, there's no need to mitigate the risk. It is best to spend effort on countermeasures against a stuck TRNG, by accident or attack.

[Late addition]: One such countermeasure is to replace the TRNG by a PRNG seeded by some combination of the private key and the (hash of) the message. This is used in Ed25519 and increasingly many signature schemes.

$\endgroup$
1
  • $\begingroup$ Also, I think there's one more thing that we are missing: even if you would be able to "capture" enough signatures to make an attack possible, you would still have to store and match them altogether to find signatures with equal ephemeral keys. This seems a tough problem too. Not as hard as others, but computationally difficult as it would imply storing and searching through Tb of data. $\endgroup$
    – xxxxxxxxx
    Jan 27, 2014 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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