Kleptography - undetectable key recovery

Kleptography; "The art and science of stealing information securely and subliminally. Kleptographic attacks are primarily geared towards designing black box ciphers to leak secret key information securely and subliminally to the designer."

This is yet another argument for why source code for cryptographic programs should be publicly available. Technically, this could be ranked as the perfect key recovery method since not even experts can not discover its existence. PGP users will not be affected by this hidden key recovery method, since PGP's source code is publicly available. PGP's quality control is based upon the believe that the first one who discovers undocumented code parts would ring the alarm bell. For other encryption programs, which are distributed in binary form, New Image suggests that the only protection is to create a quality control authority that certifies encryption programs.

The main idea is to have encryption program to use a special key generator. When a key pair is created, the public key contains clues to the private key. Only the implementor of the key generator knows how to interpret the clues.

The term Kleptography was introduced by Adam Young and Moti Yung at Crypto '96 Rump Session Presentations.

Published:
Adam Young, Moti Yung: The Dark Side of "Black-Box" Cryptography, or: Should We Trust Capstone? CRYPTO 1996: page 89-103, LNCS (Lecture Notes in Computer Science) #1109, exists also in postscriptformat.

A. Young, M. Yung, "Kleptography: Using Cryptography Against Cryptography",
Eurocrypt '97, page 62-74, Springer-Verlag, LNCS #1233, ISBN 3-540-62975-0

A. Young, M. Yung, "The Prevalence of Kleptographic Attacks on Discrete-Log
Based Cryptosystems
", CRYPTO '97, page 264-276, Springer-Verlag, LNCS #1294, ISBN 3-540-63384-7

 

August 5, 1998. The company; New Image has packaged the mathemathic into a product. A Crypto toolkit that contains an RSA key generator with the special characteristic to also include a hidden (sublimal) backdoor in to the private the encryption keys. It is especially well suited for creating a hidden key recovery function in encryption programs.
"A Key Recovery System Based on the Subliminal RSA Key Generator" By Gregory Y. Tang, August 8, 1998
Pressrelease: RSA Cryptosystem with a hidden backdoor,   http://www.newimage.com.tw/crypto/pr03.htm
It is also possible to download a free demoversion of this "subliminal RSA key generator"

--- A cut from the press release from New Engine, 5 Aug -98  ---

"RSA Cryptosystem with a backdoor
... worldwide marketing ... of the RSA cryptosystem with a backdoor ... [it] is different from the commonly used RSA cryptosystem. It has a unique feature called the backdoor PD. ... The existence of [a backdoor in] RSA system is due to the subliminal RSA key generator .... [that] can generate the RSA key pairs which can be used in any existent RSA systems. For those who know the backdoor PD can extract the subliminal data easily. For those who do not know the backdoor cannot distinguish the subliminal RSA keys and the regular RSA keys. Practically anything can be put in the subliminal channel. So the backdoor PD can be used to recognized whether a particular key is generated by a given key generator.
... the subliminal RSA cryptosystem has the same strength as the regular RSA cryptosystem. And no method found yet, by looking at only the keys without the knowledge of the backdoor, can tell whether the keys are generated by a regular RSA key generator or by a subliminal RSA key generator.
The existence of such a subliminal RSA key generator places a serious threat on any existing applications which use RSA cryptography. One threat is that the client will not be able to tell whether the key generator he got from his contractor or from the shelve is a regular one or a subliminal one. It will be dangerously incentive for the software engineer to cheat his clients by offering his clients subliminal key generators unlawfully. Another possible threat is to use the subliminal RSA key generator as a weapon in the infowar. One can use the subliminal RSA technology to make an imposter of a regular RSA key generator. Then he can silently replace the regular key generator with the imposter, either manually or via virus. The enemy will not know and will use the imposter. The secretes of the enemy is thus exposed.
The so called "Government Access Cryptosystem" can be implemented with the subliminal RSA key generation technique. The government can easily order all the lawful certificate authorities to accept public key certificate request only for those keys which are generated by a backdoor key generator and the government knows the backdoor. In this way, person_to_person secrecy can be maintained, but nothing is secrete to the government. There is no need to maintain a huge database to hold all the keys of all the people any more. And people can generate keys any way he likes as if no one is watching. Obviously, this concept can extend to "Corporate Access Cryptosystem," and "Cryptosystem with an Access Tree," where the lower level has no secrete to the upper level, but the upper level can keep secrete with the lower level.
A complete development tool for the RSA cryptosystem with a backdoor will be included in the forthcoming toolkit CryptoEngine. "

Reference:
RSA Cryptosystem with a hidden backdoor, Pressrelease:  August 5, 1998, http://www.newimage.com.tw/crypto/pr03.htm


Latest change 11 November -98, Laszlo Baranyi, lb@qainfo.se, PGP5 Key ID; 3CEAEF2C