Understanding fail-stop subliminal channels

Question

It has long been known that randomness can be used to create subliminal channels (see Simmons' "Prisoner's problem" in 1983) and that preventing such subliminal channels is hard.

For the case at hand, Simmons proposed a protocol for preventing subliminal channels within the random numbers generated during the creation of DSA signatures in his "An Introduction to the Mathematics of Trust in Security Protocols" paper in 1993. In Simmons' modification to DSA, the signer Alice (A) tries to communicate a subliminal bit b to Bob (B), communicating through a warden (W) who tries to prevent subliminal channels. The approach to prevent it is basically forcing A to incorporate some randomness that W provides A before A generates the final signature. The rationale of subliminal-freeness being that A can no longer choose the random number on her own.

However, it was later shown by Desmedt in "Simmons' protocol is not free of subliminal channels" that even in that case, there exists a specific type of subliminal channel, which I've seen sometimes referred to as fail-stop subliminal channel. This type of channel works as follows in the DSA case: since A has access to W's randomness before producing the final signature, she can (a) halt the signing process if the last bit of the signature after having incorporated W's randomness does not match b; or (b) complete the process if, after having incorporated W's randomness, the resulting signature's last bit matches b. There may of course be more convoluted ways to decide whether or not to keep going, but that seems to be the overall idea.

My doubt comes at this point. After this reasoning, Desmedt argues that, in order to show whether or not a channel is subliminal-free (i.e., no subliminal channel can be created within it), only the case in which A does not stop should be considered, as in the case in which she stops, W detects that some suspicious behavior is taking place and thus no subliminal exchange can occur (because W detects it, which directly contradicts the principle of subliminal communications). So, following this argument, a system with a fail-stop subliminal channel would (assuming uniformity of the bits to transmit in a subliminal manner) be detectable 1/2 of the executions.

But then, this subliminal channel is of little use in general: if I have a device/software that fails 1/2 of the times, I would, in the best case, assume it is a quite useless device/software and would change it for another different device/software, so no subliminal communication would be possible any longer (and probably, I would think that something weird is happening in that device/software).

Main question: Is this the way in which fail-stop subliminal channels are expected to work, or have I misunderstood something?

Follow up question: If this is indeed the way they do work, when does this type of subliminal channels make sense in practice and how can they be used? (Note: I am not asking in what kind of real-world scenario would a fail-stop channel be applicable, although that can of course help. Rather, I am interested in how could a fail-stop channel be used without the warden detecting/highly suspecting that subliminal communications are taking place and deciding to discard the involved software/device.)

Answer 1

Answer to main question: Yes, it is indeed the way they work. Specifically, the rationale that in order to demonstrate whether or not a channel is subliminal-free, one needs to focus only on the instances in which A does not stop, is quite logical. Consider that, if A stops, then W realizes that a subliminal communication is taking place and the channel is not subliminal-free. But similarly, for the cases in which A does not stop, W still needs to decide if there is a subliminal channel. This is more clearly explained in "A Progress Report on Subliminal-Free Channels." (Check specifically Definition 3, although the prevoius sections help understanding the thought process of the authors.)

Answer to follow up question: TLDR; a fail-stop subliminal channel is practical roughly when only one subliminal bit needs to be transmitted. Thus, it may make sense only in very restricted cases. The example by Desmedt is that in D day, it would have been enough to transmit a subliminal bit of "landing would not take place at Calais." When more bits need to be transmitted, it is very probably not practical, as its probability of going undetected goes down exponentially (and its capacity drops to $0$ just as quickly).

It can be naturally argued that the practicality of a subliminal channel is determined by its capacity, when the subliminal communication goes undetected. The maximum capacity of a channel (in the absence of communication errors), is determined by its entropy. And given the previous answer, we know that a fail-stop subliminal channel is undetected as long as A does not halt, so we can use conditional entropy.

The condition making A halt may be defined arbitrarily, but for the sake of simplicity, I stick to Desmedt's example (the following calculations are actually sketched in Desmedt's paper, although a bit succinctly...). In Desmedt's example, A stops if the last bit of the r value of the DSA signature matches $b \oplus c$, where $b$ is a secret (uniformly sampled) bit shared by A and B, and c is the subliminal bit to be transmitted. The event in which A does not stop implies that W sees a perfectly valid DSA signature that has been generated according to the protocol. Thus, he cannot differentiate it from a completely legitimate run. This is denoted with $\{w = 0\}$ (i.e., W ouputs "no subliminal information").

Lets generalize and assume that A wants to transmit u bits. I denote the bitstring to transmit subliminally with $c_i$, for every $i \in [0,2^u-1]$. Then, the capacity of one single execution of the protocol is:

$H(c_u|w = 0) = -\sum_{i\in[0,2^u-1]} p(c_i,w=0) \log \frac{p(c_i,w=0)}{p(w=0)} = -\sum_{i\in[0,2^u-1]} 2^{-2u} \log \frac{2^{-2u}}{2^{-u}}=u2^{-u}$

[Note that $p(c_i,w=0)$ is the event in which $c_i$ equals the $u$ least significant bits of $r$. Then, $p(c_i,w=0)=2^{-u} \cdot 2^{-u}$, as $c_i$ and $w=0$ are independent random variables, given that $b$ is chosen uniformly at random, and $r=(g^{k' \cdot k''} \bmod p) \bmod q$ is also drawn uniformly at random (because $k''$, chosen by W, is.)]

Now, the function $f(u)=u2^{-u}$ has a maximum at $1/\ln2$ and therefore the maximum capacity is $1/\ln2 \cdot 2^{-1/\ln2}=0.5307$.

Note that, if we want to analyze the case in which A tries to transmit t different signatures (restricting to the fail-stop strategy), each including $u$ bits of subliminal information, it is equivalent to having A try to transmit $tu$ bits in a single signature, which is again maximal when $tu = 1/\ln2$.