CS461 09 Cryptography

Download
Share  Add to  Flag Embed
Uploaded from authorPOINTLite
Views:
 
Category: Entertainment
     
 
License:   All Rights Reserved

Presentation Description

No description available.

Comments

 

By: source_cod (12 month(s) ago)

send me this source_cod@yahoo.com

 

By: swtshruti (19 month(s) ago)

please let me know how 2 download tis ppt...! pleasedo help me.. shrutimicku@gmail.com

 

By: Akash_ch (20 month(s) ago)

kindly allow me to download this ppt as it will be of immense help to me.

 

By: 18mana (21 month(s) ago)

kindly allow me to download this ppt as it will be of immense help to me.

 

By: dynamicashok1 (26 month(s) ago)

PLS TELL ME HOW TO DOWNLOAD IT ITS REALY GOOD

See all

Presentation Transcript

Cryptography: 

Cryptography CS461 - Spring 2007 Nikita Borisov

Research Opportunities: 

Research Opportunities Information Trust Institute undergraduate research internship program http://www.iti.uiuc.edu/iti_funding_opportunities.html Apply by March 5

Overview: 

Overview Introduction to cryptography and cryptanalysis Historical ciphers DES and AES Stream ciphers and cipher modes

Readings: 

Readings Ch. 9 of textbook “Applied Cryptography” by Bruce Schneier Accessible description of cryptographic primitives “Handbook of Applied Cryptography” by Menezes, van Oorschot, Vanstone Dense, makes a good reference Available online http://www.cacr.math.uwaterloo.ca/hac/

Definitions: 

Definitions Cryptosystem Transforms plaintext into ciphertext using a key ciphertext unintelligible without knowledge of key Cryptography Cryptology (design of cryptosystems) + cryptanalysis (study of cryptosystems) Always go hand in hand

Warning!: 

Warning! “A little knowledge is a dangerous thing” Very true in cryptography

Historical Ciphers: 

Historical Ciphers Caesar cipher

Caesar Cipher: 

Caesar Cipher More formally: Encrypt(Letter, Key) = (Letter + Key) (mod 26) Decrypt(Letter, Key) = (Letter - Key) (mod 26) Encrypt(“NIKITA”, 3) = “QLNLWD” Decrypt(“QLNLWD”, 3) = “NIKITA”

Attacks: 

Attacks Ciphertext only attack: Recover plaintext knowing only the ciphertext Ciphertext: HSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUN

Frequency analysis: 

Frequency analysis HSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUN Find most frequent letters 4 times: L 3 times: A, H, N, P, S, U Guess: Decrypt(L) = E Key = L-E = 7 Decrypt(HSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUN, 7) = ALITT LEKNO WLEDG EISAD ANGER OUSTH ING

Brute force: 

Brute force Ciphertext = IGKYGXOYOTYKIAXK Decrypt(IGKYGXOYOTYKIAXK, 1) = HFJXFWNXNSXJHZWJ Decrypt(IGKYGXOYOTYKIAXK, 2) = GEIWEVMWMRWIGYVI Decrypt(IGKYGXOYOTYKIAXK, 3) = FDHVDULVLQVHFXUH Decrypt(IGKYGXOYOTYKIAXK, 4) = ECGUCTKUKPUGEWTG Decrypt(IGKYGXOYOTYKIAXK, 5) = DBFTBSJTJOTFDVSF Decrypt(IGKYGXOYOTYKIAXK, 6) = CAESARISINSECURE

Vigenere cipher: 

Vigenere cipher A different caesar cipher per letter MORESECURETHANCAESAR (Ciphertext) + SECRETSECRETSECRETSE (Key) = FTUWXYVZUWYBTSFSJMTW M (13) + A (19) = F (6) mod 26 O (15) + E (5) = T (20) mod 26 ...

Vigenere analysis: 

Vigenere analysis Key space? 26Length(Key) 10-20 characters to prevent brute force on modern computers Frequency analysis? Doesn’t work because of different keys

Vigenere Analysis: 

Vigenere Analysis Guess period = p Construct p frequency tables Cryptanalyze each one http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html Better yet, recover period Look for repeated n-grams

n-gram analysis: 

n-gram analysis JBEDH WKDIT ZVIRR FEVYJ VSNTY BWTEG MLGMT QNIFG LRIIN KAIXQ GEZLX YUXEC TCZDG OMBRX IOPGH WVQJL RRIIJ SPVLE DEPEW HVYYM SYBTR DXHZM WIUNU IGAYQ NHRIT VDMTY XRKXY PCTCV HJRFV IJIMA MXWLF GEJLE CTC: 59, 136 (7, 11) ED: 89, 2 (87) FG: 38, 154 (2, 4, 29) GM: 29, 32 (3) HW: 4, 74 (2,5,7) II: 82, 42 (2, 4, 8, 5) IJ: 145, 83 (2, 31) IT: 123, 8 (5, 23) JL: 157, 78 (79) LE: 158, 88 (2, 5, 7) YB: 101, 24 (7, 11) LR: 40, 79 (3,13) MT: 33, 127 (2, 47) RF: 14, 142 (2, 4, .., 128) RII: 81, 41 (2, 4, 8, 5) RI: 41,81,122 (1) RR: 13, 80 (67) TC: 137, 60 (7, 11) TY: 23, 128 (3, 5, 7) VI: 11, 144 (7, 19) VY: 17, 96 (79) XY: 133, 54 (79)

