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