Analyse et conception d'algorithmes de chiffrement à flot
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
The primary goal of cryptography is to protect the confidentiality of data and communications. Stream ciphers is one of the two most popular families of symmetric encryption algorithms that allow to guaranty confidentiality and to achieve high performances. In the first part of this thesis, we present different cryptanalysis techniques against stream ciphers: correlation attack against the stream cipher GRAIN, guess and determine attack against the BSG mechanism, algebraic attack against special kinds of non-linear feedback shift registers, and chosen IV attack against a reduced version of the stream cipher SALSA. In a second part, we focus on proofs of security for stream ciphers: we introduce the new algorithm QUAD and give some provable security arguments in order to link its security to the conjectured intractability of Multivariate Quadratic problem. We also try to extend the security requirements of stream ciphers to the case where initialisation values (IV) are used: we present a construction which allows us to build a secure IV dependent stream cipher from a number generator and apply it to QUAD, which becomes the first IV dependent stream cipher with provable security arguments. We also present the algorithms DECIM and SOSEMANUK, to which we made design contributions. Finally in a third part, we present efficient software and hardware implementations of the QUAD algorithm.
Abstract FR:
L'objectif premier de la cryptographie est la protection de la confidentialité des données. Les algorithmes de chiffrement à flot constituent une des familles d'algorithmes de chiffrement symétrique permettant de garantir cette confidentialité tout en satisfaisant un haut niveau de performances. Dans cette thèse, nous nous intéressons dans un premier temps à différents types d'attaques contre les algorithmes de chiffrement à flot que nous illustrons : attaque par corrélation contre l'algorithme GRAIN, attaque par reconstruction contre le mécanisme BSG, attaque algébrique contre certains types de registres à décalage à rétroaction non linéaire et attaque par resynchronisation contre une version réduite de l'algorithme SALSA. La seconde partie de cette thèse décrit nos travaux en matière de sécurité prouvée pour les algorithmes de chiffrement à flot. Nous présentons l'algorithme QUAD et donnons un certain nombre d'arguments de sécurité prouvée reliant la sécurité de l'algorithme à la difficulté conjecturée du problème Multivariate Quadratic. Nous nous intéressons au modèle de sécurité des algorithmes de chiffrement à flot utilisant des valeurs d'initialisation (IV) et nous présentons une construction qui permet de construire de manière standard un algorithme de chiffrement à flot utilisant des IV à partir d'un générateur de nombres. Nous appliquons cette construction à l'algorithme QUAD, ce qui en fait le premier algorithme de chiffrement à flot utilisant des IV et doté d'arguments de sécurité prouvée. Nous présentons également les algorithmes DECIM et SOSEMANUK, à la conception desquels nous avons participé. Finalement, nous présentons des implantations logicielles et matérielles efficaces de l'algorithme QUAD.