Topic: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms (RFC 6979) - page 2. (Read 17286 times)

Why should S be even? Any citation?

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:

Thanks for all the hard work on this.

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.

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

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:

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

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.
 

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)

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.

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

Colin Percival is the author of the only recent notable hash-function with significant data-dependent-timing attack problems, so perhaps thats why it's on his brain.

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.

Being hard against an attacker with physical access is very hard, as I mentioned a simple bit error in our the multiply will put you on the twist and the largest prime factor of the order of SECP256k1's twist is only around 2^50.

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?

I'm probably missing something here, but it seems to me that the argument that you're giving is similar to what Colin Percival had in mind, though you're interpreting it in the opposite way than he, and I don't exactly understand your argument yet.

I think that the concern is that there might be side-channel attacks on the hash function (heat as in your example, acoustic noise, timing, etc.) that may recover the input that it's invoked with. On the other hand, while it is true that the privkey and K are also used in the next calculations that finally derive the signature, those calculations can be masked in order to protect from such side-channel attacks (like multiplying k by a fresh random value before calculating k^{-1} and then unmasking). For the hash function, there's no way to do these masking tricks, hence the concern?

I suppose that it's a good idea that deterministic signatures would be a user configurable option, but the important question still remains regarding whether the default behavior should be deterministic or random.

Other than this supposed protection from side-channel attacks, does anyone know if there are any other advantages or practical use cases for random signatures (as is obviously the case with random encryption so that it'd be semantically secure) ?

::sigh::  If adding the secret to the input were problematic the entire signing function would very likely be insecure: Computing a collision is easier than recovering an unknown pre-image, doubly so because the next thing you do is multiply K by G to get R, which both reduces the space of the output, and makes K unrecoverable from unless you can solve a discrete log problem.

The cost of this is that you produce a device whos correct behavior is not measurable. It could have backdoors inserted in several forms which would be very difficult to discover, or it could have flawed operation.

e.g. if it gets hot there are random bitflips in the multiply used to derive R from K, because the twist of secp256k1 is a smooth field where solving the DLP is relatively easy a single bit-flip in the multiply can result in a R value from which K can be recovered in about 2^51 work.

[Edit: Actually this is incorrect secp256k1 is twist secure, the error there resulted from an apparently transcription error copying down the order of the twist for factoring.  Of course the potential for backdoors in DSA nonce generation are universal and apply to all curves, and to edDSA as well]

Essentially I view this as increasing weakness to these specific but "kind of boring" threats which I can articulate and even show you demonstrations of (e.g. the backdoored signers) in favor or speculatively increasing security against vague cryptographic boogymen, which— if they exist at all— will probably kill us all regardless (by allowing collisions on the data being signed, and thus allowing signature rebinding).


So this doesn't really quite reflect the "defense model" I'm going for. Realistically— whos going to go and do those things?  Even of those people with a million dollars to protect?  Very few.

But not zero, a few geeks are reasonably likely to go splunking around— and I'd think that really any one attempting to be a vendor in this space should even set aside some budget to pay for third party auditing to make _sure_ some external eyes dig in deep.

What I think what would be beneficial for the Bitcoin-using economy is if these few rare instances of crazy, curious, or otherwise motivated adventure seekers somehow protected all of us from badness.   This is what happens with open code: When I review code thoroughly, I'm not just protecting myself: I'm protecting everyone I can communicate with.

The problem with (2) there is that I can't tell if the device was unfaithful to begin with. So if I'm the guy who doesn't trust my device the result is that I get a safe device, but I don't get the ability to sound an alarm to warn anyone else.  In particular, if the device is deterministic, someone who goes in with the logic analyzers can certify the device and document the behavior, then other people can randomly check that their devices measure the documented behavior with far less work.

A compromise in the middle if the device has a display: when signing, show the extra "bonus" randomness on the display. The behavior could still then be completely deterministic (assuming you capture the bonus randomness).. but since the protocol should still be secure against anything by cryptographic boogymen even if the "bonus randomness" is just a constant it should be harmless to display it, you could even send it over USB to the host.  Unless you're worried about boogmen who can invert sha256 and own a camcorder (or, in the latter, and who've hacked your computer).

I hope you don't think I'm ranting at you too much. My replies here are all in the spirit of talking through building the best and most practically secure systems possible— a goal I think we all share.

Round of applause.  Very awesome to see!  Thank you for sharing, and pushing to warner's repo.

Personally, I'd like to see it use a separate HMAC-DRBG module, to help code separation, unit testing, and code reuse (https://github.com/fpgaminer/python-hmac-drbg is public domain).  Also, the possibility to swap out HMAC-DRBG for a different function, so it can be used as a test-bed for using plain HMAC.

Pull request adding RFC 6979 into python-ecdsa: https://github.com/warner/python-ecdsa/pull/10

This optimization makes code 5x faster on x86. Even more on ARM devices. That's a significant improvement. Unfortunately, it makes also code 3x-4x bigger, that's why there are macros to turn it on/off.

I reached out to Colin Percival (who wrote scrypt, for example) for his thoughts/comments on RFC 6979.  Here's what he had to say (with his permission):


This seems to be in agreement with pretty much everyone else's opinion on RFC 6979, which is good to see.  Many thanks to Colin Percival for taking the time to respond to my inquiry!

Shameless self-promotion: https://github.com/fpgaminer/strong-arm

Looks to me like the LUT implementation of EC scalar multiplication.  You have 256 pre-computed values, each of the form 2^i * G so you can just add them together depending on the bits of the scalar.  I can go into a more detailed explanation if you would like.

I chose not to implement that optimization in strong-arm, since it really wasn't much of a bottleneck, and I personally prefer transparent code over optimized code.  Easier to audit and avoid bugs.

You can do that in pseudo-RFC 6979 by just reseeding the DRBG with any extra entropy you'd like.  Though, as natb pointed out, gmaxwell and others believe it best to leave things fully deterministic.  I'm ... still on the fence, but leaning more towards deterministic after reading gmaxwell's arguments.

Two stages, depending on user paranoia:

1) Update the device before using it, with known good firmware (cryptographically signed + deterministic compilation). [Does not rule out rootkit]
2) Open the device, visually verify hardware, and use JTAG/SWD to manually wipe and flash. [Rules out rootkit, FPGA masquerade, etc]

This will mitigate all reasonable attacks.  The only one left would a malicious custom ASIC pretending to be the MCU.  But if your attacker is willing to spend millions of dollars ... hell, you must be doing something right in your life.

Yes, there are a million and one ways to attack a user when a malicious party can manipulate the hardware.  But, you make a great point regardless; better safer than sorry.

Rather than that, and assuming you have a trusted computer on which to do all this (since it will have access to your master key), just build the backup manually using your own entropy and restore it to the device.  Then query the device for a few public keys to verify it's using your backup.  I specifically left this option open on my platform, so that advanced users could choose their own means of creating the master key.  For example, choosing it like a brainwallet.

As usual, gmaxwell, your comments are wonderfully insightful and helpful.  Thank you for taking the time to bat around these ideas with me (and the rest of the community).