DOC PREVIEW
UVA CS 588 - Two Fish on the Rijndael

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1David Evanshttp://www.cs.virginia.edu/~evansCS588: Security and PrivacyUniversity of VirginiaComputer ScienceLecture 6: Two Fish on the RijndaelThe algorithm might look haphazard, but we did everything for a reason. Nothing is in Twofish by chance. Anything in the algorithm that we couldn't justify, we removed. The result is a lean, mean algorithm that is strong and conceptually simple.Bruce Schneier17 Sept 2001 University of Virginia CS 588 2Menu• Clipper• AES Program• RC6• Blowfish• AES Winner - Rijndael17 Sept 2001 University of Virginia CS 588 3Breaking Grades File• Not in my office or any UVA computer– Do not try to break into any UVA computer• Home PC: C:\cs588\grades.txt (encrypted)– If you obtain that file, it tells you what to do next• Adelphia Cable Modem• My browser is set to disallow ActiveX, allow Java and JavaScript17 Sept 2001 University of Virginia CS 588 4Clipper• 1993 – AT&T markets secure telephony device• Law enforcement: US courts can authorize wire taps, must be able to decrypt• NSA proposes Clipper Chip– Secret algorithm (Skipjack), only implemented in hardware17 Sept 2001 University of Virginia CS 588 5Key Escrow• NSA has copy of special key, can get with a court order• Sender transmits E (M, k) || LEAF (“law enforcement agents’ field”)• Holder of special key can decrypt LEAFto find message key and decrypt message17 Sept 2001 University of Virginia CS 588 6LEAFLEAF = E ((E (k, u) || n || a), f )k = message keyu = 80-bit special key (unique to chip)n = 30-bit identifier (unique to chip)a = escrow authenticatorf = 80-bit key (same on all chips)Known by FBI217 Sept 2001 University of Virginia CS 588 7Wire Tap• FBI investigating Alice, intercepts Clipper communication• Uses f to decrypt LEAF:D (E ((E (k, u) || n || a), f )) = E (k, u) || n || a• Delivers n and court order to 2 escrow agencies, obtains u• Decrypts E (k, u) to obtain message key and decrypt message17 Sept 2001 University of Virginia CS 588 8Two Escrow Agencies• Proposal didn’t specify who (one probably NSA)• Divide u so neither one can decrypt messages on their own (even if they obtain f )One gets u ⊕ X, other gets X17 Sept 2001 University of Virginia CS 588 9Clipper Security• How do you prevent criminals from transmitting wrong LEAF?– NSA solution: put it in hardware, inspect all Clipper devices• Still vulnerable to out-of -the box device17 Sept 2001 University of Virginia CS 588 10Clipper Politics• Not widely adopted, administration backed down– Secret algorithm– Public relations disaster• Didn’t involve academic cryptographers early• Proposal was rushed, in particular hadn’t figured out who would be escrow agencies• See http://www.eff.org/pub/Privacy/Key_escrow/Clipper/• Future?: Senators have called for new Clipper-like restrictions on cryptography • Lessons learned well for AES process17 Sept 2001 University of Virginia CS 588 11AES• 1996: NIST initiates program to choose Advanced Encryption Standard to replace DES• Requests algorithm submissions: 15 • Requirements:– Secure for next 50-100 years– Performance: faster than 3DES– Support 128, 192 and 256 bit keys• Brute force search of 2128 keys at 1 Trillion keys/second would take 1019years (109* age of universe)– Must be a block cipher17 Sept 2001 University of Virginia CS 588 12AES Process• Open Design– DES: design criteria for S-boxes kept secret• Many good choices– DES: only one acceptable algorithm• Public cryptanalysis efforts before choice– Heavy involvements of academic community, leading public cryptographers• Conservative (but quick): 4 year+ process317 Sept 2001 University of Virginia CS 588 13AES Round 1• 15 submissions accepted• Weak ciphers quickly eliminated– Magenta broken at conference!• 5 finalists selected: MARS (IBM), RC6 (Rivest, et. al.), Rijndael (top Belgium cryptographers), Serpent (Anderson, Biham, Knudsen), Twofish(Schneier, et. al.)– Security v. Performance is main tradeoff• How do you measure security?– Simplicity v. Complexity• Need complexity for confusion• Need simplicity to be able to analyze and implement efficiently17 Sept 2001 University of Virginia CS 588 14Breaking a Cipher• Real World Standard– Attacker can decrypt secret messages– Reasonable amount of work, actual amount of ciphertext• “Academic” Standard– Attacker can determine something about the message– Given unlimited number of chosen plaintext -ciphertext pairs– Can perform a very large number of computations, up to, but not including, 2n, where n is the key size in bits (i.e. assume that the attacker can’t mount a brute force attack, but can get close)17 Sept 2001 University of Virginia CS 588 15AES Evaluation Criteria1. SecurityMost important, but hardest to measureResistance to cryptanalysis, randomness of output2. Cost and Implementation CharacteristicsLicensing, Computational, MemoryFlexibility (different key/block sizes), hardware implementationFrom RC5 to RC6in seven easy stepsFrom Rivest’s RC6 talk, http://www.rsasecurity.com/rsalabs/aes/17 Sept 2001 University of Virginia CS 588 17Description of RC6• RC6-w/r/b parameters:– Word size in bits: w ( 32 ) ( lg(w) = 5 )– Number of rounds: r ( 20 )– Number of key bytes: b ( 16, 24, or 32 )• Key Expansion: – Produces array S[0, … 2r + 3] of w-bit round keys.• Encryption and Decryption:– Input/Output in 32-bit registers A,B,C,D17 Sept 2001 University of Virginia CS 588 18Design Philosophy• Leverage experience with RC5: use data-dependent rotations to achieve a high level of security.• Adapt RC5 to meet AES requirements • Take advantage of a new primitive for increased security and efficiency: 32x32 multiplication, which executes quickly on modern processors, to compute rotation amounts.417 Sept 2001 University of Virginia CS 588 19Data-Dependent Rotationshgfedcba << 3cbahgfedX ⊕ X’ = ∆ XX1= X << f(X, k) X1’ = X’ << f (X’, k)Can we say anything about ∆X1 = X1⊕ X1’?Same number of bits are still different, but can’t tell which ones.<<< n means rotate left by amount in low order log2wbits of n (word size w = 32, 5 bits)17 Sept 2001 University of Virginia CS 588 20(1) Start with RC5RC5 encryption inner loop:for i = 1 to r doA = ((A ⊕ B) <<< B) + S [i](A, B) = (B, A)<<< only depends on 5 bits of BCan RC5 be strengthened by having rotation amounts depend on all the bits of B?17 Sept


View Full Document

UVA CS 588 - Two Fish on the Rijndael

Download Two Fish on the Rijndael
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Two Fish on the Rijndael and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Two Fish on the Rijndael 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?