Always create signatures with Low R values

achow101 commented at 5:10 am on July 15, 2018: member

When creating signatures for transactions, always make one which has a 32 byte or smaller R and 32 byte or smaller S value. This results in signatures that are always less than 71 bytes (32 byte R + 32 byte S + 6 bytes DER + 1 byte sighash) with low R values. In most cases, the signature will be 71 bytes.

Because R is not mutable in the same way that S is, a low R value can only be found by trying different nonces. RFC 6979 for deterministic nonce generation has the option to specify additional entropy, so we simply use that and add a uin32_t counter which we increment in order to try different nonces. Nonces are sill deterministically generated as the nonce used will the be the first one where the counter results in a nonce that results in a low R value. Because different nonces need to be tried, time to produce a signature does increase. On average, it takes twice as long to make a signature as two signatures need to be created, on average, to find one with a low R.

Having a fixed size signature makes size calculations easier and also saves half a byte of transaction size, on average.

DUMMY_SIGNATURE_CREATOR has been modified to produce 71 byte dummy signatures instead of 72 byte signatures.

fanquake requested review from sipa on Jul 15, 2018

in src/test/data/script_tests.json:1407 in d7be065a0b outdated

1403@@ -1404,14 +1404,14 @@
1404     "P2PK with too much S padding"
1405 ],
1406 [
1407-    "0x47 0x30440220d7a0417c3f6d1a15094d1cf2a3378ca0503eb8a57630953a9e2987e21ddd0a6502207a6266d686c99090920249991d3d42065b6d43eb70187b219c0db82e4f94d1a201",
1408+    "0x47 0x3044022093c20fae34ef6ba13038515d18ece7374141b3f051e2cb93a78e4fd7f4e63f34022075037b8f491c746f92318816314c9269679d8702161b9c541f95bd9f029b3ac401",

sipa commented at 5:26 am on July 15, 2018:

Why are these tests changing?

achow101 commented at 5:50 am on July 15, 2018:

I assume that they are changing because they are signatures produced with an extra entropy value of 0 (provided by the test case, not the signing method). However in the signing method, an entropy value of 0 has the same meaning as no extra entropy provided which means that the signature will be ground for low R. So in order to get high R, the extra entropy value will need to increment so that a high R signature can be found which is going to result in a different signature.

sipa commented at 5:57 am on July 15, 2018:

Perhaps you should split up the signing method into a grinding and a manual one, so the tests can keep creating the old method with provided entropy rather than grindjng?

achow101 commented at 7:30 am on July 15, 2018:

I changed it to have a grind boolean to indicate whether grinding should be used. This results in those tests not changing now.

luke-jr commented at 6:02 am on July 15, 2018: member

Does this reduce the entropy of the nonce? To what degree?

sipa commented at 6:04 am on July 15, 2018: member

@luke-jr By around 1.0226 bits.

achow101 force-pushed on Jul 15, 2018

sipa commented at 6:23 pm on July 15, 2018: member

utACK af049b2b52a93dcd05a78c381510534b0c52b4de

I believe there are no downsides to this, except for making the signing time double on average. It reduces the entropy in the nonce slightly, but not in a way that is usable to an attacker as far as I can tell.

Comments, @gmaxwell, @apoelstra ?

gmaxwell commented at 8:38 pm on July 15, 2018: contributor

It seems weird– wasteful and needlessly more identifiable– to not emit a smaller signature when one shows up. That seems like a bad idea to me. Why not just check that the R size is <=32 bytes? Sometimes you’ll be smaller and ‘overpay’ fee– yes, but you’ll at least get extra priority for your cost. If you instead throw out that candidate signature, you’ll still pay the same, but not get the improved priority. With that changed (or convincing me that I’m wrong), this would get a concept ACK from me.

I see no security problem from doing this, though the grinding could made ~3x faster by using the endomorphism.

I was going to argue that it should shave another byte off, but sipa pointed out to me that it would be plenty fast for us (esp with optimized code), it’s a lot less likely that anyone else would implement that kind of signing. I think that a great point, and implementing ’lowR’ certainly gets the most bang for the computational buck. It might make sense to deploy at the same time as some other change that makes our transactions more identifiable (perhaps the recent coinselection changes count).

sipa commented at 8:44 pm on July 15, 2018: member

I see no security problem from doing this, though the grinding could made ~3x faster by using the endomorphism.

I believe that doing so would introduce an (additional) bias in the resulting nonce. For example, in groups of 3 points related by multiplication by beta, if only two are low-R, one will be chosen 2/3rd of the time, and the other will be chosen 1/3rd of the time. I don’t see a way to exploit that, but it feels scary.

Out of every 24 points, instead of having 12 with probability 1/12, there will be 3 with probability 1/7, 3 with probability 2/21, and 6 with probability 1/21; overall 0.1576 bits entropy less.

achow101 force-pushed on Jul 16, 2018

achow101 commented at 6:46 pm on July 16, 2018: member

I have changed this to allow signatures less than 71 bytes and fixed/added tests for this.

achow101 renamed this:
~~Always create 71 byte signatures with Low R values~~
Always create signatures with Low R values
on Jul 16, 2018

achow101 force-pushed on Jul 16, 2018

sipa commented at 11:03 pm on July 16, 2018: member

utACK 9b7e6e9f0efc74d4f1576802494b5b7966699949

gmaxwell commented at 4:36 pm on July 17, 2018: contributor

You should also change DummySignatureCreator() and all the comments in wallet.cpp talking about the dummy signatures being 72 bytes, no?

sipa commented at 9:46 pm on July 17, 2018: member

@gmaxwell The change to DummySignatureCreator is already included here.

gmaxwell commented at 0:36 am on July 18, 2018: contributor

Hm. Weird, I see it now, dunno why I missed it before.

gmaxwell commented at 7:06 pm on July 18, 2018: contributor

ACK

achow101 force-pushed on Jul 18, 2018

achow101 commented at 7:27 pm on July 18, 2018: member

Rebased onto master and removed a psbt signing test that has a high R value (signing is still tested with the other test vector that has low R). Also updated comments in wallet.

JeremyRubin commented at 7:52 pm on July 18, 2018: contributor

Noting that the search is easily parallelizable without loss of determinism. With this, we can pretty comfortably ignore the overhead for most users.

A separate concern is this makes hardware wallets more identifiable if this is difficult for them to implement.

gmaxwell commented at 0:56 am on July 19, 2018: contributor

@JeremyRubin each trial has a 50% probability of success the search tries 2 values on average, it wouldn’t make sense to parallelize. :) and should be okay for any hardware wallet.

