Kleptography

Key takeaways

Kleptography belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Kleptography to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Kleptography from memory before moving on to harder problems.

Reference excerpt

Kleptography is the study of stealing information securely and subliminally. The ideas were introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96 and the term was coined in their EUROCRYPT '97 paper. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

Kleptographic attack

Meaning A kleptographic attack is an attack which uses asymmetric cryptography to implement a cryptographic backdoor. For example, one such attack could be to subtly modify how the public and private key pairs are generated by the cryptosystem so that the private key could be derived from the public key using the attacker's private key. In a well-designed attack, the outputs of the infected cryptosystem would be computationally indistinguishable from the outputs of the corresponding uninfected cryptosystem. If the infected cryptosystem is a black-box implementation such as a hardware security module, a smartcard, or a Trusted Platform Module, a successful attack could go completely unnoticed. A reverse engineer might be able to uncover a backdoor inserted by an attacker, and when it is a symmetric backdoor, even use it themself. However, by definition a kleptographic backdoor is asymmetric and the reverse-engineer cannot use it. A kleptographic attack (asymmetric backdoor) requires a private key known only to the attacker in order to use the backdoor. In this case, even if the reverse engineer was well-funded and gained complete knowledge of the backdoor, it would remain useless for them to extract the plaintext without the attacker's private key.

Construction 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.

Design 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 their 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.

Examples 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. The Dual_EC_DRBG cryptographic pseudo-random number generator from the NIST SP 800-90A is thought to contain a kleptographic backdoor. Dual_EC_DRBG utilizes elliptic curve cryptography, and NSA is thought to hold a private key which, together with bias flaws in Dual_EC_DRBG, allows NSA to decrypt SSL traffic between computers using Dual_EC_DRBG for example. The algebraic nature of the attack follows the structure of the repeated Dlog Kleptogram in the work of Young and Yung.

References

Worked examples

Example 1 — a first encounter with Kleptography

Start with the simplest possible case. Write down what Kleptography claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Kleptography before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Kleptography ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Kleptography

In research: Kleptography appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Kleptography in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Kleptography is common in secondary-school and first-year university syllabi. It links to neighbouring topics Kleptography, so understanding it makes those chapters shorter.
In everyday life: Look for Kleptography outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Kleptography in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Kleptography means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Kleptography out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Kleptography in simple terms?

Kleptography is the study of stealing information securely and subliminally. The ideas were introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96 and the term was coined in their EUROCRYPT '97 paper.

Why does Kleptography matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Kleptography?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Kleptography.