posted 25 Dec 2021

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"[1]; 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 mm we construct a signature (S1,S2)(S_1, S_2) which has a bit length of 22\ell where =log2q\ell = \lceil\log_2 q\rceil, and two primes p,qp, q where q(p1)q | (p - 1).

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

By inspecting how we generate S1S_1,

S1(gk(modp))(modq),S_1 \equiv \left(g^k \pmod{p}\right) \pmod{q},

we realize that we are mapping the residues of gkg^k modulo pp to residues modulo qq. Since ordp(g)=q\text{ord}_p(g) = q and kFqk \in \mathbb{F}_q, gk(modp)g^k \pmod{p} maps to a unique cycle of order qq in Fp\mathbb{F}_p. Then, gk(modp)g^k \pmod{p} for any element gFpg \in \mathbb{F}_p with the order of qq will cycle over the same qq elements.

For large qq, the probability that a S1FqS_1 \in \mathbb{F}_q chosen uniformly at random is part of the cycle – and as a result, part of the DSA signature – is approximately 63%.63\%. However, it is trivial to construct a S1S_1 that is guaranteed to occur; choose any kFqk \in \mathbb{F}_q and compute S1(gk(modp))(modq)S_1 \equiv \left(g^k \pmod{p}\right) \pmod{q}.

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

It is impractical to compute an exhaustive list of valid S1S_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 aa with Bob.

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

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

DSA Subliminal Broadband

Suppose Alice wants to send a covert message mm' to Bob, Alice begins by following the standard DSA procedure: picking p,qp, q, and a overt document DD.

Alice then generates the signature for the overt document with its signature (D,S1,S2)(D, S_1, S_2) with the standard formulae

S1(gk(modp))(modq)S2(D+aS1)k1(modq),\begin{align*} S_1 &\equiv \left(g^k \pmod{p}\right) \pmod{q}\\ S_2 &\equiv (D + aS_1)k^{-1} \pmod{q}, \end{align*}

except Alice uses k=mk = m'.

Assuming D+aS1̸q0D + aS_1 \not\equiv_q 0 and S2̸q0S_2 \not\equiv_q 0, Bob can recover mm' by

mS21(D+aS1)(modq).m' \equiv S_2^{-1}(D + aS_1) \pmod{q}.

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

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

An issue with this method is that it relies on Alice and Bob knowing the same secret aa 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=pqm = pq where p,qp, q are large primes. However, if we chose m=pqrm = pqr where p,q,rp, 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 rr, and testing if the value mm is divisible by rr.

§ Detecting the Subliminal Channel

Next, we want to investigate if there is method to determine whether mm 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=pqm = 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"[2] that references a procedure from a paper[3] 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 NN is of the form N=PrQsN=P^rQ^s where r,s1(mod2)r, s \equiv 1 \pmod{2} and P,Q3(mod4)P, Q \equiv 3 \pmod{4}.

Safe-Prime

A prime pp is considered to be a safe-prime iff p12\frac{p-1}{2} is prime as well.

Historically, pp and qq were desired to be safe-primes as the structure of a Blum integer is more difficult to factor by Pollard's ρ\rho and p1p-1 algorithms.

Blum Integer

A natural number nn is said to be a Blum integer if nn is semiprime, i.e. n=p×q,n = p \times q, and that pp and qq are primes that are congruent to 33 modulo 4.4.

All safe-primes, except for 55, belong to the residue class 33 modulo 44. So, for m=pqm = pq where p,qp,q are safe-primes, mm 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×qm = p \times q?" boils down to "is the RSA modulii mm 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.

ZKP that mm is a Blum integer

Suppose we want to verify that a composite number mm is in fact the product of two primes, without knowledge of the two primes.

Suppose Samantha has a composite number m=pqm = pq where pp and qq prime.

Victor wants to verify that mm is Blum and requests Samantha to find a value DD such that the Jacobi symbol (Dm)=1\genfrac{(}{)}{}{}{D}{m} = 1.

Samantha and Victor then generate random residues RS,RVR_S, R_V modulo mm such that their Jacobi symbol is equal to 1,1, and they exchange residues.

Victor chooses either RSR_S or RSRVR_S R_V and challenges Samantha to pick values b{1,1}b \in \{-1, 1\} and R(modm)R \pmod{m} such that RAR_A is equal to Victor's choice of RSR_S or RSRVR_S R_V; RAR_A is defined to be

RA=DbR2(modm).R_A = D^bR^2 \pmod{m}.

Samantha sends (b,R)(b, R) to Victor, and Victor verifies that DbR2(modm)D^bR^2 \pmod{m} satisfies his challenge to Samantha.

Samantha has a 34\frac{3}{4} chance of producing a successful pair of values.

Therefore, Victor will continue this adversarial approach multiple times until he is satisfied that mm is indeed Blum.

The proofs of correctness and security can be found on the paper by de Graaf and Peralta[3:1].

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

Unfortunately for this method, it is no longer considered to be advantageous to choose mm Blum due to advances in factorization techniques. As far as I am aware, there is no known method to determine whether a given integer is semiprime short of factorization, making it more difficult to uncover this subliminal channel.


  1. Simmons G.J. (1994) Subliminal Communication is Easy Using the DSA. In: Helleseth T. (eds) Advances in Cryptology — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_18 ↩︎

  2. den Boer B. (1991) Oblivious transfer protecting secrecy. In: Damgård I.B. (eds) Advances in Cryptology — EUROCRYPT ’90. EUROCRYPT 1990. Lecture Notes in Computer Science, vol 473. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46877-3_4 ↩︎

  3. van de Graaf J., Peralta R. (1988) A Simple and Secure Way to Show the Validity of Your Public Key. In: Pomerance C. (eds) Advances in Cryptology — CRYPTO ’87. CRYPTO 1987. Lecture Notes in Computer Science, vol 293. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48184-2_9 ↩︎ ↩︎

  4. Camenisch J., Michels M. (1999) Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. In: Stern J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_8 ↩︎