Substitution cipher: 

Substitution cipher Each letter gets mapped to another letter E.g. A -> E, B -> R, C -> Q, ... What’s the key space? 26! Cryptogram puzzles in newspapers How do you solve them?

Permutation Cipher: 

Permutation Cipher Rearrange letters instead of substituting them E.g. Plaintext = “HELLO WORLD” H W E O L R L L O D Ciphertext = “HWEOLRLLOD”

Modern Ciphers: 

Modern Ciphers Enigma Machine to encrypt German communications in WWII Consisted of plug board, 3 rotors, and reflector board Each implemented a substitution Rotors shifted after each letter, so like Vigenere, but with period of about 16,900

Enigma cryptanalysis: 

Enigma cryptanalysis Brute force out of the question 1023 keys if plugboard is known, or 10114 if unknown Known plaintext attack Learn (or guess) part of plaintext, decrypt the rest How to obtain plaintext? “Nothing to report” is a common one “eins” (1) appeared in 90% of messages Set up mines in some area, look for reports Bombe, designed by Alan Turing Automated cryptanalysis based on known plaintext and frequency analysis tests

Data Encryption Standard (DES): 

Data Encryption Standard (DES) Designed at IBM in 1975 Based on Lucifer designed by Feistel and Coppersmith Changes suggested by the NSA Standardized by NIST in 1977 Official cipher for civilian cryptography Reviewed by the NSA Combines substitutions and permutations Operates on bits

Feistel Network: 

Feistel Network Iterative structure Efficient hardware implementation Non-linear element F provides security Multiple rounds provide mixing (diffusion) between the two halves

“F” of DES: 

“F” of DES

DES Criticism: 

DES Criticism NSA involvement in DES design was criticized Allegedly, they: Made it deliberately weaker (56-bit keys) Modified S-boxes Idea is that the NSA made DES easy for them to break, but not everyone else

Differential Cryptanalysis: 

Differential Cryptanalysis Invented in 1990 by Shamir and Biham Linear encryption: E(P xor ∆) = E(P) xor E(∆) Non-linear element (S-boxes) designed to prevent this Differential characteristic E(P xor ∆) = E(P) xor ∆’ with “high” probability Obtain many pairs E(P xor ∆) and E(P) Look for statistical patterns, recover key

Chosen Plaintext: 

Chosen Plaintext Chosen plaintext attack Find encryption of particular plaintext (pairs in this case), use it to recover key / decrypt other messages Is this a practical attack? Not practical for DES 247 chosen plaintexts required! S-boxes were found to specifically resist differential attacks

Key size: 

Key size 256 not that large In 70’s, published design of a $20M machine to break DES in a day Within the NSA’s budget 1998: “Deep Crack” Built by EFF for ~$250,000 Broke DES challenge in 56 hours Other distributed projects broke other challenges NIST reaffirmed as federal standard, but Triple-DES recommended

Triple-DES: 

Triple-DES C = Encrypt(K1, Decrypt(K2, Encrypt(K3, P))) Key length = 168 bits Effective key length: 112 bits Meet in the middle attack: Pick all pairs K1, K2 and encrypt plaintext Pick all values of K3 and decrypt ciphertext Look for matches Still too slow for brute force

AES contest: 

AES contest Death of DES of imminent Triple-DES secure, but slow in software DES designed for hardware implementation NIST held a contents to find an ``Advanced Encryption Standard’’ Started in 1997, finished in 2001

AES Criteria: 

AES Criteria Requirements Symmetric block cipher Large key size: 128, 192, or 256 bits Large block size: 128 bits Desired features: Security Performance (hardware and software) Simplicity Flexibility Licensing

AES Selection Process: 

AES Selection Process 15 entrants Two conferences: Aug 1998, March 1999 Teams analyze their own and each other’s designs After 1999 conference, 5 were left standing

AES Finalists: 

AES Finalists MARS (Coppersmith, DES veteran) “Kitchen sink” cipher RC6 (Rivest) Rijndael (Rijmen, Daemen) Simple algebraic structure Serpent (Anderson, Biham, Knudsen) Twofish (Schneier, Kelsey, Whiting, Wagner, Hall, Ferguson)

AES winner: 

AES winner AES3 conference in April 2000 Winner chosen in October 2000 Rijndael was selected Basic feeling: all algorithms are “good enough” on security, but Rijndael is simple and fast AES and Rijndael now synonymous Most recent encryption standards use it

DES and AES redux: 

DES and AES redux DES kick-started the field of open cryptanalysis Closed cryptanalysis was much further ahead back in the 70’s, claim is we only recently caught up AES rejuvenated the field of cipher design Many new ideas explored NIST selection process largely praised Cipher design notoriously hard Best security assurance is peer analysis

Midterm Statistics: 

Midterm Statistics Average: 74.3, Median 77

