Deterministic Usage of DSA and ECDSA Digital Signature Algorithms (RFC 6979)

[natb]

Ok. I was seeing it as insurance against faulty PRNGs. Hardware wallets are always going to have a problem in ensuring the private keys are generated ok anyway.
 But if you did want to check the signing nonce would it be possible to pre-generate a file of random numbers, store them on the wallet and give them to the purchaser of the wallet in a file or online, then deterministically generate the number and add the next number from the random number file and reduce mod n and sign with this?

Sure, I suppose you could do this. However, its probably easier to do the following if your wallet is conforming to BIP 32 and using RFC 6979 for signing:

1. User generates their own master seed
2. User, with software running on their own computer, generates N keys using BIP 32 and the seed from step 1 and signs a bunch of test transactions using these keys.
3. User loads your HW wallet with the master seed from step 1
4. User asks your wallet to sign the same test transactions they did in step 2.
5. User compares his local signatures with the ones generated by you, if they match - your wallet is working as expected without any code review needed.

Now, the normal user will generate a master seed based on input from the user plus randomness from your device. This seed is displayed only on your devices screen so it never leaves the device. The user could then, if they so chose, repeat steps 2,4,5 on a secure computer to again verify your wallet was 100% doing as they expected.

This is what I plan on doing for my device. I think its pretty solid. And I don't buy the argument that you need 'insurance' by adding randomness to RFC 6979 - if you think you need to do that aren't you saying you don't trust that SHA-256 is truly a 1-way trapdoor function with no fast way to brute force it? If you believe that then there are alot more problems in the Bitcoin protocol itself which relies on SHA-2 for alot of things.

I'm happy to be proven wrong if anyone finds something bad about my logic above

[iddo]

If you have non-memory access related power or timing side channels (e.g. like adders leaking data, which is what would be required for HMAC-SHA512 to leak) then there is going to be no way to avoid the ECDSA point math leaking like crazy. Using non-deterministic DSA does not save you from side channels. Maybe deterministic makes a really side-channel heavy implementation more vulnerable, but people have already demonstrated recovery on devices with randomized DSA, so I am a little skeptical that it matters. Some masking behavior would be fine, but it wouldn't require making the output non-deterministic.

I'm not sure that in general it's completely true that a side-channel attack on a hash function like SHA512 involves only non-memory access, because the input to the hash function probably resides in memory, so there might be side-channel attacks that involve cache misses etc., though I suspect that in this case you're right because the input is short (privkey + hash of the message), and even if there was a possible danger here then there are probably side-channel resistance techniques to mitigate the risk.

More importantly, in the specific case of ECDSA it's enough to recover the output of k=hash(privkey, msg) rather than the input (privkey, msg) because if k leaks then the privkey also leaks. Therefore, it doesn't really matter if we use deterministic signatures via k=hash(privkey, msg) or random signatures via e.g. k=hash(privkey xor random, msg) because carrying out a side-channel attack that recovers the output of the hash function should be much easier than carrying out a side-channel attack that recovers the input to the hash function.

And more generally, side-channels attacks against symmetric crypto primitives like AES and SHA2 are a lot more difficult than side-channel attacks on public-key/asymmetric crypto primitives, so the risk of possible side-channel attacks on either the input or the output of SHA512 are probably not so significant.

Maybe there should be a parameter (on by default as in OpenSSL ?) to toggle the protection from side-channels attacks, and if the user wishes to have the best possible protection then he could specify via this parameter that the input to the hash function should be masked with randomness, which would imply random signatures because it cannot be unmasked.

I'm not sure if we're missing anything interesting here, so it'd be a good idea to consult with experts on side-channel attacks before having deterministic signatures as the default.

[gmaxwell]

I'm not sure that in general it's completely true that a side-channel attack on a hash function like SHA512 involves only non-memory access, because the input to the hash function probably resides in memory, so there might be side-channel attacks that involve cache misses etc.,

