Could deterministic signatures be used to reduce Bitcoin's dependency on PRNG?

[DeathAndTaxes]

Bitcoin relies heavily on cryptographically secure PRNG and as we have seen from the android exploit, ensuring high entropy is often a challenge.  This functionality is handled by the operating system which means the security of the client becomes heavily dependent on the security of underlying operating system.  Even if we discount the possibility of three letter agencies intentionally weakening the PRNG (which they may do even for non-Bitcoin reasons and Bitcoin users become collateral damage) there is always the possibility of implementation bug in certain situations.

There is a proposal for deterministic ECDSA signatures
http://tools.ietf.org/html/rfc6979

This would remove the need for random values as nonces in Bitcoin transaction signatures.
HD wallets remove the need for random values when generating private keys.
HD wallet seeds still need a high entropy random number but as this only needs to be done once it could even be done by dice rolls (100 rolls of standard six sided for 256 bit seed).

[1714694417]

1714694417

[gmaxwell]

http://sourceforge.net/p/bitcoin/mailman/message/31306213/

I expect we'll make that change in Bitcoin-QT as a part of the change to libsecp256k1... though the most recent versions of openssl use something like H(message||private||rng_output) as the nonce, so even in the case of RNG failure you don't get a DSA leak.

It's also the case that OpenSSL uses its own internal randomness pool seeded initially from the OS. There isn't any particular reason that you couldn't send your dice input into that, though the seeding interface isn't exposed in Bitcoin currently, though perhaps it should be.

[Eadeqa]

http://sourceforge.net/p/bitcoin/mailman/message/31306213/

I expect we'll make that change in Bitcoin-QT as a part of the change to libsecp256k1... though the most recent versions of openssl use something like H(message||private||rng_output) as the nonce, so even in the case of RNG failure you don't get a DSA leak.

It's also the case that OpenSSL uses its own internal randomness pool seeded initially from the OS. There isn't any particular reason that you couldn't send your dice input into that, though the seeding interface isn't exposed in Bitcoin currently, though perhaps it should be.

What do you think about this?

http://safecurves.cr.yp.to/

They don't consider secp256k1 to be safe

There is also this video lecture

SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography
Daniel J. Bernstein and Tanja Lange

https://archive.org/details/ShmooCon2014_SafeCurves

[gmaxwell]

What do you think about this?

Please search the forum. This has been answered previously: https://bitcointalk.org/index.php?topic=380482.msg4083612#msg4083612

[piotr_n]

Sorry for maybe a stupid question.

Is there any reason against using the value that is getting signed as the R as well?

I mean, apart from the fact that it might be out of range.

But would there be any technical or security concerns having the same value at two different input params?

[DeathAndTaxes]

Sorry for maybe a stupid question.

Is there any reason against using the value that is getting signed as the R as well?

I mean, apart from the fact that it might be out of range.

But would there be any technical or security concerns having the same value at two different input params?

Well a couple of things.

1) You don't supply the R you supply the k (a nonce) and the R is computed from that. 
2) The k (and thus computed R) must be unique AND unknown.  The tx (or hash of tx) is unique but it isn't unknown.

Simple version:
If attacker can determine the k, then given the message (tx) and pubkey (both available in a signed transaction), the attack can compute the private key.

