Cryptography Concepts and Algorithms PDF

Chapter 2 Cryptographic Tools  Outline Overview of Cryptography Classical Symmetric Cipher Modern Symmetric Ciphers (DES)  Basic Terminology plaintext - the original message ciphertext - the coded message Cipher (encryption algorithm) - algorithm for transfor...

Chapter 2 Cryptographic Tools  Outline Overview of Cryptography Classical Symmetric Cipher Modern Symmetric Ciphers (DES)  Basic Terminology plaintext - the original message ciphertext - the coded message Cipher (encryption algorithm) - algorithm for transforming plaintext to ciphertext key - information used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - recovering plaintext from ciphertext  Basic Terminology cryptography - study of encryption principles/methods cryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key cryptology - the field of both cryptography and cryptanalysis  Classification of Cryptography a) Based on Number of keys used Hash functions: no key Secret key cryptography: one key Public key cryptography: two keys - public, private b) Based on Type of encryption operations used substitution / transposition / product c) Based on the Way in which plaintext is processed block / stream  Encryption types Symmetric Asymmetric  Symmetric Encryption The universal technique for providing confidentiality for transmitted or stored data Also referred to as conventional encryption or single-key encryption Two requirements for secure use: Need a strong encryption algorithm Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure  Symmetric encryption scheme has five ingredients Plaintext (X): This is the original message or data that is fed into the algorithm as input. Encryption algorithm (E): The encryption algorithm performs various substitutions and transformations on the plaintext. Secret key (K): The secret key is also input to the encryption algorithm. The exact substitutions and transformations performed by the algorithm depend on the key. Ciphertext (Y): 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. Decryption algorithm (D): This is essentially the encryption algorithm run in reverse. It takes the ciphertext and the secret key and produces the original plaintext.  Y = EK(X) X = DK(Y) Assume encryption algorithm is known Implies a secure channel to distribute key  Attacks on Symmetric Encryption Cryptanalytic Brute-Force Attacks Attack  Attacking Symmetric Encryption 1. Cryptanalytic Attacks Nature of the algorithm Some knowledge of the general characteristics of the plaintext Some sample plaintext-cipher text pairs Exploits the characteristics of the algorithm If successful all future and past messages encrypted with that key are compromised Cryptanalysis Scheme Ciphertext only: Exhaustive search until “recognizable plaintext” Need enough ciphertext Known plaintext: Secret may be revealed (by spy), thus pair is obtained Great for monoalphabetic ciphers Chosen plaintext: Choose text, fed into the encryption algorithm, get encrypted Useful if limited set of messages  2. Brute-Force Attack try all possible keys on some cipher text until an intelligible translation into plaintext is obtained on average half of all possible keys must be tried to achieve success Average Time Required for Exhaustive Key Search  Outline Overview of Cryptography Classical Symmetric Cipher Modern Symmetric Ciphers (DES)  Classical Symmetric Cipher o Substitution Cipher o Transposition Cipher  Classical Substitution Ciphers Letters of plaintext are replaced by other letters or by numbers or symbols Plaintext is viewed as a sequence of bit, then substitution replaces plaintext bit patterns with ciphertext bit patterns  a. Caesar Cipher Earliest known substitution cipher Replaces each letter by 3rd letter on Example: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB  Caesar Cipher Define transformation as: a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Mathematically give each letter a number 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 Then have Caesar cipher as: C = E(p) = (p + k) mod (26) p = D(C) = (C – k) mod (26)  Cryptanalysis of Caesar Cipher Only have 25 possible ciphers o Example: A mapped to letters from B,..Z Given ciphertext, just try all shifts of letters Do need to recognize when have plaintext E.g., break ciphertext "GCUA VQ DTGCM" b. Monoalphabetic Cipher Rather than just shifting the alphabet Could shuffle (jumble) the letters arbitrarily Each plaintext letter maps to a different random ciphertext letter Key is 26 letters long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA  Monoalphabetic Cipher Security Now have a total of 26! = 4 x 1026 keys Is that secure? Problem is language characteristics o Human languages are redundant o Letters are not equally commonly used Example Cryptanalysis Given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ Count relative letter frequencies (see text) Guess P & Z are e and t Guess ZW is th and hence ZWP is the Proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow  c. One-Time Pad If a truly random key as long as the message is used, the cipher will be secure - One-Time key E.g., a random sequence of 0’s and 1’s XORed to plaintext, no repetition of keys Unbreakable since ciphertext bears no statistical relationship to the plaintext or any other ciphertext For any plaintext, it needs a random key of the same length Hard to generate large amount of keys Have problem of safe distribution of key  Transposition Ciphers Classical transposition or permutation ciphers, 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.  a. Rail Fence cipher Write message letters out diagonally over a number of rows Then read off cipher row by row E.g., write message out as (in two rows): m e m a t r h t g p r y e t e f e t e o a a t Giving ciphertext MEMATRHTGPRYETEFETEOAAT  Product Ciphers Product Cipher combines two or more transformations in a manner intending that the resulting cipher is more secure to make it resistant to cryptanalysis. 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 a substitution followed by a transposition makes a new much harder cipher This is bridge from classical to modern ciphers  Outline Overview of Cryptography Classical Symmetric Cipher Modern Symmetric Ciphers (DES,3DES, & AES)  The most commonly used symmetric encryption algorithms are block ciphers. The most important symmetric algorithms, all of which are block ciphers, are i. Data Encryption Standard (DES) ii. triple DES iii. Advanced Encryption Standard (AES);  Comparison of Three Popular Symmetric Encryption Algorithms The most important factor in the symmetric encryption Data Encryption Standard (DES) The most widely used encryption scheme Federal Information Processing Standard 46 (FIPS PUB 46). Referred to as the Data Encryption Algorithm (DEA) Uses 64 bit plaintext block and 56 bit key to produce a 64 bit ciphertext block Data Encryption Standard (DES) Concerns about the strength of DES 1. Concerns about algorithm refers to the possibility that cryptanalysis is possible DES is the most studied encryption algorithm in existence 2. Concerns about the use of 56-bit key Electronic Frontier Foundation (EFF) announced in July 1998 that it had broken a DES encryption  Triple DES (3DES)  Repeats basic DES algorithm three times using either two or three unique keys  First standardized for use in financial applications in ANSI standard X9.17 in 1985  Attractions:  168-bit key length overcomes the vulnerability to brute-force attack of DES  Underlying encryption algorithm is the same as in DES  Drawbacks:  Algorithm is sluggish in software and slower  Uses a 64-bit block size. For reasons of both efficiency and security, a larger block size is desirable.  Advanced Encryption Standard (AES) NIST called for Needed a Selected proposals for a replacement Rijndael in new AES in for 3DES November 2001 1997 Should have a security strength equal to or better than 3DES Significantly improved 3DES was not efficiency Published as reasonable for long term use FIPS 197 Symmetric block cipher 128 bit data and 128/192/256 bit keys  Table 2.2 Average Time Required for Exhaustive Key Search  Block Ciphers Block Cipher More common used in symmetric encryption Encryption algorithm that takes a fixed size of input (block) and produces a ciphertext Processes the input one block of elements at a time Produces an output block for each input block Can reuse keys Block size 64-bit or 128-bit Block Cipher modes of operations: Electronic Code Book (ECB) ---- broken Cipher Feedback Mode (CFB) Cipher Block Chaining  Electronic Codebook (ECB) each block of bits of plaintext is encrypted independently with the same key. Plaintext blocks (P1, P2, …..Pn) Ciphertext blocks (C1, C2,…..Cn)  Stream Ciphers In stream cipher, one byte is encrypted at a time while in block cipher , one block is encrypted at a time. Key will be input to key stream generator and then it produces a random 8-bit output which is treated as keystream. Then keystream will XOR with plain text to produce cipher text Stream ciphers are fast because they encrypt data byte by byte, Stream ciphers work well for real-time communication Stream Ciphers  Stream Ciphers Example for stream cipher encryption : Plaintext : 10011001 Keystream : 11000011 ---------------------------------- XOR Ciphertext : 01011010 Decryption Ciphertext : 01011010 Keystream : 11000011 --------------------------------- XOR Plaintext : 10011001