In cryptography, subliminal channels are
covert channels
In computer security, a covert channel is a type of attack that creates a capability to transfer information objects between processes that are not supposed to be allowed to communicate by the computer security policy. The term, originated in 197 ...
that can be used to communicate secretly in normal looking communication over an
insecure channel
In cryptography, a secure channel is a means of data transmission that is resistant to overhearing and tampering. A confidential channel is a means of data transmission that is resistant to overhearing, or eavesdropping (e.g., reading the conten ...
.
[Gustavus J. Simmons. ]
The Prisoners Problem and the Subliminal Channel
'. In Advances in Cryptology – CRYPTO ’83, pages 51–67, New York, 1984. Lecture Notes in Computer Science, ed. D. Chaum. Subliminal channels in
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
crypto systems were found in 1984 by
Gustavus Simmons
Gustavus J. Simmons (born 1930) is a retired cryptographer and former manager of the applied mathematics Department and Senior Fellow at Sandia National Laboratories. He worked primarily with authentication theory, developing cryptographic techni ...
.
Simmons describes how the "Prisoners' Problem" can be solved through parameter substitution in
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
algorithms.
[Gustavus J. Simmons. ]
The subliminal channel and digital signatures
'. In Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, pages 364–378, New York, NY, USA, 1985. Springer-Verlag New York, Inc.
(Note that Simmons' Prisoners' Problem is not the same as the
Prisoner's Dilemma
The Prisoner's Dilemma is an example of a game analyzed in game theory. It is also a thought experiment that challenges two completely rational agents to a dilemma: cooperate with their partner for mutual reward, or betray their partner ("defe ...
.
)
Signature algorithms like
ElGamal
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in th ...
and
DSA have parameters which must be set with random information. He shows how one can make use of these parameters to send a message subliminally. Because the algorithm's signature creation procedure is unchanged, the signature remains verifiable and indistinguishable from a normal signature. Therefore, it is hard to detect if the subliminal channel is used.
* Subliminal channels can be classified into broadband and narrowband channel types.
* Broadband and narrowband channels can exist in the same datastream.
* The broadband channel uses almost all available bits that are available to use. This is commonly understood to mean channel utilization.
* Every channel which uses fewer bits is called a narrow-band channel.
* The additional used bits are needed for further protection, e.g.,
impersonation
An impersonator is someone who imitates or copies the behavior or actions of another. There are many reasons for impersonating someone:
*Entertainment: An entertainer impersonates a celebrity, generally for entertainment, and makes fun of ...
.
The broadband and the narrow-band channels can use different algorithm parameters. A narrow-band channel cannot transport maximal information, but it can be used to send the authentication key or datastream.
Research is ongoing : further developments can enhance the subliminal channel, e.g., allow for establishing a broadband channel without the need to agree on an authentication key in advance. Other developments try to avoid the entire subliminal channel.
Examples
An easy example of a narrowband subliminal channel for normal human-language text would be to define that an even word count in a sentence is associated with the bit "0" and an odd word count with the bit "1". The question "Hello, how do you do?" would therefore send the subliminal message "1".
The
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a Public-key cryptography, public-key cryptosystem and Federal Information Processing Standards, Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular e ...
has one subliminal broadband
[Gustavus J. Simmons. ]
Subliminal communication is easy using the DSA
'. In EUROCRYPT ’93: Workshop on the theory and application of cryptographic techniques on Advances in cryptology, pages 218–232, Secaucus, NJ, USA, 1994. Springer-Verlag New York, Inc. and three subliminal narrow-band channels
[Gustavus J. Simmons. The subliminal channel in the U.S. Digital Signature Algorithm (DSA), in
''Proceedings of the 3rd Symposium on State and Progress of Research in Cryptography'' (''SPRC '93''), Rome, Italy, February 15–16, 1993.]
At signing the parameter
has to be set random. For the broadband channel this parameter is instead set with a subliminal message
.
# Key generation
## choose prime
## choose prime
## calculate generator
## choose authentication key
and send it securely to the receiver
## calculate public key
mod
# Signing
## choose message
## (hash function
is here substituted with a modulo reduction by 107) calculate message hash value
mod
mod
## instead of random value
subliminal message
is chosen
## calculate inverse of the subliminal message
mod
## calculate signature value
mod
mod
mod
mod
## calculate signature value
mod
mod
## sending message with signature triple
# Verifying
## receiver gets message triple
## calculate message hash
mod
mod
## calculate inverse
mod
## calculate
mod
mod
## calculate
mod
mod
## calculate signature
mod
mod
mod
mod
## since
, the signature is valid
# Message extraction on receiver side
## from triple (1337; 12, 3)
## extract message
mod
The formula for message extraction is derived by transposing the signature value
calculation formula.
*
mod
*
mod
*
mod
Example: Using a Modulus n = pqr
In this example, an RSA modulus purporting to be of the form n = pq is actually of the form n = pqr, for primes p, q, and r. Calculation shows that exactly one extra bit can be hidden in the digitally signed message. The cure for this was found by cryptologists at the
Centrum Wiskunde & Informatica
The (abbr. CWI; English: "National Research Institute for Mathematics and Computer Science") is a research centre in the field of mathematics and theoretical computer science. It is part of the institutes organization of the Dutch Research Cou ...
in
Amsterdam
Amsterdam ( , , , lit. ''The Dam on the River Amstel'') is the Capital of the Netherlands, capital and Municipalities of the Netherlands, most populous city of the Netherlands, with The Hague being the seat of government. It has a population ...
, who developed a
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
that n is of the form n = pq. This example was motivated in part by
The Empty Silo Proposal.
Example - RSA Case study
Here is a (real, working) PGP public key (using the RSA algorithm), which was generated to include two subliminal channels - the first is the "key ID", which should normally be random hex, but below is "covertly" modified to read "C0DED00D". The second is the base64 representation of the public key - again, supposed to be all random gibberish, but the English-readable message "//This+is+Christopher+Drakes+PGP+public+key//Who/What+is+watcHIng+you//" has been inserted. Adding both these subliminal messages was accomplished by tampering with the random number generation during the RSA key generation phase.
PGP Key. RSA 2020/C0DED00D Fprint: 250A 7E38 9A1F 8A86 0811 C704 AF21 222C
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: Private
mQESAgAAAAAAAAEH5Ar//This+is+Christopher+Drakes+PGP+public+key//
Who/What+is+watcHIng+you//Di0nAraP+Ebz+iq83gCa06rGL4+hc9Gdsq667x
8FrpohTQzOlMF1Mj6aHeH2iy7+OcN7lL0tCJuvVGZ5lQxVAjhX8Lc98XjLm3vr1w
ZBa9slDAvv98rJ8+8YGQQPJsQKq3L3rN9kabusMs0ZMuJQdOX3eBRdmurtGlQ6AQ
AfjzUm8z5/2w0sYLc2g+aIlRkedDJWAFeJwAVENaY0LfkD3qpPFIhALN5MEWzdHt
Apc0WrnjJDby5oPz1DXxg6jaHD/WD8De0A0ARRAAAAAAAAAAAbQvQ2hyaXN0b3Bo
ZXIgRHJha2UgPENocmlzdG9waGVyLkRyYWtlQFBvQm94LmNvbT60SE5ldFNhZmUg
c2VjdXJpdHkgc29mdHdhcmUgZGlyZWN0b3IgQ2hyaXN0b3BoZXIgRHJha2UgPE5l
dFNhZmVAUG9Cb3guY29tPokBEgMFEDPXgvkcP9YPwN7QDQEB25oH4wWEhg9cBshB
i6l17fJRqIJpXKAz4Zt0CfAfXphRGXC7wC9bCYzpHZSerOi1pd3TpHWyGX3HjGEP
6hyPfMldN/sm5MzOqgFc2pO5Ke5ukfgxI05NI0+OKrfc5NQnDOBHcm47EkK9TsnM
c3Gz7HlWcHL6llRFwk75TWwSTVbfURbXKx4sC+nNExW7oJRKqpuN0JZxQxZaELdg
9wtdArqW/SY7jXQn//YJV/kftKvFrA24UYLxvGOXfZXpP7Gl2CGkDI6fzism75ya
xSAgn9B7BqQ4BLY5Vn+viS++6Rdavykyd8j9sDAK+oPz/qRtYJrMvTqBErN4C5uA
IV88P1U=
=/BRt
-----END PGP PUBLIC KEY BLOCK-----
Improvements
A modification to the
Brickell and DeLaurentis signature scheme provides a broadband channel without the necessity to share the authentication key.
[Gustavus J. Simmons. ]
A Secure Subliminal Channel (?)
'. In CRYPTO ’85: Advances in Cryptology, pages 33–41, London, UK, 1986. Springer-Verlag.
The
Newton channel is not a subliminal channel, but it can be viewed as an enhancement.
[Ross J. Anderson, Serge Vaudenay, Bart Preneel, and Kaisa Nyberg. ]
The Newton Channel
'. In Proceedings of the First International Workshop on Information Hiding, pages 151–156, London, UK, 1996. Springer-Verlag.
Countermeasures
With the help of the
zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
and the
commitment scheme
A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.Oded Goldreich (2001). Foundations of Crypt ...
it is possible to prevent the usage of the subliminal channel.
[Yvo Desmedt. ]
Abuses in Cryptography and How to Fight Them
'. In CRYPTO ’88: Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, pages 375–389, London, UK, 1990. Springer-Verlag.[
Yvo Desmedt.
"Subliminal-free authentication and signature".
p. 24 of
Christoph G. Günther, editor]
"Advances in Cryptology - EUROCRYPT '88"
1988.
It should be mentioned that this countermeasure has a 1-bit subliminal channel. The reason for that is the problem that a proof can succeed or purposely fail.
Another countermeasure can detect, but not prevent, the subliminal usage of the randomness.
References
{{reflist
* Bruce Schneier. Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C, 2. Ed. Wiley Computer Publishing, John Wiley & Sons, Inc., 1995.
External links
Cryptography