Paper: Using the Cloud to Determine Key Strenghts09/10/2012
Using the Cloud to Determine Key Strenghts
We develop a new methodology to assess cryptographic key strength using cloud computing, by calculating the true economic cost of (symmetric- or private-) key retrieval for the most common cryptographic primitives. Although the present paper gives both the current (2012) and last years (2011) costs, more importantly it provides the tools and infrastructure to derive new data points at any time in the future, while allowing for improvements such as of new algorithmic approaches. Over time the resulting data points will provide valuable insight in the selection of cryptographic key sizes.
Paper by T. Kleinjung, A.K. Lenstra, D. Page, N.P. Smart - PDF Download
Recently on the airplane I read this paper and totally enjoyed it. It’s not a real “cloud” paper but more focusing on cryptographic key strengths and the potential power of high scalable environments such as clouds. So basically, two main approaches dominate in order to assess cryptographic primitives: software-oriented computations and special purpose hardware coming along with substantial upfront costs. I should also mention that this is ongoing research – so check out this webpage where annually updates can be found: http://www.cs.bris.ac.uk/~nigel/Cloud-Keys/
Within the paper, the following algorithms are assessed: DES, AES, SHA-2 family, RSA and ECC. The cloud platform that is used is AWS EC2. The following techniques are used to attack the algorithms:
DES: bit-sliced implementation method of Biham
AES: traditional AES implementation due to keeping the general approach (it’s also interesting to mention that according to the authors, there is only little research in terms of AES specific hardware attacks due to the key space of 2^128)
SHA-2: parallel “distinguished points” method of van Oorschot and Wiener
RSA: Coppersmith’s variant of the Number Field Sieve (NFS) method
ECC: Pollard’s rho method
Finally, the results are interesting and can, due to the general approach, be repeated frequently. Interesting stuff – so keep in mind that even the cloud cannot solve all issues, fortunately.