A covert-channel-free black-box signer without ZNPs

[Sergio_Demian_Lerner]

In another thread people are discussing the problems with unauditable implementations of ECDSA (https://bitcointalk.org/index.php?topic=883793.0). Everyone assumes a non-interactive signing method. If you allow interaction, then the solution seems to be easy.

A year ago, when I designed the Firmcoin (Firmcoin.com), I proposed an implementation of a ECDSA signer which uses a random k, but uses a fair coin-flipping kind of protocol to create a k that is private but auditable. In other words, the device and the software in the PC cooperate to create a k value that such that the following properties hold :

1. k is uniformly random and covert-channel-free if the PC software is not backdoored and the device is backdoored
2. k is is uniformly random and covert-channel-free if the PC software is backdoored and the device is not backdoored
3. The PC software cannot obtain the private key.

The full protocol is described here: http://firmcoin.com/?p=52

But I'm copying it here:

The signing of a transaction using the private key is a special two-party protocol. A ECDSA signature consist of the tuple (r,s). All known subliminal channels in ECDSA consist of hiding some information in r. s is computed deterministically from d_A, z and r (except from a single bit, which is the sign of y_1). Our protocol guarantees that r is indeed random.

This is the standard ECDSA signing protocol:

1. The signer calculates e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
2. Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
3. The signer selects a random integer k from [1, n-1].
4. The signer calculates the curve point (x_1, y_1) = k * G.
5. The signer calculates r = x_1 (mod n). If r = 0, go back to step 3.
6. The signer calculates s = k^{-1}(z + r d_A) (mod n). If s = 0, go back to step 3.
7. The signature is the pair (r, s) which is sent to the user.

This is our protocol (the user is the PC software the user trusts)

1-2. These steps are similar to the standard protocol.
3. The signer selects a random integer u from [1, n-1].
3.1. The signer calculates Q=u * G.
3.2. The signer calculates h=HASH(Q). This is a commitment to Q.
3.3. The signer sends h to the user.
3.4. The user selects a random integer t from [1, n-1].
3.5. The user sends t to the signer.
3.6. The signer verifies t is  [1, n-1]. The signer sends Q to the user.
3.7. The user verifies that HASH(Q)=h. If not equal, then the signer is cheating.
3.8. The signer calculates k = t * u.
4-7. These steps are similar as the standard protocol.
8. The user calculates the curve point (x_2, y_2) = t * Q.
9. The user verifies that r = x_2 (mod n). If not equal, then the signer is cheating.

This protocol guarantees that the r value is chosen uniformly random from the set of x-coordinates of curve points, and at the same time guarantees that the user cannot arbitrarily force this value.
It must be noted that the protocol should not be repeated unlimited times if it fails. If failure occurs after step 3.5, and not before step 6, because of the signer not responding properly (either providing and invalid message or by not responding at all), then a new iteration of the protocol may allow the signer to leak some information. If the signer fails n times before finishing the protocol properly, then a side channel that hides approximately log2(n) bits may have been tried. For an 256-bit ECDSA private key, we would not recommend executing the protocol more than 16 times if is continuously fails, limiting the amount of information leakage to 4 private bits.

If you find a vulnerability with this protocol please let me know. Also if anyone wants to do a formal analysis of it that would be awesome. As far as I have studied it, it relies on the same crypto assumptions of ECDSA.

Best regards,
 Sergio.

[Sergio_Demian_Lerner]

3.3 The user sends z, P = t*G to the signer
3.4 The signer selects k = u*P and performs ECDSA

It's not exactly the same.  ECDSA security is based on the difficulty of the discrete log of the subgroup.
AFAIK, I does not require the additional assumption of the difficulty of DH on the curve.
But this does not seems to be a problem, since P is not published.

Another detail:

In 3.4 the signer should check that P lies on the curve.
Also in my protocol the user should check that Q lies on the curve.

[Sergio_Demian_Lerner]

To prevent any leakage due to simulated communication failures by the hardware wallet I propose making the whole protocol deterministic.
The user now stores a table TX[msg,pubk] of the h value received for the transaction with the message msg to sign and the public key pubk. This table is used to check that the signer is using a deterministic method to build h. Also the user has a private HMAC key s, that the signer does not know (it's not stored in the hardware wallet).

In bold are the modified steps.

1-2. These steps are similar to the standard protocol.
2.1. The user tells the signer which private key it should use, by sending the pubkey pubk.
3. The signer computes u = HMAC(privkey,msg). Where msg is the transaction hash to sign and privkey is the ECDSA private key.
3.1. The signer calculates Q=u * G.
3.2. The signer calculates h=HASH(Q). This is a commitment to Q.
3.3. The signer sends h to the user.
3.4. The user verifies if TX[msg,pubk] exists. If exists then the user checks that TX[msg,pubk] = h. If not then the signer is cheating and he will never ever use this signer again. Then the user computes t = HMAC(s,msg | pubk )
3.5. The user sets TX[msg,pubk] = h and sends t to the signer.
3.6. The signer verifies t is  [1, n-1]. The signer sends Q to the user.
3.7. The user verifies that HASH(Q)=h and that Q lies on the curve. If not then the signer is cheating.
3.8. The signer calculates k = t * u.
4-7. These steps are similar as the standard protocol.
8. The user calculates the curve point (x_2, y_2) = t * Q.
9. The user verifies that r = x_2 (mod n). If not equal, then the signer is cheating.

[hhanh00]

3.3 The user sends z, P = t*G to the signer
3.4 The signer selects k = u*P and performs ECDSA

It's not exactly the same.  ECDSA security is based on the difficulty of the discrete log of the subgroup.
AFAIK, I does not require the additional assumption of the difficulty of DH on the curve.
But this does not seems to be a problem, since P is not published.

DDH holds for EC over GF(p) provided it has a large embedding degree which as far as I know is the case for secp256k1. k|x should be indistinguishable from random. Then again, I'm not going to pretend I know this stuff so I'm most likely wrong.
If it works, you wouldn't have to do an additional data transfer from offline storage which usually involves plugging/unplugging a USB drive - that's nice.

[gmaxwell]

Our curve has a cofactor of 1, which makes this easier... but it might be metter to describe it in a way that doesn't reduce security when the curve has a cofactor.  I'm not sure how to accomplish that though, since the normal measure of using numbers which a multiple of the cofactor won't work since the signer could potentially encode their sidechannel in the choice of the subgroup.

It seems like a great proposal to me.  It's basically the blinding scheme but it replaces a lot of impracticality with some interaction.  OTOH, the interaction is a major PITA for truly offline signing. No one wants to go back and forth to the safe twice.

I think we could make the interaction into a largely one-time setup... with a cost of some complexity:

Sequentially,
(1) Signer generates _many_ future k values, and builds a hash-tree over G*k. Gives user the root.
(2) User generates _many_ future blinding values, and builds a hash-tree over them to the signer.
(3) User forms a signing request, picks a blinding value, and gives to the signer the blinding value and the membership proof.
(4) Signer verifies the membership proof, picks a k value, combines and signs, and provides a membership proof.
(5) User verifies the membership proof and R consistency or otherwise discards the signature.

Now, though, you need to worry about nonce reuse, the signer must keep state to prevent reusing one of its nonces, which would be unfortunate. In particular if the signers state can be rolled back, it can be induced to reuse a nonce.

Ideally, you'd just form trees of 2^256 nonces and just have each message deterministically select its nonce. This has computational ... challenges.

I thought for a moment that perhaps you could just have two nonces for each bit in the message, but this results in straightforward linear relationships.  But perhaps there is some way to make it largely stateless.

[stv]

This is a very nice protocol to tackle the problem of leakage, but it is not perfect either. It is practically the same as mine with ZK proofs or gmaxwell's based on Schnorr, because leakage can still happen via “u”.

But it is better than mine because it is easily computable. It is better than gmaxwell's because it does not require a protocol change.

[Sergio_Demian_Lerner]

This is a very nice protocol to tackle the problem of leakage, but it is not perfect either. It is practically the same as mine with ZK proofs or gmaxwell's based on Schnorr, because leakage can still happen via “u”.

The value u never leaves the user computer, so it would be impossible to a backdoored hardware wallet to communicate u to the malicious party.

But it is better than mine because it is easily computable. It is better than gmaxwell's because it does not require a protocol change.

Could you provide the link here to your method ?

[adam3us]

The EDH idea seems not bad.  Have to check the math but that sounds like it should be possible to make work.

It seems like a great proposal to me.  It's basically the blinding scheme but it replaces a lot of impracticality with some interaction.  OTOH, the interaction is a major PITA for truly offline signing. No one wants to go back and forth to the safe twice.

Yeah imagine armory usb, and other limited comms mechanisms: at hardware or human interactive level these can be basically untenable with a 4-move protocol.  Worth working hard to make that a 2-move protocol.

(1) Signer generates _many_ future k values, and builds a hash-tree over G*k. Gives user the root.
...
Now, though, you need to worry about nonce reuse, the signer must keep state to prevent reusing one of its nonces, which would be unfortunate. In particular if the signers state can be rolled back, it can be induced to reuse a nonce.

State is a bit risky, hard to make cheap devices storage database transactional, where each nonce is used 0 or 1 times maximum.

Adam

[stv]

Could you provide the link here to your method ?

https://bitcointalk.org/index.php?topic=883793.msg9816870#msg9816870

[gmaxwell]

I can make this non-interactive at a cost of not eliminating the side channel, only drastically reducing it.

This is effectively a scheme  for "sign-to-contract" I was thinking thinking about using for zero-overhead timestamping as a side effect of transactions.

User sends picks a random 256 bit integer t.
Users sends t and the signature request to the signer.

Signer picks a nonce k, computes R = G*k.
Signer computes h=hmac(msg=r,key=t)
Signer computes k' = k+h mod order and R' = R + G*h
Signer signs like normal, using k'
Signer emits signature along with R.

User verifies that R + G*h mod order == signature.r.

This leaves open a side-channel that has exponential cost per additional bit, via grinding the resulting R' mod order.  Using the FEC schemes that I've discussed before it's possible to leak a message of any size using even a single bit channel and enough signatures...  But it eliminates the obvious and very powerful attacks where everything is leaked in a single signature.

This is clearly less good, but it's only a two-move protocol, so many places which wouldn't consider using a countermeasure could pick this up for free just as an element of a protocol spec.

[adam3us]

eh what happened to the message from hhanh00 that this was quote from?  Seems to have been deleted from the thread?

Someone want to reinstate that or retype the missing protocol steps from it?

3.3 The user sends z, P = t*G to the signer
3.4 The signer selects k = u*P and performs ECDSA

Adam

[adam3us]

eh what happened to the message from hhanh00 that this was quote from?  Seems to have been deleted from the thread?

OK never mind I think it must be this:

3.2 t=random(0,n)
3.3 user sends z=H(m), P=tG
3.4 signer sets u=random(0,n),r=[uP].x
3.5 signer sends s'=(z+rd)/u,r
3.6 user sets s=s'/t (so that k=ut and s=(H(m)+rd)/k)
3.7 user verifies sR=?zG+rQ

that seems pretty good, two moves only, nice hhanh00.

Adam

[stv]

This protocol has another nice feature: The non-signer party in this protocol does not have to be the party who generates the message to be signed. This is a relevant difference to the blind-signature variant.

This means you have the following setup:

Code:

   online        |         offline                     offline

[Application] <---> [Signing Wallet Device] <---> [Verifying Device]

         dangerous connection         internal connection

Signer and Verifier can prepare a number of choices for “u” and “t” like in gmaxwell's Hashtree proposal. After that, the App can request Transactions from the Wallet, and the independent verifier device can verify that they are leak-free. Note that “u” may contain secret messages, but only the verifying device (which can be offline) knows the “u” values.

[stv]

To prevent any leakage due to simulated communication failures by the hardware wallet I propose making the whole protocol deterministic.
The user now stores a table TX[msg,pubk] of the h value received for the transaction with the message msg to sign and the public key pubk. This table is used to check that the signer is using a deterministic method to build h. Also the user has a private HMAC key s, that the signer does not know (it's not stored in the hardware wallet).

In bold are the modified steps.

1-2. These steps are similar to the standard protocol.
2.1. The user tells the signer which private key it should use, by sending the pubkey pubk.
3. The signer computes u = HMAC(privkey,msg). Where msg is the transaction hash to sign and privkey is the ECDSA private key.
3.1. The signer calculates Q=u * G.
3.2. The signer calculates h=HASH(Q). This is a commitment to Q.
3.3. The signer sends h to the user.
3.4. The user verifies if TX[msg,pubk] exists. If exists then the user checks that TX[msg,pubk] = h. If not then the signer is cheating and he will never ever use this signer again. Then the user computes t = HMAC(s,msg | pubk )
3.5. The user sets TX[msg,pubk] = h and sends t to the signer.
3.6. The signer verifies t is  [1, n-1]. The signer sends Q to the user.
3.7. The user verifies that HASH(Q)=h and that Q lies on the curve. If not then the signer is cheating.
3.8. The signer calculates k = t * u.
4-7. These steps are similar as the standard protocol.
8. The user calculates the curve point (x_2, y_2) = t * Q.
9. The user verifies that r = x_2 (mod n). If not equal, then the signer is cheating.

Do I get this right that the table only checks whether the signer's current behavior is consistent with the signer's past behavior? I don't get how the user could possibly know what “h” or “Q” is correct for a certain secret key (or its corresponding public key).

[gmaxwell]

I don't think the determinism detection is all that interesting.

An evil signer can use the message input as the 'random state' needed to leak data, and be completely deterministic over the inputs.

Take your secret, encrypt it with the attackers pubkey, boost it up with an infinite rate code, use the message to select which codeword of the infinite rate code you're leaking. Thats how I was able to get a 'deterministic' signer that could leak arbitrary sized secrets with enough signatures.

If the concern is the 1 bit failure channel, you can even pre-process the code to make it binary unbalanced so most of the time it's successful, which may make it less obvious that it's using a failure channel to communicate...  (uh, decoders for this may be more complicated however) Though if you don't know the messages that triggered failures, only the successes, your data rate will be very very low unless the failure probability is close to 50%.

[gmaxwell]

3.2 t=random(0,n)
3.3 user sends z=H(m), P=tG
3.4 signer sets u=random(0,n),r=[uP].x
3.5 signer sends s'=(z+rd)/u,r
3.6 user sets s=s'/t (so that k=ut and s=(H(m)+rd)/k)
3.7 user verifies sR=?zG+rQ

Interestingly, the TPM 2.0 signing stuff computes the nonce this way: https://eprint.iacr.org/2013/667.pdf (Section 3), it lets you use a arbitrary point for the nonce multiply.

I wonder if they'd been thinking of s similar blinding scheme?

[stv]

I don't get why you insist on calling it “blinding”, since no message is hidden here. Using commitments to cooperatively generate a random bitstring is pretty common.

[gmaxwell]

I don't get why you insist on calling it “blinding”, since no message is hidden here. Using commitments to cooperatively generate a random bitstring is pretty common.

I was referring to the two move protocol in Adam's message (apparently originally by hhanh00 but lost?). not the ordinary commitment there by Sergio.  And I refereed to it as blinding because it makes the numbers in the transcript statistically uniform to a party who doesn't know the secret, and because it's similar in construction to a full blinding scheme-- effectively it's blinding the nonce used by the signer but not the message. Thats all.

[hhanh00]

I removed my message while I was working out how to use uP|x. In my message I wrote k = uP|x which I realized later doesn't work.
Adam's modified version should work, shouldn't it?

[Sergio_Demian_Lerner]

Do I get this right that the table only checks whether the signer's current behavior is consistent with the signer's past behavior? I don't get how the user could possibly know what “h” or “Q” is correct for a certain secret key (or its corresponding public key).

Yes, just that, only to verify consistency. And I think it's important to prevent the hardware wallet from using communication failures as a covert-channel.
The attack is the obvious one: You try executing the protocol but it fails (e.g. the hardware wallet never responds with the signature). The hardware fails on purpose because the resulting signature does not meet the side-channel requirement (e.g. it does not start with the bit of the private key it's trying to leak). When you retry the protocol, if the hardware wallet cannot send a different h, then the signature will be the same. So there is no point in aborting the protocol.
With all randomized protocols (e.g. the two-move protocol proposed), the hardware wallet may abort the protocol in order to get a different random from the user or from itself in order to create a signature with the required leakage properties.

Once the signature has been created, the TX table can be cleared. It should only store data for unfinished protocol runs.