laanwj added this to the milestone 0.17.0 on Jul 19, 2018

JeremyRubin commented at 10:21 pm on July 19, 2018: contributor

If I’m not mistaken (my EC math knowledge isn’t amazing), could you re-use (k X G) and k^-1 by doing the search via doubling rather than increment.

Suppose

k’ = 2k, then k’ x G = 2k x G = k x G + k x G

now k’^-1 = 2^-1 k^-1

Not sure if this further reduces the entropy of the nonce too much, but the same optimization also eliminates an ec mul for k’ = k+1.

sipa commented at 10:42 pm on July 19, 2018: member

@JeremyRubin That loses another 0.2885 bits of entropy (1 in 2^N nonces will have N times higher probability). Though in general, I’m really uncomfortable with anything but a uniform distribution (over a sufficiently large subset of acceptable values). See https://www.wolframalpha.com/input/?i=255+-+sum(i%2F2%5E256*log(i%2F2%5E256)*2%5E(255-i),i%3D1…infinity)%2Flog(1%2F2)

JeremyRubin commented at 1:42 am on July 20, 2018: contributor

@sipa just k’=k+1 and eliminating an ec mul shouldn’t lose any additional entropy, though not sure what percent of the compute time k’G is.

In general, I’m not sure it is worth it to lose any entropy for signature time, but .2885 isn’t much (nor is the endomorphism thing @gmaxwell mentioned).

I think it would be good to provide a strong rationale in this PR on exactly how much entropy is tolerable to drop (e.g. why 1.0226 bits is OK and not 1.3111 bits). Dropping any entropy seems like a non-starter to me.

I’m also curious if there’s an opportunity to leak entropy out of this as a timing attack. If the attacker can make unlimited requests, they can clearly figure out the difference between a msg that (deterministically) takes one signing time and two signing times (or more) by making a historgram of the signing times. From there, they can figure out whether the first or not-first R value was small. This should reduce the space by at least a bit, if not more – for instance if we infer that it took 10 signature attempts (which should happen once in 1024 attempts), we reduce the nonce space for that message by 1/1024.

