# Reversible and Plausibly Deniable Covert Channels in One-Time Passwords Based on Hash Chains +
## 3 Covert Channels in Hash Chains
### Covert Channel Variants  
The secret message that CS wants to send is broken into \(t\) symbols from an alphabet \(V=\{0,1,\ldots,v-1\}\), i.e., the message comprises at most \(l=\lfloor t\log_{2}v\rfloor\) bits. To embed a symbol \(s_{j}\in V\) into a password \(x_{i}\) that is going to be transmitted, CS modifies the password by applying a transformation \(T:R\times V\to R\), i.e., replaces \(x_{i}\) by a different password \(x_{i}^{\prime}=T(x_{i},s_{j})\). In the following, we will mostly use the notation \(T_{s_{j}}(x_{i})\) instead. This password is intercepted by CR, who knows the previous password \(x_{i+1}\). CR first tests if \(h(x_{i}^{\prime})=x_{i+1}\). In that case, no symbol has been embedded and \(x_{i}=x_{i}^{\prime}\). Otherwise, for each possible symbol \(s\), CR applies \(T_{s}^{-1}\) to \(x_{i}^{\prime}\) and checks if hashing produces \(x_{i+1}\). CR stops with the first hit, extracts symbol \(s_{j}\) of the secret message, and forwards the original password \(x_{i}=T_{s_{j}}^{-1}(x_{i}^{\prime})\) to B.  
Embedding is repeated until the complete message is transmitted. This requires that the number of symbols in the message is \(t<n\), as we do not embed a symbol in the first password \(x_{n-1}\) to enable reversibility (see below). The extracting procedure requires that \(T\) is injective in each argument, and that \(T_{s}(x)\
eq x\). To implement \(T\), we identify \(V\) with a subset of size \(v\) of \(R=\{0,1\}^{m}\), and define \(T_{s_{j}}(x)=x\oplus s_{j}\), where \(\oplus\) denotes the bitwise exclusive OR operation. Then \(T\) is self-inverse, i.e., \(T_{s}^{-1}=T_{s}\). An upper bound for \(v=|V|\) is \(2^{m}-1=|R\setminus\{00\cdots 0\}|\), so that the message might comprise up to \(l=\lfloor(n-1)\log_{2}(2^{m}-1)\rfloor\) bits, i.e., almost \(n\cdot m\) bits can be transmitted. A first variant is found by defining set \(V\) of size \(v=m\) comprising all \(m\)-bit strings with exactly one bit set to \(1\), i.e., embedding symbol \(s_{j}\) means to flip bit \(j\) of the password to be transmitted. We illustrate this variant in Figure 1.  
A much more restrictive variant could embed only one bit per password, e.g., by using \(V=\{100\cdot 0,010\cdot 0\}\). Please note that when a symbol is embedded in each password (except \(x_{n-1}\)), then we might even use \(V=\{000\cdot 0,100\cdot 0\}\), i.e., flipping bit \(0\) of the password only when a \(1\) is embedded, and leaving the password unmodified for embedding \(0\). More liberal variants are also possible, e.g., defining \(V\) as the set of strings with one or two bits set to \(1\), resulting in \(v={m\choose 1}+{m\choose 2}=m(m+1)/2\), or taking all strings with at least \(m/2\) bits set to \(1\), so that  
\[v=|V|=\sum_{k=m/2}^{m}{m\choose k}=2^{m-1}\,\]  
by applying the binomial theorem with \(a=b=1\) and taking the symmetry of binomials into account [39]. Those variants might be useful for cases where \(m\) is small, e.g., when hash chains of a small width are used in WSN networks [40]. In order to decouple the embedded symbols from the particular message, i.e., to get random-looking symbols, the message might be encrypted before embedding, using a stream cipher or a block cipher with a chaining method such as cipher block chaining (CBC), to avoid the case when two identical symbols result in two identical encrypted symbols [3]. While this may increase stealthiness during communication, the computational effort on the receiver side, which may also threaten stealthiness (see below), can alternatively be optimized by using an encoding based on the frequency of symbols: the symbol with the highest frequency gets a code symbol that is checked first by CR, and so on. When  
Figure 1: Example of variant 1. Covert sender (CS) embeds symbol 2 by flipping bit 2 of a password. Covert receiver (CR) first tries out which bit of the transmitted password must be flipped so that the check is successful, i.e., that its hash corresponds to the password stored at CR.