How to check security strength of random k if k is an input parameter of ECDSA signature generation function using openssl-fips

pe flag

As I understand,

1.The security strength is specified in bits according to

2.Security strength is depend on the length of entropy input when generating random number

So, in the signature generation function, if the random k is an input parameter (not generate random k in this function)

How to check valid k? security strength of random k?

1, Only check number of bits of random k ?

2, Other testing ?


ng flag

In the standard definition of ECDSA, the nonce $k$ should be a secret uniformly random integer in range $[1,n)$, where $n$ is the prime order of the generator. Analysis of message/signature pairs when $k$ is known, or has a defect (such as a bias, or a tendency to repeat) can leak the private key, thus generation of $k$ matters to security.

It is not possible for an implementation of ECDSA signature generation to meaningfully check that the value of an input $k$ it receives is suitable for safe use as prescribed in the standard definition of ECDSA signature, because there is not way to tell from a value if it is secret or not, which is a most essential quality $k$ should possess. It's also impossible to assess if a given $k$ is random as the question suggests, at least unless we know how it was produced. And anyway, in the context, being random is secondary to being secret.

Therefore, rather than accepting $k$ as an input, common procedure is to make the generation of a random $k$ part of the implementation of ECDSA signature generation. A basic (if not necessarily recommendable) procedure is to draw $\lceil\log_2(n)\rceil$ bits from an assumed cryptographically strong RNG (such as /dev/urandom) and interpret these bits as an integer $k$ per e.g. big-endian convention, until it holds $0<k<n$ (which for many $n$ used in practice is essentially always, because $n$ is just below a power of two). I disregard this basic procedure in the rest of the answer (even though this comment suggests that was the meat of the question).

It is possible to modify the ECDSA signature generation procedure to safely use whatever $k$ it receives. Instead of $k$, the signature generation can use $k':=f(d_U,H,k)$ where $d_U$ is the private key, $H$ is the hash of the message to sign, and $f$ is a public key derivation function using $d_U$ as master key, with output close to uniform in $[1,n)$ where $n$ is the order of the generator. Such practice does not break compatibility in any way, and is only detectable with both $k$ and the private key (on top of other public information). For $n$ up to 384-bit at least, a suitable function would be $$k':=1+(\operatorname{HMAC-SHA-512}(d_U,H\mathbin\|k)\bmod(n-1))$$

Note: in theory, the signing procedure has a number of "return to Step 1" which will re-invoke $f$ and expect a different $k'$, and won't get that. However that's moot, since the likelihood of re-invocation of $f$ is entirely negligible, and not testable even with control of $d_U$, $H$ and $k$, for proper fixed non-malignant $f$. If that possibility nevertheless prevents a rubber stamp from hitting the paper, we could use $k'=f(d_U,H\oplus j,k)$ where $j$ is the number of previous invocations of $f$ in the signature.

Note: when and if there is no drawback in making the signature deterministic, we can ignore the input $k$. When considering some (but far from all) side-channel attacks that may even be safer, in particular against attacks by adversaries that know and control $k$.

Andy avatar
pe flag
First of all, thanks a lot for your explanation ! So, If k is from TRNG (, Knowing how it was produced. Is my 1st solution still possible? which is only check number of bits of k. Assume that, k (from TRNG) are secret and random
fgrieu avatar
ng flag
@Andy: I have expanded on the basic (if not recommendable) way to generate $k$ in ECDSA, see third paragraph of the answer. Note that if you use an existing implementation of ECDSA signature, likely it generates $k$ (and if it cares about security it might use a technique similar to the one I describe in the fourth paragraph). Beware that there are many difficulties in making a secure implementation of ECDSA signature generation (side channels, fault attacks..), and common wisdom is that it should be left to experienced security programmers.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.