sipa commented at 1:54 am on July 20, 2018: member

@JeremyRubin Using k' = k + 1 has the same loss of entropy. For example if a particular nonce k has a corresponding low-R, and the 6 nonces before it (k-6…k-1) all have high-R, then that nonce has 7 times more chances to be chosen than one where k-1 is also low-R.

sipa commented at 1:57 am on July 20, 2018: member

for instance if we infer that it took 10 signature attempts (which should happen once in 1024 attempts), we reduce the nonce space for that message by 1/1024.

Yes, indeed. Information theoretically this is a leak. But the only way an attacker can find out whether a particular nonce is in that subset of 1/1024 is by doing 10 EC multiplications on the preceeding nonces… the exact operation we’re trying to make expensive.

achow101 commented at 2:03 am on July 20, 2018: member

I think it would be good to provide a strong rationale in this PR on exactly how much entropy is tolerable to drop (e.g. why 1.0226 bits is OK and not 1.3111 bits). Dropping any entropy seems like a non-starter to me.

The actual entropy loss is 1 bit exactly. The 0.0226 comes from a previous version of this PR where all signatures had to be 71 bytes. With that now removed, only 1 bit of entropy is lost.

JeremyRubin commented at 3:48 am on July 20, 2018: contributor

@sipa ah thanks, they key information I was missing was that the counter goes through a hash (it’s not just directly put on the curve).

Sjors commented at 11:49 am on July 20, 2018: member

Should there be an informational BIP for this to make it more likely other wallets do the same? Any feedback on that BIP might have to wait for the next release to be implemented, but perhaps some obvious problem is found in time.

At the same time, it might be useful to propose replacement test vectors for BIP-174, rather than deleting them. I’m sure you and the author get along well :-P

Grinding seems to ~ double the amount of data about the private key the wallet gives to a side-channel attacker. Is that an issue, or do all conceivable side-channel attacks require many orders of magnitude more signing operations so that doubling has insignificant impact? And does that apply to less rigorous alternative implementations?

laanwj added the label Wallet on Jul 20, 2018

sipa commented at 7:13 pm on July 20, 2018: member

@Sjors I think that’s a good idea, actually. There are clearly several questions in this thread about which specific variant to use, and the trade-offs, so I think it would be good to have it written up somewhere. That would also make it easy to point to, or to have a write-up we can ask expert advice about.

Doing so also gives us the opportunity to drop RFC6979 and favor of a faster construction (RFC6979 is very much overkill).

The question is whether that should stand in the way of implementing this PR (which wouldn’t be following such a spec, it’s too ad hoc I think).

Sjors commented at 7:50 am on July 21, 2018: member

I’d say there’s two separate goals:

Get more eyes on this specific change before it’s irreversible (e.g. it could be merged, but removed from a 0.17rc)
Come up with an even better approach for a future next release (can blend in with whatever coin selection changes are ready then)

So maybe hold off on the BIP and just drop a summary of this thread on the bitcoin-dev list?

gmaxwell commented at 5:39 pm on July 21, 2018: contributor

This isn’t really very important one way or another, but I think it’s not good for the project that every single little thing takes forever for no obvious reason. There isn’t anything meaningful that would change about this– sure, someone might optimize it further by not using 6979 or whatnot, but at the end of the day instead of flipping a coin once, it flips it until it comes up tails. And anything similar is going to do the same.

I think our time would be better spent working on other improvements than debating and documenting this one forever.

sipa commented at 9:13 pm on July 21, 2018: member

@gmaxwell That’s fair; there is no observable difference between generating nonces one way or another as long as the success condition is the same (low R). I’m mostly wondering if people are ok with changing signatures once and then changing them again if/when there would be a more widely adopted standard.

maaku commented at 7:08 pm on July 23, 2018: contributor

I am not in favor of this change. It would add a way of (statistically) differentiating Bitcoin’s wallet from other signers and it is unlikely that all implementations will switch to this scheme. In particular there are potential improvements that could be made to hardware wallets to export a bulletproof that the nonce was selected according to a specified deterministic algorithm. Adding additional constraints like this blow up proof generation time and size by a significant factor for a low power signing devices. And if forced with a choice, I’d much rather have the ability to verify my hardware wallet is not leaking bits of key material than save one measly byte of witness data, on average.

