Analysis of Public-Key Encryption Schemes in Extended Attack Models

Cryptographic models are intended to represent an adversary’s capabilities when attacking encryption schemes. Models often err on the side of caution by over-estimating the power of adversaries. However, several recent attacks reported in the literature demonstrate that measuring an adversary’s potential is a difficult task. This thesis will view the cryptographic landscape from the perspective of an adversary and the implementer. The first part of this thesis will consider the view of an adversary. We study how an adversary can obtain leaked information about a private key. The particular scenario we study is the cold boot attack whereby an adversary can procure a noisy version of the key (i.e. the noisy copy will contain errors). Such an attack is not traditionally modelled by the standard security games. We show how the adversary can recover the original secret key, and hence compromise security, in the RSA and discrete logarithm settings. In the discrete logarithm setting our approach is general, but we mount attacks against specific elliptic curve implementations of OpenSSL and PolarSSL. In the second part of this thesis we introduce a new type of attack, which we call the Related Randomness Attack. We define a security game to model these new attacks in a variety of scenarios, such as encryption schemes having access to non-uniform randomness sources, or perhaps the randomness source is under the control of an adversary. We introduce several variants of this model, and we provide generic transforms that convert traditional indistinguishabilitystyle secure schemes into schemes that are secure with respect to our new, extended definition.