Topic: A covert-channel-free black-box signer without ZNPs (Read 2745 times)

No it wouldn't, adding a new signature system is just a soft forking addition, of a smaller scale than we've made several times before (e.g. with the introduction of p2sh).  Not something to do lightly but not that big a deal.

But blinding alone isn't enough, because you actually want the signer to see the message (because the signer needs to display what the message will do to act as an independent check or to enforce business logic).  Though there is probably a very narrow and very efficient ZKP that can be used to unblind only the message.

I can't see how this can be avoided without blinding the signature but this would require a hard fork.

Yes/no. I thought it was nice at first but then I realized it's no better than my two move scheme, I think.

The signer knows the resulting r that will show up in the signature so he can grind u to stuff bits into it.

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.

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?

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.

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.

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?

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%.

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).

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:


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.

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

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?


Adam

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.

https://bitcointalksearch.org/topic/m.9816870

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


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.


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

Adam

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.

Could you provide the link here to your method ?

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.

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.

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.