PICSI

Attaque par distingueur

Un peu de théorie...

Le principe général de la cryptanalyse repose sur la notion d'attaques par distingueur. Un distingueur A est en fait une machine de Turing probabiliste qui cherche par un jeu de questions/réponses à distinguer un système de chiffrement C d'un autre système de chiffrement souvent idéal noté C^*. On note p la probabilité que le distingueur, après qu'on lui ait fourni un certain nombre d'informations, renvoie la réponse "1" (c'est à dire que la suite de réponses fournies aux différentes requêtes permettent de dire que le chiffrement étudié est bien l'algorithme C). On note p^* la probabilité correspondante pour C^*. Il s'agit alors d'étudier le biais probabiliste qui existe éventuellement entre ces deux chiffrements, c'est ce qu'on nomme l'avantage du distingueur et qui correspond à la quantité Adv_A(C, C^*)=|p−p^*|. Lors d'une attaque, on cherche donc un distingueur particulier souvent donné par des relations particulières liant les clairs et/ou les chiffrés de l'algorithme C qui fournit un avantage le plus grand possible, c'est à dire que l'on cherche des relations fournies par le chiffrement C qui ont une probabilité de se produire la plus éloignée possible de la probabilité uniforme. Ces relations peuvent être de tout type (dans le cas de la cryptanalyse différentielle, il s'agit d'un x-or entre deux blocs d'entrée dont on étudie les probabilités de transition pour un certain nombre de tours,...). Plus le nombre d'étage impliqué dans la relation est grand et plus le biais est important, plus on pourra efficacement obtenir de l'information sur les sous-clés et la clé maître. Pour tester une clé (ou une partie seulement de cette clé selon le type de relation utilisé dans le distingueur), il suffit de regarder, sur un nombre suffisant de messages, si le biais obtenu réellement pour cette clé particulière après passage dans le distingueur est très proche du biais théorique. C'est ce qu'on appelle un test d'hypothèse. Celui-ci fait donc essentiellement appel à des tests statistiques où la probabilité de réussite, liée au biais impliqué par la relation dans le distingueur, permet de calculer la complexité et le nombre de textes nécessaires au succès d'une telle attaque. Le principal but des attaques est de construire un distingueur à partir d'une relation portant sur les (r−2) étages du milieu ou sur les (r−1) premiers étages, puis, à partir de ce distingueur, de faire des tests d'hypothèse sur tout ou partie des première et/ou dernière clés.