Kleptography
Encyclopedia
Kleptography is the study of stealing information securely and subliminally. Kleptography is a subfield of cryptography
and cryptovirology
, and is a natural extension of the theory of subliminal channels
that was pioneered by Gus Simmons
. Kleptography is also related to steganography
.
Kleptography was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96. A kleptographic attack is a forward-engineering attack that is built into a cryptosystem or cryptographic protocol. The attack constitutes an asymmetric backdoor that is built into a smartcard, dynamically linked library, computer program
, or other cryptographic device. Unlike a symmetric backdoor, which can be accessed by anyone who is aware of it, an asymmetric backdoor can be used exclusively by the attacker who planted it. Even if the full specification of the backdoor is published, it would remain unusable without additional data possessed only by the attacker. Furthermore, the outputs of the infected cryptosystem are computationally indistinguishable from the outputs of the corresponding uninfected cryptosystem. Hence, in black-box implementations (e.g., smartcards) the attack is likely to go entirely unnoticed. The asymmetry ensures that even a well-funded reverse-engineer can at best detect the asymmetric backdoor — but not use it.
Kleptographic attacks can be constructed as a cryptotrojan that infects a cryptosystem and opens a backdoor for the attacker, or can be implemented by the manufacturer of a cryptosystem. The attack does not necessarily have to reveal the entirety of the cryptosystem's output; a more complicated attack technique may alternate between producing uninfected output and insecure data with the backdoor present.
Kleptographic attacks have been designed for RSA key generation, the Diffie-Hellman key exchange, the Digital Signature Algorithm
, and other cryptographic algorithms and protocols. SSL, SSH
and IPSec
protocols are vulnerable to kleptographic attacks. In each case, the attacker is able to compromise the particular cryptographic algorithm or protocol by inspecting the information that the backdoor information is encoded in (e.g., the public key, the digital signature, the key exchange messages, etc.) and then exploiting the logic of the asymmetric backdoor using his or her secret key (usually a private key).
A. Juels and J. Guajardo proposed a method (KEGVER) through which a third party can verify RSA key generation. This is devised as a form of distributed key generation in which the secret key is only known to the black box itself. This assures that the key generation process was not modified and that the private key cannot be reproduced through a kleptographic attack.
Four practical examples of kleptographic attacks (including a simplified SETUP attack against RSA) can be found in JCrypTool 1.0, the platform-independent version of the open-source CrypTool
project. A demonstration of the prevention of kleptographic attacks by means of the KEGVER method is also implemented in JCrypTool.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and cryptovirology
Cryptovirology
Cryptovirology is a field that studies how to use cryptography to design powerful malicious software. The field was born with the observation that public-key cryptography can be used to break the symmetry between what an antivirus analyst sees regarding a virus and what the virus writer sees...
, and is a natural extension of the theory of subliminal channels
Subliminal channels
In cryptography, subliminal channels are covert channels that can be used to communicate secretly in a normal looking communication over an insecure channel with help of digital signatures...
that was pioneered by Gus Simmons
Gustavus Simmons
Gustavus J. Simmons is a retired cryptographer and former manager of the applied mathematics Department and Senior Fellow at Sandia National Laboratories...
. Kleptography is also related to steganography
Steganography
Steganography is the art and science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message, a form of security through obscurity...
.
Kleptography was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology—Crypto '96. A kleptographic attack is a forward-engineering attack that is built into a cryptosystem or cryptographic protocol. The attack constitutes an asymmetric backdoor that is built into a smartcard, dynamically linked library, computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, or other cryptographic device. Unlike a symmetric backdoor, which can be accessed by anyone who is aware of it, an asymmetric backdoor can be used exclusively by the attacker who planted it. Even if the full specification of the backdoor is published, it would remain unusable without additional data possessed only by the attacker. Furthermore, the outputs of the infected cryptosystem are computationally indistinguishable from the outputs of the corresponding uninfected cryptosystem. Hence, in black-box implementations (e.g., smartcards) the attack is likely to go entirely unnoticed. The asymmetry ensures that even a well-funded reverse-engineer can at best detect the asymmetric backdoor — but not use it.
Kleptographic attacks can be constructed as a cryptotrojan that infects a cryptosystem and opens a backdoor for the attacker, or can be implemented by the manufacturer of a cryptosystem. The attack does not necessarily have to reveal the entirety of the cryptosystem's output; a more complicated attack technique may alternate between producing uninfected output and insecure data with the backdoor present.
Kleptographic attacks have been designed for RSA key generation, the Diffie-Hellman key exchange, the Digital Signature Algorithm
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...
, and other cryptographic algorithms and protocols. SSL, SSH
Secure Shell
Secure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...
and IPSec
IPsec
Internet Protocol Security is a protocol suite for securing Internet Protocol communications by authenticating and encrypting each IP packet of a communication session...
protocols are vulnerable to kleptographic attacks. In each case, the attacker is able to compromise the particular cryptographic algorithm or protocol by inspecting the information that the backdoor information is encoded in (e.g., the public key, the digital signature, the key exchange messages, etc.) and then exploiting the logic of the asymmetric backdoor using his or her secret key (usually a private key).
A. Juels and J. Guajardo proposed a method (KEGVER) through which a third party can verify RSA key generation. This is devised as a form of distributed key generation in which the secret key is only known to the black box itself. This assures that the key generation process was not modified and that the private key cannot be reproduced through a kleptographic attack.
Four practical examples of kleptographic attacks (including a simplified SETUP attack against RSA) can be found in JCrypTool 1.0, the platform-independent version of the open-source CrypTool
Cryptool
CrypTool is an open source e-learning tool illustrating cryptographic concepts.-Features:The graphical interface, online documentation, analytic tools and algorithms of CrypTool introduce users to the field of cryptography...
project. A demonstration of the prevention of kleptographic attacks by means of the KEGVER method is also implemented in JCrypTool.