gmaxwell commented at 7:24 pm on July 26, 2018: contributor

I am not in favor of this change. It would add a way of (statistically) differentiating Bitcoin’s wallet from other signers

Other changes in the current version make its transactions identifyable, so for the moment I think that concern is mostly moot. The expectation here is that other wallets would also adopt this change over time. This is the reason that it doesn’t shave an additional byte off too: it’s less realistic to expect others to imitate that functionality.

In particular there are potential improvements that could be made to hardware wallets to export a bulletproof that the nonce was selected according to a specified deterministic algorithm

Rerunning RFC6979 every time is a lot slower, but a BP that the nonce is H(x||m) + [0..256] would be hardly any more expensive that the nonce is H(x||m). And unfortunately, I’ve yet to see any hardware wallet with resources within two orders of magnitude needed for this.

Unrelated, I’m not aware of any reason that the sign-2-contract fix for nonce sidechannels isn’t just as effective as a BP… and it’s actually computationally reasonable on existing hardware… and would still work with this approach.

Sjors commented at 9:06 am on July 27, 2018: member

I wrote:

Grinding seems to ~ double the amount of data about the private key the wallet gives to a side-channel attacker.

But that’s not true. Unlike when deriving a public key Q = d × G, where you could determine d by monitoring a device that performs this elliptic curve multiplication multiple times (with a not perfectly time-constant implementation ), for signatures the private key isn’t used in such multiplication. Only a random nonce k is, which is completely different on each attempt. @gmaxwell wrote:

I think it’s not good for the project that every single little thing takes forever for no obvious reason. There isn’t anything meaningful that would change about this

That’s not the primary reason I’m in favor of posting this on a mailinglist, although I do think it’s useful to give other wallet developers guidance on this topic in the form of a BIP. My bigger concern is that in cryptography it’s easy to make a mistake if you don’t know what you’re doing. Obviously @achow101 knows what he’s doing and you and @sipa are able to tell that this particular change is safe. But it’s hard for me to verify what makes a simple change safe and what doesn’t.

maaku commented at 11:15 pm on August 2, 2018: contributor

@gmaxwell wrote:

Unrelated, I’m not aware of any reason that the sign-2-contract fix for nonce sidechannels isn’t just as effective as a BP… and it’s actually computationally reasonable on existing hardware… and would still work with this approach.

Can you expand on this? What “sign-2-contract fix for nonce side channels”? It might be the case this is something you’ve explained to me before, but it’s not coming to mind.

sipa commented at 11:41 pm on August 2, 2018: member

@maaku

HW device generates a nonce k (deterministically from msg/privkey, or with real RNG).
HW device computes R = kG and sends it to host device.
Host device generates randomness c (possibly based on R), and sends it in plain text to HW device.
HW device computes k' = H(R, c) + k and R' = H(R, c)G + R, and uses those in the signature it produces.
HW device sends the signature and R to the host device.
The host device recomputes R' = H(R, c)G + R (taking R' from the signature itself) which guarantees that its randomness c was included in the signature.

An attacker needs to control both devices in order to leak information through the nonce now. The HW device can’t even grind without the host machine knowing.

laanwj commented at 11:23 am on August 7, 2018: member

One question I have here: With the PSBT work, would this affect potential usage of bitcoin core with hardware wallets that do not implement this specific trick and might still generate 72-byte signatures?

sipa commented at 4:23 pm on August 7, 2018: member

@laanwj That’s a good point. Perhaps we should still count the size of unknown signatures in DummySignatureCreator as 72 rather than 71, to account for the possibility that external signers produce 72 bytes?

achow101 commented at 4:47 pm on August 7, 2018: member

Perhaps we should still count the size of unknown signatures in DummySignatureCreator as 72 rather than 71, to account for the possibility that external signers produce 72 bytes?

I think that kind of defeats the purpose of this change. Since the DummySignatureCreator is only used for fee estimation of unsigned transactions, perhaps we could make it work so that it uses 72 bytes for inputs that we cannot sign for, and 71 bytes for inputs that we can sign for?

in src/wallet/wallet.cpp:1523 in d8e6ed1209 outdated

1522 
1523-    if (!ProduceSignature(*this, DUMMY_SIGNATURE_CREATOR, scriptPubKey, sigdata))
1524-    {
1525-        return false;
1526+    if (use_max_sig) {
1527+        if (ProduceSignature(*this, DUMMY_MAXIMUM_SIGNATURE_CREATOR, scriptPubKey, sigdata)) {

sipa commented at 0:05 am on August 8, 2018:

You can write this much more compactly using a conditional

0If (ProduceSignature(*this, use_max_sig ? DUMMY_MAXIMUM_SIGNATURE_CREATOR : DUMMY_SIGNATURE_CREATOR, scriptPubKey, sigdata)) {

achow101 commented at 0:21 am on August 8, 2018:

Done

in src/wallet/wallet.cpp:1569 in d8e6ed1209 outdated

1575-    if (!wallet->DummySignTx(txNew, txouts)) {
1576+    if (!wallet->DummySignTx(txNew, txouts, use_max_sig)) {
1577         // This should never happen, because IsAllFromMe(ISMINE_SPENDABLE)
1578         // implies that we can sign for every input.
1579-        return -1;
1580+        return -2;

sipa commented at 0:19 am on August 8, 2018:

Why?

achow101 commented at 0:25 am on August 8, 2018:

Oops, forgot to remove some of my debugging stuff. Fixed

in src/script/sign.cpp:429 in d8e6ed1209 outdated

424@@ -425,28 +425,33 @@ class DummySignatureChecker final : public BaseSignatureChecker
425 const DummySignatureChecker DUMMY_CHECKER;
426 
427 class DummySignatureCreator final : public BaseSignatureCreator {
428+private:
429+    char r_len = 32;

sipa commented at 0:20 am on August 8, 2018:

Variable naming style nit: m_r_len.

achow101 commented at 0:27 am on August 8, 2018:

Fixed

achow101 force-pushed on Aug 8, 2018

achow101 commented at 0:22 am on August 8, 2018: member

I pushed a commit that switches between 71 and 72 byte signatures depending on whether watching only inputs can be selected.

in src/script/sign.cpp:457 in 598e796595 outdated

456     }
457 };
458 }
459 
460 const BaseSignatureCreator& DUMMY_SIGNATURE_CREATOR = DummySignatureCreator();
461+const BaseSignatureCreator& DUMMY_MAXIMUM_SIGNATURE_CREATOR = DummySignatureCreator(33, 32);

sipa commented at 0:22 am on August 8, 2018:

Maybe you can drop the default constructor, and just specify the actual sizes in for both instances?

achow101 commented at 0:27 am on August 8, 2018:

Done

achow101 force-pushed on Aug 8, 2018

DrahtBot commented at 5:07 am on August 8, 2018: member

#13917 (Additional safety checks in PSBT signer by sipa)
#13723 (PSBT key path cleanups by sipa)
#13268 (Consistently bounds-check vin/vout access by Empact)
#11634 (wallet: Add missing cs_wallet/cs_KeyStore locks to wallet by practicalswift)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in src/key.cpp:202 in b43b651e2a outdated

193+// Check that the sig has a low R value and will be less than 71 bytes
194+bool SigHasLowR(const secp256k1_ecdsa_signature* sig)
195+{
196+    unsigned char compact_sig[64];
197+    secp256k1_ecdsa_signature_serialize_compact(secp256k1_context_sign, compact_sig, sig);
198+    return compact_sig[0] < 0x80;

kallewoof commented at 11:41 pm on August 9, 2018:

In “Always create 70 byte signatures with low R values”:

A comment explaining why the first byte being < 0x80 means the signature has a low R would be useful, unless this is blindingly obvious to everyone else.

achow101 commented at 1:22 am on August 10, 2018:

Done

in src/key.cpp:214 in b43b651e2a outdated

211+    int ret = secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, (!grind && test_case) ? extra_entropy : nullptr);
212+
213+    // Grind for low R
214+    while (ret && !SigHasLowR(&sig) && grind) {
215+        WriteLE32(extra_entropy, ++counter);
216+        ret &= secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, extra_entropy);

kallewoof commented at 11:49 pm on August 9, 2018:

In “Always create 70 byte signatures with low R values”:

Nit: &= unnecessary, can just use =, ret is always true (though compilers will most likely figure this out and optimize away).

achow101 commented at 1:22 am on August 10, 2018:

Done

in src/wallet/wallet.h:511 in 7e425fa211 outdated

496@@ -497,20 +497,23 @@ class COutput
497     /** Whether we know how to spend this output, ignoring the lack of keys */
498     bool fSolvable;
499 
500+    /** Whether this output is a watch-only output */
501+    bool use_max_sig;

kallewoof commented at 0:01 am on August 10, 2018:

In “Use 72 byte dummy signatures when watching only inputs may be used “:

I know this flag is used for watch-only outputs, but that’s not what the flag is, it’s a flag that uses the 72 byte dummy signature instead of the 71 byte one. Noting that this is enabled when output is watch-only is useful, of course.

achow101 commented at 1:22 am on August 10, 2018:

Fixed

kallewoof commented at 0:03 am on August 10, 2018: member

utACK 7e425fa2114674578522291a57fd7eec02f16b28

achow101 force-pushed on Aug 10, 2018

in src/key.cpp:199 in 069c879576 outdated

195+{
196+    unsigned char compact_sig[64];
197+    secp256k1_ecdsa_signature_serialize_compact(secp256k1_context_sign, compact_sig, sig);
198+
199+    // In DER serialization, all values are interpreted as big-endian, signed integers. The highest bit in the integer indicates
200+    // it's signed-ness; 0 is positive, 1 is negative. When the value is interpreted as a negative integer, it must be converted

kallewoof commented at 1:25 am on August 10, 2018:

Nit: its signed-ness

achow101 commented at 1:40 am on August 10, 2018:

Fixed

in src/key.cpp:220 in 069c879576 outdated

217+
218+    // Grind for low R
219+    while (ret && !SigHasLowR(&sig) && grind) {
220+        WriteLE32(extra_entropy, ++counter);
221+        ret = secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, extra_entropy);
222+    }

kallewoof commented at 1:30 am on August 10, 2018:

Maybe overkill, but you could in theory do

0while (secp256k1_ecdsa_sign(secp256k1_context_sign, &sig, hash.begin(), begin(), secp256k1_nonce_function_rfc6979, (counter || (!grind && test_case)) ? extra_entropy : nullptr)
1    && !SigHasLowR(&sig) && grind) {
2    WriteLE32(extra_entropy, ++counter);
3}

to replace

https://github.com/bitcoin/bitcoin/blob/069c87957660adda97083fb77a48cbbcec253418/src/key.cpp#L214-L220

achow101 commented at 1:39 am on August 10, 2018:

I’d rather not. It’s kind of hard to read (at least to me).

kallewoof commented at 1:32 am on August 10, 2018: member

utACK w/ a typo and suggestion. Feel free to ignore.

Always create 70 byte signatures with low R values

When extra entropy is not specified by the caller, CKey::Sign will
now always create a signature that has a low R value and is at most
70 bytes. The resulting signature on the stack will be 71 bytes when
the sighash byte is included.

Using low R signatures means that the resulting DER encoded signature
will never need to have additional padding to account for high R
values.

18dfea0dd0

Use 71 byte signature for DUMMY_SIGNATURE_CREATOR

Changes DUMMY_SIGNATURE_CREATOR to create 71 byte dummy signatures.

Update comments to reflect this change

48b1473c89

Use 72 byte dummy signatures when watching only inputs may be used

With watching only inputs, we do not know how large the signatures
for those inputs will be as their signers may not have implemented
71 byte signatures. Thus we estimate their fees using the 72 byte
dummy signature to ensure that we pay enough fees.

This only effects fundrawtransaction when includeWatching is true.

e306be7429

achow101 force-pushed on Aug 10, 2018

kallewoof approved

kallewoof commented at 2:19 am on August 10, 2018: member

utACK e306be742932d4ea5aca0ea4768e54b2fc3dc6a0

gmaxwell commented at 5:56 am on August 10, 2018: contributor

Re-ACK

sipa commented at 10:31 pm on August 10, 2018: member

utACK e306be742932d4ea5aca0ea4768e54b2fc3dc6a0

laanwj merged this on Aug 13, 2018

laanwj closed this on Aug 13, 2018

ken2812221 referenced this in commit 2115cba9c6 on Aug 13, 2018

sipa added the label Needs release notes on Aug 14, 2018

laanwj commented at 3:31 pm on August 14, 2018: member

@JeremyRobin commented the following:

I’m also curious if there’s an opportunity to leak entropy out of this as a timing attack. If the attacker can make unlimited requests, they can clearly figure out the difference between a msg that (deterministically) takes one signing time and two signing times (or more) by making a historgram of the signing times. From there, they can figure out whether the first or not-first R value was small. This should reduce the space by at least a bit, if not more – for instance if we infer that it took 10 signature attempts (which should happen once in 1024 attempts), we reduce the nonce space for that message by 1/1024.

I don’t think this was addressed, is this a potential issue?

sipa commented at 4:03 pm on August 14, 2018: member

We had a discussion about this on IRC with @gmaxwell and @JeremyRubin. While I think it would be good to document this reasoning, I’ll summarize here:

RFC6979 itself specifies a very similar form of iteration to produce nonces, to make sure they are in the valid range (between 1 and the group’s order). For secp256k1 this is not observable, as the order is so close to a power of 2 (2256 - 232 - 977), but for other curves it is an actually practically observable bias. Clearly the authors of RFC6979 did not consider this to be an issue.
The information “whether or not the first generated nonce was Low-R” was already available in the old scheme as well, by virtue of revealing the first R value (in cases where the old scheme produces a Low-R, the new scheme will have 1 iteration; in cases where the old scheme produces a High-R, the new scheme will have 2 or more iterations). The only additional information to a timing attacker in the new scheme is how many iterations were needed (if more than 1).
In general, to meaningfully reduce the nonce space for an attacker, requires in the order of 2256 hashing operations. This is far slower than a direct ECDLP attack on the R point or public key itself. As the information does not lead to a more efficient attack, it does not reduce security.

Anything I’m missing?

junderw commented at 8:44 am on August 20, 2018: contributor

Clarification request:

Ref: https://tools.ietf.org/html/rfc6979#section-3.2

In 3.2 d and f. it states:

0d:
1K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
2f:
3K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))

but in the case where r is >= 2^255 we must re-try the RFC6979 k generation this time with the extra_entropy set to 1 (since when counter is set to 0, extra_entropy becomes nullptr, and the WriteLE32(extra_entropy, ++counter) is using ++ beforehand) and the following is done. shown below:

0d:
1K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || int2octets(extra_entropy))
2f:
3K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1) || int2octets(extra_entropy))

