3
$\begingroup$

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$?

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Feb 23, 2022 at 9:11
  • $\begingroup$ @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. $\endgroup$
    – DannyNiu
    Feb 23, 2022 at 9:13
  • $\begingroup$ I'm aware of it. I'm just asking why do you want to this? $\endgroup$
    – kelalaka
    Feb 23, 2022 at 9:17
  • $\begingroup$ @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. $\endgroup$
    – DannyNiu
    Feb 23, 2022 at 9:20
  • $\begingroup$ @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. $\endgroup$
    – DannyNiu
    Feb 23, 2022 at 9:22

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – DannyNiu
    Feb 23, 2022 at 13:16
  • $\begingroup$ I would like to note that LadderLeak uses side-channel to improve 2-bit biases to $<1$. $\endgroup$
    – kelalaka
    Feb 23, 2022 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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