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

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

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?

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?

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

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

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.


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)

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.

Wonderful and insightful comments, gmaxwell; thank you.

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)

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

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.

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

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

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?