IT3122 Cryptography PDF

Cryptography IT3122 Computer Security Intended Learning Outcomes  Present an overview of the main concepts of symmetric cryptography.  Explain the operation of a monoalphabetic substitution cipher.  Describe the different ways of attacking ciphers.  Explain the difference between c...

Cryptography IT3122 Computer Security Intended Learning Outcomes  Present an overview of the main concepts of symmetric cryptography.  Explain the operation of a monoalphabetic substitution cipher.  Describe the different ways of attacking ciphers.  Explain the difference between cryptanalysis and brute-force attack.  Explain the operation of the shift cipher and the affine cipher.  Explain the operation of a polyalphabetic substitution cipher.  Explain the operation of a transposition cipher. Overview of the Field of Cryptology Cryptography and Cryptanalysis  Cryptography: The science of securing communication against an adversary.  Cryptanalysis: The science and sometimes art of breaking cryptosystems. Cryptography  Symmetric Algorithms  All cryptography from ancient times until 1976.  Two parties have an encryption and decryption method for which they share a secret key.  Asymmetric/Public-Key Algorithms  Introduced by Whitfield Diffie, Martin Hellman and Ralph Merkle in 1976.  Two keys exist: A user possesses a secret key as in symmetric cryptography but also a public key.  Cryptographic Protocols  Realize more complex security functions using cryptographic algorithms. Hybrid Schemes  In most cryptographic applications in practical systems, symmetric and asymmetric algorithms (and often also hash functions) are all used together.  The reason for using both families of algorithms is that each has specific strengths and weaknesses. Symmetric Cryptography  Also referred to as symmetric-key, secret-key and single-key cryptography.  Problem Statement: 1. There are two users, Alice and Bob, who want to communicate over an insecure channel. 2. The bad guy, Oscar has access to the channel, but should not be able to understand the communication. Communication over an Insecure Channel Solution: Symmetric Cryptography  Alice encrypts her message x using a symmetric algorithm, yielding the ciphertext y.  Bob receives the ciphertext and decrypts the message.  Decryption is the inverse process of encryption.  If we have a strong encryption algorithm, the ciphertext will look like random bits and Oscar will not be able to obtain any useful information from it.  Solution: Symmetric-key Cryptosystem x – plaintext/cleartext y – ciphertext k – key The problem of transmitting a message securely is reduced to the problems of transmitting a key secretly and of storing the key in a secure fashion. Encryption and Decryption  Encryption: 𝑦 = 𝑒𝑘 (𝑥) or 𝑌 = 𝐸(𝐾, 𝑋)  Decryption: 𝑥 = 𝑑𝑘 𝑦 or X = 𝐷(𝐾, 𝑌) x – plaintext/cleartext y – ciphertext k – key Substitution Cipher  Substitution = Replacement.  Historically substitution cipher has been widely used.  Goal: The encryption of text (as opposed to bits in modern digital systems).  Idea: Substitute each letter of the alphabet with another one. Monoalphabetic Substitution Cipher x A B C D E F G H I J K L M y k d w h l j o b t q y c v x N O P Q R S T U V W X Y Z y u s z m g a e x f n i p r x – plaintext y – ciphertext Encryption: HELLO WORLD → blccs nsgch Decryption: ossh vsgutuo → GOOD MORNING Example: Breaking the Cipher iq ifcc vqqr fb rdq vfllcq na rdq cfjwhwz hr bnnb hcc hwwhbsqvqbre hwq vhlq First Attack: Brute-Force Attack or Exhaustive Key Search  Brute-force attacks treat the cipher as a black box.  Oscar, the attacker, has the ciphertext from eavesdropping on the channel and happens to have a short piece of plaintext, e.g., the header of a file that was encrypted.  Oscar now simply decrypts the first piece of ciphertext with all possible keys.  If the resulting plaintext matches the short piece of plaintext, he knows that he has found the correct key.  Note: In practice, a brute-force attack can be more complicated because incorrect keys can give false positive results. Definition: Basic Exhaustive Key Search or Brute-Force Attack Let (𝑥, 𝑦) denote the pair of plaintext and ciphertext, and let 𝐾 = 𝑘1 , … , 𝑘𝜅 be the key space of all possible keys 𝑘𝑖. A brute-force attack now checks for every 𝑘𝑖 ∈ 𝐾 whether 𝑑 𝑘𝑖 𝑦 ≟ 𝑥 If the equality holds, a possible correct key is found; if not, proceed with the next key. First Attack: Brute-Force Attack or Exhaustive Key Search  Key Space: The set of all possible keys.  Key space of the substitution cipher = 26 × 25 × ⋯ × 3 × 2 × 1 = 26! ≈ 288  The key space has roughly a size of 288 , which is equal to the key space of a cipher that has a key consisting of 88 bits.  Even with hundreds of thousands of high-end PCs such a search would take several decades!  Is the substitution cipher secure? Second Attack: Letter Frequency Analysis  The brute-force attack from above treats the cipher as a black box, i.e., we do not analyze the internal structure of the cipher.  The substitution cipher can easily be broken by such an analytical attack.  Major weakness of the substitution cipher: each plaintext symbol always maps to the same ciphertext symbol.  The statistical properties of the plaintext are preserved in the ciphertext. Properties of Language that can be Exploited 1. Determine the frequency of every ciphertext letter. The frequency distribution, usually quite stable even for relatively short pieces of encrypted text, will be close to that of the given language in general. The most frequent letters can often easily be spotted in ciphertexts. For instance, in English E is the most frequent letter (about 13%), T is the second most frequent letter (about 9%), A is the third most frequent letter (about 8%), and so on. Relative Letter Frequencies of the English Language Properties of Language that can be Exploited 2. The method above can be generalized by looking at pairs or triples, or quadruples, and so on of ciphertext symbols. For instance, in English, the letter Q is almost always followed by a U. This behavior can be exploited to detect the substitution of the letter Q and the letter U. Properties of Language that can be Exploited 3. If we assume that word separators, which means “blanks”, have been found one can often detect frequent short words such as THE, AND, etc. Once we have identified one of these words, we immediately know three letters (or whatever the length of the word is) for the entire text. Solution: Breaking the Cipher WE WILL MEET IN THE MIDDLE OF THE LIBRARY AT NOON ALL ARRANGEMENTS ARE MADE Lesson Learned  Good ciphers should hide the statistical properties of the encrypted plaintext.  The ciphertext symbols should appear to be random.  A large key space alone is not sufficient for a strong encryption function. Cryptanalysis  The science and sometimes art of breaking cryptosystems. Classical Cryptanalysis  Ciphertext-only Attack: The adversary has only access to the ciphertext.  Known-plaintext Attack: In addition to the ciphertext, the adversary also knows some pieces of the plaintext.  Chosen-plaintext Attack: The adversary can choose the plaintext that is being encrypted and has access to the corresponding ciphertext.  Chosen-ciphertext Attack: The adversary can choose ciphertexts and obtains the corresponding plaintexts. Cryptanalysis vs Brute-force Attack  Cryptanalysis: Cryptanalytic attacks rely on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext–ciphertext pairs. This type of attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used.  Brute-force Attack: The attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average, half of all possible keys must be tried to achieve success. Implementation Attacks  Side-channel analysis can be used to extract a secret key by observing the behaviour of a cryptographic implementation. E.g.,  Using the electrical power consumption or electromagnetic radiation of the CPU that computes the cryptographic algorithms as side channels, the attacker records the power or electromagnetic traces and applies signal processing techniques to recover the key.  Timing side-channels: The adversary measures the run time behavior of a cryptographic implementation and attempts to compute the key from the timing measurements  Software side-channels: The adversary controls one process with which he or she can learn secret values such as cryptographic keys from another process by exploiting effects such as timing behaviour or cache access patterns. Social Engineering Attacks  Bribing  Blackmailing  Tricking  Classical espionage https://xkcd.com/538/ Lesson Learned  An attacker always looks for the weakest link in your cryptosystem. That means we must choose strong algorithms, and we must make sure that all other attacks such as social engineering and implementation attacks are not feasible. Security by Obscurity  A system can appear to be more secure because we keep the details hidden.  However, experience and military history has shown over time that such systems are almost always weak, and they are very often broken easily as soon as the secret design has been reverse-engineered or leaked out through other means.  E.g., Content Scramble System (CSS) Kerckhoffs’ Principle  Kerckhoff’s Principle: A cryptosystem should be secure even if the attacker knows all details about the system, with the exception of the secret key. In particular, the system should be secure when the attacker knows the encryption and decryption algorithms.  Solid cryptosystems should adhere to Kerckhoffs’ Principle. Shift/Caesar Cipher A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Let 𝑥, 𝑦, 𝑘 ∈ ℤ26. Encryption: 𝑦 = 𝑒𝑘 𝑥 ≡ 𝑥 + 𝑘 𝑚𝑜𝑑 26 Decryption: 𝑥 = 𝑑𝑘 𝑦 ≡ 𝑦 − 𝑘 𝑚𝑜𝑑 26 Ways of Attacking Shift Cipher 1. Brute-force Attack: Since there are only 26 different keys (shift positions), one can easily launch a brute-force attack by trying to decrypt a given ciphertext with all possible 26 keys. 2. Letter Frequency Analysis: As soon as the attacker has discovered the ciphertext letter for one plaintext letter, he/she knows the number of shifts and thus has the key Affine Cipher  Extension of the shift cipher. Let 𝑥, 𝑦, 𝑎, 𝑏 ∈ ℤ26. Encryption: 𝑦 = 𝑒𝑘 𝑥 ≡ 𝑎𝑥 + 𝑏 𝑚𝑜𝑑 26 Decryption: 𝑥 = 𝑑𝑘 𝑦 ≡ 𝑎−1 (𝑦 − 𝑏) 𝑚𝑜𝑑 26 with the key: 𝑘 = (𝑎, 𝑏), which has the restriction: gcd 𝑎, 26 = 1. Affine Cipher  An element 𝑎 and the modulus must be relatively prime for the inverse of 𝑎 to exist. 𝑎 ∈ {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}  𝑎 ∙ 𝑎−1 ≡ 1 𝑚𝑜𝑑 26  E.g., if 𝑎 = 3, then 𝑎−1 = 9 since 3 ∙ 9 = 27 ≡ 1 𝑚𝑜𝑑 26.  The inverse of 𝑎−1 is 𝑎 itself. Ways of Attacking Affine Cipher 1. Brute-force Attack: Since there are only 312 different keys, one can easily launch a brute- force attack by trying to decrypt a given ciphertext with all possible 312 keys. 2. Letter Frequency Analysis Polyalphabetic Substitution Cipher (Vigenère Cipher)  Extension of the shift cipher.  Instead of using a single key 𝑘 for the shift, it uses 𝑙 different shifts that are derived from a secret code word 𝑐.  The code word consists of 𝑙 letters and has the form 𝑐 = (𝑐0 , 𝑐1 , … , 𝑐𝑙−1 ).  Each letter 𝑐𝑖 corresponds to a number 0, … , 25, which is given by its position in the alphabet.  These numbers are the 𝑙 shift positions, which we denote (𝑘0 , 𝑘1 , … , 𝑘𝑙−1 ). Encryption: 𝑦𝑗 ≡ 𝑥𝑗 + 𝑘(𝑗 𝑚𝑜𝑑 𝑙) 𝑚𝑜𝑑 26 Decryption: 𝑥𝑗 ≡ 𝑦𝑗 − 𝑘(𝑗 𝑚𝑜𝑑 𝑙) 𝑚𝑜𝑑 26 where 𝑥𝑗 denotes the 𝑗th letter of the plaintext 𝑥 = (𝑥0 , 𝑥1 , … ). Plaintext: GOODMORNING Key: APPLEAPPLEA Ciphertext: GDDOQOGCTRG WEAREDISCOVEREDSAVEYOURSELF ALGORITHMALGORITHMALGORITHM WPGFVLBZOOGKFVLLHHEJUIIAXSR Cryptanalysis of Vigenère Cipher  The strength of this cipher is that there are multiple ciphertext letters for each plaintext letter, one for each unique letter of the keyword.  Thus, the letter frequency information is obscured.  However, not all knowledge of the plaintext structure is lost. Cryptanalysis of Vigenère Cipher  An analyst looking at only the ciphertext would detect the repeated sequences FVL at a displacement of 9 and assume that the keyword is either three or nine letters in length.  The appearance of FVL twice could be by chance and may not reflect identical plaintext letters encrypted with identical key letters.  However, if the message is long enough, there will be several such repeated ciphertext sequences.  By looking for common factors in the displacements of the various sequences, the analyst should be able to make a good guess of the keyword length. Cryptanalysis of Vigenère Cipher  If the keyword length is 𝑚, then the cipher, in effect, consists of 𝑚 monoalphabetic substitution ciphers.  E.g., with the keyword ALGORITHM, the letters in positions 1, 10, 19, and so on are all encrypted with the same monoalphabetic cipher.  Thus, we can use the known frequency characteristics of the plaintext language to attack each of the monoalphabetic ciphers separately. Cryptanalysis of Vigenère Cipher  The periodic nature of the keyword can be eliminated by using a nonrepeating keyword that is as long as the message itself. Transposition Cipher  Mapping is achieved by performing some sort of permutation on the plaintext letters.  Transpositions might look less secure than substitutions, but can in fact be more secure.  E.g., rail fence technique: THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG t e u c b o n o j m s v r h l z d g h q i k r w f x u p o e t e a y o teucbonojmsvrhlzdghqikrwfxupoeteayo Scytale of Sparta Columnar Transposition Key: 4 3 1 2 5 6 7 Plaintext: T H E Q U I C K B R O W N F O X J U M P S O V E R T H E L A Z Y D O G Ciphertext: ERJEZQOURYHBXVATKOOLUWMTDINPHOCFSEG Cryptanalysis of Transposition Cipher  A pure transposition cipher is easily recognized because it has the same letter frequencies as the original plaintext.  For the type of columnar transposition just shown, cryptanalysis is straightforward and involves laying out the ciphertext in a matrix and playing around with column positions.  Digram and trigram frequency tables can be useful. Cryptanalysis of Transposition Cipher  The transposition cipher can be made significantly more secure by performing more than one stage of transposition.  The result is a more complex permutation that is not easily reconstructed. Double Transposition Key: 4 3 1 2 5 6 7 Plaintext: E R J E Z Q O U R Y H B X V A T K O O L U W M T D I N P H O C F S E G Ciphertext: JYKTCEHODFRRTMOEUAWHZBOISQXLNEOVUPG Questions References  C. Paar, J. Pelzl and T. Güneysu, “Introduction to Cryptography and Data Security,” Understanding Cryptography: From Established Symmetric and Asymmetric Ciphers to Post-Quantum Algorithms, Springer, 2nd Edition, 2024, pp. 1–35.  W. Stallings, “Classical Encryption Techniques,” Cryptography and Network Security: Principles and Practice, 8th Edition, 2023, pp. 83–111.