RFC6979 IS the solution.  Simplified it uses a HMAC ( http://en.wikipedia.org/wiki/Hash-based_message_authentication_code ) from the private key and transaction to create a k value which is both deterministic and unknown (unless you know the private key in which case keeping k a secret is a moot point).

I have implemented it in my own C# library, others have implemented it in libraries for other languages (C++, java, perl, php, js).  In another thread there is a semi-standard set of test vectors ( I have asked the author of RFC6979 to include a standard set of test vectors for SECP256K1 in the RFC doc).  The nice thing is that RFC6979 isn't Bitcoin specific so hopefully it will be widely supported in standard crypto libraries.  The one issue w/ RFC6979 is it is rather complex as it is designed to handle all possible edge cases.   Bitcoin (using HMAC-SHA-256) is a rather simplified usage with fixed key and hash sizes so most of the complexity is "unused"  it is possible to refactor RFC6979 to remove the checks and conversions for handling unused cases to create a "Reduced RFC6979" which can only be used for Bitcoin that is much smaller and simpler to understand (useful for say a bitcoin specific library).

If I have the chance I will write up some documentation.

[piotr_n]

Well you can't just use the value being signed.   The k value must be both unique AND UNKNOWN.  If the attacker knows the k value even if it is unique they can derive the private key.

I though the problem was with R values being re-used. Then you calculate S, for a specific R and the private key.
And you publish R values anyway, as a part of the signature, so by definition these cannot be UNKNOWN.

Sorry, isn't it how it works?

[DeathAndTaxes]

Well you can't just use the value being signed.   The k value must be both unique AND UNKNOWN.  If the attacker knows the k value even if it is unique they can derive the private key.

I though the problem was with R values being re-used. Then you calculate S, for a specific R and the private key.
And you publish R values anyway, as a part of the signature, so by definition these cannot be UNKNOWN.

That is a simplification.  R is computed from k.  If you use the same k you will end up with the same R.  If you use the same k then you will end up with the same R.  However due to some ECDSA magic knowing R doesn't allow you to know k (much like knowing a PubKey doesn't allow you to know the PrivKey).

R is computed from k.  Here is a snippet of code.  It is C# but the nice thing about C# is it is pretty high level and thus easy to read like pseudo code

Code:

            do // Generate s.  
            {
                BigInteger k;
                do // Generate r.
                {
                    k = KGenerator.GetK();
                    var p = G.Multiply(k);
                    r = p.X.Mod(N);
                }
                while (r.IsZero); //An r of zero (very unlikely) is an invalid signature. Loop until we randomly produce a valid r.

                s = k.ModInverse(N).Multiply(e.Add(d.Multiply(r))).Mod(N);
            }
            while (s.IsZero); //An s of zero (very unlikely) is an invalid signature. Loop until we randomly produce a valid s.

            if (forceCanonical && s > N / 2)
                s = N - s;

            return new[] { r, s };

Trying not to get too far into the ECDSA weeds but G is the base point of the secp256k1 curve.

So we generate a k (either randomly or deterministically).
A point p is produced from multiplying the G by k.  We then do a mod of N (to avoid p being larger than N).  R is that modded value.

This is just as secure as Q(PubKey) generation

Code:

R = Gk (where R < N, and k is a random 256 bit nonce)
Q = Gd (where Q < N, and d is a random 256 bit private key)

There is no feasible method to derive k from R.  If there was then you could also derive d from G as well (privKey from PubKey).  That property is where ECDSA gets its security from.

[piotr_n]

Oh, I think I get it.
R is a function of (k, private key), while S if a function (R, hash).
Stupid me

Anyway, thanks for the answer.

[DeathAndTaxes]

Oh, I think I get it.
R is a function of (k, private key), while S if a function (R, hash).
Stupid me

Anyway, thanks for the answer.

Yes and that function for R is a one way function.  Lastly to avoid compromising the security of the private key, k must be secret (a release of k is equivalent to a release of the private key).  Due to the derivation of R that means k must be unique (well unique with respect to the private key).

Done right there is nothing wrong with using a random k.  It is a cheap and easy way (in theory) to ensure k is unique without having to securely store k.  The issue is that relying on a PRNG has its own sets of risks.  A naive alternative would be to simply pick a random k-seed and increment it for each transaction.  The "k-counter" could be encrypted in the wallet.  That would work but if an attacker sniffed the k value from memory it would allow them to not only compromise the current private key but any private keys used in prior transactions.

RFC6979 is way to ensure unique k values without relying on either a PRNG or keeping a high risk "k counter".

