Our work on Cryptovirology

The papers below cover our contributions to cryptovirology. There are many other results in this area by other research scientists, some of which are mentioned in the FAQ, some of which are covered in "Malicious Cryptography," etc.

Cryptoviral Extortion
  • Adam Young, "Cryptoviral Extortion Using Microsoft's Crypto API: Can Crypto APIs Help the Enemy?," International Journal of Information Security, v. 5, n. 2, pages 67-76, Springer, April, 2006. (Journal version of the ISC '05 paper shown below) .

    Abstract. This paper presents the experimental results that were obtained by implementing the payload of a cryptovirus on the Microsoft Windows platform. The attack is based entirely on the Microsoft Cryptographic API and the needed API calls are covered in detail. More specifically, it is shown that by using eight types of API calls and 72 lines of C code, the payload can hybrid encrypt sensitive data and hold it hostage. Benchmarks are also given. A novel countermeasure against cryptoviral extortion attacks is shown that forces the API caller to demonstrate that an authorized party can recover the asymmetrically encrypted data.

  • Adam Young, "Building a Cryptovirus Using Microsoft's Cryptographic API," Information Security Conference---ISC '05, Jianying Zhou, Javier Lopez (Eds.), LNCS 3650, pages 389-401, 2005.

    Abstract. This paper presents the experimental results that were obtained by implementing the payload of a cryptovirus on the Microsoft Windows platform. A novel countermeasure against cryptoviral extortion is presented that forces the API caller to demonstrate that an authorized party can recover the asymmetrically encrypted data. The attack is based entirely on the Microsoft Cryptographic API and the needed API calls are covered in detail. The exact sequence of API calls that is used for both the viral payload and the code for key generation, decryption, and so on is given. More specifically, it is shown that by using 8 types of API calls and 72 lines of ANSI C code, the payload can hybrid encrypt sensitive data and hold it hostage on the host computer system. These findings demonstrate the ease with which one can apply cryptography to devise the payload of a cryptovirus when a cryptographic API is readily available on host machines.

  • Adam Young, Moti Yung, "Cryptovirology: Extortion-Based Security Threats and Countermeasures," IEEE Symposium on Security & Privacy, pages 129-141, May 6-8, 1996.

    Abstract. Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. In this paper we present the idea of Cryptovirology which employs a twist on cryptography, showing that it can also be used offensively. By being offensive we mean that it can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents. In this paper we analyze potential threats and attacks that rogue use of cryptography can cause when combined with rogue software (viruses, Trojan horses), and demonstrate them experimentally by presenting an implementation of a cryptovirus that we have tested (we took careful precautions in the process to insure that the virus remained contained). Public-key cryptography is essential to the attacks that we demonstrate (which we call "cryptovirological attacks"). We also suggest countermeasures and mechanisms to cope with and prevent such attacks. These attacks have implications on how the use of cryptographic tools should be managed and audited in general purpose computing environments, and imply that access to cryptographic tools should be well controlled. The experimental virus demonstrates how cryptographic packages can be condensed into a small space, which may have independent applications (e.g., cryptographic module design in small mobile devices).

  • Evasive Electronic Espionage/Deniable Password Snatching
  • Adam Young, Moti Yung, "Deniable Password Snatching: On the Possibility of Evasive Electronic Espionage," IEEE Symposium on Security & Privacy, pages 224-235, May 4-7, 1997.

    Abstract. Cryptovirology has recently been introduced as a means of mounting active viral attacks using public key cryptography. It has been shown to be a tool for extortion attacks and "electronic warfare", where attacks are mounted against information resources. The natural question to ask is whether Cryptovirology is also useful in the area of spying via malware. We demonstrate that Cryptovirology does help in "electronic espionage" and allows the spy to conceal his or her identity (as well as past collected information). Specifically, we present an attack that can be mounted by a cryptotrojan that allows the attacker to gather information (passwords) from a system in such a way that the attacker cannot be proven guilty beyond reasonable doubt. That is, even if the attacker is under surveillance on the local machine from when he first attacks the target machine, to when he obtains the passwords, and even if the leaked information is made available to the attacker exclusively, he still cannot be caught. The threat is made possible by the combination of public key cryptography, probabilistic encryption, and the use of public information (I/O or communication) channels which together form a "secure receiver-anonymous channel". The machine can be standalone or networked. What we learn from the attack is extracted as general tools and basic principles for "espionage attacks".

  • Asymmetric Backdoors in Block Ciphers (Kleptography)
  • Adam Young, Moti Yung, "A Subliminal Channel in Secret Block Ciphers," Selected Areas in Cryptography---SAC '04, Helena Handschuh, M. Anwar Hasan (Eds.), LNCS 3357, pages 198-211, 2004.

    Abstract. In this paper we present the first general purpose subliminal channel that can be built into a secret symmetric cipher by a malicious designer. Subliminal channels traditionally exploit randomness that is used in probabilistic cryptosystems. In contrast, our channel is built into a deterministic block cipher, and thus it is based on a new principle. It is a broadcast channel that assumes that the sender and the receiver know the subliminal message ms (i.e., something derived from their common key). We show that the designer can expect to be able to read ms when O(|ms| log |ms|) plaintext/ciphertext pairs are obtained. Here |ms| is the length of ms in bits. We show how to turn the channel into a narrowcast channel using a deterministic asymmetric cipher and then present an application of the narrowcast channel. In this application, the secret block cipher securely and subliminally transmits the symmetric key of the sender and receiver to the malicious designer and confidentiality holds even when the cipher is made public.

  • Adam Young, Moti Yung, "Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy Plaintexts," 8th Australasian Conference on Information Security and Privacy---ACISP '03, Reihaneh Safavi-Naini, Jennifer Seberry (Eds.), LNCS 2727, pages 297-311, 2003.

    Abstract. There has been much recent research in designing symmetric ciphers with backdoors that have either public designs or black-box designs. Current Digital Rights Management needs have resurrected the use of hidden ciphers (which were traditionally suggested by the government as black-box designs) in the form of obfuscated "white-box" algorithms. A recent backdoor proposal is the Monkey cipher which is intended to have a secret design and that can be implemented using any deterministic trapdoor one-way function (that is used off-line). Monkey leaks information about its user's key to the designer. The primary drawback of Monkey is that it requires the designer (attacker) to obtain a sufficient number of ciphertexts all under the same symmetric key, such that each contains one known plaintext bit. The attacker is thus faced with the potentially arduous task of collecting enough of these bits in order to form the full public key ciphertext of the users symmetric key. In this paper a new design is proposed that eliminates the need for known plaintext entirely . Also, whereas Monkey reveals one plaintext bit of each ciphertext to the reverse-engineer (i.e., an entity that tries to learn the black-box device), our solution only leaks a bound on the message entropy to the reverse-engineer, while requiring that the designer obtain a sufficient number of ciphertexts that encrypt messages with a requisite level of redundancy. The information leakage method we use employs "data compression" as a basic tool for generating a hidden information channel. This highlights the need to only encrypt compressed (high entropy) strings when a block cipher with a secret design must be used.

  • Adam Young, Moti Yung, "Monkey: Black-Box Symmetric Ciphers Designed for monopolizing keys," In proceedings of Fast Software Encryption---FSE '98, Serge Vaudenay (Ed.), LNCS 1372, pages 122-133, 1998.

    Abstract. We consider the problem of designing a black-box symmetric cipher that leaks information subliminally and exclusively to the designer. We show how to construct a cipher which we call `Monkey' that leaks one key bit per output block to the designer of the system (in any mode). This key bit is leaked only if a particular plaintext bit is known to the designer (known bit/message attack which is typically available in plain ASCII). The attack is of kleptographic nature as it gives a unique advantage to the designer while using strong (e.g., externally supplied) keys. The basic new difficulty with the design of spoofable block ciphers is that it is a deterministic function (previous attacks exploited randomness in key generation or message encryption/signature), and the fact that we do not want easy (statistical) observability of the spoofing (e.g., the variability of ciphertexts should be noticeable when keys change etc.). We distinguish between three entities: the designer, the reverse-engineer and the user. We show a design methodology that assures that: (1) if the device is not reverse-engineered, the attack is secure (namely, the cipher is good) and undetectable, (2) if the device is reverse-engineered, then the reverse-engineer learns at most one plaintext bit from every ciphertext (but no past/future keys), and (3) the designer learns one plaintext bit and one key bit from each ciphertext block (say in ECB mode). The method is therefore highly robust against reverse-engineering.

  • Asymmetric Backdoors in Asymmetric Key Generation, Signing, Key Exchange, etc. (Kleptography)
  • Adam Young, Moti Yung, "A Space Efficient Backdoor in RSA and its Applications," Selected Areas in Cryptography---SAC '05, Bart Preneel, Stafford Tavares (Eds.), LNCS 3897, pages 128-143, 2005.
  • Adam Young, "Mitigating insider threats to RSA key generation," CryptoBytes, RSA Laboratories, vol. 7, no. 1, Spring 2004.

    Abstract. RSA keys form the cornerstone for numerous security systems. They provide for confidentiality of communications as well as non-repudiability of digital signatures. However, there are several insider attacks against RSA key generation that can have devastating effects when carried out. In this paper we address such attacks by surveying measures that can be taken to mitigate insider attacks against RSA generation.

  • Adam Young, Moti Yung, "Malicious Cryptography: Kleptographic Aspects," The Cryptographers' Track at the RSA Conference, Alfred Menezes (Ed.), LNCS 3376, pages 7-18, 2005.

    Abstract. In the last few years we have concentrated our research efforts on new threats to the computing infrastructure that are the result of combining malicious software (malware) technology with modern cryptography. At some point during our investigation we ended up asking ourselves the following question: what if the malware (i.e., Trojan horse) resides within a cryptographic system itself? This led us to realize that in certain scenarios of black box cryptography (namely, when the code is inaccessible to scrutiny as in the case of tamper proof cryptosystems or when no one cares enough to scrutinize the code) there are attacks that employ cryptography itself against cryptographic systems in such a way that the attack possesses unique properties (i.e., special advantages that attackers have such as granting the attacker exclusive access to crucial information where the exclusive access privelege holds even if the Trojan is reverse-engineered). We called the art of designing this set of attacks kleptography. In this paper we demonstrate the power of kleptography by illustrating a carefully designed attack against RSA key generation.

  • Adam Young, Moti Yung, "The Dark Side of Black-Box Cryptography, or: Should we trust Capstone?" Advances in Cryptology---Crypto '96, Neal Koblitz (Ed.), LNCS 1109, pages 89-103, 1996.

    Abstract. The use of cryptographic devices as "black boxes", namely trusting their internal designs, has been suggested and in fact Capstone technology is offered as a next generation hardware-protected escrow encryption technology. Software cryptographic servers and programs are being offered as well, for use as library functions, as cryptography gets more and more prevalent in computing environments. The question we address in this paper is bow the usage of cryptography as a black box exposes users to various threats and attacks that are undetectable in a black-box environment. We present the SETUP (Secretly Embedded Trapdoor with Universal Protection) mechanism, which can be embedded in a cryptographic black-box device. It enables an attacker (the manufacturer) to get the user's secret (from some stage of the output process of the device) in an unnoticeable fashion, yet protects against attacks by others and against, reverse engineering (thus, maintaining the relative advantage of the actual attacker). We also show how the SETUP can, in fact, be employed for the design of "auto-escrowing key" systems. We present embeddings of SETUPs in RSA, El-Gamal, DSA, and private key systems (Kerberos). We implemented an RSA key-generation based SETUP that performs favorably when compared to PGP, a readily available RSA implementation. We also relate message-based SETUPs and subliminal channel attacks. Finally, we reflect on the potential implications of "trust management" in the context of the design and production of cryptosystems.

  • Adam Young, Moti Yung, "Kleptography: Using Cryptography Against Cryptography," Advances in Cryptology---Eurocrypt '97, Walter Fumy (Ed.), LNCS 1233, pages 62-74, 1997.

    Abstract. The notion of a Secretly Embedded Trapdoor with Universal Protection (SETUP) has been recently introduced. In this paper we extend the study of stealing information securely and subliminally from black-box cryptosystems. The SETUP mechanisms presented here, in contrast with previous ones, leak secret key information without using an explicit subliminal channel. This extends this area of threats, which we call "kleptography". We introduce new definitions of SETUP attacks (strong, regular, and weak SETUPs) and the notion of m out of n leakage bandwidth. We show a strong attack which is based on the discrete logarithm problem. We then show how to use this setup to compromise the Diffie-Hellman key exchange protocol. We also strengthen the previous SETUP against RSA. The strong attacks employ the discrete logarithm as a one-way function (assuring what is called "forward secrecy"), public-key cryptography, and a technique which we call probabilistic bias removal.

  • Adam Young, Moti Yung, "The Prevalence of Kleptographic Attacks on Discrete-Log Based Cryptosystems," Advances in Cryptology---Crypto '97, Burton S. Kaliski Jr. (Ed.), LNCS 1294, pages 264-276, 1997.

    Abstract. The notion of a Secretly Embedded Trapdoor with Universal Protection (SETUP) and its variations on attacking black-box cryptosystems has been recently introduced. The basic definitions, issues, and examples of various setup attacks (called Kleptographic attacks) have also been presented. The goal of this work is to describe a methodological way of attacking cryptosystems which exploits certain relations between cryptosystem instances which exist within cryptosystems. We call such relations "kleptograms". The identified kleptogram is used as the base for searching for a setup. In particular, we employ as a discrete log based kleptogram a basic setup that was presented for the Diffie-Hellman key exchange. We show how it can be embedded in a large number of systems: the ElGamal encryption algorithm, the ElGamal signature algorithm, DSA, the Schnorr signature algorithm, and the Menezes-Vanstone PKCS. These embeddings can be extended directly to the MTI two-pass protocol, the Girault key agreement protocol, and many other cryptographic systems. These attacks demonstrate a systematic way to mount kleptographic attacks. They also show the vulnerability of systems based on the difficulty of computing discrete logs. The setup attack on DSA exhibits a large bandwidth channel capable of leaking information which hardware black-box implementations (e.g., the Capstone chip) can use. We also show how to employ such channels for what we call "device marking". Finally, note that it has been perceived that the DSA signature scheme was originally designed to be robust against its abuse as a public-key channel - to distinguish it from RSA signatures (where the signing function is actually a decryption function). In this paper we refute this "perceived advantage" and show how the DSA system (in hardware or software) can be easily modified to securely leak private keys and secure messages between two cooperating parties.

  • Adam Young, Moti Yung, "Bandwidth-Optimal Kleptographic Attacks," Cryptographic Hardware and Embedded Systems---CHES '01, Cetin Kaya Koc, David Naccache, Christof Paar (Eds.), LNCS 2162, pages 235-250, 2001.

    Abstract. Cryptographic and physical leakage attacks on devices and systems which implement cryptosystems, is an area of much recent activities. One type of attacks are what is called kleptographic attacks which are mounted against black-box cryptosystems. They are issued by and serve solely the designer/manufacturer giving it unique advantage. Kleptographic attacks are capable of leaking the private keys of users securely and subliminally to the manufacturer of the black-box system (based on the availability of public values, such as keys (produced when the system is initiated) or signature/ciphertext values (produced by systems in operation). These attacks provide a very high level of security against reverse-engineering since even if the black-box is successfully reverse-engineered, no information can be obtained that compromises the secrets of the users (thus, the unique advantage of the attacker is retained).

    Numerous open questions remain in the area. One issue is that the only key generation procedure with known attack is the RSA/factoring based PKC, while for Discrete Logarithm based keys attacks are not known. Similarly open, is the existence of bandwidth-optimal leakage attacks, namely attacks on a “single signature” in Discrete Logarithm based signatures (both in the full group and prime order sub-group cases).

    In this paper, we solve the above open questions. We develop new attack techniques, which unlike earlier attacks, require only one value in order to leak the secret. This gives an attack on modular exponentiation keys. We then show how to implement an attack on ElGamal signature which leaks the private key in each signature, and which requires only 160 bits of smoothness in p-1, where p is the common ElGamal prime. The attack utilizes the Newton channel. This channel, however, does not extend to DSA, since DSA operates in a prime order subgroup of Zp. In the second part of this work, we nevertheless show a subliminal channel attack on DSA that assumes the existence of a small amount of non-volatile memory in the device. This gives a kleptographic attack against DSA that leaks the private key in each signature as well. Non-volatility is only needed to assure the polynomial indistinguishability of the outputs of the devices under attack from that of a normal devices' outputs. We investigate our non-volatility assumption against hardware feasibility (in quite a popular EEPROM devices, used in manufacturing of smart-cards).

  • Questionable Encryption
  • Adam Young, Moti Yung, "On Fundamental Limitations of Proving Data Theft," IEEE Transactions on Information Forensics and Security, Volume 1, number 4, pages 524-531, December 2006.

    (this version of the abstract fixes last-minute editorial errors)

    Abstract. We show software agents that operate on input plaintext, transmit the result, and have the property that characterizing the operation as theft of plaintext amounts to solving a hard cryptographic problem. Such agents employ what we call a "questionable encryption scheme" in which it is computationally intractable to determine if the output is an asymmetric ciphertext or nonce. We therefore show a fundamental computational limitation of information forensics.

  • Adam Young, Moti Yung, "Questionable Encryption and its Applications," First International Conference on Cryptology in Malaysia---MyCrypt '05, Ed Dawson, Serge Vaudenay (Eds.), LNCS 3715, pages 210-221, 2005.

    Abstract. In this paper we investigate a primitive called a questionable encryption that is related to oblivious transfer. We consider a mobile agent that asymmetrically encrypts plaintext data from the host machine that it resides on and then broadcasts the resulting ciphertext so that it can be obtained by the creator of the agent. We formally define the notion of a questionable encryption scheme that can be used to perform this operation. The user of a questionable encryption scheme chooses to generate a real or fake public key. The choice is conveyed to the key generation algorithm which then outputs a poly-sized witness and either a real or fake key pair. If the public key is `real' then it produces decipherable encryptions and the poly-sized witness proves this. If the key is generated to be `fake' then it produces indecipherable encryptions (even with the private key) and the poly-sized witness proves this. Without knowledge of the witness it is intractable to distinguish between the two types of public keys. We present a construction for a questionable encryption scheme based on the Paillier cryptosystem. We prove the security of the scheme based on the difficulty of deciding nth degree composite residuosity. When applied to this application, the creator of the agent retains the exclusive ability to reveal whether or not the agent in fact transmits plaintexts. Our results show that agents that appear to compute asymmetric encryptions may in fact not (in a provable sense). We present other applications of questionable encryptions as well.

  • Adam Young, Moti Yung, "Hiding Information Hiding," 8th Conference on Information Hiding---IH '06, Jan Camenisch, Christian Collberg (Eds.), July 10-12, 2006. Conference Website
  • Distributed Game-Theoretic Cryptoviral Attacks
  • Adam Young, "Non-Zero Sum Games and Survivable Malware," 4th Annual IEEE Information Assurance Workshop, United States Military Academy, West Point, New York, 2003.

    Abstract. There has been much recent work in the area of beneficial mobile agents and malicious mobile agents such as cryptoviruses. In this paper a novel distributed cryptovirus attack is presented that forces the victim to become a player in a non-zero sum game under the threat of sensitive information disclosure. The attack is modeled as a non-zero sum game wherein the rules are enforced by cryptographic protocols. It is shown that the optimal strategy for the host machine involves the extension of the life of the payload even after it is discovered. This therefore extends both the life and decision capability of the virus. The existence of this attack demonstrates the plausibility of survivable malware in public networks. The attack assumes the existence of a public mix network and the wide-scale adoption of Public Key Infrastructures.

  • Threshold Cryptovirology Attacks

  • Shouhuai Xu, Moti Yung, "The Dark Side of Threshold Cryptography," Financial Cryptography, Matt Blaze (Ed.), LNCS 2357, pages 198-219, 2002.

    Abstract. It is typical for a cryptographic technology to be useful in its primary goal and applications, yet to exhibit also a dark side, namely to allow abuses in some other situations. Examples are subliminal channels in strong (randomized) signature schemes, employing authentication for encryption, kleptography exploiting strong randomness, etc. Threshold cryptography was introduced to realize better security and availability. However, its "dark side" has never been addressed seriously. We investigate some possible abuses of threshold cryptography which result from users not possessing the entire private key due to threshold splitting. This is a deficiency which can hurt de-commitment in procedures like "contract signing" and nullify non-transferability properties. To attempt solving the problem, one may suggest to assure that the user has full control of his private key via a zero-knowledge confirmation. However, advances in cryptography itself defeat this, since the Completeness Theorem for secure computations implies that servers in possession of shares of a key can answer on behalf of the "virtual holder" of the entire private key, without compromising the secrecy of their shares. We are then forced to look at more physical limitations of the setting. We propose a notion we call Verifiable Secret Non-Sharing (VSNS) where we can replace the strong (i.e., less realistic) physical isolation assumption (namely, a Faraday's cage) with a more realistic timing assumption. We then introduce a new class of "combined software engineering and cryptography" adversarial capability, which employs software preprocessing and cryptography in breaking all previous suggestions to our problem. It seems that the adversary is so powerful that we have to rely on certain tamper-resistant device to block it. We show how to prevent a malicious participant from compromising the secrecy of the provers' secret keys in this case.

  • Other Research