Evolution of Cryptography: From Ancient Techniques to Modern Security Mechanisms
Explore the evolution of cryptography from ancient techniques like the Caesar Cipher to modern security mechanisms like SSL, SSH, and IPSec. Learn how cryptography plays a crucial role in ensuring confidentiality, integrity, authentication, non-repudiation, and availability in network security. Discover the limitations of cryptography and why it is essential to study cryptography for securing networks and systems effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Introduction to Cryptography INFSCI 1075: Network Security Spring 2013 Sam T. Zargar
Security Features and Mechanisms Security Features (Security Services) Measures intended to counter security attacks by employing security mechanisms Take on functions of physical documents and procedures like signatures, identity cards, endorsements, etc. Typical services: Confidentiality, integrity, authentication, non- repudiation, and availability. Security Mechanisms Prevent, detect, and recover from security attacks No single security mechanism can provide all the security services 2
Remarks Not all security services can be provided by a single security mechanism Cryptography, if used cleverly and correctly, can provide several of the security services Cryptography is the backbone of most security mechanisms SSL, SSH, IPSec, WPA, Kerberos, VPNs, Dial-up, etc. Cryptography: using encryption and decryption principles/methods to conceal information 3
Limitations of Cryptography Cryptography is not a complete solution in itself Systems and networks are not secure today Not because of the mathematics behind cryptography The math is sound Implementation of the cryptosystems and usage of cryptography in protocols are occasionally flawed The human factor Why you need to study cryptography An important component of information security today Awareness of what is used where and why it works Sense of why crypto in itself is not enough, but you need things around it to make networks and systems secure 4
History For thousands of years people have used methods of concealing information Concealing Ciphering or Encryption Examples Writing concealed information from the illiterate Mirrors were used in India Tattoo messages on scalps and allow hair to grow Biblical times (500 BC) Substitution of one alphabet by another in a systematic way Sparta (500 BC) Scytale (sitaali) http://en.wikipedia.org/wiki/Scytale 5
History (2) Caesar Cipher (50 BC) Described by Julius Caesar Example of a Shift Cipher World War I Creation of many new ciphers ADFGVX code by the German military in World War 1 A product cipher Cryptography and Mathematics Linkages started in the 1920s Extended to World War II Information Theory played a role in 1949 when Shannon defined perfect secrecy 6
Modern Times Data Encryption Standard (DES)(1977) Opened up a new area of research for securing digital information All encryption algorithms from BC till 1976 were secret key algorithms Also called private key algorithms or symmetric key algorithms Public key algorithms were introduced in 1976 by Whitfield Diffie and Martin Hellman (asymmetric) 7
Some Basic Terminology Plaintext - original message Ciphertext - coded message Cipher - algorithm for transforming plaintext to ciphertext Key - info used in cipher known only to sender/receiver Encipher (encrypt) - converting plaintext to ciphertext Decipher (decrypt) - recovering plaintext from ciphertext 8
Definitions Cryptography using encryption and decryption principles/methods to conceal information Cryptanalysis (code breaking) - study of principles/ methods of deciphering ciphertext without knowing the key Cryptology study of both cryptography and cryptanalysis Encryption Conventional (symmetric) encryption Public-key (asymmetric) encryption 9
Cryptology PROTOCOLS CRYPTOLOGY CRYPTOGRAPHY CRYPTANALYSIS Private Key (Secret Key) Public Key Block Cipher Stream Cipher Integer Factorization Discrete Logarithm 10
Cryptography Can characterize cryptographic system by: Type of encryption operations used Substitution / transposition / product Number of keys used Single-key or private / two-key or public Way in which plaintext is processed block / stream 11
Block vs. Stream Ciphers Block ciphers process messages in blocks, each of which is then en/decrypted like a substitution on very big characters 64-bits or more Stream ciphers process messages a bit or byte at a time when en/decrypting Many current ciphers are block ciphers Broader range of applications 12
Cryptanalysis The science/art of breaking an encryption scheme Objective is to recover key not just message General approaches: Cryptanalytic attack May rely on: Nature of encryption algorithm Characteristics of the plaintext Some plaintext-cipher text pairs Brute-force attack Try every key time and space complexity! On average, half of all possible keys must be tried to achieve success. 13
Cryptanalytic Attacks Ciphertext only Cryptanalyst has only Ciphertext of possibly many messages. Known plaintext Access to both plain and ciphertext of several messages, probable words. Chosen plaintext Attacker can select plaintext and obtain its ciphertext. Chosen ciphertext Attacker has access to decrypting box, objective is deduce the key, have the corresponding plaintext. The HUMAN factor Rubber hose attack -- threaten, torture, blackmail for the key Purchase-key attack -- bribery (or burglary) Scam attack excuse me, could you tell me your password? I m stupid attack easy to guess key (name, birthdate, phone number, .) 14
Encryption scheme is: Unconditionally secure if: No matter how much computer power or time is available, the cipher cannot be broken since the cipher-text provides insufficient information to uniquely determine the corresponding plaintext \ e.g., one-time pad (later) Computationally secure if: Given limited computing resources (e.g. time needed for calculations is greater than age of universe), the cipher cannot be broken and it is costly! 15
Brute Force Search Always possible to simply try every key Most basic attack, proportional to key size Assume either know / recognize plaintext Time required at 106 decryptions/ s Key Size (bits) Number of Alternative Keys 232 = 4.3 109 Time required at 1 decryption/ s 231 s 32 = 35.8 minutes 2.15 milliseconds 256 = 7.2 1016 255 s 56 = 1142 years 10.01 hours 2128 = 3.4 1038 = 5.4 1024 years 5.4 1018 years 2127 s 128 2168 = 3.7 1050 = 5.9 1036 years 5.9 1030 years 2167 s 168 26! = 4 1026 2 1026 s = 6.4 1012 years 6.4 106 years 26 characters (permutation) 16
Symmetric Encryption OR conventional / private-key / single-key Sender and receiver share a common key All classical encryption algorithms (from BC till 1976) Was only type prior to invention of public-key in 1976 and by far most widely used 17
Conventional Encryption Model Insecure channel Alice Bob x Encrypt Decrypt y x k k Secure Channel Oscar Key Source 19
Requirements Two requirements for secure use of symmetric encryption: a strong encryption algorithm a secret key known only to sender / receiver Mathematically have: Y = ek(X) X = dk(Y) The functions ek() and dk() must be inverses of one another ek(dk(y)) = ? dk(ek(x)) = ? ek(dk(x)) = ? Assume encryption/decryption algorithm is known, strength is in key Implies a secure channel to distribute key 20
Classical Substitution Ciphers where letters of plaintext are replaced by other letters or by numbers or symbols or if plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns
Shift Ciphers Idea Represent the capital letters of the English alphabet by integers Encryption ek(x) = (x + k) mod 26 Decryption dk(y) = (y k) mod 26 A 0 N 13 14 15 16 17 18 19 20 21 22 23 24 25 B 1 O C 2 P D 3 Q E 4 R F 5 S G 6 T H 7 U I J 9 W K 10 11 12 X Y L M 8 V Z 23
Caesar Cipher earliest known substitution cipher by Julius Caesar (50 BC) first attested use in military affairs replaces each letter by 3rd letter on example: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB
Set of Residues: Zn The result of the modulo operation with modulus n is always an integer between 0 and n-1. Modulo operation creates a set, which in modular arithmetic is referred to as the set of least residues, modulo n, or Zn E.g. Z2 ={0,1} Z6 ={0,1,2,3,4,5} Z10={0,1,2,3,4,5,6,7,8,9} 25
The modulo operation (Quick review) What is 27 mod 5? Quotient? 5 Divisor 5 27 Dividend - 25 Remainder? 2 What is -27 mod 5? Quotient? -6 Divisor 5 -27 Dividend - (-30) Remainder? 3 26
Examples 36 mod 9 = 0 4 9 36 -36 0 -45 mod 9 = 0 -5 9 -45 -(- 45) 0 27
Shift Ciphers Cipher-text: HCEGDQQM K: C What is the plain-text? Encryption ek(x) = (x + k) mod 26 Decryption dk(y) = (y k) mod 26 A 0 N 13 14 15 16 17 18 19 20 21 22 23 24 25 B 1 O C 2 P D 3 Q E 4 R F 5 S G 6 T H 7 U I J 9 W K 10 11 12 X Y L M 8 V Z 28
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 "GCUA VQ DTGCM
Monoalphabetic Cipher Rather than just shifting the alphabet Could shuffle (jumble) the letters arbitrarily Each plaintext letter maps to a different random ciphertext letter Hence key is 26 letters long Plain: 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 Cipher:D K V Q F I B J W P E S C X H T M Y A U O L R G Z N If we wish to replace letters Plaintext: ifwewishtoreplaceletters Ciphertext:WIRFRWAJUHYFTSDVFSFUUFYA 30
Monoalphabetic Cipher Security now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !!!WRONG!!! problem is language characteristics
Language Redundancy and Cryptanalysis human languages are redundant eg "th lrd s m shphrd shll nt wnt" letters are not equally commonly used in English E is by far the most common letter followed by T,R,N,I,O,A,S other letters like Z,J,K,Q,X are fairly rare have tables of single, double & triple letter frequencies for various languages
English Letter Frequencies (Stallings Fig 2.5) Seberry & Pieprzyk, "Cryptography - An Introduction to Computer Security", Prentice-Hall 1989, Appendix A has letter frequency graphs for 20 languages (most European & Japanese & Malay). 33
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 34
The Affine Cipher Use A 0, B 1, C 2, , Z 25 Plaintext: x P= {0,1,2, , 25} Ciphertext: y C= {0,1,2, , 25} Encryption is defined as: ek (x) = ax + b mod 26 How is decryption defined? dk(y) = (y b)/a mod 26 How do we divide modulo 26? 35
Example of Affine Ciphers Let ek(x) = 3x + 7 mod 26 Consider encrypting ANT = 0, 13, 19 Ciphertext is 7, 20, 12 = HUM Let us decrypt it H = 7 => (7-7)/3 = 0 = A U = 20 => (20-7)/3 = 13/3 =? 13 * 3-1 mod 26 M = 12 => (12-7)/3 = 5/3 =? 5 * 3-1 mod 26 3-1 ? Multiplicative Inverse of 3 in Z26? Using extended Euclidean algorithm Ref. Cryptography and Network Security (Behrouz A. Forouzan) Chapter 2: Mathematics of Cryptography 36
Polyalphabetic Ciphers Polyalphabetic substitution ciphers Improve security using multiple cipher alphabets Make cryptanalysis harder with more alphabets to guess and flatter frequency distribution Use a key to select which alphabet is used for each letter of the message Use each alphabet in turn Repeat from start after end of key is reached 37
Vigenre Cipher Simplest polyalphabetic substitution cipher Effectively multiple Caesar cipher Key is multiple letters long K = k1 k2 ... kd nth letter specifies nth alphabet to use Use each alphabet in turn Repeat from start after d letters in message Decryption simply works in reverse 38
Example of Vigenre Cipher Write the plaintext out Write the keyword repeated above it Use each key letter as a Caesar cipher key Encrypt the corresponding plaintext letter E.g. Using deceptive as a key key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ A B C D E F 0 1 2 3 4 5 N O P Q R S 13 14 15 16 17 18 G 6 T 19 H 7 U 20 I J 9 W 22 K 10 X 23 L 11 Y 24 M 12 Z 25 8 V 21 39
Security of Vigenre Cipher Have multiple ciphertext letters for each plaintext letter Hence letter frequencies are obscured But not totally lost! Start with letter frequencies See if look monoalphabetic or not E.g. 1 10 19 key: deceptivedeceptivedeceptive Letters in positions 1,10, 19, and so on are all encrypted with the same monoalphabetic cipher! Using known frequency characteristics of plaintext language to attack each monoalphabetic ciphers Solution: Increase the key size to the length of message! 40
Autokey Cipher Ideally want a key as long as the message Vigen re proposed the autokey cipher With keyword as a prefix to as much of the message as is needed to be used as key Knowing keyword can recover the first few letters Use these in turn on the rest of the message But still have frequency characteristics to attack E.g. Given deceptive as a key key: deceptivewearediscoveredsav plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA 41
One-Time Pad If a truly random key as long as the message is used, the cipher will be secure Called a One-Time pad It 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 There are problems in generation & safe distribution of key 42
Brute Force Search Always possible to simply try every key Most basic attack, proportional to key size Assume either know / recognize plaintext Time required at 106 decryptions/ s Key Size (bits) Number of Alternative Keys 232 = 4.3 109 Time required at 1 decryption/ s 231 s 32 = 35.8 minutes 2.15 milliseconds 256 = 7.2 1016 255 s 56 = 1142 years 10.01 hours 2128 = 3.4 1038 = 5.4 1024 years 5.4 1018 years 2127 s 128 2168 = 3.7 1050 = 5.9 1036 years 5.9 1030 years 2167 s 168 26! = 4 1026 2 1026 s = 6.4 1012 years 6.4 106 years 26 characters (permutation) 43
Question Assume that you have a PC that can do 106 decryption per s. You want to decrypt an algorithm that its key space/key size has 56 bits using brute force approach. So you need to in average check half of the key space. How long does it take to check half of the key space using your PC? ( s = 10-6 seconds) 256 / 2 = 255 different keys to be checked (should be decrypted) In each s you can decrypt 106 ciphertexts using 106 keys out of 255 So: How many s to decrypt using 255 keys? 255 / 106 = 36028797018.963968 s = 36028797018.963968 *10-6 ~ 36029 s 36029 s / 60 ~ 600 min 600 min / 60 ~ 10 hours 44
Transposition Ciphers Now consider classical transposition or permutation ciphers Hide the message by rearranging the letter order without altering the actual letters used. Can recognize these since they have the same frequency distribution as the original text 46
Permutation Cipher Permutation cipher Do not change the plaintext Simply shuffle the plaintext according to a known permutation (j) Different from the substitution cipher Suppose the plaintext is x = (x1,x2,x3, xm) Encryption is: ek(x) = y = (x (1),x (2),x (3), x (m)) Note that the ciphertext still consists of the same elements that were present in the plaintext 47
Example of Permutation Cipher P 1 2 3 (P) 3 1 2 C 1 2 3 -1(C) 2 3 1 More like an anagram Encrypt HOTDOG = HOT DOG Shuffling, we get THO GDO Decrypt THO GDO Shuffling, we get HOTDOG 48
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: Org message: meet me after the toga party 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 49
Remarks on Permutation Cipher Read Section 2.3 Transposition Techniques for more on permutations Permutations and substitutions are very important in modern encryption schemes Example: DES makes use of permutations Example: AES makes use of many rounds of substitutions and permutations 50