Message Size: 

Message Size DES and AES are block ciphers Encrypt a block of 64 or 128 bits into another block of 64 or 128 bits Most messages we want to encrypt are larger than a block (some are smaller) How do we use block ciphers?

Electronic Code Book: 

Electronic Code Book Split message up into blocks Encrypt each one separately I.e. P = P1 | P2 | P3 | ... C = E(K,P1) | E(K, P2) | E(K, P3) | ... Easy but not very secure

Plaintext: 

Plaintext

Ciphertext: 

Ciphertext

Randomized Encryption: 

Randomized Encryption Block ciphers are deterministic If P1 = P2 then E(K, P1) = E(K, P2) This is undesirable for many contexts Randomized encryption: C = Encrypt(K, R, P) R is not secret, often embedded as part of C E.g.: Encrypt(K,R,P) = (R, E(K, P xor R))

Cipher Block Chaining (CBC): 

Cipher Block Chaining (CBC) Builds on randomized encryption Uses a single R per message: C1 = E(K, P1 xor R) C2 = E(K, P2 xor C1) C3 = E(K, P3 xor C2) ... R called Initialization Vector or IV

CBC Diagram: 

CBC Diagram

CBC Decryption: 

CBC Decryption

Cipher Block Chaining: 

Cipher Block Chaining Security Single bit change in plaintext affects all following bits Resilience Ciphertext error results in two corrupted blocks Synchronization Recover after losing sync with sender Parallelism Decryption only requires previous cipher block

Propagating CBC: 

Propagating CBC C1 = E(K, P1 xor IV) C2 = E(K, P2 xor P1 xor C1) C3 = E(K, P3 xor P2 xor C2) Single bit error in ciphertext propagates to all following bits Why would we want this?

Ciphertext Feedback Mode: 

Ciphertext Feedback Mode Encrypt: C1 = E(K, IV) xor P1 C2 = E(K, C1) xor P2 ... Decrypt P1 = E(K, IV) xor C1 P2 = E(K, C1) xor C2 ...

CFB diagram: 

CFB diagram

CFB decryption: 

CFB decryption

CFB: 

CFB Error propagation Plaintext bit: forever Ciphertext bit: two blocks Advantages over CBC Only use Encrypt function, never Decrypt No need to pad message

Output Feedback: 

Output Feedback Special output sequence: O1 = E(K, IV) O2 = E(K, O1) ... Encryption / decryption Ci = Pi xor Oi Pi = Ci xor Oi

OFB diagram: 

OFB diagram

OFB properties: 

OFB properties No error propagation Single bit error affects only one bit No padding required Like CFB Encryption and decryption are the same Can precompute Oi sequence Only one XOR left to encrypt Good for streaming multimedia

Stream Ciphers: 

Stream Ciphers Used to encrypt streaming data Basic operation: Keystream generator: Key,IV -> Keystream Key short, Keystream long (“infinite”) Encryption / Decryption Ciphertext = Plaintext xor Keystream Plaintext = Ciphertext xor Keystream Often very fast, esp. in hardware

LFSRs: 

LFSRs Linear Feedback Shift Register Very fast to implement in hardware Maximal period (2^n-1)

LFSR-based stream ciphers: 

LFSR-based stream ciphers Combine one or more LSFRs in a non-linear fashion Why non-linear? A5/1, A5/2 used in GSM cellphones (broken)

RC4: 

RC4 Stream cipher designed by Ron Rivest Simple, fast to implement in software Very popular Used in SSL/TLS, WEP/WPA

RC4: 

RC4 for i=0 to 255 S[i] = i j=0 for i=0 to 255 j = (j + S[i] + key[i mod keylen]) mod 256 swap(S[i],S[j]) i=j=0 while True i = i+1 mod 256 j = j + S[i] mod 256 swap(S[i],S[j]) output S[S[i]+S[j]]

Stream cipher concerns: 

Stream cipher concerns Must be very careful about choosing IV Do not want to use the same key stream to encrypt two plaintexts C1 = P1 xor Keystream C2 = P2 xor Keystream C1 xor C2 = P1 xor P2 Must worry about integrity Attacker can change: “PAY ALICE $1M” to “PAY NIKITA$1M” by flipping bits NB: Other modes don’t solve integrity either

Counter Mode: 

Counter Mode Another way to turn block cipher into stream cipher C1 = E(K, IV+1) xor P1 C2 = E(K, IV+2) xor P2 ... Completely parallelizable Random access possible Decrypt block n without computing other blocks AES-CTR is a popular choice today

One-Time Pads: 

One-Time Pads Inspiration for stream ciphers len(Key) = len(Message) Ciphertext = Plaintext xor Key Unconditionally secure Even under brute force attack Different key yields different plaintexts Used for highly secure communication Same problem as stream ciphers

For exams & homeworks: 

For exams & homeworks Define cryptography / cryptology / cryptanalysis Ciphertext only / known plaintext / chosen plaintext Understand early ciphers and how to attack them DES: what are weaknesses, what is triple-DES, meet-in-the-middle attack AES: motivation for AES, name of winner Everything from today’s lecture, except RC4 source code