@sipa just checking, but is the appended buffer for extra_entropy big endian? Edit: nvm WriteLE32 32 byte Little Endian… rtfm

bitcoinhodler referenced this in commit 8259c477b7 on Aug 22, 2018

junderw referenced this in commit 0228dbdc44 on Aug 23, 2018

azuchi referenced this in commit 8ffc908a5d on Nov 28, 2018

azuchi referenced this in commit 157246a128 on Nov 28, 2018

fanquake removed the label Needs release note on Mar 20, 2019

SomberNight referenced this in commit d16fd2783c on Dec 5, 2019

roth-a referenced this in commit 18a7b125ac on Feb 1, 2020

kittywhiskers referenced this in commit e14701d349 on Jun 4, 2021

kittywhiskers referenced this in commit 18ae7a1b35 on Jun 4, 2021

UdjinM6 referenced this in commit bd7e39514f on Jun 7, 2021

barrystyle referenced this in commit acb122e6cf on Jun 8, 2021

barrystyle referenced this in commit 9166796714 on Jun 8, 2021

kittywhiskers referenced this in commit b6bbfdf82a on Jun 9, 2021

MarcoFalke referenced this in commit 74013641e0 on Jun 21, 2021

sidhujag referenced this in commit fbdbdc0e1d on Jun 24, 2021

UdjinM6 referenced this in commit 85b284ebdd on Jul 4, 2021

UdjinM6 referenced this in commit 57fce04399 on Jul 6, 2021

UdjinM6 referenced this in commit 90154c6074 on Jul 6, 2021

kittywhiskers referenced this in commit a651d03e90 on Jul 9, 2021

kittywhiskers referenced this in commit aac6aacfaf on Jul 13, 2021

kittywhiskers referenced this in commit e42afa4795 on Jul 13, 2021

kittywhiskers referenced this in commit 472cfcbf7f on Jul 13, 2021

PastaPastaPasta referenced this in commit e98241da5d on Jul 13, 2021

DrahtBot locked this on Dec 16, 2021

Always create signatures with Low R values #13666