Cryptography (Classic) Lecture Notes PDF

Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida, College...

Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida, College of Computer Science, King Khaled University 'KKU', KSA okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA No List of Topics Contact Hours 1. Review of number theory, Probability and Statistics Ch01 Maths 4 2. Security functions of cryptography Ch1 8 Intro & Ch2 Classical 3. Symmetric cryptography Ch3- 8 1 & Ch3-2 4. Public key cryptography Ch4-1 8 & Ch4-2 5. Key generation, Management, Exchange and distribution 8 Ch5 6. Digital certificate Ch6 2 7. Hash functions Ch6 4 8. Digital signature Ch7 4 9. Collision resistance Ch7 2 10.HMIDA, okhtar BEN Common Cryptographic Dr. & Protocols Full Professor, Head andExpert of ATMS Lab, standards Processing , in SignalCh8 CS4College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-1 : Preface to Symmetric Cryptography, Cryptanalysis, Attacks, Ciphers Symmetric Cryptography ; OTP, Transposition vs Substitution… Symmetric Cryptography ; OTP vs Perfect Scerecy… Symmetric Cryptography ; Principles… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Cryptanalysis Objective to recover key not just message General approaches: Cryptanalytic attack Brute-force attack okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Types of Cryptanalytic Attacks harder for ciphertext only adversary only know (algorithm +) ciphertext, statistical, in order to identify plaintext, or worse: the key known plaintext know plaintext & ciphertext pairs in order to get deduce plaintext of one important pair or key chosen plaintext select plaintext and obtain ciphertext to attack cipher chosen ciphertext select ciphertext and obtain plaintext to attack cipher (chosen plaintext in reverse) chosen text select either plaintext or ciphertext to en/decrypt to attack cipher (think easier for stolen crypto unit) adversary 5 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Types of Attacks on Encrypted Messages (05) okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Chosen-Plaintext Attack PIN is encrypted and transmitted to bank cipher(key,PIN) Crook #2 eavesdrops Crook #1 changes on the wire and learns his PIN to a number ciphertext corresponding of his choice to chosen plaintext PIN … repeat for any PIN value Chosen plaintext attack is a scenario in which the attacker has the ability to choose plaintexts Pi and to view their corresponding encryptions – ciphertexts Ci. This attack is considered to be less practical than the known plaintext attack, but is still a very dangerous attack. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Brute-force attack 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. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Brute Force Search Always possible to simply try every key Most basic attack, proportional to key size Assume either know / recognise plaintext okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Rail Fence cipher Type of Transpositional cipher. For example, to encipher the message “meet me after the toga party” with a rail fence of depth 2, we write the following: mematrhtgpry etefeteoaat The encrypted message is MEMATRHTGPRYETEFETEOAAT okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Cryptanalysis of Caesar Cipher  only have 26 possible ciphers  A maps to A,B,..Z  could simply try each in turn  a brute force search  given ciphertext, just try all shifts of letters  do need to recognize when have plaintext  eg. break ciphertext "sdd qgmj tskw sjw twdgfy lg mk" okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-1 : Preface to Symmetric Cryptography, Cryptanalysis, Attacks, Ciphers Symmetric Cryptography ; OTP, Transposition vs Substitution… Symmetric Cryptography ; OTP vs Perfect Scerecy… Symmetric Cryptography ; Principles… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA One-Time Pad ‘OTP’  if a truly random key as long as the message is used, the cipher will be secure…  called a One-Time pad ‘OTP’  is unbreakable since ciphertext bears no statistical relationship to the plaintext  since for any plaintext & any ciphertext there exists a key mapping one to other  can only use the key once though  problems in generation & safe distribution of key okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Transposition Ciphers Now consider classical transposition or permutation ciphers These hide the message by rearranging the letter order without altering the actual letters used Can recognise these since have the same frequency distribution as the original text okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Row Transposition Ciphers A more complex scheme is to write the message in a rectangle, row by row, and read the message off, column by column, but permute the order of the columns. The order of the columns then becomes the key to the algorithm. the key is 4312567. To For example, encrypt, start with the Key: 4 3 1 2 5 6 7 column Plaintext: a t t a c k p that is labelled 1, in this o s t p o n e case column 3. Write d u n t i l l t w o a m x y down all the letters in that column. Ciphertext: TTNOAPTATSUWAODTCOIMKNLPEL Proceed to column 4, which is labelled 2, then column 2, then column 1, then columns 5, 6, and 7. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Product Ciphers Ciphers using Substitutions or Transpositions are not secure because of language characteristics Hence, consider using several ciphers in succession to make harder, but: Two Substitutions make a more complex substitution ; Two Transpositions make more complex transposition ; But Substitution followed by Transposition makes a new much harder cipher. This is bridge from classical to modern ciphers okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Simple Idea: ‘OTP’ One-Time Pad = 10111101… 10111101… ----- ----- -----  10001111…  = 00110010… 00110010… Key is a never-repeating bit sequence as long as plaintext Decrypt by bitwise XOR of ciphertext and key: ciphertext  key = Encrypt by bitwise XOR of (plaintext  key)  key = plaintext and key: plaintext  (key  key) = ciphertext = plaintext  key plaintext One-time pad is a unique encryption process. Like most, it uses a key to encrypt and decrypt. However, in this process, a key is generated randomly to encrypt the messages for a specific session. To decrypt, the same key is used. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA If you have a message M and the OTP One-Time Pad ciphertext C, Can you recover the KEY? okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-1 : Preface to Symmetric Cryptography, Cryptanalysis, Attacks, Ciphers Symmetric Cryptography ; OTP, Transposition vs Substitution… Symmetric Cryptography ; OTP vs Perfect Scerecy… Symmetric Cryptography ; Principles… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA ‘OTP’ One-Time Pad and Perfect Secrecy okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Explanation  Even if given a choice of two Plaintexts, one the real one, for a ciphertext, you cannot distinguish which plaintext is the real one (perfect message indistinguishability)  Seeing a ciphertext doesn't give you any extra information about the plaintext. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA So, okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Does OTP One-Time Pad have perfect secrecy? Given perfect secrecy, in contrast to conventional symmetric encryption, the one-time pad is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA How do you prove that OTP has perfect secrecy ? Since P(C = c)=1/N = P(K = c + m), we can multiply by N to obtain P(M = m | C = c) = P(M = m), which says that the one-time pad is perfectly secret. One of the difficulties with using the OTP one-time pad is that the number of possible keys is as least as large the number of possible messages. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Advantages of One-Time Pad Easy to compute Encryption and decryption are the same operation Bitwise XOR is very cheap to compute As secure as possible Given a Ciphertext, all Plaintexts are equally likely, regardless of attacker’s computational resources …as long as the key sequence is truly random True randomness is expensive to obtain in large quantities …as long as each key is same length as plaintext okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Problems with One-Time Pad Key must be as long as plaintext Impractical in most realistic scenarios Still used for diplomatic and intelligence traffic Does not guarantee integrity One-time pad only guarantees confidentiality Attacker cannot recover plaintext, but can easily change it to something else Insecure if keys are reused Attacker can obtain XOR of plaintexts okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Type of ciphers Symmetric encryption: Secret key cryptography Asymmetric encryption: Public/private key cryptography Cryptography Designing mechanisms to assure secrecy Cryptography Cryptography With Secret key With Public key (Symmetric Encryption) (Asymmetric Encryption) In both cases, the encryption function is known, the nature of the key (secret/public/private) which makes okhtar BENthe difference HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-1 : Preface to Symmetric Cryptography, Cryptanalysis, Attacks, Ciphers Symmetric Cryptography ; OTP, Transposition vs Substitution… Symmetric Cryptography ; OTP vs Perfect Scerecy… Symmetric Cryptography ; Principles… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Symmetric Encryption Process Definition: symmetric encryption also called secret key or symmetric key encryption uses one and the same key for encryption and decryption. was only type prior to invention of public-key in 1970’s General idea of symmetric-key cipher okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Algorithms in which the key for Encryption and Decryption are the Encryption same are Symmetric Symmetric Algorithms Example: Caesar Cipher in the Past, others NOW !!! Types: 1. Block Ciphers – Encrypt data one block at a time (typically 64 bits, or 128 bits) – Used for a single message 2. Stream Ciphers – Encrypt data one bit or one byte at a time okhtar BEN HMIDA, Dr. & Full Professor, Head – of Used if data ATMS Lab, isinaSignal Expert constant stream Processing , of information CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Symmetric Encryption ; Key Strength Strength of algorithm is determined by the size of the key The longer the key the more difficult it is to crack Key length is expressed in bits Typical key sizes vary between 48 bits and 448 bits Set of possible keys for a cipher is called key space For 40-bit key there are 240 possible keys For 128-bit key there are 2128 possible keys Each additional bit added to the key length doubles the security To crack the key the hacker has to use brute- force (i.e. Dr. okhtar BEN HMIDA, try& Full all Professor, the possible keys Head of ATMS till Lab, a key Expert that in Signal works, Processing is CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Principle of Symmetric encryption Also called Secret-key Encryption, Symmetric Encryption uses the same key, kept secret, for Encryption and Decryption. – Encryption is performed by adding (XOR function) the key to the message cut into blocks, and performing several permutations, while iterating several times. Symmetric encryption uses secure channels to exchange the secret key ( IPSec ). Algorithms: o DES (Data Encryption Standard), o Triple-DES (3DES), o AES (Advanced Encryption Standard), o IDEA (International Data Encryption Algorithm ), Blowfish => Simple to implement, execution can be very fast okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Principle of Symmetric encryption Key Transmission by secure channel Key Plaintext Plaintext Encryptio Decryptio n n Encrypted Text Sender Receiver okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Symmetric Cipher Model okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Symmetric Key Cryptography Symmetric key : Bob and Alice share the same (symmetric) key: KA-B e.g., key is knowing substitution pattern in mono alphabetic substitution cipher K K A-B A-B Encryption Ciphertext Decryption Plaintext; m algorithm algorithm Plaintext; m K (m) m=K ( K (m) ) A-B A-B A-B okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Model of Symmetric Encryption Encryption algorithm: Encryption algorithm performs various substitutions & transformations on Plaintext. Secret key: as an input to the Encryption algorithm. Its value independent of Plaintext & of the Algorithm. The algorithm will produce a different output depending on the specific key being used at the time. The exact substitutions and transformations performed by the algorithm depend on the key. Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the secret key. For a given message, two different keys will produce two different ciphertexts. The ciphertext is an apparently random stream of data and, as it stands, is unintelligible. Decryption algorithm: This is essentially the encryption algorithm run in reverse. It takes okhtar the ciphertext BEN HMIDA, and Dr. & Full the secret Professor, key Head of and ATMSproduces the Lab, Expert in original Plaintext. Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Two requirements for secure use of Symmetric Encryption: Strong Encryption Algorithm Secret key known only sender/receiver Y = EK(X) & X = DK(Y) Assume Encryption Algorithm is known, Implies a secure channel to distribute key… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh