Introduction to Cryptanalysis

Full Course: https://www.youtube.com/playlist?list=PLUoixF7agmIsF8NiiQcCMB9x5mi3l8dEW Introduction to Cryptanalysis Cryptology is about secure communication in an insecure channel Cryptography is about designing secure cryptosystems Cryptanalysis is about analyzing (breaking) cryptosystem Today the words Cryptology and Cryptography are used interchangeably Some of the Security Problems Solved by Cryptography 1 Privacy of stored data, messages, and conversations 2 Integrity of stored data, messages, and conversations 3 User and data authentication 4 Transaction non-repudiation What is a Cryptosystem? Plaintext is what you want to protect A cryptosystem is pair of algorithms that convert plaintext to ciphertext and back Ciphertext is the encrypted version of the plaintext Ciphertext should appear like a random sequence Simple Monoalphabetic Substitution Every letter is replaced by a letter Weakness: Redundancy in the language Can be broken by frequency analysis Frequency Analysis Frequency analysis is introduced by Al-Kindi in "A Manuscript Deciphering Cryptographic Messages" in 9th century It is based on the redundancy of the language: 1 For a given language, find a long text and count the number of frequencies of every letter 2 For instance, in English E is the letter that appears the most. The second place belongs to T 3 If the ciphertext is long enough, the letter that appears the most in the ciphertext is most probably corresponds to E in the plaintext 4 The letter in the ciphertext with the second most frequency is most probably corresponds to T in the plaintext 5 And so on... What should be the key size? An attacker that captures a single ciphertext, can try to decrypt it with every possible key to check if it provides a meaningful plaintext. Such an attack is called exhaustive search or brute force attack. Exhaustive search is a generic attack, i.e. valid for every cipher. For a k-bit keyed cipher, the attacker is required to perform at most 2^k encryptions/decryptions. Thus, security of a block cipher is upper bounded by exhaustive search, i.e. 2^k encryptions. This quantity is referred to as Time Complexity. Aim of the cryptanalyst Try to break the cipher (or its round-reduced version) with a time complexity less than 2^k encryptions Data Types For cryptanalysis, attacker may need different types of data: 1 Ciphertext Only 2 Known Plaintext 3 Chosen Plaintext 4 Adaptively Chosen Plaintext Collecting data becomes harder as we move down the list Resource Types The success of an attack is measured according to the resources it uses: 1 Time: The time or effort required to perform the attack 2 Memory: The amount of memory or storage required the perform the attack 3 Data: The amount of data required to perform the attack Some Non-generic Attack Techniques Differential Cryptanalysis (Biham-Shamir 1980s) Truncated Differential Cryptanalysis (Knudsen 1994) Higher Order Differential Cryptanalysis (Knudsen 1994) Impossible Differential Cryptanalysis (Biham-Biryukov-Shamir 1998) Boomerang Attack (Wagner 1999) Improbable Differential Cryptanalysis (Tezcan 2010) Linear Cryptanalysis (Matsui 1992) Multiple Linear Cryptanalysis Multidimensional Linear Cryptanalysis Slide Attack (Wagner-Biryukov 1999) Integral Cryptanalysis (Knudsen 2001) eXtended Sparse Linearization (XSL) (Courtois-Pieprzyk 2002) Invariant Subspace Attack (Leander et al. 2011) Subspace Trail Attack (Grassi-Rechberger-Ronjom 2016) #cryptanalysis #crypto #cryptography