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

[fpgaminer]

I've seen this RFC mentioned once or twice on this forum, but could not find any extensive dialog about it.  I would like to implement this as part of my hardware wallet, but am hesitant to do so without seeing what others have to think about the approach.

Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)


Summary of RFC 6979
ECDSA signature generation uses a number k, which must be randomly and uniformly chosen each time a signature is created.  Under deterministic ECDSA, as proposed by RFC 6979, k is chosen deterministically.

We start by creating an instance of HMAC-DRBG, with the private key as the source of entropy, and the hash of the message as the nonce.  k is generated from the output of this HMAC-DRBG instance.  This makes k deterministic, given the message and the private key, but still uniformly distributed and ~impossible for an attacker to guess/calculate.

Most importantly, signatures generated this way are compatible with existing ECDSA signature verification implementations.


Why make ECDSA deterministic?
There are two major reasons to use a deterministic algorithm here.  In regular ECDSA, if two signatures are created (different messages) with the same k value, the private key can be calculated.  This means that ECDSA immediately fails if k is not chosen randomly.  The recent Android mishap led to such a problem.  Using deterministic ECDSA avoids this.

Secondly, it allows easy verification of ECDSA implementations, using fixed test vectors.  Regular ECDSA implementations cannot use signature test vectors, because the signatures are random by design.


Thoughts?

[1713254676]

1713254676

[1713254676]

1713254676

[1713254676]

1713254676

[gmaxwell]

Here are my thoughts: http://permalink.gmane.org/gmane.comp.bitcoin.devel/2734

[fpgaminer]

Here are my thoughts: http://permalink.gmane.org/gmane.comp.bitcoin.devel/2734

Yup, that seems to resonate well with my conclusions.  Thank you for the link.

I just finished coding an HMAC_DRBG implementation in Python and threw it up on github, as a nice reference.  I'll follow that up with an implementation of RFC 6979 in Python, to play around with.

Personally, I'm leaning towards an implementation of RFC 6979, with an extra switch in the API to enable the usage of additional entropy.  The switch could default on, thus avoiding concerns over leaking information about the private key.  During unit or continuous tests, though, it could be switched off to verify conformance to RFC 6979, and switched back on to verify non-conformance (and thus confirm that entropy is being added).

[gmaxwell]

I was leaning towards recommending using HMAC-SHA512 since its already required for  BIP32.

I'd generally recommend against non-deterministic signatures. If the signatures are non-deterministic it is impossible for someone to verify that the implementation is not using the R value as a side channel to leak the private keys.

In open source pure software implementations it easy to be relatively confident that an implementation isn't cryptographically encoding the private key in the choice of R value (via, e.g. incrementing K until an R that leaks a non-deterministic part of the master private key), but in a hardware wallet implementation this is impossible, and it is trivial to construct a malicious implementation that leaks the private key via the R value in just a few signatures.

I actually have two implementations of example malicious signers:  One produces non-deterministic signatures and leaks a 256 bit private key, to the holder of a specific public key and no one else, in ~33 signatures with very high probability (failure rate of 1 in 1000 for 33 signatures, around 1 in a million for 34). The other produces a seemingly RFC 6979 like deterministic signatures and with a single signature leaks the current private key, and with 16 signatures leaks an additional 256 bit secret (e.g. a master private key, with a failure rate of around 1:1000 for 16 signatures, ~1:1e6 for 17 signatures).

Both work by performing an extra point multiply to gain an ECDH shared secret between the attacker and the user's key.

In the first case it then searches for a K value where H(secret||R)'s least significant bits match the data being leaked.  The leaked data is selected based using the data being signed to drive a fountain code over the private data.

In the second, the ECDH shared secret replaces the secret key in the RFC6979 K value selection (this is especially diabolical because the implementation with openssl looks fairly benign as its just point multiplying the secret by a constant), and appeneding 16 bits of (again) message digest selected secret data (which just looks like more 'salt') this time just a index into 65535 16 bit words from a 16 bit RS code expansion of the private key.  The attacker computes the shared secret and then searches for the 16 bit value that gives him the same R. He then knows K and can recover the current key and has learned 16 bits of secret data. The RS code can be precomputed and passed off as just storage redundancy for the master key.

Because tractability in hardware devices is already weak, it would sure be better if the device could be put in a mode which would make its behavior completely reproducible externally. If the security assumptions underlying the SHA2 based derandomized DSA do not hold, then it is almost certain that SHA2 using ECDSA will also not hold.  Whatever version you implement, I hope there will be a way for someone with the device to verify that it's doing what its supposted to be doing.

[fpgaminer]

Wonderful and insightful comments, gmaxwell; thank you.

but in a hardware wallet implementation this is impossible

If the hardware is known, and it is running open source firmware, what concerns would there be?

Also, malicious firmware doesn't need to leak information through signatures to enable an attack vector.  It could be using a DRBG to select the private keys, seeded from a secret known to the attacker and a device specific id.  This would enable the attacker to calculate potential private keys and search the blockchain.  To an outside observer, the private keys would look random as usual.  (This is the same worry people have about the RdRand instruction)

it would sure be better if the device could be put in a mode which would make its behavior completely reproducible externally

Perhaps deterministic signatures could be a user configurable option, allowing expert users to "pick their poison".

[gmaxwell]

but in a hardware wallet implementation this is impossible

If the hardware is known, and it is running open source firmware, what concerns would there be?
Also, malicious firmware doesn't need to leak information through signatures to enable an attack vector.

