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.
Topic: A covert-channel-free black-box signer without ZNPs - page 2. (Read 2745 times)
Quote
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.
In another thread people are discussing the problems with unauditable implementations of ECDSA (https://bitcointalksearch.org/topic/how-perfect-offline-wallets-can-still-leak-bitcoin-private-keys-883793). 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.
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.
Jump to: