An introduction to Tagada: a Tool for Automatic Generation of Abstraction-based Differential Attacks

Venerdì 05 Maggio alle ore 14.00, presso il Dipartimento di Matematica e Fisica (Edificio C - Aula 311), si terrà nell'ambito dei seminari di Crittografia il seminario del dott. Loïc Rouquette (Équipe CARAMBA, Loria, Université de Lorraine and Équipe CHROMA, CITI, INSA Lyon) dal titolo: "An introduction to Tagada: a Tool for Automatic Generation of Abstraction-based Differential Attacks".

L'evento sarà in diertta anche sulla piattaforma Teams al seguente Link identifier #identifier__37562-1Link

Abstract: Data confidentiality is one of the main goals of cryptography. It can be achieved by using symmetric ciphers. Symmetric ciphers are so-called because they use the same, secret, key to cipher and decipher messages. To find witnesses in ciphers, cryptanalysts look for specific properties that allow the ciphers to be distinguished from random streams. In the case of differential cryptanalysis, the distinguisher is built by finding an input difference $\delta_{in}$ that is injected into the plaintext, and optionally into the key, and that maximises the probability of observing an output difference $\delta_{out}$. More formally, we try to maximise $\mathbb{P}( E_K(P) \oplus E_K(P \oplus \delta_{in}) = \delta_{out})$. This problem is hard to compute as is and we generally use approximations called differential characteristic probabilities. In the case of differential characteristic probabilities, we fix all the internal differences of the cipher, not just the differences between the inputs and the outputs. This representation allows us to compute an approximation of the distinguisher probability by assuming that each round of the cipher is independent and that the probability of the best differential characteristic is close to the differential probability.

After all these approximations, the problem is still too hard to solve. In 1994, Knudsen introduced truncated differential characteristics. The idea is to abstract the cipher word differences into Boolean variables that indicate whether there is a difference in the word or not. Since then, several algorithms have been developed to find such truncated differential characteristics and they are included in many differential characteristic search algorithms. One of the main drawbacks of such algorithms is that they are highly adapted to a target cipher. This can be error-prone as ciphers become more and more complex and this can lead to a lack of portability as the algorithms need to be reimplemented for each cipher target.

To improve the portability of differential attack models we propose a new tool called Tagada, which allows to automatically generate differential attack models from cipher specifications. To do this, we use a graph representation of ciphers. This representation can be manipulated in order to extract mathematical properties, to adapt it to the attack model, and to generate high-order (truncated) representations.