### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Cryptography CS 4363

UTSA

GPA 3.55

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 109 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 4363 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/231400/cs-4363-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.

## Reviews for Cryptography

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Lecture 9 Confidentiality Symmetric Key Encryption Read Chapter 12 15 16 17 Shouhuai Xu CS 4363 Cryptography Spring 2007 1 Motivation CI Encryption is the very original motivation of cryptography Cl How do we encrypt a message provided that a sender and a receiver already had a common secret key 393 A strong assumption Shouhuai Xu CS 4363 Cryptography Spring 2007 Motivation cont Cl One time pad method is simple ie ciphertext plaintext XOR keyStream gt Key distribution may be too hard Cl So we need more practical methods for broader applications Shouhuai Xu CS 4363 Cryptography Spring 2007 Roadmap CI Definitions D Real life constructs building blocks Cl Real life constructs modes of operation putting building blocks together Shouhuai Xu CS 4363 Cryptography Spring 2007 What is secure communication Bob Bob Shouhuai Xu CS 4363 Cryptography Spring 2007 5 Symmetric encryption scheme Alice s processor O Shouhuai Xu CS 4363 Cryptography Spring 2007 6 Key distribution is deferred to later jv Bob Here is O Shouhuai Xu CS 4363 Cryptography Spring 2007 7 Abstracted Model Shouhuai Xu CS 4363 Cryptography Spring 2007 8 Definition Cl A symmetric encryption scheme SKES KeyGen ENC DECx 393 The key generation algorithm KeyGen is a randomized algorithm that takes as input a security parameter k and returns a string K from the key space according to its prob distribution Denote this procedure by K e KeyGen139lt 39o The encryption algorithm ENC takes as input a key K and a plaintext M e 0 1 and returns a ciphertext Ce 0 1 D J ENC might be randomized or stateful Denote this procedure by C e ENCKM Sho h 39 u CS 4363 Cryptography Spring 2007 9 bEac Definition CI A symmetric encryption scheme SKES KeyGen ENC DEC 39o KeyGen 393 ENC 39o The deterministic decryption algorithm DEC takes as input a key K and a ciphertext C e 0 1 and returns M e 0 1 D J Denote this procedure by M e DECKC Shouhuai Xu CS 4363 Cryptography Spring 2007 10 DUDE Security What it means by saying an encryption scheme is secure It should capture the envelope abstractionsemantics But what is the envelope semantics Failed attempts ie these requirements are too weak 3 Attacker cannot recover the key 3 Attack cannot recover the plaintext Why 9 Not as strong as the envelop semantics see below 393 Not capturing legitimate adversarial behaviors see below Shouhuai Xu CS 4363 Cryptography Spring 2007 11 Envelope Semantics Cl Suppose the glue and the paper are good enough CI Envelope semantics No single bit information of the enveloped content can be leaked 393 This is true even if the attacker knows that the content must be one of two strings 3 buy 100 Google shares or sell 100 Google shares gt Or equivalently O or 1 Shouhuai Xu CS 4363 Cryptography Spring 2007 12 Legitimate Attacks CI Attacker knows plaintextciphertext pairs ltM1 C1gt ltMq Cqgt But the way they are obtained makes a difference 39339 Bruteforce attack search all the possible keys until it nds one that correctly encryptdecrypt one or all the plaintextciphertext pairs Typically q 1 t Known message attack M1 Mq are not chosen by the attacker but known to it typically q gt 1 gt Does this make sense gt Insider or social en ineerin attacker Shouhuai Xu CS 4363 Cryp ography Sp mg 2007 13 Legitimate Attacks CI Attacker knows plaintextciphertext pairs ltM1 C1gt ltMq Cqgt 3 Chosen message attack M1 Mq are chosen by the attacker perhaps in an adaptive fashion q gt 1 v Chosenciphertext attack M1 Mq are chosen by the attacker and the attacker may be further allowed to ask the decryption machine to decrypt messages perhaps both are done in an adaptive fashion q gt 1 gt Does this make sense Shoul ai XLaU nCh39tim atmtography Spring 2007 14 Security Notion I INDCPA CI INDistinguishability under Chosen Plaintext Attack 393 This notion captures the envelop semantics under the premise that the adversary can only launch Qhosen Elaintext Attack 393 Mistinguishability captures that no single bit information about the enveloped content is leaked Shouhuai Xu CS 4363 Cryptography Spring 2007 15 IN DCPA p ltM1O M11gt C1 ENCKM1b O 1 ltMq Mq gt Cq ENCKqu I bet b Ok you win Sorry b t b Smartest cracker Shouhuai Xu CS 4363 Cryptography Spring 2007 16 Cryptographer Pr INDCPA p ltM1O M11gt C1 ENCKM1b O 1 ltMq Mq gt Cq ENCKqu I bet b Ok you win 69 e 12 negk 12 negk Shouhuai Xu CS 4363 Cryptography Spring 2007 ENCKLR oracle CI In order to formalize security we adopt the following oracle Oracle ENCKLRMO M b b e 0 1 M0 M1 eO 1 C e ENCKMb return C CI This oracle allows us to capture the chosenplaintext attack 3 Good guy is the oracle Shouhuai Xu CS 4363 Cryptography Spring 2007 Security Notion I INDCPA Cl INDCPA Let SKESKeyGen ENC DEC be a symmetric encryption scheme b ER 0 1 and A be an algorithm that has access to the encryption oracle Consider two worlds World 0 b 0 World 1 b 1 K eRO1k K eRO1k b e AENCKLRy0o b lt AENCKLRm1o return b return b We say SKES is an INDCPA scheme if Prb OGame is in world 0 Prb OGame is in world 1 CS 4363 Cryptography Spring 2007 19 Bonus credit Cl Show the above de nition is equivalent to Prb 1 Game is in world 1 Prb 1Game is in world O neglk Prb 1Game is in world 1 Prb OlGame is in world 1 neglk Prb OGame is in world 0 Prb 1Game is in world O neglk Pr attacker makes correct bet O5 neglk Shouhuai Xu CS 4363 Cryptography Spring 2007 20 Security Notion II INDCCA CI INDistinguishability under Chosen Ciphertext Attack 3 This notion captures the envelop semantics when the adversary can launch Qhosen Qiphertext Attack while having access to a decryption oracle 393 Mistinguishability captures no single bit information about the enveloped content is leaked Shouhuai Xu CS 4363 Cryptography Spring 2007 21 INDCCA p ltM1O M11gt R O1k C1 ENCKM1b or DECKC1 ltMq0 Mq1gt or CltWgt Cq ENCKqu or DECKCltWgt A lt I bet b Ok you win Sorry b t b under premise 01 CW 0 C1 Cq 1 Cryptographer Smartest cracker Shouhuai Xu CS 4363 Cryptography Spring 2007 22 INDCCA p ltM1o M11gt or C0 K R 01A C1 ENCKM1b or DECKC Pr ltMq0 Mq1gt or CltWgt Cq ENCKqu or DECKCltWgt A lt I bet b Ok you win under premise 171 CltWgt m C1 Cq I 4 lt e 12 negk 12 negk Shouhuai Xu CS 4363 Cryptography Spring 2007 23 ENCKLR and DECK Oracles CI In order to formalize security we adopt the following oracle Oracle ENCKLRMO M b b e 0 1 M0 M1 eO 1 C e ENCKMb return C CI Further adopt DECK oracle for capturing CCA attack Oracle DECKC M e DECKC return M Shouhuai Xu CS 4363 Cryptography Spring 2007 24 CI Security Notion II INDCCA INDCCA Let SKESKeyGen ENC DEC be a symmetric encryption scheme b e R 0 1 and A be an algorithm that has access to the above two oracles Consider two worlds World 0 World 1 b0 b1 KeRO1k KeRO1k b e AENCKLRlt0 DECK b e AENCKLRlt1 DECK return b return b We say SKES is an INDCCA scheme ie INDCCAZ secure if Prb 0 Game is in world 0 Prb OGame is in world 1 neglk under the restriction that any ciphertext fed to DECK is not returned by querycs 4363 Cryptography Spring 2007 25 Bonus credit Cl Show the above de nition is equivalent to Prb 1 Game is in world 1 Prb 1Game is in world O neglk Prb 1Game is in world 1 Prb OlGame is in world 1 neglk Prb OGame is in world 0 Prb 1Game is in world O neglk Pr attacker makes correct bet O5 neglk Shouhuai Xu CS 4363 Cryptography Spring 2007 26 Relationship between CPA and CCA CI If SKESKeyGen ENC DEC is IND CCA then it must be INDCPA CI Why INDCCA is relevant o CPA does not capture launch time attack during which the attacker has temporary access to the decryption box o CPA does not capture the immunity to malleability that an attacker could output C ENCKM1 from C ENCKM gt Relevant to applications such as e auction Shouhuai Xu CS 4363 Cryptography Spring 2007 27 Roadmap Cl De nitions D Real life constructs building blocks CI Real life constructs modes of operation putting building blocks together Shouhuai Xu CS 4363 Cryptography Spring 2007 28 Reallife Constructs Cl How can we construct SKES for reallife applications 3 How to deal with 0 1 Cl Approach I Stream cipher 9 0 RC4 gt RC4 is not predecessor of RC5 and RC6 block ciphers Cl Approach II Block cipher 9 o Construct encryption for 0 1 out of encryption for 0 1k 9 o We need to know symmetric ciphers on 0 1ksuch as DES AES Shouhuai Xu CS 4363 Cryptography Spring 2007 29 Approach I Stream ciphers Cl Suppose a sender and a receiver share a short secret from which they can magically produce a very long pseudorandom strings Cl Can we emulate one time pad 3 V reless Encryption Protocol WEP was broken 3 New result shows that RC4 streams does not even pass some statistical test Shouhuai Xu CS 4363 Cryptography Spring 2007 30 Model of stream ciphers k k sender 1 1 receiver k2 k2 k3 k3 1010110 1010110 m1101001 c0111111 m1101001 or w Finite state machine with output filter Keys determine state update k1 initial state k2 and output filter k3 Shouhuai Xu CS 4363 Cryptography Spring 2007 31 Model of stream ciphers El We have ci mi Gr ki meaning mi ci Gr ki where v m m0 m1 are the plaintex bits 3 k k0 k1 are the keystream bits 9 v c c0 c1 are the ciphertext bits Cl Characterization o Encryptiondecryption can be very fast gt 50MBs on PC o No error propagation one error in ciphertext only affect that bit v No integrity protection against message manipulation we need Message Authentication Code o Senderreceiver synchronization is crucial o Deterministic same key used twice gives same keystream Shouhuai Xu CS 4363 Cryptography Spring 2007 32 Model of stream ciphers Cl What kind of finite state machines are good for stream ciphers o The resulting keystream must look random ie behave like pseudo random functions and thus unpredictable gt Pass known statistical independence test does not provide any assurance v Cannot have any significant correlation between key bits and keystream bits v Keystream bits should be very efficient to generate Cl Many stream ciphers are based on nonlinear combinations of Linear Feedback Shift Register LFSR Shouhuai Xu CS 4363 Cryptography Spring 2007 33 Approach II Block ciphers CI Philosophy Since we do not know exactly how long messages will need to be encrypted may be we can divide a possibly long message into blocks of xed length 393 That is block ciphers are building blocks used to construct symmetric key encryption schemes Or block ciphers are symmetric key encryption schemes but only for encrypting xedlength messages CI So that we can encrypt a message via somekind of block byblock encryption Shouhuai Xu CS 4363 Cryptography Spring 2007 34 Approach II Block ciphers Cl This is a good idea because it is relatively easier to investigate the mathematical property of block ciphers dealing with messages of xed length Cl Famous examples DES AES Shouhuai Xu CS 4363 Cryptography Spring 2007 35 Abstracted model fixed message space Shouhuai Xu CS 4363 Cryptography Spring 2007 36 Model of block ciphers m 128 k k sender receiver m1101001 ENC c1101101 DEC m1101001 Cl Theoretic security model pseudorandom functions 3 However design is still an art eg design of AES Cl One would wonder whether one can get some hint from many plaintext pairs namely m1 c1 mq cq 3 Nothing can be learned using polynomialtime algorithms eg machine learning data mining pattern recognition or any AI algorithms 3 Indeed crypto has been used to prove impossibility results in machine learning theory ie many things cannot be machinelearned Shouhuai Xu CS 4363 Cryptography Spring 2007 37 Techniques used in block ciphers Transportation permute a block of plaintext Substitution each character is replaced by other symbol Cl Repeated use ofa round function which combines transportation and substitution v Feistel cipher input divided into two halves right half becomes left half left half is XORed with function of the right half and key V Substitutionpermutation network input divided in blocks which are encrypted with substitution cipher blocks are mixed using permutation and roundkey is XORed Cl It is this technique assured much more than classic ciphers did Shouhuai Xu CS 4363 Cryptography Spring 2007 38 Two types of round functions I I I I I I I I I Feistel cipher SP network You can treat them as the architectures of block ciphers you can define your own S and P Shouhuai Xu CS 4363 Cryptography Spring 2007 39 Iteration how to bind the rounds CI An iterated block cipher involves repeated use of a round function which takes as input an n bit block and outputs an n bit block 393 Each round uses a subkey 3 For every subkey the round function is invertible to make decryption possible CI Intuitively the more rounds the encryption shuffles better ie more secure Shouhuai Xu CS 4363 Cryptography Spring 2007 40 Data Encryption Standard DES CI Published in 1977 as US federal standard 393 Based on IBM s Lucifer but amended by NSA 6 56bit key gtlt 64bit plaintext block a 64bit ciphertext block 393 V dely deployed as international banking standard CI Designed based on Feistel Cipher 393 16round most analyzed crypto algorithm v DES is not a group math properties CI Reviewed every 5 years now retired Shouhuai Xu CS 4363 Cryptography Spring 2007 41 Known weaknesses of DES Cl Secret design criteria IBM were requested by NSA not to publish the design criteria latter reinvented as differential cryptanalysis El Weak keys four keys for which ENCkENCkmm for any m meaning DECk ENCk 6 Should be avoided El Semiweak keys 12 keys 6 pairs for which ENCk1ENCk2mm for any m meaning DECk2 ENCk1 6 Should be avoided CI The S boxes are not random Shouhuai Xu CS 4363 Cryptography Spring 2007 42 Attacks against DES Cl Exhaustive attack ie bruteforce us not entirely infeasible 3 56bit keys means 255 complexity on average gt gt gt gt Thousands of years in the 70 s 1997 90 days with 1400078000 Internet computers Jan 1998 39 days with Internet computers July 1998 an 210000 search machines called deep crack was built Found a key within 56 hours Cl More sophisticated attacks Shouhuai Xu CS 4363 Cryptography Spring 2007 43 Attacks against DES Exhaustive attack ie bruteforce us not entirely infeasible More sophisticated attacks o Differential cryptanalysis 247 chosen plaintexts early 90 s by BihamShamir o Linear cryptanalysis 243 known plaintexts o Statistical cryptanalysis 243 known plaintext 1996 Vaudenay Shouhuai Xu CS 4363 Cryptography Spring 2007 44 Triple DES early days caution CI Motivation 56bit keys are too short use 2 k1k3 or 3 keys quot plaintext k1 k2 k3 ciphertext I DESquot1 DES DESquot1 Shouhuai Xu CS 4363 Cryptography Spring 2007 45 I3 AES new standard 1997 NIST call for proposals for replacing DES O 09 128192256 bit keys gtlt 128bit plaintext block gt 128bit ciphertext block 6 09 Selection criteria gt Security gt costefficiency software hardware smartcard intellectual property V The designers had to decide which target platform to optimize for Pentium Pentium II 64bit processors 16bit processors 8bit processors Smartcards gt Algorithm characterizations flexibility simplicity elegance gt Not by exportability nationality Attracted 15 submissions Shouhuai Xu CS 4363 Cryptography Spring 2007 46 Shouhuai Xu AES new standard Five finalists from 15 submissions 3 Mars IBM 6 RC6 RivestRSA V Rijndael DaemenRijmen Belgium v Serpent AndersonBihamKnudsen v Twofish Counterpane CS 4363 Cryptography Spring 2007 47 Shouhuai Xu AES new standard Mars IBM v Extended Feistel structure v Two types of rounds v Uses multiplications and variable rotations v Hardly fits into smartcards v A complex round function v Attacks succeed up to 21 rounds out of 32 CS 4363 Cryptography Spring 2007 48 Shouhuai Xu AES new standard RC6 RivestRSA v Fast o Compact code o Elegant easy to remember 639 Based on RC5 o Relies on multiplications and variable rotations v Hardly fits into smartcards o Attacks succeed up to 15 rounds out of 20 small security margins CS 4363 Cryptography Spring 2007 49 AES new standard CI Rijndael DaemenRijmen Belgium 0 Very fast and ef cient in software and hardware 0 0 0 Based on square 0 0 SP network structure 0 00 Key size dependent number of rounds 101214 0 00 Attacks succeed up to 8 rounds out of 10 Shouhuai Xu CS 4363 Cryptography Spring 2007 50 Shouhuai Xu AES new standard Serpent AndersonBihamKnudsen o Software implementation is slowest among the finalist though faster then DES o Fastest in hardware o SP network structure with bitslice optimization o attacks succeed up to 9 rounds out of 32 largest security margins among the finalist CS 4363 Cryptography Spring 2007 51 Shouhuai Xu AES new standard Twofish Counterpane v Fast v Feistel structure v Highly optimized for Pentium v Smartcard friendly v Keydependent Sboxes v Attacks succeed up to 8 rounds out of 16 CS 4363 Cryptography Spring 2007 52 Should select multiple AES ciphers El Pros 393 Backup for case of a total break 39o Gain both speed and security by selecting two algorithms a very fast cipher and a very secure but slower cipher o39 Backup against intellectual property attacks Shouhuai Xu CS 4363 Cryptography Spring 2007 53 Should select multiple AES ciphers CI Cons 39o VWI both have to be implemented in each chip v Which will be actually used 39o If a backup in which conditions will it be used 39o How will the chip know which should be used 39o If only one is implemented in each chip better to have the same one in all chips Shouhuai Xu CS 4363 Cryptography Spring 2007 54 Should select multiple AES ciphers Cl At AES3 NIST made a poll on o Which nalists should be selected as AES o How many should be selected o Which combinations to consider o Which must not be selected Shouhuai Xu CS 4363 Cryptography Spring 2007 55 Should select multiple AES ciphers Cl At AES3 NIST made a poll on O 0 Which nalists should be selected as AES gt Rijndael gt Serpent gt mush less votes 0 00 How many should be selected gt one o Which combinations to consider o Which must not be selected Shouhuai Xu CS 4363 Cryptography Spring 2007 56 The AES decision The winner Rijndael See httpwwwnistgovaes for reference implementations etc Shouhuai Xu CS 4363 Cryptography Spring 2007 57 Rijndael highlevel pseudo code Shouhuai Xu AddRoundKeyS K0 FOR i 1 to 9 SubBytesS ShiftRowsS MixColumnsS AddRoundKeyS Ki SubBytesS ShiftRowsS AddRoundKeyS K10 CS 4363 Cryptography Spring 2007 58 Roadmap Cl De nitions l3 Real life constructs building blocks Cl Real life constructs modes of operation putting building blocks together Shouhuai Xu CS 4363 Cryptography Spring 2007 59 How to construct symmetric encryption schemes out of block ciphers Cl We have studied the definitions of secure symmetric key encryption schemes what we needed for encrypting reallife arbitrary long messages Cl We have studied the reallife constructions of block ciphers that can encrypt fixedlength messages Cl How should we utilize block ciphers to encrypt arbitrary long messages 9 v Given a blockcpiher Enc Dec how to encrypt a message m with key k 9 o There are several methods only consider ECB and CBC Shouhuai Xu CS 4363 Cryptography Spring 2007 60 Electronic Code Book ECB mode 128 bit k EnVC k En C L4 EEC l BIcok cipher Enc ownicni C L IEe L4 Dec Blcokcipher Dec Shouhuai Xu CS 4363 Cryptography Spring 2007 61 Electronic Code Book ECB mode Input message m and key k block cipher with Enc encrypting t bit blocks ENC Algorithm for the resulting symmetric key encryption scheme Divide m into n blocks of t bit long m1 mn last block padded if needed FOR i 1 to n ci Enck mi note mi m implies ci cj ciphertext c c1 cn DEC Algorithm for the resulting symmetric key encryption scheme Divide c into n blocks of t bit long c1 cn FOR i 1 to n mi Deck ci note ci cj implies mi mj ciphertext m m1 mn after de padding if needed Shouhuai Xu CS 4363 Cryptography Spring 2007 62 Electronic Code Book ECB mode Cl Characterizing ECB 0 o Blocks are independent thus does not hide patterns or repetitions 3 Error does not propagate to other blocks 39339 Susceptible to block replay attack Shouhuai Xu CS 4363 Cryptography Spring 2007 63 ECB insufficiency example credit John Malone Lee and Nigel Smart ECB encryption Plaintext original picture Ciphertext picture So ECB should not be used in practice Shouhuai Xu CS 4363 Cryptography Spring 2007 64 Cipher Block Chaining CBC mode 128 bit m2i m m1 mn Initial Vector Eb Cn i x9 k En c k E 39 I nc Blcokcipher Enc chi Initial Vector Eb k V Dec Blcokcipher m m1 Shouhuai Xu lt 9 lt9 a i m i i m i CS 4363 Cryptography Spring 2007 65 CBC mode Input message m and key k block cipher with Enc encrypting t bit blocks ENC Algorithm for the resulting symmetric key encryption scheme Divide m into n blocks of t bit long m1 mn last block padded if needed c0 initial vector FOR i 1 to n ci Enck mi 69 CH note mi mj does not imply ci cj ciphertext c c1 cn DEC Algorithm for the resulting symmetric key encryption scheme Divide c into n blocks of t bit long c1 cn c0 initial vector FOR i 1 to n mi Deck ci 69 ci1 note ci cj does not imply mi mj Shouhoip39lvaitext m m1 mamMnWifWamn 66 CBC mode Cl Characterizing CBC v Ciphertext depends on all previous plaintext blocks o Different IV hides patterns and repetitions o Error in one block propagates to all following blocks v Most widely deployed in reallife IPsec SSL etc Shouhuai Xu CS 4363 Cryptography Spring 2007 67 CBC sufficiency example credit John Malone Lee and Nigel Smart CBC encryption Plaintext original picture Ciphertext picture CBC hides well but does indicate secret communication is in use to hide this fact we need steganography advanced crypto can do it Shouhuai Xu CS 4363 Cryptography Spring 2007 68 Summary Cl For one time pad and stream ciphers synchronization is a critical issue CI For block ciphers chainingthe blocks together is a critical issue 3 How to encrypt arbitrary long messages with a block cipher that encrypts only xedlength messages Shouhuai Xu CS 4363 Cryptography Spring 2007 69 Lecture 10 Data Integrity Message Authentication Schemes Sh39ouhuai Xu CS4363 Cryptography Spring 2007 Roadmap El Problem Statement CI Definition El Constructions Cl Remarks sh o u h uaj xu 543 6 3 Cryptog rap h y Sp r i n g 207 Problem Statement Cl Suppose you are communicating via any channel the air the wire whispering with your friend Cl Sure you want what your friend received is exactly what you sent CI Yeah this is trivially ensured in the face to face case Cl Now we ask the question what if the channel is under the control of some bad guy Shouhuai Xu CS4363 Cryptography Spring 2007 3 Sweet If Channel Is Secure I like you Sh39ouhuai Xu CS4363 Cryptography Spring 2007 4 What If There Is a Bad Guy The bad guy controls the channel maninthe middle attack Shouhuai Xu CS4363 Cryptography Spring 2007 5 How We Get There Cl So we need a technical mechanism to ensure that the output of the channel is the same as the input to it and detectable othenNise CI How we achieve this in the physical world Cl For 103 years people knew how to use sealed envelope Shouhuai Xu CS4363 Cryptography Spring 2007 6 Not It s Clear What We Want CI Message authentication scheme can be viewed as the analogy of sealed envelope in the physical world CI That is emulating an envelope so that nobody can tamper with the content 3 Of course we ignore con dentiality for simplicity 3 You may thinkthe envelope is transparent But Indeed Shouhuai Xu CS4363 Cryptography Spring 2007 7 For Your Curiosity D A classic part 01 cryptography is Was 393 nobody can tamper with the content message authentication 339 Nobody can peep the content encryption not that simple it took many years to understand what it is Shouhuai Xu CS4363 Cryptography Spring 2007 8 Warning Encryption does not provide data integrity 0 3 Pro argument f like you is encrypted how can the adversary change the ciphertext to a new one corresponding to the plaintext I dislike you 393 This has been incorrectly understood by many people for many years So do not commit the same mistake Shouhuai Xu CS4363 Cryptography Spring 2007 9 Sh 390 u h ua j Xu Roadmap CI Problem Statement El Definition El Constructions Cl Remarks GSA363 Cryptography Spring 27 10 How Do We Specify a MAS Cl Let s recall what happens in the physical world gt Before you write the rst letter to your friend V You two agree on a handwriting style only you know gt Before you mail you letter in a transparent envelope you knew how you friend will verify it V You already had a tagging algorithm in your mind gt When your friend receives your mail heshe knows how to verify if the letter is from you because V Heshe had a veri cation algorithm in mind Shouhuai Xu CS4363 Cryptography Spring 2007 11 How Do We Specify a MAS Cl Let s recall what happens in the physical world gt Before you write the rst letter to your friend V Key Generation and Distribution gt Before you mail you letter in a transparent envelope you knew how you friend will verify it V Tagging gt When your friend receives your mail heshe knows how to verify if the letter is from you because V Veri cation Shouhuai Xu CS4363 Cryptography Spring 2007 12 Definition A message authentication scheme MAS KeyGen Tag Ver gt KeyGen is a randomized algorithm that returns a key k That is k e KeyGenSecurityParameter gt Tag is an algorithm that takes input k and a message m and return a tag 8 This algorithm may be probabilistic That is 8 e Tagkm We also denote it by 5 e Tagkm gt Ver is a deterministic algorithm that takes as input the key k a message m and a tag 5 and returns a bit validinvalid That is Verkm5 returns valid or invalid We also denote it by Ver m5 Shouhl ai Xu CS4363 Cryptography Spring 2007 13 Disclaimer Cl Message Authentication Scheme MAS and Message Authentication Code MAC are interchangeable Cl In the context of MAS tag generation algorithm is typically the same as the tag veri cation algorithm Moreover the keys are the same Shouhuai Xu CS4363 Cryptography Spring 2007 14 Security Cl We have specified the syntax of message authentication schemes Cl What is the semantics In particular gt What that means when we say a message authentication scheme is secure Shouhuai Xu CS4363 Cryptography Spring 2007 15 Security CI Intuition O fthe key is leaked then an adversary can arbitrarily forge message authentication tags gt So we have to ensure that seeing polynomial many tags does not enable the adversary to recover the key because gt we cannot afford to not allow the adversary to see the genuine authentication tags because the network is open Shouhuai Xu CS4363 Cryptography Spring 2007 16 Security CI De nition 0 we say a message authentication scheme is secure if seeing polynomial many authentication tags does not enable the adversary to recover the message authentication key Cl Is this de nition good enough Shouhuai Xu CS4363 Cryptography Spring 2007 17 Security Cl What if the adversary can forge say a single genuine authentication tag eg even though the adversary is still unable to get the key Cl So we need to refine the definition Shouhuai Xu CS4363 Cryptography Spring 2007 18 Security Cl Intuition 1 Seeing polynomial many genuine authentication tags still does not enable the adversary to generate a single genuine authentication tag on a different message Cl Is this de nition good enough Shouhuai Xu CS4363 Cryptography Spring 2007 19 Security CI What if the genuine authentication tags are for messages chosen by the adversary Cl Lunch time attack the operator is out for lunch the adversary has physical access to the message authentication machine to generate message authentication tags for the messages he prepared in the morning Cl So we need to re ne the de nition Shouhuai Xu CS4363 Cryptography Spring 2007 20 Security CI Intuition 2 Security means that seeing polynomial many genuine authentication tags on messages chosen by the adversary does not enable the adversary to generate even a single genuine authentication tag on a new message Cl Is this de nition good enough Shouhuai Xu CS4363 Cryptography Spring 2007 21 Security Cl What if the adversary can choose the next message based on the state information or history of the output of the message authentication machine Cl This is indeed called adaptive chosen message attack Shouhuai Xu CS4363 Cryptography Spring 2007 22 Security Cl Intuition 3 Security means that seeing polynomial many message authentication tags on messages adaptively chosen by an adversary does not enable the adversary to generate even a single genuine authentication tag on a new message Shouhuai Xu CS4363 Cryptography Spring 2007 23 Security Cl Intuition 35 Is the above definition enough Cl To the best of our knowledge there is currently no more sophisticated definition Cl But if you can have a more sophisticated yet meaningful one then this lecture is paid off Shouhuai Xu CS4363 Cryptography Spring 2007 24 Now We Are Ready to Cl Combine the above discussions together to get a fullfledged version of the definition of message authentication schemes Sh 390 u h u39a39j Xu CS43 6 3 Cryptog rap h y Sp r i n g 207 25 Definition syntax A message authentication scheme MAS KeyGen Tag Ver gt KeyGen is a randomized algorithm that returns a key k That is K e KeyGenSecurityParameter gt Tag is an algorithm that takes input k and a message m and return a tag 8 This algorithm may be probabilistic That is 8 e TagKm We also denote it by 5 e TagKm gt Ver is a deterministic algorithm that takes as input the key K a message m and a tag 5 and returns a bit validinvalid That is VerKm5 returns valid or invalid We also denote it by Ver m5 Shouhl ai Xu CS4363 Cryptography Spring 2007 26 Definition semantics Requirements on a message authentication scheme MAS KeyGen Tag Ver where gt Correctness for any m e MessageSpace we have VerKm 8 TagKm 1 gt Security unforgeability under adaptive chosen message attack Shouhuai Xu CS4363 Cryptography Spring 2007 27 Definition semantics K lt Ke Gen k y m1 TagKm1 1 mn1 TagKmn1 t quot if 391 i Ok you Wln as VerK TagKmn11 a subject to mn1 m1 m2 mn Challengw negligiblesecurityparameter k Kattacker Shouhuai Xu CS4363 Cryptography Spring 2007 28 Sh 390 u h ua j Xu Roadmap Cl Problem Statement Cl Definition Cl Constructions Cl Remarks GSA363 Cryptography Spring 27 2939 Constructions PRFCBC MACS BellareKilian Rogaway Crypto 94 XOR MACS Bellare GuerinRogaway Crypto 95 m I ll It I E 5 SI 1 Universal Hash based MACs BIack HaleviKrawczyk KrovetzRogaway Crypto 99 Shouhuai Xu CS4363 Cryptography Spring 2007 30 Constructions cont Cl Can we use keyed hash functions such as MD5km and SHA1km directly as a message authentication code 3 Currently nobody knows and no positive evidence Cl But evidences do show that HMAC is good 3 Remains to be true even if MD5ISHA1 is not collision resistant because a weaker property suf ces HMAC Shouhuai Xu CS4363 Cryptography Spring 2007 31 HMAC CI HMAC BellareCanettiKrawczyk Crypto 96 why hash gt faster than block ciphers in software implementation gt software implementations are widely available gt not subject to export restriction Cl HMAC is now IETF mandatory MAS Shouhuai Xu CS4363 Cryptography Spring 2007 32 HMAC Cl Suppose H is a good hash function eg MD5 with 128bit output SHA 1 with 160bit output Cl ipad the byte 0x36 repeated 64 times Cl opad the byte OXSC repeated 64 times Cl k is the message authentication key El HMACkm Hk 6r opad Hk 6r ipad m Shouhuai Xu CS4363 Cryptography Spring 2007 33 HMAC Append zeros to the end of k to create a 64 bytes string XOR the 64 byte string computed in step 1 with ipad Append m to the 64 bytes string resulting from step 2 Apply H to the stream generated in step 3 XOR the 64 byte string computed in step 1 with opad Append the in step 4 to the 64 byte result in step 5 Apply H to the output in step 6 and output the result Shouhuai Xu CS4363 Cryptography Spring 2007 34 HMAC The recommended length of the key is at least I bits where l is the length of the output of the hash function ie l128 for MDS and l160 for SHA 1 A longer key does not add signi cantly to the security of HMAC HMAC allows truncation of the nal output to say 80 bits Shouhuai Xu CS4363 Cryptography Spring 2007 35 HMAC Security Security of HMAC can be justi ed given some reasonable assumptions about the strength of the underlying H Assume only that H has a certain kind of weak collision freeness and some limited unpredictability Details may be covered in advanced cryptography course Shouhuai Xu CS4363 Cryptography Spring 2007 36 Roadmap CI Problem Statement CI Definition El Constructions El Remarks shouhu aj Xu 54363 Cryptograp hyslor ing 2 7 3739 Applications CI FriendOr Foe CI TESLA multicast authentication CI As a building block in advanced protocols CI nd more that is your contribution Shouhuai Xu CS4363 Cryptography Spring 2007 38 What MAC Isn t When Alice and Bob rare in honeymoon Bob said I will give all my property to Alice if we divorce someday The statement is authenticated using a message authentication code with a key known to both Alice and Bob Alice knowing some crypto is happy and keeps it in a safe Life is really wonderful many days passed sweet Shouhuai Xu CS4363 Cryptography Spring 2007 39 What MAC Isn t cont CI Unfortunately bad days come up CI Divorce is on agenda Alice presents the safe to ajudge CI Can Alice convince thejudge that Bob did make the promise Cl No way Alice could have done it herself Shouhuai Xu CS4363 Cryptography Spring 2007 40

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.