How should one handle the identity value and other "obviously" weak secret random values?

Question

In RSA, ECDSA, ElGamal and quite a few other schemes, using a secret (random) value equal to 1 might not provide any form of security, while still being mathematically sound.

For RSA, ECDSA or ElGamal, the secret random value might typically be the secret exponent, for example. Or for ElGamal and ECDSA, it might be the ephemeral secret we need to encrypt or sign (the infamous $k$ for ECDSA).

Arguably this holds for secret values smaller than 80 bits, as it might otherwise well be attacked using a brute force search attack.

The same might hold for secret values whose secrecy is crucial to the security of the scheme at hand, such as the ephemeral $k$ used in ECDSA signatures, although specific scheme might have specific guidelines depending on their specific requirements.

In order to avoid such obvious problems, are there any kind of (official or standard) recommendations regarding the rejection of "bad" random values based on certain criteria?

Or more broadly, in the same way that we have recommendations for the group size or the way to generate large primes (see keylength.com), do we have some kind of guidelines for the generation of the "secret random values" we have in cryptographic software. (For instance, I do not see any kind of "sanity checks" being performed on the $k$ values generated for ECDSA as per FIPS 186-4, even though it is crucial for $k$ values to be unbiased. The only "standard" that I'm aware of that specify how the secret random value should be generated, and it only covers the specific case of the generation $k$, is the RFC6979 and is using derandomization, like the standard for EdDSA (RFC8032). But this is not always possible for secret values.)

Is this documented in some other NIST document, or in some RFC?

PS: notice this question is assuming randomness is difficult for implementation, and that as such it might be best to have "fail-safes" in place in a way to have defense in depth.

Answer 1

In RSA, ECDSA, ElGamal and quite a few other schemes, using a secret (random) value equal to 1 might not provide any form of security, while still being mathematically sound.

One could argue that the exponent '1' doesn't have any security (because it's easy to compute the discrete log of $1G$); on the other hand, you could equally argue that the value $z = 8827773752...7876547109$ equally does not provide any security, because an attacker could easily compute $zG$ and if he sees that, he knows the discrete log.

Arguably this holds for secret values smaller than 80 bits, as it might otherwise well be attacked using a brute force search attack.

This is true, if the attacker knows apriori that the secret value was smaller than 80 bits. Actually, if the attacker knows that, he can find the discrete log with $O(2^{40})$ effort, which is doable by private individuals with access to somewhat more than average computational resources.

On the other hand, taking a random $kG$ value, and making that guess will succeed (assuming a 256 bit curve) with probability circa $2^{-176}$. In addition, this doesn't only apply only to secrets smaller than 80 bits; if the attacker guesses that the top 176 bits are the value $z$ (above), then he can compute $kG - (z2^{80})G$; if his guess is correct, that'll be in the range $0G$ to $2^{80}G$, and so the brute force effort will succeed (and with the same success probability).

Hence, it is hard to say that a point that happens to be in the range $1G … 2^{80}G$ is any weaker than a point that happens to be in the range $(z2^{80}+1)G … (z2^{80}+2^{80})G$ (and all points are in such a range, for some value of $z$).

do we have some kind of guidelines for the generation of the "secret random values" we have in cryptographic software.

Why, yes, yes we do. You pointed out the sections in FIPS 186-4 where they make recommendations (mandates, actually, we're talking about FIPS here) on how to generate such random values.

even though it is crucial for $k$ values to be unbiased.

And these recommendations accomplish precisely that. They do assume that the approved RBG that is used generates indistinguishable-from-random bit patterns; as far as we know, the approved ones do precisely this.

You appear to be asking for some tests that reject certain values (such as 1); such a test would introduce a bias (if possibly a tiny one); such a bias is precisely what we're trying to avoid...