Also they are not stupid questions; ECC is a lot harder to "get" than public key systems based on integer factorization (RSA).  Even now while I "get it" (through a lot of trial and error), I often use incorrect terminology.  Thankfully gmaxwell points them out.  He is one of the few people that I confidently trust his answers.  When he talks about ECC (or crypto in general) I stop and listen.

[DeathAndTaxes]

http://sourceforge.net/p/bitcoin/mailman/message/31306213/

I expect we'll make that change in Bitcoin-QT as a part of the change to libsecp256k1... though the most recent versions of openssl use something like H(message||private||rng_output) as the nonce, so even in the case of RNG failure you don't get a DSA leak.

It's also the case that OpenSSL uses its own internal randomness pool seeded initially from the OS. There isn't any particular reason that you couldn't send your dice input into that, though the seeding interface isn't exposed in Bitcoin currently, though perhaps it should be.

Reading through that message thread it looks like a proposed plan was a compile time flag to enable libsecp256k1.  That was almost six months ago.  What ever happened to that idea?

[gmaxwell]

Reading through that message thread it looks like a proposed plan was a compile time flag to enable libsecp256k1.  That was almost six months ago.  What ever happened to that idea?

It's part of making openssl optional. There are currently a half dozen pull req basically waiting for the release of 0.9.2 to get merged that move that subproject along.

[DeathAndTaxes]

Reading through that message thread it looks like a proposed plan was a compile time flag to enable libsecp256k1.  That was almost six months ago.  What ever happened to that idea?

It's part of making openssl optional. There are currently a half dozen pull req basically waiting for the release of 0.9.2 to get merged that move that subproject along.

Nice to know.  Thanks for the heads up.

[Peter R]

I think a deterministic k-value will be less prone to errors (like the Android repeat k-value bug).  However, RFC6979 seems more complex than it needs to be.  Why can't I just take the 256-bit private key, concatenate it with the 256-bit hash I'm about to sign, apply SHA256 to the resulting 512-bit integer

   k = sha256(private_key || hash_to_sign)

and (assuming 0<k<n) use the resulting hash as my per-message secret number?

[gmaxwell]

I think a deterministic k-value will be less prone to errors (like the Android repeat k-value bug).  However, RFC6979 seems more complex than it needs to be.  Why can't I just take the 256-bit private key, concatenate it with the 256-bit hash I'm about to sign, apply SHA256 to the resulting 512-bit integer
   k = sha256(private_key || hash_to_sign)
and (assuming 0<k<n) use the resulting hash as my per-message secret number?

Because they are trying to do things like avoid extension attacks in hash functions (which all MD structure hash functions have at least in theory), as its a spec which is hash-function neutral. This might lead to things like preparing messages with particular structure to sign that reduce the apparent uniformity of k leading to compromise.  Right away I'd strongly recommend against your simple design and suggest that it be using HMAC-SHA256 instead to close the extension attack concern. Of course, pile on a few more layers of opinion and you probably get the RFC.  Doubly so when you want to be hash function and application independent (e.g. the extension concerns aren't so much of an issue in Bitcoin with sha256 and ... few applications where you'd blindly sign some hash without knowing what it was).

[DeathAndTaxes]

I think a deterministic k-value will be less prone to errors (like the Android repeat k-value bug).  However, RFC6979 seems more complex than it needs to be.  Why can't I just take the 256-bit private key, concatenate it with the 256-bit hash I'm about to sign, apply SHA256 to the resulting 512-bit integer

   k = sha256(private_key || hash_to_sign)

and (assuming 0<k<n) use the resulting hash as my per-message secret number?

