Histoire des codes secrets

Histoire des codes secrets est un livre écrit par Simon Singh (titre original en anglais : The Code Book) publié pour la première fois en 1999. Le livre se décompose en chacune passant en revue l'évolution de la cryptographie des pharaons, passant par Marie Stuart, reine d'Écosse et la machine Enigma, jusqu'à l'ordinateur quantique. Exercices Le livre permet grâce à 10 exercices de mettre en application les techniques vues dans le livre. D'une difficulté croissante, les premiers se résolvent en quelques heures alors que les derniers sont d'un niveau quasi-professionnel. Le concours mis en place à la première édition du livre sorti en 1999 avait pour récompense . Le , les solutions furent trouvées après plus d'un an de recherche. Critiques D'après Sciences et Avenir, le livre . D'après France Culture, le livre a le mérite d'attirer l'attention sur l'enjeu actuel de respect de la vie privée. Chapitres *Chapitre 1: Le chiffre de Marie, reine d'Écosse

Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT

Jorge Nakahara, Pouyan Sepehrdad

The contributions of this paper include the first linear hull and a revisit of the algebraic cryptanalysis of reduced-round variants of the block cipher PRESENT, under known-plaintext and ciphertext- only settings. We introduce a pure algebraic cryptanalysis of 5-round PRESENT and in one of our attacks we recover half of the bits of the key in less than three minutes using an ordinary desktop PC. The PRESENT block cipher is a design by Bogdanov et al., announced in CHES 2007 and aimed at RFID tags and sensor networks. For our linear attacks, we can attack 25-round PRESENT with the whole code book, 296.68 25- round PRESENT encryptions, 240 blocks of memory and 0.61 success rate. Further we can extend the linear attack to 26-round with small success rate. As a further contribution of this paper we computed linear hulls in practice for the original PRESENT cipher, which corroborated and even improved on the predicted bias (and the corresponding attack complexities) of conventional linear relations based on a single linear trail.

Springer Berlin / Heidelberg2009

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Fatma Betül Durak, Serge Vaudenay

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS~2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity

O(N^5\log(N))

, which is much larger than the code book (but using many tweaks), where

N^2

is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

O(N^{5})

. Our attack was successfully tested with

N\leq2^9

. It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4-round Feistel network. Biryukov et. al. already gave a 4-round Feistel structure attack in SAC~2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

O(N^{3})

. Our 4-round attack is simple to extend to five and more rounds with complexity

N^{(r-5)N+o(N)}

. It shows that FF1 with

N=7

and FF3 with

7\leq N\leq10

do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our

O(N^{5})

attack.

2017

Serge Vaudenay

Triple encryption was proposed to increase the security of single encryption when the key is too short. In the past, there have been several attacks in this encryption mode. When triple encryption is based on two keys, Merkle and Hellman proposed a subtle meet-in-the-middle attack which can break it at a price similar to breaking single encryption (but with nearly all the code book). When triple encryption is based on three keys, Kelsey, Schneier, and Wagner proposed a related-key attack which can break it at a price similar to breaking single encryption. In this paper, we propose a new related-key attack against triple encryption which compares to breaking single encryption in the two cases. Our attack against two-key triple-encryption has exactly the same performances as a meet-in-the-middle on double-encryption. It is based on the discovery of fixed points in a decrypt-encrypt sequence using related keys. In the two-key case, it is comparable to the Merkle-Hellman attack (except that is uses related keys). In the three-key case, it has a higher complexity than the Kelsey-Schneier-Wagner attack but can live with known plaintexts.

SciTePress2011

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Fatma Betül Durak, Serge Vaudenay

O(N^5\log(N))

, which is much larger than the code book (but using many tweaks), where

N^2

is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

O(N^{5})

. Our attack was successfully tested with

N\leq2^9

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

O(N^{3})

. Our 4-round attack is simple to extend to five and more rounds with complexity

N^{(r-5)N+o(N)}

. It shows that FF1 with

N=7

and FF3 with

7\leq N\leq10

do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our

O(N^{5})

attack.

2017

Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Related-Key Attack against Triple Encryption based on Fixed Points

Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Related-Key Attack against Triple Encryption based on Fixed Points