Cracking AES/3-DES

In 2002, a distributed network (desitributed.net) was successfully recovers a DES encryption key within 2.25 days. In order to estimate if 3-DES or AES keys can be recovered using a brute-force attack, this paper calculates the number of encryption operations and the (potentially) available processing power.

One of the largest distributed computing projects, folding@home estimates that with utilization of modern hardware such as Graphic Processing Unit (GPU), it is possible to achieve an acceleration of up to forty times (x40) over CPU due to its ability to perform “an enormous number of Floating Point OPerations (FLOPs) “ (Vijay Pande, 2010). Therefore, by using 200,000 actively processing computers, it is possible to surpass the 10 Petaflop level. As such, it is safe to assume that one average each participating machine contributes:

10×(10^15)÷200,000=50,000,000,000=50*(10^9)

or 50 billion calculations per second.

To amass the required computing power to brute force 3-DES or AES encryption, a bot network could be use to “harvest” idle CPU/GPU cycles. One of the most advance malware today, TDL-4, controls over 4.5 million infected computers in 2011 (Sergey Golovanov and Igor Soumenkov, 2011). Therefore, using previous assumption that zombie (infected computer) is capable of processing 50 billions calculations per seconds, the total computing power of a bot-net network such as TDL-4 is:

50*(10^9)*4.5*(10^6)=2.25×10^17=225×10^15

or 225 quadrillion (short scale) operations per second.

S. Kelly (2006) note that because in 3DES encryption scheme, the encryption keys relationship is C = E_k3(D_k2(E_k1(p))), in order to brute force a 3DES encryption a total of 2^168 cryptographic operation will be required. Assuming that a single 3DES decryption takes a microsecond (10^-6), it will take:

2^168÷225×10^15×10^6

1.66286409 × 10^27 second, or 5.26941088 × 10^19 years. This is far longer than the universe exist (4.339×10^17 seconds). The reader should note that the figure is by far smaller than what was estimated by S. Kelly (2006) and this is due to increased computing power of moder CPU and GPU devices. Regardless, it is safe to assume that 3DES can withstand a brute force attack.

Bibliography

• Kaur, G, & Kumar, D 2010, 'Performance and Analysis of AES, DES and Triple DES against Brute Force Attack to protect MPLS Network', International Journal Of Advanced Research In Computer Science, 1, 4, p. 420, EDS Foundation Index, EBSCOhost, viewed 17 March 2012.
• Ross J. Anderson 2008, “Security Engineering: A Guide to Building Dependable Distributed Systems”. 2nd Edition. Wiley.
• Sergey Golovanov, Igor Soumenkov 2011, “TDL4 – Top Bot” [online]. Kaspersky Lab ZAO. Available from: http://www.securelist.com/en/analysis/204792180/TDL4_Top_Bot?print_mode=1 (accessed: March 17, 2012).
• S. Kelly, 2006, “Security Implications of Using the Data Encryption Standard (DES)” [online]. Network Working Group. Available from: http://www.ietf.org/rfc/rfc4772.txt (accessed: March 17, 2012).
• Vijay Pande, 2010. “Folding@home high performance client FAQ” [online]. Available from: http://folding.stanford.edu/English/FAQ-highperformance (accessed: March 17, 2012).