Stagiaire F/H : Estimation de la Probabilité d’un Distingueur Boomerang

Contexte : Ce stage s'inscrit dans le cadre du projet Cryptanalyse du PEPR Cybersécurité et a pour objectif d'étudier les différentes techniques d'estimation de la probabilité d’un distingueur boomerang.

Atout : Des déplacements en conférence ou en séminaire, en France comme à l'étranger, seront à envisager pour diffuser les travaux réalisés. Les frais de déplacement et d'hébergement seront pris en charge dans la limite du barème en vigueur.

Contexte

L’attaque boomerang est une technique de cryptanalyse de chiffrements par blocs introduite en 1999 par Wagner [Wag99]. Cette technique s’inspire de la cryptanalyse différentielle mais en diffère par l’utilisation de 4 messages au lieu de 2 pour former une propriété qui distinguera le chiffrement E d’une permutation aléatoire, pour ensuite en déduire une attaque.

Plus en détail, l’attaquant cherche deux différences alpha et delta telles que la relation suivante soit vérifiée avec forte probabilité :
     E^{-1}(E(M) + delta) + E^{-1}(E(M + alpha) + delta) = alpha. (1)
 
La première construction proposée pour ce type de distingueurs (et largement utilisée par la suite) repose sur deux différentielles portant chacune sur une moitié du chiffrement : si la différence alpha mène à la différence beta avec probabilité p sur E0 et que la différence gamma mène à la différence delta avec probabilité q sur E1, la probabilité de (1) sur E = E1 \circ E0 était approximée par p^2q^2.


Objectifs

Cette estimation a cependant été prouvée incorrecte dans de nombreux articles dont les plus connus sont celui de Murphy [Mur11] qui pointe des impossibilités et celui de Biryukov et Khovratovich [BK09] qui exhibe des cas où la probabilité est plus élevée que ce qui est attendu.
Face à ces problèmes, l’idée de découper le distingueur en trois parties a rapidement été proposée, sous le nom de framework sandwich [DKS10]. La partie du milieu Em sert alors à contenir l’ensemble des tours où une interdépendance existe et donne l’estimation en p^2q^2r où r correspond à la probabilité du boomerang sur Em. Une première idée de systématisation du calcul de r a été proposée par Cid et co-auteurs en 2018 [Cid+18] avec l’introduction de la BCT (Boomerang Connectivity Table) qui réduit le problème du calcul de la probabilité d’un Em d’un tour à celui de la probabilité de chacune des Sboxes de ce tour.
Une multitude de tables ont par la suite été introduites, comme la FBCT [Bou+20], la UBCT et la LBCT [DDV20] et la DBCT [HBS21; Yan+22].

Objectif : Proposer une analyse critique des techniques existantes d’estimation de la probabilité des distingueurs boomerang et de leur utilisation dans les outils automatiques.

Le premier objectif sera de comprendre les liens existant entre l’ensemble des tables précédemment introduites pour ensuite proposer une théorie unificatrice de celles-ci. Plusieurs travaux récents traduisent en effet une réelle confusion sur l’usage de ces tables, menant dans certains cas à des utilisations incorrectes, comme montré par exemple dans [BL24].
Une partie du stage sera ensuite consacrée à la comparaison des modèles utilisés lors de la recherche automatique de distingueurs boomerangs [DDV20; HBS21; BL23] (basés sur des techniques comme le MILP ou le SAT par exemple). L’ambition sera de mettre en lumière les différentes hypothèses faites lors de ces modélisations, leur validité et les erreurs possibles qu’elles peuvent introduire, des éléments qui jusque là sont peu discutés lors de la proposition de nouveaux modèles.

Équipe

La personne recrutée sera en lien avec Virginie Lallemand (Chargée de recherche, CNRS) et Xavier Bonnetain (Chargé de recherche, INRIA). Elle sera pleinement intégrée à CARAMBA, une équipe de recherche dont les membres s'intéressent à des questions d'algorithmiques liées à la cryptographie. Plus d'informations ici : https://www.inria.fr/equipes/caramba

Références

[BK09] Alex Biryukov and Dmitry Khovratovich. “Related-Key Cryptanalysis of the Full AES-192 and AES-256”. In: ASIACRYPT 2009. Ed. by Mitsuru Matsui. Vol. 5912. LNCS. Springer, Berlin, Heidelberg, Dec. 2009, pp. 1–18. doi: 10.1007/978-3-642-10366-7_1.

