Score:3

Can I get away with generating 512-bit k (and d) for ECDSA based on P-521?

vu flag

I've been implementing a hobbyist cryptography library, and I'm at the part where elliptic-curve cryptography is being implemented. I've already implemented and tested ECDSA with P-256 and P-384, where static and ephemeral private keys are 256-bit and 384-bit each, so far so good.

What's bothering me is P-521. I'm planning to generate 512-bit static ($d$) and ephemeral keys ($k$) to ease implementation, since most hash functions (excluding XOFs) have at most 512-bit output (I'm not using hash functions to generate the keys directly, I'm just allocating stack space according to the output length of typical hash functions).

If I do this, the resulting signature component $s$ may have some kind of bias, but since the product of $d \cdot k^{-1}$ will overflow $n$, I'm having the pseudo-belief that this is not too serious a problem.

So I ask 2 related question:

Q1: can I get away with generating 512-bit static and ephemeral keys for ECDSA over P-521 and not harm security?

Q2: for general case, given a prime modulus $n$, an adversary is given $s = k \cdot r + d \pmod n$ and $r$, where $d$ is static and $r$ is deterministically randomly computed from $k$; both $k$ and $d$ have less than $\lceil {\log_2{n} \over 4} \rceil$ of top bits chopped off; can the adversary obtain any part of $d$ or $k$?

kelalaka avatar
in flag
Why don't you choose uniform random bits? Are you planning to create the secret key $d$ from the user's password? Isn't $s = k^{-1} (z + rd)$ Are you planning to implement deterministic ECDSA?
DannyNiu avatar
vu flag
@kelalaka You missed my point. I'm planning to generate only 512-bit entropy on the P-521 curve, but I'm not sure if this is secure.
kelalaka avatar
in flag
I'm aware of it. I'm just asking why do you want to this?
DannyNiu avatar
vu flag
@kelalaka, to ease implementation, as I said in the question. 521-bit key require additional masking after generating 65 random bytes, so I'd like to skip that. This also saves a bit of stack space and is better for datum alignment.
DannyNiu avatar
vu flag
@kelalaka I used a different formula in Q2 because it's easier to analyze and its result can be applied to other DSS formula more easily, or at least I thought so.
kelalaka avatar
in flag
Don't you know already about [How does the "biased-k attack" on (EC)DSA work?](https://crypto.stackexchange.com/q/44644/18298)
DannyNiu avatar
vu flag
Well, I'm not too good with crypto maths, and I thought this would be a different kind of bias.
kelalaka avatar
in flag
Here the video https://www.youtube.com/watch?v=6ssTlSSIJQE
Score:6
ru flag

Don't do this!

Biases in ECDSA nonces across multiple signatures will leak the signing key over time. See for example the paper Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies by Breiner and Heninger.

The general Q2 is known as the hidden number problem and it is indeed this problem that is solved in the paper when multiple $r$ and $s$ are provided.

Score:4
cn flag

No! Even generating a 520-bit $k$ is likely an exploitable vulnerability.

A 2020 result on the topic is LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage. §5 discusses the cost estimate for the attack: it's not really feasible for a single-bit bias beyond P256, but larger biases allow cheaper attacks, and attacks only get better with time.

Use deterministic ECDSA unless you have a good reason to use randomized ECDSA. Deterministic ECDSA can use HMAC_DRBG as a black box: you just have to instantiate HMAC_DRBG with the requisite parameters. An advantage of this being a deterministic algorithm is that if your known-answer tests give the expected results, you have a fairly high amount of confidence that you've implemented it correctly. Most systems that do signatures have a RNG anyway, and HMAC_DRBG is a pretty good DRBG (not the fastest, but relatively easy to implement and FIPS-compliant).

If you use randomized ECDSA, I recommend implementing it by doing deterministic ECDSA and feeding extra randomness into HMAC_DRBG. This way, if you do the randomness part wrong, it will at worst degrade to deterministic ECDSA, without any risk of leaking the nonce. There are two reasons why you might prefer randomized ECDSA: if it's a security objective that an adversary can't tell whether two signatures produced separately happen to be for the same message (an uncommon security objective), or because it can make some side channels or fault injection weaknesses harder to exploit (on the flip side, it can also make some weaknesses easier to exploit).

DannyNiu avatar
vu flag
Thanks. My project has a modular set of hash, prng, and ecc curves implementation, and each component can easily be reused. I'm keen on ensuring I don't make security mistake when adding p521 to the existing p256 and p384.
kelalaka avatar
in flag
I would like to note that LadderLeak uses side-channel to improve 2-bit biases to $<1$.
mangohost

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.