Subliminal Channels in ECDSA and RSA

Motivation§

Initially, I found the “Subliminal channel” article on Wikipedia when looking into DSA, and I thought it was interesting. Unfortunately, it is lacking in details and citations.

Cryptosystems often utilize randomized values for security, however, fixing some of these random values to some known value can open up methods of sending covert messages.

DSA Subliminal Broadband§

This section is based off of Gustavus Simmons’ paper “Subliminal Communication is Easy Using the DSA”¹; refer to this paper for more details regarding this method, and a discussion about a subliminal channel in Elgamal.

Background§

In DSA for a given message $m$ we construct a signature $(S_1, S_2)$ which has a bit length of $2\ell$ where $\ell = \lceil\log_2 q\rceil$, and two primes $p, q$ where $q | (p - 1)$.

One way we could attempt to send subliminal messages is to fix either $S_1$ or $S_2$ in the DSA signature, and let the other represent our covert message. Then, the probablilty that we can find $(m, S_1, S_2)$ that is accepted is the same as the probability of picking a random element in $\mathbb{F}_q$, or $1/q$.

By inspecting how we generate $S_1$,

$$ S_1 \equiv \left(g^k \pmod{p}\right) \pmod{q}, $$

we can realize we map the residues of $g^k$ modulo $p$ to residues modulo $q$. Since $\text{ord}_p(g) = q$ and $k \in \mathbb{F}_q$, $g^k \pmod{p}$ maps to a unique cycle of order $q$ in $\mathbb{F}_p$. Then, $g^k \pmod{p}$ for any element $g \in \mathbb{F}_p$ with the order of $q$ will cycle over the same $q$ elements.

For large $q$, we can expect the probability that a randomly chosen $S_1 \in \mathbb{F}_q$ will be part of this cycle, and thusly part of a DSA signature, is approximately $63\%$. However, it is easy to construct a $S_1$ that does occur. Choosing any $k \in \mathbb{F}_q$ and compute $S_1 \equiv \left(g^k \pmod{p}\right) \pmod{q}$.

Given any of the valid $S_1$, any element of $\mathbb{F}_p$ is a valid value for $S_2$. Also, given any $S_2$, it is possible to get every valid $S_1$ with the right choice of $a, D, k$.

It is impractical to compute an exhaustive list of valid $S_1$, and it is impossible to show that a value cannot occur without an exhaustive search. This means that half of the information in a DSA signature are used in order to provide security.

Then, the remaining $\ell$ bits in the signature are available to be used in subliminal messages.

The Broadband§

In order for Alice to utilize the subliminal channel to send messages to Bob, Alice must first share her secret key $a$ with Bob.

Then, the objective becomes: Alice must be able to communicate any choice of element in $\mathbb{F}_q$ to Bob in a way that is impossible for anyone to recover the subliminal message $m’$ without knowing Alice’s secret $a$, or detecting the subliminal channel even if the message $m’$ is known beforehand.

Because $m’ \in \mathbb{F}_q$ and $k \in \mathbb{F}_q$, there need not be a mapping from $m’ \to k$, rather we can let $k = m’$ instead of choosing a random element.

If either $D + aS_1 \equiv_q 0$ or $S_2 \equiv_q 0$, then Alice must change one of $D, m’, a$. Changing the secret $a$ is problematic as Alice must be able to alert Bob that she intends on changing the private key.

As $q$ is prime, any non-zero element of $\mathbb{F}_q$ has a multiplicative inverse. Invertibility is important because it means we do not need to do a forward search to decode $m’$ (see the paper for more details).

An issue with this method is that it relies on Alice and Bob knowing the same secret $a$ ahead of time. However, there exists narrowband subliminal channels over DSA that can be used to communicate the secret covertly before starting a broadband channel.

RSA Subliminal Narrowband§

In RSA we’d typically choose $m = pq$ where $p, q$ are large primes. However, if we chose $m = pqr$ where $p, q, r$ are primes, then we can send messages via subliminal channels using the RSA algorithm.

There wasn’t an example of this but the Wikipedia article states that we are able to send exactly one bit with this RSA subliminal channel. I suspect that to communicate via this channel, we can fix a prime value $r$, and testing if the value $m$ is divisible by $r$.

Detecting the Subliminal Channel§

Next, we want to investigate if there is method to determine whether $m$ is indeed the product of two primes with zero knowledge of the prime factors (zero knowledge proof, ZKP).

On the Wikipedia article, there is a mention to a ZKP that $m = pq$ by some researchers at the CWI in Amsterdam, without a citation nor author. Looking at the page history, I found that there once was an attribution to Bert den Boer, again without a citation to the specific paper by the author.

With some research, I found a paper by den Boer in 1991 entitled “Oblivious transfer protecting secrecy”² that references a procedure from a paper³ by Jeroen van de Graaf and Rene Peralta that goes into this problem.

The paper by de Graaf and Peralta describes a protocol for convincing an adversary that an integer $N$ is of the form $N=P^rQ^s$ where $r, s \equiv 1 \pmod{2}$ and $P, Q \equiv 3 \pmod{4}$.

Historically, $p$ and $q$ were desired to be safe-primes as the structure of a Blum integer is more difficult to factor by Pollard’s $\rho$ and $p-1$ algorithms.

All safe-primes, except for $5$, belong to the residue class $3$ modulo $4$. So, for $m = pq$ where $p,q$ are safe-primes, $m$ is a Blum integer.

In the case of RSA implementations that utilize Blum modulii, the procedure outlined by de Graaf and Peralta is indeed relevant to the problem, as our question of “is $m = p \times q$?” boils down to “is the RSA modulii $m$ Blum?”.

Outlined below is the procedure from den Boer’s paper which is an adversarial version that does not rely on both parties using a mutually trusted source of randomness.

The proofs of correctness and security can be found on the paper by de Graaf and Peralta³.

On researching this problem, I found another paper⁴ by Jan Camenisch and Markus Michels on another ZKP that a number is a product of two safe primes.

Unfortunately, with the advent of the quadratic and general number field sieves, it is no longer considered to be advantageous to choose $m$ Blum. There is currently no known method to determine if a given number is semiprime short of factorization, which makes finding this subliminal channel much harder to find.