[BL23] Xavier Bonnetain and Virginie Lallemand. “On Boomerang Attacks on Quadratic Feistel Ciphers New results on KATAN and Simon”. In: IACR Trans. Symm. Cryptol. 2023.3 (2023), pp. 101–145. doi: 10.46586/tosc.v2023.i3.101-145.

[BL24] Xavier Bonnetain and Virginie Lallemand. A Note on the use of the Double Boomerang Connectivity Table (DBCT) for Spotting Impossibilities. Cryptology ePrint Archive, Paper 2024/1218. 2024. url: https://eprint.iacr.org/2024/1218.

[Bou+20] Hamid Boukerrou, Paul Huynh, Virginie Lallemand, Bimal Mandal, and Marine Minier. “On the Feistel Counterpart of the Boomerang Connectivity Table (Long Paper)”. In: IACR Trans. Symm. Cryptol. 2020.1 (2020), pp. 331–362. issn: 2519-173X. doi: 10.13154/tosc.v2020.i1.331-362.

[Cid+18] Carlos Cid, Tao Huang, Thomas Peyrin, Yu Sasaki, and Ling Song. “Boomerang Connectivity Table: A New Cryptanalysis Tool”. In: EUROCRYPT 2018, Part II. Ed. by Jesper Buus Nielsen and Vincent Rijmen. Vol. 10821. LNCS. Springer, Cham, 2018, pp. 683–714. doi: 10.1007/978-3-319-78375-8_22.

[DDV20] Stéphanie Delaune, Patrick Derbez, and Mathieu Vavrille. “Catching the Fastest Boomerangs Application to SKINNY”. In: IACR Trans. Symm. Cryptol. 2020.4 (2020), pp. 104–129. issn: 2519-173X. doi: 10.46586/tosc.v2020.i4.104-129.

[DKS10] Orr Dunkelman, Nathan Keller, and Adi Shamir. “A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony”. In: CRYPTO 2010. Ed. by Tal Rabin. Vol. 6223. LNCS. Springer, Berlin, Heidelberg, Aug. 2010, pp. 393–410. doi: 10.1007/978-3-642-14623-7_21.

[HBS21] Hosein Hadipour, Nasour Bagheri, and Ling Song. “Improved Rectangle Attacks on SKINNY and CRAFT”. In: IACR Trans. Symm. Cryptol. 2021.2 (2021), pp. 140–198. issn: 2519-173X. doi: 10.46586/tosc.v2021.i2.140-198.

[Mur11] Sean Murphy. “The Return of the Cryptographic Boomerang”. In: IEEE Trans. Inf. Theory 57.4 (2011), pp. 2517–2521. doi: 10.1109/TIT.2011.2111091. url: https://doi.org/10.1109/TIT.2011.2111091.

[Wag99] David Wagner. “The Boomerang Attack”. In: FSE’99. Ed. by Lars R. Knudsen. Vol. 1636. LNCS. Springer, Berlin, Heidelberg, Mar. 1999, pp. 156–170. doi: 10.1007/3-540-48519-8_12.

[Yan+22] Qianqian Yang, Ling Song, Siwei Sun, Danping Shi, and Lei Hu. “New Properties of the Double Boomerang Connectivity Table”. In: IACR Trans. Symm. Cryptol. 2022.4 (2022), pp. 208–242. doi: 10.46586/tosc.v2022.i4.208-242.

Principales activités :

• S'approprier l'état de l'art de la recherche de distingueurs boomerangs,
• Comprendre le lien entre les différentes tables utilisées dans ce contexte,
• Déterminer les limitations des différents modèles automatiques existants.

Langues : bonne maîtrise de l'anglais.

Compétences relationnelles : La personne recrutée sera amenée à communiquer régulièrement avec ses encadrants. Il est attendu qu'elle s'intègre et participe activement à la vie de l'équipe.

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement)
• Possibilité de télétravail (après 6 mois d'ancienneté) et aménagement du temps de travail
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
• Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d'Inria)
• Accès à la formation professionnelle
• Sécurité sociale

4.35 €/heure