04 Cryptanalysis PDF

04 Cryptanalysis Types of Attacks in Practice Exhaustive search Exhaustive search in restricted keyspace, e.g. due to poor practice Exploit malpractice, e.g. key management or storage Steal keys Spoofing Weakn...

04 Cryptanalysis Types of Attacks in Practice Exhaustive search Exhaustive search in restricted keyspace, e.g. due to poor practice Exploit malpractice, e.g. key management or storage Steal keys Spoofing Weaknesses of ciphers DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 2 Types of Attacks in Theory Ciphertext only Known plaintext Chosen plaintext Chosen ciphertext DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 3 Ciphertext Only Attack The attacker has access to one or more ciphertexts This is the hardest attack to carry out The most common case, since it is rather easy to retrieve a ciphertext by simply eavesdropping an insecure connection DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 4 Known Plaintext Attack The attacker has access to one or more ciphertexts and the corresponding plaintexts This case provides more information to the attacker than a ciphertext only attack Not as common as a ciphertext only attack DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 5 Chosen Plaintext Attack Similar to a know plaintext attack The attacker has the possibility to generate the ciphertext to an arbitrarily chosen plaintext DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 6 Chosen Ciphertext Attack Similar to a chosen plaintext attack The attacker has the possibility to generate the plaintext to an arbitrarily chosen ciphertext DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 7 Recap Classical Ciphers Transposition Ciphers Substitution Ciphers Modern Ciphers Symmetric Ciphers Asymmetric Ciphers DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 8 Attack on a Transposition Cipher That's actually pretty hard by hand, so we'll skip that! DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 9 Attack on a Monoalphabetic Substitution Cipher - Letter Frequencies German English E 17.40 % E 12.70% N 9.78 % T 9.06% I 7.55 % A 8.17% S 7.27 % O 7.51% R 7.00 % I 6.97% A 6.51 % N 6.75% T 6.15 % S 6.33% … … … … DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 10 Attack on a Monoalphabetic Substitution Cipher - Letter Frequencies II Letter Frequencies DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 11 Attack on a Monoalphabetic Substitution Cipher - Other Properties of natural Language Not only the letters itself have interesting properties, there are some more interesting things to look at: Frequency of certain letters at the beginning of a word Frequency of certain letters at the end of a word Bi- and Trigrams DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 12 Attack on a Monoalphabetic Substitution Cipher - Beginning and Ending of Words Begin Frequency End Frequency t 0.1594 e 0.1917 a 0.155 s 0.1435 i 0.0823 d 0.0923 s 0.0775 t 0.0864 o 0.0712 n 0.0786 c 0.0597 y 0.0730 m 0.0426 r 0.0693 f 0.0408 o 0.0467 … … … … DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 13 Attack on a Monoalphabetic Substitution Cipher - Bi- and Trigrams Bigram Frequency Trigram Frequency th 0.03882 the 0.0351 he 0.03681 and 0.0159 in 0.02283 ing 0.0115 er 0.02178 her 0.0082 an 0.02140 hat 0.0065 re 0.01749 his 0.0060 nd 0.01571 tha 0.0059 on 0.01418 ere 0.0056 … … … … DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 14 Attack on a Polyalphabetic Substitution Cipher - Prerequisites Statistical properties of the natural language are destroyed, BUT... As a keyword of finitely many characters is used, there is a distance n in which characters of the plaintext are encrypted using the same letter of the keyword This gives us in fact multiple puzzles to solve But how to find n? DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 15 Attack on a Polyalphabetic Substitution Cipher - The Kasiski Test The ciphertext is searched for repetitions of fragments with at least three characters It is much more likely that such a fragment occurs within a distance of b ∗ n from the beginning of the text than purely random Once all repetitions have been found, n can be potentially derived DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 16 Attack on a Symmetric Cipher Symmetric ciphers can be attacked by...... linear cryptanalysis... differential cryptanalysis... integral cryptanalysis DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 17 Linear Cryptanalysis Based on linear equations relating plaintext, ciphertext and key Those linear equations are used in conjunction with known plaintext- ciphertext pairs to derive key bits DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 18 Differential Cryptanalysis Based on the differences of two ciphertexts or two plaintexts, e.g. an XOR operation The pair of differences of two ciphertexts and of the corresponding two plaintexts is called differential Usually used with a chosen plaintext attack DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 19 Integral Cryptanalysis Based on sets of plaintexts of which a part is constant and another part is different for every two plaintexts in the set Another set of the corresponding ciphertexts is constructed The sum of the elements of each set is then computed and analyzed DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 20 Attack on an Asymmetric Cipher As asymmetric ciphers are based on mathematical principles for which rigorous proofs can be given (under certain assumptions), there is no general attack for asymmetric ciphers DEPARTMENT OF ADVANCED COMPUTING SCIENCES, MAASTRICHT UNIVERSITY COMPUTER SECURITY | 21