Deterministic signatures

sipa commented at 3:11 pm on November 6, 2014: member

This implements deterministic (RFC6979-based) signatures using libsecp256k1’s signing. Note that the test cases here were constructed using an earlier version of this patch (which implemented them on top of OpenSSL), so the deterministism has been consistent.

Earlier version of this message: The OpenSSL-based deterministic signing implementation is likely very temporary, as we may switch to libsecp256k1 for signing soon (#5220), but it allows testing. The signatures generated by the OpenSSL and libsecp256k1 based implementations should be identical, so the test cases are already useful.

sipa force-pushed on Nov 6, 2014

sipa commented at 4:36 pm on November 6, 2014: member

Also, here is a sweet canary: bcdf879e47de3b3d93d111d4cada5b59961f51c6879a01ad53df98ae76144b7c

theuni commented at 8:33 pm on November 6, 2014: member

For 0.10, why not take both and verify them against eachother?

gmaxwell commented at 2:46 am on November 7, 2014: contributor

@theuni that would defeat one of the advantages of libsecp2561k: its signing is effectively constant time, openssl currently leaks secret data over cache/timing sidechannels like a sieve.

Verification tests the signature in any case (and doesn’t touch secret data).

sipa commented at 9:25 am on November 10, 2014: member

Note that this implementation is certainly worse in terms of timing leaks than OpenSSL’s own (which takes some steps to prevent those, at least in their current master branch). If we’d want to merge this without libsecp256k1-based signing, it could be improved though.

EDIT: no longer relevant, as this is now using libsecp256k1’s signing.

sipa force-pushed on Nov 10, 2014

sipa commented at 1:23 pm on November 10, 2014: member

Rebased on top of #5256, as it’s otherwise hard to merge with #5220.

sipa commented at 11:58 am on November 12, 2014: member

By the way, the unit tests here were generated using @ciphrex’s CoinCore implementation of RFC6979 with HMAC-SHA256 (https://github.com/ciphrex/CoinVault/blob/5da653249680169822afa3aecd0bcffb2ddf4961/deps/CoinCore/tests/secp256k1/src/secp256k1_rfc6979_test.cpp).

sipa added the label Feature on Nov 18, 2014

sipa added the label Wallet on Nov 18, 2014

laanwj added this to the milestone 0.10.0 on Nov 18, 2014

gmaxwell commented at 5:46 pm on November 18, 2014: contributor

The iter argument is kinda ugly, since thats really not a good way to stir the nonce. I’d find it preferable to xor it into the message input into the PRNG. Of course this is pointless nitpicking since it’s only a testing shim… I did wtf at seeing a nonce += iter in that inner loop.

WRT timing, I think the “takes some steps” is only true in openssl pre-release code. :(

In any case, ACK. (needs preimage for merge)

sipa commented at 5:53 pm on November 18, 2014: member

@gmaxwell I initially wrote it so that the iter argument just skipped the first N outputs of the PRNG. Turns out that that makes the unit tests take many minutes, as some script generations require a few hundred attempts (which becomes squared…).

Mixing it into the message is fine to me.

gmaxwell commented at 6:15 pm on November 18, 2014: contributor

If you do make that change, perhaps also rename the argument to be test_case or something? I’m concerned that someone immitating this code will think that iter is related to nonce retries for out of range nonces. (Though I suppose they may have more problems, like leaving the secret key out.)

sipa commented at 6:35 pm on November 18, 2014: member

I’m not updating the code now, people may already be reviewing it. As you say, it’s only for testing (and the comment in header even says so explicitly).

sipa force-pushed on Nov 19, 2014

sipa commented at 11:35 am on November 19, 2014: member

Rebased on top of #5220 and #5313.

sipa force-pushed on Nov 19, 2014

sipa commented at 11:53 am on November 19, 2014: member

And renamed the argument to test_case as suggested by @gmaxwell.

in src/crypto/hmac_sha256.h: in 6fd1d5505e outdated

0@@ -0,0 +1,32 @@
1+// Copyright (c) 2014 The Bitcoin developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#ifndef BITCOIN_HMAC_SHA256_H

Diapolo commented at 12:29 pm on November 19, 2014:

New format would result in BITCOIN_CRYPTO_HMAC_SHA256_H I guess you should look at the oder headers and end comments, too :). I just will give this single nit, nice, isn’t it ^^?

sipa force-pushed on Nov 19, 2014

sipa commented at 9:18 pm on November 19, 2014: member

Added a commit to make @Diapolo happy.

in src/crypto/rfc6979_hmac_sha256.cpp: in ced61f6c99 outdated

22+    CHMAC_SHA256(K, sizeof(K)).Write(V, sizeof(V)).Finalize(V);
23+}
24+
25+RFC6979_HMAC_SHA256::~RFC6979_HMAC_SHA256()
26+{
27+    memset(V, 0x01, sizeof(V));

theuni commented at 9:42 pm on November 19, 2014:

Isn’t it possible that these will be optimized away by the compiler? Is it worth worrying about?

sipa commented at 9:46 pm on November 19, 2014:

Yup, that’s possible. OpenSSL has OPENSSL_cleanse() for that, which we could use too (but I would prefer crypto to not depend on OpenSSL…).

Ideally, I think we use belt-and-suspenders and let every layer do as much as it can to avoid this sort of leakage (which can’t be 100% avoided anyway, unless you only ever let assembly code touch the confidential data).

gmaxwell commented at 10:21 pm on November 19, 2014:

To add some color there… we could (and perhaps should– I’d be a fan of it) have some extern-ed memsetting function for these cases which we can be sure won’t get optimized away.

However, thats not sufficient: The compiler can randomly stash data from variables into random spots on the stack, the compiler can and commonly will leave data sitting around in registers from where other functions may push them onto the stack (e.g. consider how PUSHA works on x86) and will never zeroize them.

sipa force-pushed on Nov 20, 2014

sipa commented at 2:01 pm on November 20, 2014: member

Rebased.

Split up crypto/sha2 36fa4a78ac

Add HMAC-SHA256 a8f5087e53

Add the RFC6979 PRNG 3060e36098

Deterministic signing a53fd41485

Header define style cleanups 9d8604f36a

sipa force-pushed on Nov 20, 2014

sipa commented at 10:21 am on November 27, 2014: member

Updated the PR description.

laanwj commented at 4:40 pm on November 28, 2014: member

I was looking at 36fa4a78acac0ae6bb0e95c6ef78630120a28bdd and it looks like it is not entirely move-only:

 0@@ -131,8 +123,8 @@ void Transform(uint64_t* s, const unsigned char* chunk)
 1     Round(f, g, h, a, b, c, d, e, 0x431d67c49c100d4cull, w11 += sigma1(w9) + w4 + sigma0(w12));
 2     Round(e, f, g, h, a, b, c, d, 0x4cc5d4becb3e42b6ull, w12 += sigma1(w10) + w5 + sigma0(w13));
 3     Round(d, e, f, g, h, a, b, c, 0x597f299cfc657e2aull, w13 += sigma1(w11) + w6 + sigma0(w14));
 4-    Round(c, d, e, f, g, h, a, b, 0x5fcb6fab3ad6faecull, w14 + sigma1(w12) + w7 + sigma0(w15));
 5-    Round(b, c, d, e, f, g, h, a, 0x6c44198c4a475817ull, w15 + sigma1(w13) + w8 + sigma0(w0));
 6+    Round(c, d, e, f, g, h, a, b, 0x5fcb6fab3ad6faecull, w14 += sigma1(w12) + w7 + sigma0(w15));
 7+    Round(b, c, d, e, f, g, h, a, 0x6c44198c4a475817ull, w15 += sigma1(w13) + w8 + sigma0(w0));
 8
 9     s[0] += a;
10     s[1] += b;

Doesn’t make a difference in practice as wX are local variables that are not used afterwards.

Resize after succesful result 4cdaa95a20

in src/key.cpp: in 9d8604f36a outdated

71@@ -71,19 +72,22 @@ CPubKey CKey::GetPubKey() const {
72     return result;
73 }
74 
75-bool CKey::Sign(const uint256 &hash, std::vector<unsigned char>& vchSig) const {
76+bool CKey::Sign(const uint256 &hash, std::vector<unsigned char>& vchSig, uint32_t test_case) const {
77     if (!fValid)
78         return false;
79     vchSig.resize(72);

laanwj commented at 6:12 pm on November 28, 2014:

Better to move this before secp256k1_ecdsa_sign below, with the nSigLen = 72 line. Otherwise it could theoretically happened that the buffer has been made smaller and receives 72 bytes in a next iteration of the loop.

sipa commented at 8:17 pm on November 28, 2014:

Fixed (in a different way).

in src/crypto/hmac_sha256.cpp: in 4cdaa95a20

29+void CHMAC_SHA256::Finalize(unsigned char hash[OUTPUT_SIZE])
30+{
31+    unsigned char temp[32];
32+    inner.Finalize(temp);
33+    outer.Write(temp, 32).Finalize(hash);
34+}

apoelstra commented at 3:11 pm on November 29, 2014:

This is maybe not worth the hassle, but it’s possible to do this with only a single CSHA256. In Finalize you’d put the output of inner into hash, then reset inner, write the outer key to it, write hash to it, then output to hash. This way you don’t have any non-final HMAC state hanging around in memory after finalization.

sipa commented at 3:13 pm on November 29, 2014:

I prefer keeping an extra SHA256 state in memory than keeping the key in memory.

apoelstra commented at 3:25 pm on November 29, 2014:

Oh, of course. I somehow missed that you avoided storing the key.

in src/crypto/hmac_sha512.cpp: in 4cdaa95a20

29+void CHMAC_SHA512::Finalize(unsigned char hash[OUTPUT_SIZE])
30+{
31+    unsigned char temp[64];
32+    inner.Finalize(temp);
33+    outer.Write(temp, 64).Finalize(hash);
34+}

apoelstra commented at 3:13 pm on November 29, 2014:

Ditto.

apoelstra commented at 4:26 pm on November 29, 2014: contributor

ACK, verified code correctness against my Rust code and the RFC, checked for secret data being left in memory, but did not think about timing since I don’t know the first thing about that. Also ran make check.

gmaxwell commented at 11:45 pm on November 30, 2014: contributor

ACK

laanwj merged this on Dec 1, 2014

laanwj closed this on Dec 1, 2014

laanwj referenced this in commit f0877f8b62 on Dec 1, 2014

SergioDemianLerner commented at 11:15 pm on December 10, 2014: contributor

Does OpenSSL implements RFC6979? I propose that the test cases include the code that implements deterministic signatures over OpenSSL (which Sipa already coded) and compares the results with the test vectors. I cannot validate the correctness of the test vectors without creating such a tool myself. Alternatively, the tool to generate the test vectors from OpenSSL should be part of the source code, stored somewhere. After that I check those test vectors, I ACK this commit.

sipa commented at 11:16 pm on December 10, 2014: member

AFAIK, OpenSSL does not do RFC6979. It just has a means of mixing in the private key and message into the RNG (in addition to the normal randomness) used for generating the nonce.

in src/key.cpp: in 4cdaa95a20

84-        nonce.MakeNewKey(true);
85-        if (secp256k1_ecdsa_sign((const unsigned char*)&hash, 32, (unsigned char*)&vchSig[0], &nSigLen, begin(), nonce.begin()))
86-            break;
87+        uint256 nonce;
88+        prng.Generate((unsigned char*)&nonce, 32);
89+        nonce += test_case;

SergioDemianLerner commented at 11:19 pm on December 10, 2014:

I would prefer not to iterate though all the words of the nonce unnecessarily, even if nothing is changed. It reduces the possibility that part of the nonce is kept in the stack or in registers.

I propose adding: if (test_case) nonce += test_case;

sipa commented at 11:22 pm on December 10, 2014: member

@SergioDemianLerner I created the unit tests using an independent implementation (@Codeshark’s CoinVault/CoinCore).

SergioDemianLerner commented at 11:23 pm on December 10, 2014: contributor

Ok, so I’ll use it.

gmaxwell commented at 11:23 pm on December 10, 2014: contributor

@SergioDemianLerner What pieter said, OpenSSL git (not a release version; release versions are all stright up random) implements a non-standard DSA RNG hardening scheme. The most important thing is that the hash depend on at least the message and a secret, which OpenSSL achieves. Satisifying 6979 is an extra perk.

I believe our test vectors were actually generated with the Ciphrex software rather than the implemention for Bitcoin core.

sipa commented at 0:34 am on December 11, 2014: member

Well if anything, I agree that RFC6979 seems total overkill. One HMAC should have sufficed. But sticking to accepted standards is nice.

Regarding specific concerns: I don’t believe the SHA256 code we have should result in variable-time code on any supported platform. EM or power comsumption… I don’t believe there is any reasonable way to avoid those.

gmaxwell commented at 0:36 am on December 11, 2014: contributor

Additions are constant time up to my ability to measure on the platforms we support. If they are not constant time, then all bets are off for timing sidechannel immunity anywhere in the signature system. That hashing the key may have some sidechannel leak is very small concern compared to any place else there where there could be (or would be) a timing sidechannel. (Multiplies are also constant time on the platforms we currently support, though I believe (some) PPC has non-constant time multiplies).

They are almost certantly not constant power (in general without special differential logic it’s impossible to be especially strong against power sidechannels), but again, the concern in the hash is very small compared to the potential for leaks elsewhere in the signature process, which likely have much stronger power signatures. (unfortunately the only scopes and spectrum analizer I have only go to 100MHz, which isn’t really sutiable for exploring power sidechannels on modern hardware :) )

gmaxwell commented at 0:38 am on December 11, 2014: contributor

But sticking to accepted standards is nice.

Not just nice, but producing a common reproducable output means that you can do diverse signing with multiple signers to guard against nonce covert channel backdooring.

It also provides some assurance against things like insiders intentionally making the nonce H(message) in order to leak keys.

SergioDemianLerner commented at 0:47 am on December 11, 2014: contributor

Sorry about deleting my post. I didn’t want to waste your time. But since you’ve responded, I leave it here for consistency of the conversation.

I don’t like RFC6979. I know I’m being terrible audacious by this assertion. But I don’t like the way the key is mapped into the SHA-256 key schedule. The value V (32 bytes long) ends up at the beginning of the compression block, so that the key ends up being combined with mostly fixed bytes with sparse ones. E.g. w[16], w[17] … could be susceptible to timing attacks if the addition operation has variable time depending on the number of carries. Also electromagnetic and power consumption side-channels could be used to detect those carries. Again, this is pure speculation, but I think the key should have been laid at the beginning of the compression block, and not after a fixed known mostly-zero pattern

SergioDemianLerner commented at 0:52 am on December 11, 2014: contributor

Still, if I could change RFC6979, I would make K = key at the beginning, and not part of the message, instead of K = zero.

gmaxwell commented at 0:55 am on December 11, 2014: contributor

Yea, I would have done that in terms of a preitter construction. I suspect the authors of 6979 would have done that too, but I believe what they wanted to do was to take a pre-existing, standardized, construction for a CSPRNG and turn it into a standard for derandomized DSA without any change that might have introduced an application specific weakness.

(No biggie on the response. Messages cross in flight on github all the time. Sometimes both parties will just remove their responses and move on. :) )

laanwj referenced this in commit c6a5ad4819 on Jan 8, 2015

MarcoFalke locked this on Sep 8, 2021

Deterministic signatures #5227