Skip to content

Instantly share code, notes, and snippets.

@moonsettler
Last active August 26, 2024 10:20
Show Gist options
  • Save moonsettler/d4eb59c62a2b8f104c72603231b73a41 to your computer and use it in GitHub Desktop.
Save moonsettler/d4eb59c62a2b8f104c72603231b73a41 to your computer and use it in GitHub Desktop.
Non interactive anti-exfil

Signing protocol:

x: private key
X: public key
m: message to sign
n: nonce extra

H: cryptographically secure hash committment

1. signing device

q = H(x,m,n)
Q = q·G
k = q + H(Q,m,n)
R = k·G
e = H(R,X,m)

Schnorr signature

s = k + x·e

ECDSA signature

r = R.x
s = k⁻¹·(m + r·x)

2. return to wallet app

Q, s

3. wallet app calculates

R = Q + H(Q,m,n)·G
R, s

4. verify

Schnorr verify

e = H(R,X,m)

s·G ?= R + e·X

ECDSA verify

r = R.x

s⁻¹·m·G + s⁻¹·r·X ?= R

Q&A

Where does the SD get n from?

Typically an opensource "Companion App" or view only wallet software would provide the n nonce extra.

The PSBT standard can either be extended with a new field, or n may be included as an invalid but recognizable "signature" that the SD replaces with (Q,s).

What is the function of H, why not simply hash the concatenated values?

m1 = "hello ", n1 = "world!"
m2 = "hello", n2 = " world!"
q = hash(x|"hello world!")
Q = q·G
k = q + hash(Q|"hello world!")

Would generate the exact same nonce, but the SD would sign a different message ("hello " and "hello"), allowing malicious software to extract the private key from the device.

s1 = k + x·e1
s2 = k + x·e2
s1 - s2 = (k - k) + x(e1 - e2)

With k eliminated, the private key x is revealed to the malicious software.

What function is appropriate as H?

With fixed sized fields/values hash(v1|v2|..|vn) can be safely used.

With variable size binary strings:

  • hash(serialize(v1, v2, .., vn))
  • hash(hash(v1)|hash(v2)|..|hash(vn))
  • merkle_root(v1, v2, .., vn)

Any reversible serialization may also be used.

For example: hash(6|"hello "|6|"world!") != hash(5|"hello"|7|" world!")

What is the reason for committing to n in generation of q?

Let's take a look at what happens, when we sign the same message twice, with different nonce extras!

q = H(x,m)
Q = q·G
s1 = q + H(Q,m,n1) x·e1
s2 = q + H(Q,m,n2) x·e2
s1 - s2 = (q - q) + H(Q,m,n1) - H(Q,m,n2) + x(e1 - e2)

With q eliminated, the private key x is revealed to the malicious software.

Are low bandwidth attacks still possible?

Yes, theoretically the SD with malicious firmware could churn the final R point to leak information using for example FEC codes (Pieter Wuille on delving) with 2n rounds of churning SD can leak the seed phrase by creating bits(seed)/n signatures. For example if the attacker chooses to leak 4 bits each time it takes 32 signatures to leak a 128 bit (12 word) seed phrase. Due to the public transaction graph and plainly observable wallet characteristics the attacker can make good guesses at which signatures could belong to the same seed.

  • The attacker can just generate a random q, normally this can not be detected
  • The verifier needs to know the private key to verify generation of q (same as RFC6979)
  • The attacker can encrypt and obfuscate his own channel
  • The attacker decides his channel bandwidth making it impossible to estimate "seed health"
  • Transactions may have multiple inputs making signing them not deterministic in time
  • Said attack is likely to be "always on" and would be caught by verifying generation of q
  • Evil maid scenario is still problematic, factory and user acceptance tests are already passed
  • Tamper evident storage of signing devices is still heavily recommended
  • This is not a huge concern for cold storage scenarios with very infrequent signing
  • This protocol offers protection from immediate catastrophic leaks via chosen nonce
  • 24 words are better in this scheme than 12 words