I don't believe it would be "wrong" to do that but I would use HMAC-256(private_key, hash_to_sign) over sha256(private_key || hash_to_sign) for a variety of reasons.  More on that below.  The author of RFC 6979 took a very cautious approach and the multiple rounds of HMAC combined with initialization are designed to harden against the leakage of information in the event that partial compromises of the underlying algorithm occur in the future.  Good security looks at not just today's attack vectors but likely future attack vectors based on a detailed understanding of how the security of the algorithm is likely to be degraded through cryptanalysis.  I know enough to know "don't roll your own crypto". The standard is made more complex because it is designed to handle any HMAC, any digest size, any key, any curve parameters, and any message digest.  For Bitcoin all of those are static many of the edge cases are not possible.  This allows you to refactor the standard to produce a simplified one which only works with "Bitcoin" (256 bit hash, 256 bit private key, secp256k1 curve, HMAC-SHA256).  If you take a simple implementation and add in the various hardenings I doubt it will be much simpler than a refactored RFC6979.

Why HMAC-hash over a simple hash?  HMACs are not vulnerable to length extension attacks, and they can reduce the collision vulnerability of the underlying hash.  As an example MD5 is cryptographically broken, but HMAC-MD5 is still robust with no preimage or collision attacks (fastest possible attack is brute force).  I wouldn't recommend anyone use HMAC-MD5 just thinking ahead to the day when SHA-2 might be the next MD5.

One reason to use RFC6979 instead of some "roll your own" is repeatability.  If your hardware device implements RFC6979 an outsider can audit it by having the hardware and another RFC6979 compatible client generate the same transactions and comparing signatures.  If a device uses deterministic signatures AND implements BIP32 with a user supplied seed it becomes a lot more difficulty to build in backdoors to steal from the user.  While any custom implementation could also be tested if you have five different implementations that just means five times the work to test them all.  We could come up with a simplified deterministic signature protocol a BIP and encourage all developers to standardize around that, however even if successful it is very unlikely that "BIP XYZ" will ever be implemented in any major crypto libraries.  RFC6979 is making some progress on that front.  Bouncy castle currently supports it and with enough adoption, OpenSSL, .Net Framework, mono, etc will as well.  This will mean a wider community looking at the codebase and more eyes is always better.

Simple version: When I look at an existing standard I look at it from "Is there any reason why this standard can't be used?"  For RFC6979 the only possible answer is "it is too complex" and for me that isn't sufficient to throw it out in favor of another standard.  Most users (or even developers) will not be implementing RFC6979 by hand, they will hopefully be using well tested libraries.  Test vectors and the deterministic nature combined with the avalanche effect make it a remote chance you could "get it wrong" and still pass unit tests.

Of course this topic wouldn't be complete without:

[christianlundkvist]

Hi all, I looked up the RFC6979 implementation in pybitcointools (line 367) and it is very compact. Like you mention above, the implementation is made a lot easier if we're only considering the bitcoin usecase, so there is not that much complexity in terms of checking code.

I personally also really like the deterministic k for the reasons mentioned earlier:

• Can use a solid randomness source (like dice) for initial high entropy seed and not worry about PRNG,
• Reproducibility, unit testing and standardized test vectors.

[Peter R]

I think a deterministic k-value will be less prone to errors (like the Android repeat k-value bug).  However, RFC6979 seems more complex than it needs to be.  Why can't I just take the 256-bit private key, concatenate it with the 256-bit hash I'm about to sign, apply SHA256 to the resulting 512-bit integer

   k = sha256(private_key || hash_to_sign)

and (assuming 0<k<n) use the resulting hash as my per-message secret number?

I don't believe it would be "wrong" to do that but …..

Simple version: When I look at an existing standard I look at it from "Is there any reason why this standard can't be used?"  For RFC6979 the only possible answer is "it is too complex" and for me that isn't sufficient to throw it out in favor of another standard.  Most users (or even developers) will not be implementing RFC6979 by hand, they will hopefully be using well tested libraries.  Test vectors and the deterministic nature combined with the avalanche effect make it a remote chance you could "get it wrong" and still pass unit tests.

Thanks for the response.  I would likely use RFC6979 for the reasons you said, most importantly because using a standard with unit tests would be more confidence inspiring than some home-spun version.  The problem I encounter on a regular basis is integrating already-written code into 16-bit microcontroller firmware with significant memory and CPU limitations; I'm always asking myself what the simplest way of accomplishing something is.