ECDSA Weak signing

[Yves Cuicui]

When a signature is generated, there are a number of things to check, for example, the parameter k must be between 1 and N-1, the r and s signature must not be null etc ...

There is another condition (I have never seen), even if the probability is extremely low: k must not be equal to the private key d.

If k is equal to d, the private key can be calculated by d = z(s-r)^-1 (z is the reduced message hash)!

This case is very easy to detect. Indeed, if k == d, r is the x coordinate of the public key!

Although this case is very unlikely, it costs nothing to add this test in the module signature;

Here is an example:
Public key
 Q: "0x02f24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835" (compressed)
Message Hash
 z: "0x8d29467f53b7a412dc54de9a8eeb8960821d191568f5e22f64806326a5e11f20"
Signature
 r: "0xf24fb983ba6825277b09fabbf60afe833ebf03f0bb808cab04ccbfb81593d835"
  s: "0x24f080f53a8384be1e3263aeabc48df6569286f29a7141baf43d8723988eb558"

You can effectively see that r==Q_x. This indicates that k==d!
It is then easy to get the private key "0x26439421bbfcf3c81d8ab8cda150d6e2e280d1656e70d8e49e18acf5ae0f11df" and compute Q from it to be convinced that this is the correct value.

[kjj]

I fully support adding checks to the signing code to detect degenerate conditions, but finding k=d doesn't mean you got really lucky, it means your RNG is completely and totally broken and you need to alert the user.

[iddo]

Huh? You're describing how to carry out one particular attack that succeeds with probability 2^{-n} where n=order(G), but that's always the case, i.e. you can always carry out an attack that succeeds with probability 2^{-n} simply by guessing d (or k).
The checks that you mentioned in your first sentence are done to avoid invalid values and to have uniform probability over the range of valid values, k==d is valid and therefore it shouldn't be excluded as a potential value.

[gmaxwell]

it costs nothing to add this test in the module signature;

Sure it does. For example, with OpenSSL it would force you to add your own K generation conversion to R and Rinv. In that code you get a free chance to make many mistakes or insert many backdoors.

Assuming your RNG isn't broken you're describing something that will happen at a rate in once in the number of points on the curve... which is true for all K values. You might as well just deny K=11, since if they used 11 (or any other specific value) and you know it you could recover the private key too.

[Edit: Ah, I see iddo pointed this out too]

[piotr_n]

I think bitcoin wallets should abandon using RNG to generate the k values.
Just use hash of a data that you are signing, or wherever other unique value tied to the data that is being signed.
You can though feed your k with some additional RND data (just in case), but in general the signing process should assume that RNG is not safe - that's the safest approach.

You still have the problem of generating the private keys, but not when you use a brain wallet (a password-seed).

So IMHO bitcoin wallets can (and should) be implemented in a way that makes them 100% resistant against any RNG attacks.
Because RNG attacks are mostly very hard to detect.

[Yves Cuicui]

You're describing how to carry out one particular attack that succeeds with probability 2^{-n}

I know this will succeed with a {very low}^N probability, but this is of the same order as checking r<>0 or s<>0 (for example, r=0 only for the two points with x=N).

For example, with OpenSSL it would force you to add your own K generation conversion to R and Rinv

I am not aware of the OpenSSL modules. I imagine this test could be integrated in it.

You might as well just deny K=11, since if they used 11 (or any other specific value) and you know it you could recover the private key too.

Are you kidding me? Using k=d is made obvious by the fact that r=Qx. Using 11 or whatever cannot be guessed.

The subject is not that RNG are broken or bugged or ... I just want to draw attention to a situation on which nobody thinks

[gmaxwell]

You might as well just deny K=11, since if they used 11 (or any other specific value) and you know it you could recover the private key too.

Are you kidding me? Using k=d is made obvious by the fact that r=Qx. Using 11 or whatever cannot be guessed.

The subject is not that RNG are broken or bugged or ... I just want to draw attention to a situation on which nobody thinks

No, I am not kidding you.  If k==11 then r==11*g, which is even _more_ obvious than r==Q (it's a static comparison instead of a variable one!). Or, if you're into dynamic comparisons... what if k were one of your other private keys?

The distinction with the comparison with zero is that 0 is not a valid point on the curve, so no correct signature can ever have that value. Vs k happening to take on the value of one of your private keys which is just as likely as any other point. If you go around disallowing a bunch of K values then you're decreasing security not increasing it... Though I would agree that this specific test is perhaps mildly useful as a "RNG fatally broken, do not pass go" check.

[piotr_n]

If k is equal to d, the private key can be calculated by d = z(s-r)^-1 (z is the reduced message hash)!

The subject is not that RNG are broken or bugged or ... I just want to draw attention to a situation on which nobody thinks

That is all true what you say, but generating a really random random k that would be equal to d... hmm, good luck with it!
And even if you do it, the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)^-1
Such a computation does not seem to by much more resource friendly then a regular private to public key conversion.
So if you want to test each k value whether it might be (by a chance) the d, you might as well start testing k-1, k+1, k-2, k+2, k-3, k+3, and so on... because each of these values, a potential attacker can try to test as the private key.
And then, if you get paranoid enough, you will essentially end up with a solution in which any k value is not safe

