Towards a Book on Advances in Cryptovirology

Below are chapters and appendices of our forthcoming book on Advances in Cryptovirology. The chapters and appendices present our Fundamental Research in modern cryptovirology. The chapters are available as Adobe PDF files. The appendices contain ANSI C source code. The appendices are in the form of .c and .h files given in a .zip file. We have not yet finalized on a title for the book. All of this material is copyrighted (see fair use).

Notice to researchers and students: If possible please try to cite the papers and books that these chapters are based on rather than the chapters themselves. The book has no title yet, the chapter numbers and titles may well change, and so on. If the material that needs citation is known to be particular to the chapter below then of course there is no avoiding citing the chapter.

Chapter 2: Using Microsoft's Crypto API for Cryptoviral Extortion
Abstract. This chapter presents an experimental implementation of cryptoviral extortion, an attack that we devised and presented at the 1996 IEEE Symposium on Security & Privacy [16] and that was recently covered in Malicious Cryptography [17]. The design is based on Microsoft's Cryptographic API and the salient aspects of the implementation were presented at ISC '05 and in the International Journal of Information Security [14,15]. Cryptoviral extortion is a 2-party protocol between an attacker and a victim that is carried out by a cryptovirus, cryptoworm, or cryptotrojan. In a cryptoviral extortion attack the malware hybrid encrypts the plaintext of the victim using the public key of the attacker. The attacker extorts some form of payment from the victim in return for the plaintext that is held hostage. In addition to providing hands-on experience with this cryptographic protocol, this chapter gives readers a chance to: (1) learn the basics of hybrid encryption that is commonly used in everything from secure e-mail applications to secure socket connections, and (2) gain a basic understanding of how to use Microsoft's Cryptographic API that is present in modern MS Windows operating systems. The chapter only provides an experimental version of the payload, no self-replicating code is given. We conclude with proactive measures that can be taken by computer users and computer manufacturers alike to minimize the threat posed by this type of cryptovirology attack.

  • Chp 2: Chapter2.pdf, Appendix:
  • Chapter 4: Implementing Perfect Questionable Encryptions
    Abstract. The notion of a questionable encryption scheme was first put forth in Malicious Cryptography [10]. In this chapter we present an implementation of the perfect questionable encryption scheme that appears in [9] that is based on our MyCrypt '05 paper [11]. A questionable encryption (q.e.) scheme is a generalization of a PKCS that includes an additional key generation algorithm that outputs a fake public key and a corresponding witness of non-encryption. The perfect q.e. scheme is based on the Paillier PKCS that produces a private key (that serves as a witness of encryption) and corresponding public key. The scheme includes a predicate F that takes as input a public key and corresponding witness. The output of F is a single bit that proves whether the public key is real or fake. A perfect q.e. scheme has the property that it is information theoretically impossible for everyone including the key pair owner to decrypt ciphertexts produced using the fake public key. Also, fake public keys are computationally indistinguishable from real public keys. It has been shown that a q.e. scheme is ideal for implementation in cryptoviruses, cryptoworms, and cryptotrojans. The use of a q.e. scheme in malware to "encrypt" data prior to transmission casts doubt on the occurrence of data theft, since prosecutors cannot directly prove that such malware encrypts data even when all code, all core dumps, and all packets that are transmitted by the malware are entered into evidence. The attacker retains the witness and can reveal it at any time. Questionable encryptions also serve as a desirable alternative to oblivious transfer in certain applications.

  • Chp 4: Chapter4.pdf, Appendix:
  • Chapter 6: A Cryptocounter Based on the Paillier PKCS
    Abstract. In this chapter we present our implementation of a cryptocounter that is based on the Paillier public key cryptosystem [4]. This material and the corresponding appendix (containing the corresponding source code) constitutes Fundamental Research on the notion of a cryptocounter. Informally, a cryptocounter [3,7] is an asymmetric ciphertext of a plaintext counter that satisfies certain properties. It is produced and incremented using the public key of a key pair owner. It can only be deciphered using the corresponding private key. Confidentiality of a counter holds under the assumed intractability of deciding nth degree composite residuosity. A cryptocounter satisfies the following properties: (1) the increment operation increments the underlying plaintext counter without first decrypting the cryptocounter, (2) the probabilistic re-encryption operation "re-encrypts" the underlying plaintext counter without changing it, and (3) it is intractable to correlate cryptocounters when they are updated in a black-box using the two aforementioned operations. These properties make a cryptocounter highly robust against reverse-engineering. The adversary can only learn the change in counter value by observing it being incremented. There are many possible applications of a cryptocounter. It can be used for digital rights management, to gather statistics in a secure fashion in the honest-but-curious threat model. It can also be used in a cryptotrojan that gathers statistics on a victim (e.g., how often the victim visits a particular website).

  • Chp 6: Chapter6.pdf, Appendix:
  • Chapter 8: An Implementation of Tagged Private Information Retrieval
    Abstract. In this chapter we present an experimental implementation of the tagged private information retrieval protocol (TPIR). Informally, a TPIR protocol retrieves data from a database without revealing the entry that the data is taken from and that satisfies additional security properties. Let B = ((t0,b0),(t1,b1),...,(tW-1,bW-1)) be a database with W entries. Data bi is "tagged", (i.e., uniquely identified) using the tag string ti for i = 0,1,...,W-1. A user wants bi from the database but does not trust the database administrator to know the tag ti. In a TPIR protocol, the user supplies ti to algorithm QueryGenerator which outputs a private key and a query q. The query is given to the database administrator who then passes B and q to DatabaseAlgorithm. The output of this algorithm is a response r. The administrator sends r to the user. The user supplies r and the private key to ResponseRetriever which then outputs bi. These 3 algorithms are public and the protocol satisfies the following properties: (1) q does not reveal ti, (2) the user trusts the database administrator to run DatabaseAlgorithm on the correct inputs and return r to the user, and (3) bi can only be recovered from r using the user's private key. This chapter implements a modified version of the TPIR protocol that was introduced in Section 6.4 of the book Malicious Cryptography [10], a protocol that is closely related to [1]. We apply TPIR to implement an experimental password-snatching cryptotrojan that does not reveal the unique login/password pair that it snatches. The TPIR algorithm that we present can be applied to numerous PIR problems.

  • Chp 8: Chapter8.pdf, Appendix:
  • Chapter 10: An Elliptic Curve Asymmetric Backdoor in OpenSSL RSA Key Generation
    Abstract. In this chapter we present an experimental implementation of an asymmetric backdoor in RSA key generation. The implementation is written in ANSI C. We codified what it means for an asymmetric backdoor to be secure (for the designer) in our definition of a secretly embedded trapdoor with universal protection (SETUP). The main properties of a SETUP are: (1) the complete code for the backdoor does not enable anyone except the designer to use the backdoor, and (2) the key pairs that are output by the backdoor RSA key generator appear to all probabilistic polynomial time algorithms like normal (no backdoor) RSA key pairs. We introduced the notion of a SETUP at Crypto '96 [15] and there has been significant advances in the area since then. This chapter and the corresponding appendix constitutes Fundamental Research in cryptovirology and expands on our elliptic curve backdoor in RSA key generation that we presented at the Selected Areas in Cryptography conference in 2005. In particular, the design employs several algorithmic improvements that enable the key generator to run faster. This chapter provides a walk-through of the experimental implementation. The backdoor is based on OpenSSL and the code for it appears in the appendix that is associated with this chapter. For over 10 years we have advocated that the industry change the way RSA keys are generated. We devised and presented heuristic methods that completely foil this entire class of backdoors in RSA key generation [15,12]. The approach in [12] is reminiscent of the NIST FIPS 186-2 DSA parameter generation method.

  • Chp 10: Chapter10.pdf, Appendix:
  • Chapter 12: YYGen: A Backdoor-Resistant RSA Key Generator
    Abstract. In this chapter we present an algorithm that generates RSA key pairs in such a way that the subliminal channel in the RSA modulus n is significantly reduced. We refer to this key generator as YYGen. YYGen takes as input an RSA public exponent e that we assume is fixed and shared among all users. The key generation and verification process is as follows. A user generates a key pair, sends the public key plus auxiliary information to a verifier, and the verifier is able to verify using algorithm YYVer that the subliminal channel is reduced in n. Our solution is reminiscent of the FIPS 186-2 parameter generation method that helps guard against backdoors in DSA parameters. A disadvantage of the solution is that it does not guarantee subliminal-freeness. However, an advantage is that the solution is extremely lightweight and can be easily deployed in hardware (smartcards) and software. Our solution heuristically foils all published asymmetric backdoors in RSA key generation that we have found that utilize fixed e. For this reason we believe that YYGen and YYVer form a desirable alternative to typical RSA key generators in sensitive infosec environments.

  • Chp 12: Chapter12.pdf, Appendix:
  • Chapter 14: YYPKS: A Simple Public Key Stegosystem
    Abstract. We present YYPKS, an experimental public key stegosystem (PKS) that we designed and implemented. YYPKS satisfies the basic properties of a public key cryptosystem. However, the ciphertexts that are output have the property of being uniformly pseudorandom bytes. We do not provide a formal proof of security for YYPKCS, although we apply sound paradigms such as the probabilistic bias removal method (PBRM) to achieve pseudorandomness. Our goal was to develop a simple and practical PKS with security that can be argued on heuristic grounds. The experimental implementation yypkcs.exe is a command-line program that uses standard X.509 digital certificates and PKCS #12 files for RSA encryption and decryption, respectively. We hope that this fundamental research in cryptology will encourage further research and experimentation in the area of public key steganography.

  • Chp 14: Chapter14.pdf, Appendix:
  • More to come...from theory to experiments...stay tuned...