Another Look at the Cost of Cryptographic Attacks

This paper makes the case for considering the cost of cryptographic attacks as the main measure of their efficiency, instead of their time complexity. This allows, in our opinion, a more realistic assessment of the "risk" these attacks represent. This is half-and-half a position and a technical paper. Cryptographic attacks described in the literature are rarely implemented. Most exist only "on paper", and their main characteristic is that their estimated time complexity is small enough to break a given security property. However, when a cryptanalyst actually considers implementing an attack, she soon realizes that there is more to the story than time complexity. For instance, Wiener has shown that breaking the double-DES costs 2 6n/5 , asymptotically more than exhaustive search on n bits. We put forward the asymptotic cost of cryptographic attacks as a measure of their practicality. We discuss the shortcomings of the usual computational model and propose a simple abstract cryptographic machine on which it is easy to estimate the cost. We then study the asymptotic cost of several relevant algorithm: collision search, the three-list birthday problem (3XOR) and solving multivariate quadratic polynomial equations. We find that some smart algorithms cost much more than what their time complexity suggest, while naive and simple algorithms may cost less. Some algorithms can be tuned to reduce their cost (this increases their time complexity). Foreword A celebrated High Performance Computing paper entitled "Hitting the Memory Wall: Implications of the Obvious" [47] opens with these words: This brief note points out something obvious-something the authors "knew" without really understanding. With apologies to those who did understand, we offer it to those others who, like us, missed the point. We would like to do the same-but this note is not so short