Conception et cryptanalyse de primitives symétriques
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
Most hash functions iterate one function compression, that process one block at each round with the result of the previous iteration. The mode of operation of a hash function defines the number and the parameters of the iterations. Merkle-Damgård was the first classical mode, built with a proof of collision resistance transmitted from the compression function to the hash function. First we give a generic security reduction in the standard model for narrow-pipe modes of operation. Then we prove that for any such reduction a security loss is unavoidable, which is closely related to the message length which is considered by the reduction. Block cipher often iterate a round function several times with different parameters which are derived from the master key by a key scheduling algorithm. We analyse a set of key schedules based on xor, rotation and bit permutation, in order to derive a criterion of resistance against known cryptanalysis with a kind of genericity with respect to the round function : slide attacks and relatedkey slide attacks. Meet-in-the-Middle attack exploit the ability for the attacker to divide the key bits in three parts without intersection, where two of them permit to computed a part of a same intermediate state with the help of the third part of the key bits. We extend this cryptanalysis with the use of a probabilistic sieve in the middle, such that the attacker does not search anymore for a match at a same intermediate state but for the existence of a transition through the non-linear layer of an intermediate round. It permits to extend of one round various cryptanalysis of block ciphers. Examples are given for reduced versions of DES and PRESENT.
Abstract FR:
La plupart des fonctions de hachage sont construites comme l'itération d'une fonction de compression, absorbant à chaque tour un bloc issu du message et le résultat de l'itération précédente. Le mode d'opération définit le nombre d'itérations et les paramètres en entrée de la fonction de compression pour chacune d'entre elles. Merkle-Damgård est un mode d'opération simple et répandu qui ne garantit cependant pas la sécurité en seconde préimage, même pour une fonction de compression idéale. D'une part nous fournissons une réduction générique de sécurité en seconde préimage dans le modèle standard, d'autre part nous prouvons que la perte de sécurité des réductions des modes étudiés est inévitable pour une réduction de sécurité en seconde préimage de modes narrow-pipe. A partir des attaques qui se basent essentiellement sur des propriétés du cadencement de clé, nous analysons la sécurité d'une famille de cadencements de clé affines à base de rotations, de xor, et de choix permutés de bits. Nous obtenons ainsi des critères de conception indiquant un niveau de sécurité relativement à une classe d'attaques en fonction des coefficients d'un cadencement de clé appartenant à cette famille. Les attaques par le milieu exploitent la possibilité de séparer une partie des bits de clé en trois parties, dont deux d'entre elles interviennent exclusivement dans la première ou la seconde moitié des itérations de chiffrement. L'équilibrage entre les nombres de tours dans les moitiés de chiffrement, et entre les nombres de bits de chacune des deux portions de clé indépendantes, permettent de minimiser la complexité de l'attaque. Nous montrons comment utiliser des propriétés statistiques des boîtes S au milieu pour étendre le nombre de tours pour lequel cette complexité reste en dessous de celle d'une recherche exhaustive de clé. Nous appliquons cette technique à des versions réduites de deux chiffrements par blocs : DES et PRESENT.