How do you actually know that it is running the open source firmware and not a modified version installed by the manufacturer or replaced in transit?

Generally if your computing device is compromised you're kind of doomed, but in this case not so much... because the behavior of the device is sufficiently narrow and all communication mediated via the host, it should be possible to be a little more confident here.

Also, malicious firmware doesn't need to leak information through signatures to enable an attack vector.  It could be using a DRBG to select the private keys, seeded from a secret known to the attacker and a device specific id.  This would enable the attacker to calculate potential private keys and search the blockchain.  To an outside observer, the private keys would look random as usual.  (This is the same worry people have about the RdRand instruction)

My expectation is that you'd make your master key  some H(device randomness || user or initial host randomness).  You need a way to export the master key data for backup purposes, so with an addition that also lets the user obtain the contributing randomness after obtaining the device master key.  Effectively this means the the device cannot undetectable cheat in the way you suggest.

(now, any particular user may fail to detect it— but it changes the risk model for someone substituting the firmware, since after already committing itself to some behavior and signing transactions on behalf of the user the user could then demand it provide the device randomness and they could fully repeat the output)

it would sure be better if the device could be put in a mode which would make its behavior completely reproducible externally

Perhaps deterministic signatures could be a user configurable option, allowing expert users to "pick their poison".
[/quote]I prefer fewer options to more... but indeed.

[stick]

Last news about DRBG: http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy 

Btw, slush and I are trying to implement RFC6979 into python-ecdsa/microecdsa. Hopefully we'll publish the results soon (or watch https://github.com/trezor/python-ecdsa and https://github.com/trezor/microecdsa repos).

[gmaxwell]

Last news about DRBG: http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy 

Old news and fpgaminer is not talking about Dual_EC_DRBG. He's implemented the DRBG based on SHA256.

[natb]

Wow, thanks for posting your 'microecdsa' code - now I get to see how what I came up with stacks up to your version

Couple questions:

Is the algo you created resistant to side-channel attacks (constant time for doing the scalar multiply)?
Can you give me any insights/references into your 'PRECOMPUTED_CP/IV' technique?

Last news about DRBG: http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy 

Btw, slush and I are trying to implement RFC6979 into python-ecdsa/microecdsa. Hopefully we'll publish the results soon (or watch https://github.com/trezor/python-ecdsa and https://github.com/trezor/microecdsa repos).

[Crowex]

What would be the disadvantage of deterministically generating k each time and then multiplying by a PRNG generated number and reducing mod n and use this to sign?
Wouldn't you get protection against the failure of either method this way?

[natb]

This is all well and good - yes it works just fine. However as I understand it, it spoils the benefits of having a 3rd party entity be able to *exactly* reproduce your signatures to verify that your HW device is not doing anything dumb when generating said signatures. This gives them confidence that your HW wallet is not leaking information about private keys through sub-par 'random' number generation.

What would be the disadvantage of deterministically generating k each time and then multiplying by a PRNG generated number and reducing mod n and use this to sign?
Wouldn't you get protection against the failure of either method this way?

[fpgaminer]

How do you actually know that it is running the open source firmware and not a modified version installed by the manufacturer or replaced in transit?

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.

Generally if your computing device is compromised you're kind of doomed, but in this case not so much... because the behavior of the device is sufficiently narrow and all communication mediated via the host, it should be possible to be a little more confident here.

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.

My expectation is that you'd make your master key  some H(device randomness || user or initial host randomness).  You need a way to export the master key data for backup purposes, so with an addition that also lets the user obtain the contributing randomness after obtaining the device master key.  Effectively this means the the device cannot undetectable cheat in the way you suggest.

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

[fpgaminer]

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

I don't see any concrete problems with this proposal, but using the private key
as part of the hashed input does make me a bit nervous.

Personally, I'd prefer to feed these into an HMAC-DRBG to be used for entropy
*in addition to* normal seeding of entropy from the operating system -- unless
you really need deterministic signatures.

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!

Wow, thanks for posting your 'microecdsa' code - now I get to see how what I came up with stacks up to your version Smiley

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

Can you give me any insights/references into your 'PRECOMPUTED_CP/IV' technique?

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.

What would be the disadvantage of deterministically generating k each time and then multiplying by a PRNG generated number and reducing mod n and use this to sign?

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.

[stick]

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.

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.

[slush]

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

[fpgaminer]

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

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.

[gmaxwell]

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

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

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.

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.

[iddo]

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

I don't see any concrete problems with this proposal, but using the private key
as part of the hashed input does make me a bit nervous.

Personally, I'd prefer to feed these into an HMAC-DRBG to be used for entropy
*in addition to* normal seeding of entropy from the operating system -- unless
you really need deterministic signatures.

This seems to be in agreement with pretty much everyone else's opinion on RFC 6979, which is good to see.

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

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

[Crowex]

This is all well and good - yes it works just fine. However as I understand it, it spoils the benefits of having a 3rd party entity be able to *exactly* reproduce your signatures to verify that your HW device is not doing anything dumb when generating said signatures. This gives them confidence that your HW wallet is not leaking information about private keys through sub-par 'random' number generation.

What would be the disadvantage of deterministically generating k each time and then multiplying by a PRNG generated number and reducing mod n and use this to sign?
Wouldn't you get protection against the failure of either method this way?

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?

[gmaxwell]

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.

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.