Designing a duress PIN: covert channels for SSH (part V)

[continued form part IV]

Covert channels with ECDSA

ECDSA signatures are probabilistic, with a random nonce point chosen by the signer comprising half the signature. This potential for covert channels was known early on in the context of plain DSA over the integers, without the “EC” part— later elliptic curve adaptation of the scheme did not materially affect the existence of covert channels.

The core idea is to repeatedly try different nonces until the final signature satisfies some property. For example, suppose the goal is to convey the bit string “1011.” The signer chooses different random nonces and computes the corresponding half of the ECDSA signature. Next an HMAC is run on that result with a symmetric secret shared with the verifier. If HMAC outputs a result ending with the bit pattern “1011,” the signature can be released. Otherwise a new nonce is selected and the search continues. The verifier can extract the same bit pattern by repeating the HMAC calculation on the first half of the received signature

Compared to PSS this trial-and-error approach is very inefficient. It does not operate in constant time. Instead we check random nonces until a predicate is true, with the probability decreasing exponentially in the amount of information being conveyed. Even signaling a single bit of information—was the duress PIN invoked?—  will require 2 tries on average. That means signature times have effectively doubled on average and could get a lot worse if there is an unlucky streak of nonces failing our predicate. (Recall that the most expensive part of an ECDSA computation is the point-multiplication of random nonce with the generator point of the curve. So we are repeating the one step that accounts for the majority of CPU cycles.) One approach is to avoid starting from scratch with a new nonce, and instead building incrementally on the previous result. For example we can repeatedly multiply the current point by 2 or add the generator point until the predicate reports true. Such incremental changes are much cheaper than doing an entire multiplication from scratch. On the other hand, these short-cuts reduce the entropy of the nonce which is critical for the security of ECDSA. Even small information leaks about a nonce aggregated over many signatures can be leveraged for recovering the private key.

There is another way to convey information with ECDSA signatures owing to their malleability property. Specifically if <r, s> is a valid ECDSA signature on a given message, so is <r, -s> where the “negative” value is taken modulo curve order. This looks promising as special-case communication channel for exactly 1 bit: output either <r, +s> or <r, -s> depending on the least-significant bit of HMAC output and the true/false value we intend to convey.

Minor problem: an adversary can easily disrupt this channel. After the card releases a signature, the adversary is free to tamper with the second half without invalidating it. This makes the channel unreliable. Assuming a perfect implementation without side-channel leaks, the adversary will have no way to know for certain whether a duress PIN has been used. But if they suspect so, they can tweak the signature and send it with the opposite sign to disrupt the signal. (Of course, if the card-holder had supplied their true PIN, the adversary will have raised the alarm on themselves by manipulating it.) No such games are possible with PSS: any modification to the signature output from the card will invalidate it. An adversary can always ask the card for another signature on the same message,  but that does not help. As long as the duress PIN is being used, the card will continue to output more valid signatures tainted in exactly the same undetectable manner.

Determinism is in the eye of the beholder

The final type of key supported for SSH— EdDSA— makes for an interesting case. In principle EdDSA signatures are deterministic: signing the same message multiple times outputs the same signature. While there is still a unique nonce for each operation, this nonce is derived as a function of the message, guaranteeing determinism and reproducibility of results. Unlike ECDSA there is no freedom to leak information by playing games with the choice of random nonce.

The catch is that choice of nonce still looks random to external observers. They have no way to determine whether a blackbox signer— namely, the applet running on a smart-card— followed prescribed rules for computing the nonce or diverged from the protocol. (In fact such external verifiability is fundamentally incompatible with the security of EdDSA: if a verifier could predict what the nonce should be for a given message, they can recover the private key.) That creates some leeway for signaling a duress PIN. When a regular PIN is used, the applet follows the exact letter of EdDSA specification. By contrast when a duress PIN is used, a different deterministic scheme is invoked. “Deterministic” being the operational keyword; otherwise the adversary can trivially detect that something is amiss by asking the card to sign same message multiple times and observing different signatures. For that matter, if the adversary has ever witnessed an EdDSA signature on any message produced with the real PIN, they can detect duress PIN usage by asking for another signature on the same message and checking if results are identical.

It remains an open question how such a scheme can operate without side-channels (constant time and identical execution traces, regardless of which PIN is used) and without disclosing the private key. If we remove the latter requirement, there is a trivial solution. EdDSA uses a secret seed for deriving nonces from the message. Suppose the card application maintains two seeds, one private and one shared with the remote server. Ordinary PIN entry results in generation of nonces using the first one, while duress PIN entry switches to the latter. Since the server has a copy of the second seed, it can determine for any given signature which path was taken; the chances of a collisions are negligible. A serious disadvantage to this scheme is that invoking the duress PIN also discloses the private-key to the remote server. Recall that knowledge of nonce used for a signature allows key recovery. As such it is only feasible for closed ecosystems where the disclosure of private-key has no adverse consequences beyond that one remote system.


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s