A subliminal channel in a signature scheme allows a signing party to send a covert message to an authorized receiver of signed messages without anyone else noticing it. One property of ECDSA, DSA and many similar digital signature schemes (such as Schnorr) is that they need to produce, for each signature generation, a fresh random data (hereafter designated as a value k). This value must never repeat, and it must be uniformly random. The need for a cryptographically secure source of randomness proves to be a hindrance to deployment of signature schemes in some architectures in which secure random number generation is challenging, in particular, embedded systems such as smartcards [taken from RFC6979]. Also, the requirement of a different random k for each signature makes the signature non-deterministic. If the signer is not fully trusted, he can try signatures with different values of k until a signature with some desired properties is generated. For example, if x is a 32-bit binary number which the signer wants to secretly leak, he can try generating signatures with different k values until one signature starting with x is found, and publish only that signature. For ECDSA there exists both broad-band and narrow-band convert channels. There has been proposals to achieve either the subliminal-channel free or the deterministic property, but almost none that has attempted both. An example of the former is “A Subliminal-Free Variant of ECDSA“ (Bohli, Jens-Matthias and González Vasco, MaríaIsabel and Steinwandt, Rainer). An example of the later is “Study on Closing the Subliminal Channel Based on ECDSA Digital Signature Scheme” (Qiuyu ZHANG, Zhanhui SUN1,Yibo HUANG). An example of an attempt to achieve both properties is “On Subliminal Channels in Deterministic Signature Schemes” (Jens-Matthias Bohli and Rainer Steinwandt), but this attempt is not based on a signature scheme similar to ECDSA/DSA.
RSA PKCS1 v1.5 is one of the few examples of a subliminal-channel free deterministic signature scheme. But cryptographers seems to prefer probabilistic signature schemes, such as RSA-PSS, which offers provable security related to the RSA problem.
How much do you trust your hardware wallet?
When it comes down to how much you should trust your hardware, an issue that is becoming more popular nowadays, deterministic subliminal channel-free signature schemes seems to offer a great advantage. I’ve come to this conclusion while designing the Firmcoin and analyzing the possible adversaries for a hardware wallet. Even if you trust your private keys to your hardware wallet, you generally don’t trust it as much as giving the hardware wallet full Internet access. not even wireless communication. You provide the hardware wallet with a transaction to sign, and you get it signed. In the case of a Bitcoin hardware wallet, which uses ECDSA, the best you can have is a subliminal-free but interactive signing protocol, that still poses some risks.
I conjecture that a probabilistic signature scheme that hides k (such as ECDSA) cannot be turned into a deterministic subliminal-channel free scheme. In other words, the signer cannot prove in zero knowledge to every verifier that the random value k used when signing is derived from the message (and possibly a private key) without adding a new subliminal channel within the proof itself. All Non-Interactive Zero Knowledge proof systems for NP I know make use of random values. I still have to check SNARKs, as they may disprove my conjecture.
So instead of trying to achieve the perfect ECDSA, we can try to create an ECDSA variant I call “ECSA with a Trusted Warden” (ECDSA-TW). An ECDSA-TW is a signature schemes that allows a Warden to verify that each signature is covert-message free. The Warden is given additional information that may contain a covert-channel, but he won’t make public because he is trusted. In the hardware-wallet example, the hardware wallet is the signer and the software application running on the PC is the Warden. Suppose that k is computed as k = [y*EPoint(M)].x, where M is the message and EPoint() converts the message M into an elliptic point, y is the private key of another signer key-pair and [ ].x returns the x coordinate of the point. The problem left is how to build a short and practical non-interactive zero knowledge proof that r = k*G, hiding k.
As a final conclusion, I realized that my RSAL signature scheme as well as RSA-FDH and RSA PKCS #1 1.5 have this nice property of being subliminal-channel free and deterministic, and they would be better suited for a cryptocurrency in this regard.
Bitslog 