Advisor: Prof. Adi Shamir

The theoretical view of cryptography usually models all parties, legitimate ones as well as attackers, as idealized computational devices with designated interfaces, and their security and computational complexity are evaluated in some convenient computational model -- usually PC-like RAM machines. This dissertation investigates several cases where reality significantly deviates from this model, leading to previously unforeseen cryptanalytic attacks.

The first part of the dissertation investigates the concrete cost of factoring integers, and in particular RSA keys of commonly used sizes such as 1024 bits. Until recently, this task was considered infeasible (i.e., its cost was estimated as trillions of dollars), based on extrapolations that assumed implementation of factoring algorithms on sequential PC-like computers. We have shown that the situation changes significantly when one introduces custom-built hardware architectures, with algorithms and parametrization that are optimized for concrete technological tradeoffs and do not fit the RAM machine model. Focusing on the Number Field Sieve (NFS) factoring algorithm, we propose hardware architectures for both of its computational steps: the sieving step and the linear algebra step. Detailed analysis and a careful choice of the NFS parameters show that for breaking 1024-bit RSA keys, NFS can be be implemented at a fairly practical cost of a few million US dollars for a throughput of one factorization per year. This casts grave doubt on the security of such cryptographic keys, which are widely deployed in accordance with existing standards and recommendations.

The second part of the dissertation investigates another abstraction violation: side-channel information leakage from cryptographic systems. We demonstrate two such channels. First, cache contention in modern CPUs leads to leakage of information about memory access patterns, and we devise novel ways to exploit this leakage. The new attacks work in pure software, and are applicable even in scenarios where the attacker has no nominal communication channel with the attacked code. They are also extremely efficient; for example, we have demonstrated full recovery of an AES secret key from a Linux encrypted filesystem using just 800 analyzed encryptions, gathered within 65 milliseconds. A second side channel we observe is acoustic emanations: modern PCs produce unintentional acoustic signals that are highly correlated with processor activity, and reveal information about the calculation being performed (e.g., the secret moduli used during RSA decryption). Due to their efficiency and ubiquity, these newly recognized side-channel attacks form a threat in widespread practical circumstances, and thwart many traditional software security measures such as process separation, sandboxes and virtual machines.

Full text:
[pdf]

-- Eran Tromer