Kite attack: boosting the search of maxterms using GPUs

We leverage the horse computational power offered by Graphics Processing Units (GPUs), combined with fine grained code optimizations, to develop the first Multi-GPU tailored framework for Cube Attack. The framework is cipher independent and it can exploit newest GPU devices.

Check out our repository : KITE-ATTACK and give our framework a try!

A Novel GPU-Based Implementation of the Cube Attack Preliminary Results Against Trivium

With black-box access to the cipher being its unique requirement, Dinur and Shamir’s cube attack is a flexible cryptanalysis technique which can be applied to virtually any cipher. However, gaining a precise understanding of the characteristics that make a cipher vulnerable to the attack is still an open problem, and no implementation of the cube attack so far succeeded in breaking a real-world strong cipher. In this paper, we present a complete implementation of the cube attack on a GPU/CPU cluster able to improve state-of-the-art results against the Trivium cipher. In particular, our attack allows full key recovery up to 781 initialization rounds without brute-force, and yields the first ever maxterm after 800 initialization rounds. The proposed attack leverages a careful tuning of the available resources, based on an accurate analysis of the offline phase, that has been tailored to the characteristics of GPU computing. We discuss all design choices, detailing their respective advantages and drawbacks. Other than providing remarkable results, this paper shows how the cube attack can significantly benefit from accelerators like GPUs, paving the way for future work in the area.(Paper, pdf)

Cryptanalysis on GPUs with the Cube Attack: Design, Optimization and Performances Gains

The cube attack is a flexible cryptanalysis technique, with a simple and fascinating theoretical implant. It combines offline exhaustive searches over selected tweakable public/IV bits (the sides of the “cube”), with an online key-recovery phase. Although virtually applicable to any cipher, and generally praised by the research community, the real potential of the attack is still in question, and no implementation so far succeeded in breaking a real-world strong cipher. In this paper, we present, validate and analyze the first thorough implementation of the cube attack on a GPU cluster. The framework is conceived so as to be usable out-of-the-box for any cipher featuring up to 128- bit key and IV, and easily adaptable to larger key/IV, at just the cost of some fine (performance) tuning, mostly related to memory allocation. As a test case, we consider previous state-of-the-art results against a reduced-round version of a well-known cipher (Trivium). We evaluate the computational speedup with respect to a CPU-parallel benchmark, the performance dependence on system parameters and GPU architectures (Nvidia Kepler vs Nvidia Pascal), and the scalability of our solution on multi-GPU systems. All design choices are carefully described, and their respective advantages and drawbacks are discussed. By exhibiting the benefits of a complete GPU-tailored implementation of the cube attack, we provide novel and strong elements in support of the general feasibility of the attack, thus paving the way for future work in the area. (Paper, pdf)

Appendix to Kite attack: reshaping the cube attack for a flexible GPU-based maxterm search

It contains the cryptanalytic results obtained against Trivium and Grain-128 using the Kite attack. Moreover, the ciphers specifications are also available.(pdf)