In SHA512 none of the memory accesses are data dependent, every execution reads from the same locations. I believe this is true of all relatively modern hash functions (SCRYPT is the notable exception, though it's normally used in a way that probably makes them harmless).

(just a minor comment— I agree with everything you're writing)

[Crowex]

Ok. I was seeing it as insurance against faulty PRNGs. Hardware wallets are always going to have a problem in ensuring the private keys are generated ok anyway.
 But if you did want to check the signing nonce would it be possible to pre-generate a file of random numbers, store them on the wallet and give them to the purchaser of the wallet in a file or online, then deterministically generate the number and add the next number from the random number file and reduce mod n and sign with this?

Sure, I suppose you could do this. However, its probably easier to do the following if your wallet is conforming to BIP 32 and using RFC 6979 for signing:

1. User generates their own master seed
2. User, with software running on their own computer, generates N keys using BIP 32 and the seed from step 1 and signs a bunch of test transactions using these keys.
3. User loads your HW wallet with the master seed from step 1
4. User asks your wallet to sign the same test transactions they did in step 2.
5. User compares his local signatures with the ones generated by you, if they match - your wallet is working as expected without any code review needed.

Now, the normal user will generate a master seed based on input from the user plus randomness from your device. This seed is displayed only on your devices screen so it never leaves the device. The user could then, if they so chose, repeat steps 2,4,5 on a secure computer to again verify your wallet was 100% doing as they expected.

This is what I plan on doing for my device. I think its pretty solid. And I don't buy the argument that you need 'insurance' by adding randomness to RFC 6979 - if you think you need to do that aren't you saying you don't trust that SHA-256 is truly a 1-way trapdoor function with no fast way to brute force it? If you believe that then there are alot more problems in the Bitcoin protocol itself which relies on SHA-2 for alot of things.

I'm happy to be proven wrong if anyone finds something bad about my logic above

I'm not making any arguments as to the security of SHA-256. To the question as to whether it was better to use deterministic RFC6976 signing nonces in preference to prng generated numbers I just suggested using both methods as a belt and braces option.
 When you pointed out that my method didn't allow checking by a third party I gave an option that did and uses both methods so that if someone did have doubts about RFC6976 then they could be secure in knowing that there was a random element in the signing nonce.
 I just thought it was an interesting idea to use pre-generated random numbers but I can't see a problem with it. Maybe there is?
 As to generating private keys and BIP32,  that's a completely different question.
 

[stick]

JFYI: Latest commit adds RFC 6979 to microecdsa code as well: https://github.com/trezor/microecdsa

[fpgaminer]

Using my own implementation of RFC 6979 on top of warner's ECDSA code, I generated a few test vectors.  slush's patch matches up perfectly!

For future reference, here are the test vectors:

Code:

# Test Vectors for RFC 6979 ECDSA, secp256k1, SHA-256
# (private key, message, expected k, expected signature)
test_vectors = [
	(0x1, "Satoshi Nakamoto", 0x8F8A276C19F4149656B280621E358CCE24F5F52542772691EE69063B74F15D15, "934b1ea10a4b3c1757e2b0c017d0b6143ce3c9a7e6a4a49860d7a6ab210ee3d8dbbd3162d46e9f9bef7feb87c16dc13b4f6568a87f4e83f728e2443ba586675c"),
	(0x1, "All those moments will be lost in time, like tears in rain. Time to die...", 0x38AA22D72376B4DBC472E06C3BA403EE0A394DA63FC58D88686C611ABA98D6B3, "8600dbd41e348fe5c9465ab92d23e3db8b98b873beecd930736488696438cb6bab8019bbd8b6924cc4099fe625340ffb1eaac34bf4477daa39d0835429094520"),
	(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140, "Satoshi Nakamoto", 0x33A19B60E25FB6F4435AF53A3D42D493644827367E6453928554F43E49AA6F90, "fd567d121db66e382991534ada77a6bd3106f0a1098c231e47993447cd6af2d094c632f14e4379fc1ea610a3df5a375152549736425ee17cebe10abbc2a2826c"),
	(0xf8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181, "Alan Turing", 0x525A82B70E67874398067543FD84C83D30C175FDC45FDEEE082FE13B1D7CFDF1, "7063ae83e7f62bbb171798131b4a0564b956930092b33b07b395615d9ec7e15ca72033e1ff5ca1ea8d0c99001cb45f0272d3be7525d3049c0d9e98dc7582b857")
]

[chriswilmer]

Cool. I am a fan of this deterministic ECDSA idea. Allowing others to exactly reproduce your output is one of those things I under appreciated in my youth...

[slush]

Today the new version of python-ecdsa has been released. Version 0.9 contains implementation of RFC 6979 as well as secp256k1 curve, used in bitcoin.

[BurtW]

Today the new version of python-ecdsa has been released. Version 0.9 contains implementation of RFC 6979 as well as secp256k1 curve, used in bitcoin.

Thanks for all the hard work on this.

[plaprade]

Code:

# Test Vectors for RFC 6979 ECDSA, secp256k1, SHA-256
# (private key, message, expected k, expected signature)
(0xf8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181, "Alan Turing", 0x525A82B70E67874398067543FD84C83D30C175FDC45FDEEE082FE13B1D7CFDF1, "7063ae83e7f62bbb171798131b4a0564b956930092b33b07b395615d9ec7e15ca72033e1ff5ca1ea8d0c99001cb45f0272d3be7525d3049c0d9e98dc7582b857")

Thanks for the test vectors! They are really useful as none are provided for our curve in the RFC.

I had an issue with your last test vector. After some investigation, I noticed that the problem came from the parity of 'S'. The 'S' component is odd in your last test vector. I think that going forward, new code should produce fully valid and canonical signatures, which includes making the 'S' component even. Let me know if that is a reasonable statement or not.

For reference, here is my results for this test vector:

Code:

# Test Vectors for RFC 6979 ECDSA, secp256k1, SHA-256
# (private key, message, expected k, expected signature)
(0xf8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181, "Alan Turing", 0x525A82B70E67874398067543FD84C83D30C175FDC45FDEEE082FE13B1D7CFDF1, "7063ae83e7f62bbb171798131b4a0564b956930092b33b07b395615d9ec7e15c58dfcc1e00a35e1572f366ffe34ba0fc47db1e7189759b9fb233c5b05ab388ea")

[stick]

I noticed that the problem came from the parity of 'S'. The 'S' component is odd in your last test vector.

Why should S be even? Any citation?

[gmaxwell]

Why should S be even? Any citation?

To prevent third parties from changing your txids out from under you and invalidating transactions spending your unconfirmed transactions by replacing S with the alternative value which also allows the signature to pass.  This malleability can be used to create enormous nuisances for Bitcoin users, causing stuck transactions and making innocent people look like malicious double-spenders, as well as can be abused to extort people in some escrow protocols.

See the second half of: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02721.html

There are multiple ways to remove this 1-bit of freedom. One way is to make S even. Another way, now used by bitcoin-qt git, is to make s < order/2. The advantage of this way of removing the vs others freedom is that it also reduces the average signature size slightly.  I now prefer the s < order/2 version of this just because it produces smaller signatures and the flip is even easier to implement than the even/odd version.

[plaprade]

I noticed that the problem came from the parity of 'S'. The 'S' component is odd in your last test vector.

Why should S be even? Any citation?

From the bitcoind reference implementation:

https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp (line 295)

Code:

    if (flags & SCRIPT_VERIFY_EVEN_S) {
        if (S[nLenS-1] & 1)
            return error("Non-canonical signature: S value odd");
    }

However there's a flag to activate this check. Most of the unit tests in the reference implementation do not take even 'S' into account yet.

[gmaxwell]

However there's a flag to activate this check. Most of the unit tests in the reference implementation do not take even 'S' into account yet.

This will be changed to the alternative I described.

[plaprade]

This will be changed to the alternative I described.

Thanks! I'll update my code accordingly.

[stick]

I now prefer the s < order/2 version of this just because it produces smaller signatures and the flip is even easier to implement than the even/odd version.

So how exactly K needs to be changed/processed to have S < order/2 ?
Or we keep K as it is and just postprocess S ?

[Mike Hearn]

if you look at the current code in git master, it just subtracts order/2 when s > order/2 - pretty simple.

[stick]

There are multiple ways to remove this 1-bit of freedom. One way is to make S even. Another way, now used by bitcoin-qt git, is to make s < order/2. The advantage of this way of removing the vs others freedom is that it also reduces the average signature size slightly.  I now prefer the s < order/2 version of this just because it produces smaller signatures and the flip is even easier to implement than the even/odd version.

if you look at the current code in git master, it just subtracts order/2 when s > order/2 - pretty simple.

Flip is already being done when you deal with compressed public keys. All software that can process compressed public keys already knows how to do the flip (val = prime - val). It would be nice to be consistent here IMO.

FWIW when I used this method on S (if S is odd: S = prime -S) - the code produced signatures that are considered invalid by both my code (microecdsa) and OpenSSL. *puzzled* When I used the other way (if S > prime/2 : S -= prime/2) I ended up with the same result (invalid signatures). Any hints on what is going on?

[johoe]

FWIW when I used this method on S (if S is odd: S = prime -S) - the code produced signatures that are considered invalid by both my code (microecdsa) and OpenSSL. *puzzled* When I used the other way (if S > prime/2 : S -= prime/2) I ended up with the same result (invalid signatures). Any hints on what is going on?

The theory behind this is: if you negate K you get the same R and the negated S.  Hence you need to negate S as a post-processing step, i.e., S' = prime - S in both cases.  Did you use the right prime?  It should be the order of the elliptic curve not the size of the prime field.

[stick]

The theory behind this is: if you negate K you get the same R and the negated S. Hence you need to negate S as a post-processing step, i.e., S' = prime - S in both cases.

Thanks. That's what I thought but wanted to confirm.

Did you use the right prime?  It should be the order of the elliptic curve not the size of the prime field.

Tried both with the same result (invalid sigs).