References

  1. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-March/017667.html (Pieter Wuille 2020)
  2. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017649.html
  3. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017655.html
  4. https://blog.eternitywall.com/2018/04/13/sign-to-contract/
  5. https://bitcointalk.org/index.php?topic=893898.msg9861102#msg9861102
  6. https://bitcointalk.org/index.php?topic=893898.msg9841502#msg9841502
  7. https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199
  8. https://youtu.be/j9Wvz7zI_Ac?t=640
  9. https://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2019-02-04-threshold-signatures-and-accountability/
  10. bitcoin-core/secp256k1#590
  11. bitcoin-core/secp256k1#669
  12. https://eprint.iacr.org/2017/985
  13. https://moderncrypto.org/mail-archive/curves/2017/000925.html
@moonsettler
Copy link
Author

Very nice!

Can you tell me, how many milliseconds it takes on average to create one of these signatures on a ColdCard MK4? @scgbckbone

We are discussing low bandwidth attacks, and have been wondering if any further mitigation is possible? The problem is, the time for a single sig is one thing, but a TX can and often does contain more inputs.

@scgbckbone
Copy link

I do not have the data yet, but I assume this will have almost no visible impact as we have only changed noncefp (iirc one classic ECDSA signature is around 25ms on STM32). Default secp noncefp seem even heavier than what we have here.

I think we should first properly specify those nonce functions.

  • I do not think my ZERO_MASK thing is safu.
  • I added counter to ECDSA noncefp as we may get invalid k (small but non-zero chance):
q = H(x,m,n, counter)
Q = q·G
k = q + H(Q,m,n)

@moonsettler
Copy link
Author

moonsettler commented Aug 22, 2024

Right! A counter was a likely addition if we require a certain checksum on R. However generation of q is not routinely verifiable.

Edit: churning the outer k = q + H(Q,m,n,c) might be better. Especially if c is in a certain range prescribed by the companion app.

Edit: if you want to prove out a fix computation cost recursive hashing is needed, if you want R to conform to a harmless checksum, this is ok.

@scgbckbone
Copy link

counter is not something provided by companion app, but rather way to grind correct k to be 0<k<order. it will be 99.9% 0, from time to time 1, and very very very limited number of times something different. I think that for c to be number greater than 255 is impossible(tho non-zero but we need 255 incorrect keys in a row). As this will "always" be 1 byte in theory, it should not mess with fixed length serialization .

if you want to prove out a fix computation cost recursive hashing is needed, if you want R to conform to a harmless checksum, this is ok

iiuc k = q + H(Q,m,n,c) this better ?

@moonsettler
Copy link
Author

moonsettler commented Aug 23, 2024

Yes, my point was the companion app can also grind it. If you expect R to conform to a checksum (to make low bandwith leaks more expensive computationally) then you can use this outside counter for that and the companion app can expect a certain range like if 1 sig takes 50 ms on the device, then if the target is ~2 sec then n bit checksum or R could be demanded to be all zero or some magic word.

Edit: I probably wouldn't use this, because PoW makes the signature generation time highly random. It was just something that came up in discussion.

@moonsettler
Copy link
Author

moonsettler commented Aug 26, 2024

What if we simply used k = q - H(Q,m,n) and R = Q - H(Q,m,n)·G (or whichever is a valid R point)?
@scgbckbone

@scgbckbone
Copy link

what is that - ? is this ecdsa case where k is not valid key ?

@moonsettler
Copy link
Author

Where R is not a valid point for the scheme. At least my understanding is, that can happen. Also with BIP-340, because you need an even R (0x02).

@scgbckbone
Copy link

Where R is not a valid point for the scheme. At least my understanding is, that can happen. Also with BIP-340, because you need an even R (0x02).

as we use secp256k1_schnorrsig_sign_custom and only provide it with custom noncefp my understanding is that this is done for us in secp256k1_schnorrsig_sign_internal https://github.com/bitcoin-core/secp256k1/blob/1988855079fa8161521b86515e77965120fdc734/src/modules/schnorrsig/main_impl.h#L165-L180

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment