Master Cryptanalysis: Unlock the Secrets of Secure Communication 🔐

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