Projets étudiants cryptographie et sécurité/Caillet DiLisio IDEA

International Data Encryption Algorithm: IDEA

IDEA est l'acronyme de International Data Encryption Algorithm, décrit pour la première fois en 1991. Cet algorithme fut développé par une équipe de mathématiciens, cyptologues et informaticiens, de différentes nationalités. James Massey et Xuejia Lai ont conçu cet algorithme pour remplacer Data Encryption Standard d’IBM, pour cela ils réalisent des révisions mineures sur un chiffrement postérieur, PES (Proposed Encryption Standard), d’où le nom original d’IDEA : IPES (‘I’ pour « Improved », « Amélioré »).

Panorama

IDEA est un algorithme de chiffrement symétrique dit à clé secrète, celle-ci est choisie aléatoirement et atteint une longueur de 128 bits, elle sert à chiffrer et déchiffrer. IDEA utilise à la fois les propriétés de confusion et diffusion :

• La relation entre la clé et le texte chiffré est la plus complexe possible.
• si le changement d’un seul bit dans le texte claire est opéré, alors, statistiquement, un bit sur deux du cryptogramme devrait changer. De même, si nous changeons un bit du cryptogramme, environ la moitié des bits en clair devrait changer.

IDEA est composé d’une série de huit transformations identiques, et les procédés de cryptage et décryptage sont équivalents. Sa sécurité dépend en grande partie à l’entrelacement d’opérations provenant de groupe différent :

• OU exclusif (bit par bit)
• Addition modulo $2^{16}$
• Multiplication modulo $2^{16}+1$

qui sont algébriquement « incompatibles » dans un certain sens. Enfin, après huit rondes vient une « demi-ronde » finale.

IDEA a été utilisé dans Pretty Good Privacy (PGP) v2.0, de plus il est un algorithme optionnel dans la norme OpenPGP.

Description de IDEA

Prenons un texte clair divisé en quatre quarts: A, B, C, D et où les 52 sous-clefs sont nommées $K_{1}$ à $K_{52}$.

• Avant le Tour 1:
  

  Avant le Tour 1
  • $A*K_{1}[2^{16}+1]$
  • $(B+K_{2})[2^{16}]$
  • $(C+K_{3})[2^{16}]$
  • $D*K_{4}[2^{16}+1]$

• Tour 1 composé des éléments:
  

  Tour 1
  • A ⊻ C (appeler E)
  • B ⊻ D (appeler F)
  • $E*K_{5}[2^{16}+1]$
  • $F=(E+F)[2^{16}]$
  • $F*K_{6}[2^{16}+1]$
  • $E=(F+E)[2^{16}]$
  • A = A ⊻ F , C = C ⊻ F
  • B = B ⊻ E , D = D ⊻ E
  • Échanger B et C

Répétez la ronde huit fois, en utilisant $K_{7}$ par $K_{12}$ la deuxième fois, puis $K_{43}$ par $K_{48}$ la huitième fois. Notez que le échange de B et C n'est pas effectué après tour 8.

• Demi-Ronde
  

  Demi-Tour
  • $A*K_{49}[2^{16}+1]$
  • $(B+K_{50})[2^{16}]$
  • $(C+K_{51})[2^{16}]$
  • $D*K_{52}[2^{16}+1]$

Vue d'ensemble:

Sécurité

• Début: Les analyses d'IDEA contre de la cryptanalyse différentielle ont conclu qu'il était à l'abri des menace sous certaines hypothèses. Aucune faiblesse linéaires ou algébriques ont été rapportés.
• 1996: In my opinion, it is the best and most secure block algorithm available to the public at this time. –Bruce Schneider (Informaticien)
• 1999: des algorithme plus rapide se développe, IDEA n'est plus recommandé
• 2007: la meilleure attaque appliquée sur toute les clefs, pourrait briser IDEA réduit à 6 tours (contre 8,5 tours dans la version complète); l'attaque à 6 rondes nécessite 264 texte claire connu et 2126.8 opérations.
• 2011: IDEA complet a été "cracké", en utilisant la méthode de 1999 ( meet-in-the-middle (MITM))
• 2012: IDEA complet a été "cracké", en utilisant la méthode Biclique attack étoilé (une variante de MITM), semblable à l'attaque sur AES

Clé faible

Dans le cadre de IDEA, on dénombre plusieurs « clés faibles ». Certaines clefs contenant un grand nombre de bits à 0 produisent un chiffrement dit "faible". En pratique, cela n'a que peu d'intérêt, étant donné sa rareté d'apparition, par conséquent il n'est pas nécessaire, lors de la génération des clefs de couvrir explicitement ce cas. Toute fois il est possible d'ajouter une correction simple à l'algorithme en réalisant un OU-EXCLUSIF sur chaque sous clés avec une constante de 16 bits, tels que 0x0DAE.

Comparatif de performances

Afin de savoir où se situe IDEA par rapport aux autres algorithmes de cryptographie symétrique, voici un tableau comparatif de performance entre IDEA et ceux-ci :

Tabeau comparatif des algorithmes de cryptographie symétrique les plus connus

Algorithme	MiB/Seconde	Cycles Par Octet	Microsecondes pour préparer la Clé et le Vecteur d'Initialisation	Cycles pour préparer la Clé et le Vecteur d'Initialisation
MD5	255	6,8	/	/
SHA-1	153	11,4	/	/
AES/CBC (128-bit key)	109	16,0	0,569	1041
DES/CTR	32	54,7	8,372	15320
IDEA	35	49,9	0.698	1277

En général, l’algorithme IDEA est considéré comme étant assez nettement supérieur au DES en terme de sécurité. Sa vitesse d’exécution reste comparable avec le DES. Ses implémentations hardware sont simplement légèrement plus rapides.