[Yves Cuicui]

the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)^-1

No just to see if r equals the x coordinate of the public key.

[piotr_n]

the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)^-1

No just to see if r equals the x coordinate of the public key.

Oh, OK - that's much easier then.
Still unlikely to happen, thought equally likely as picking up zero...

So you might have some point here, because EC-Verify functions from the crypto libs I've seen, they all check the k for zero, but not for d...

[fpgaminer]

Sure it does. For example, with OpenSSL it would force you to add your own K generation conversion to R and Rinv. In that code you get a free chance to make many mistakes or insert many backdoors.

No need, just check the r value OpenSSL returns.

Until BIP 0032.5 is formalized and we feel more comfortable about it, this isn't a bad check to have in my opinion.  Combined with continuous random number generator tests (you should have those anyway, to protect private key generation).

[iddo]

If you go around disallowing a bunch of K values then you're decreasing security not increasing it... Though I would agree that this specific test is perhaps mildly useful as a "RNG fatally broken, do not pass go" check.

I don't see why K==d is more indicative of a faulty RNG than the infamous K==11 ? Are you seriously suggesting that we should test here whether we're dealing with RNG that always returns the same value, or is there something else that I'm missing?

[kjj]

If you go around disallowing a bunch of K values then you're decreasing security not increasing it... Though I would agree that this specific test is perhaps mildly useful as a "RNG fatally broken, do not pass go" check.

I don't see why K==d is more indicative of a faulty RNG than the infamous K==11 ? Are you seriously suggesting that we should test here whether we're dealing with RNG that always returns the same value, or is there something else that I'm missing?

Actually, I suggested it.

If you test for a single value of k, that test will never ever trip because the odds of drawing that one k is zero (approximately).  It doesn't matter if the value under test is D or a constant.  The exception is when your RNG is broken, perhaps XCKD-style.

[gmaxwell]

Are you seriously suggesting that we should test here whether we're dealing with RNG that always returns the same value, or is there something else that I'm missing?

No, I think this thread is foolish. But RNG's the break and return constant values do happen so I can't honestly say that its completely worthless.  I was trying to make clear that any (however small) value added here is because it detects a faulty rng, not because picking the same value as your private key is actually a threat.

[Yves Cuicui]

Once again this thread has nothing to do with RNG.
It is just a special case, very easy to detect, more or less as probable (or improbable) as other tests that are performed in the signing process.
So why not?

[DeathAndTaxes]

Correct me if I am wrong but k only needs to be unique, it doesn't need to be randomized each transaction.  We simply use an RNG because given a large enough range (256 bit) it is likely all values will be unique. However that assumes the RNG is working properly and that may be difficult to test.

Using a RNG to seed a 256 bit nonce which is incremented on each tx "next-k" would be one way to be less reliant on low entropy/flawed RNG.  The nonce could be encrypted along with private keys so any compromise of the "next-k" means your private keys are probably already stolen anyways.  As an alternative XOR the rng value with an incrementing nonce to produce k.

[gmaxwell]

Once again this thread has nothing to do with RNG.
It is just a special case, very easy to detect, more or less as probable (or improbable) as other tests that are performed in the signing process.
So why not?

Because you're wrong.

Ignoring potential problems with RNG, K=secret-key is no more a special value than K=11 (or 12 or 13 or any other specific value). All of them result in a trivally identifiable R.

Ignoring RNGs,  you are no more likely to crack ECDSA by recognizing K==secret from R than you are to crack it by recognizing K==11 from R. You're aware that if the attacker knows K they can recover your private key, right?  K doesn't need to be reused to expose you.

[Yves Cuicui]

K=secret-key is no more a special value than K=11 (or 12 or 13 or any other specific value)

Agreed, but the difference is that to recognize values k=11, 12 ... you need a lookup table on the r value that does not worth it! Checking r=Qx is at no cost!

[gmaxwell]

K=secret-key is no more a special value than K=11 (or 12 or 13 or any other specific value)

Agreed, but the difference is that to recognize values k=11, 12 ... you need a lookup table on the r value that does not worth it! Checking r=Qx is at no cost!

To recognize K=11 you do a comparison with a constant.  To recognize K=secret key you do a comparison with a dynamic value.  In either case the operation is the same and you only recognize one possible K. Maybe you can argue that you save a word of memory, but this is a trivial cost.