Popular in Course
Popular in Informatics
This 0 page Class Notes was uploaded by Mckayla Harvey on Sunday November 1, 2015. The Class Notes belongs to INFO at Indiana University taught by Xiaofeng Wang in Fall. Since its upload, it has received 19 views. For similar materials see /class/233419/info-indiana-university in Informatics at Indiana University.
Reviews for I 520
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/01/15
lndiam Unh39miw Schml of informatics Modern Cryptography Dr XiaoFeng Wang lndiam Unh39miw Schml of informatics Modern Cryptography Concepts Dr XiaoFeng Wang lndiam in rmity School of informatics Adversary Bob Reality Communications via an adversary Alice Bob and Adversary are usually assumed to have only polynomial computing capabilities Dr XiaoFeng Wang Indiana in rmity School of informatics Cryptographic Security Modern cryptography is based on exploiting a gap between gt Ef cient algorithms for Alice and Bob to establish a secure communication channel gt Computationally infeasible for the adversary to compromise that channel Dr XiaoFeng Wang lndiana Unhem39ty School of informatics Polynomial and Exponential Functions A simple and informal description gt A polynomial function is a function whose variable has constant exponents gt Examples fxxl fxx2 xx3 gt An exponential function has a variable as exponent gt Examples x2x fxle gt An exponential function changes much faster than a polynomial function Dr XiaoFeng Wang lndiam Unh39miw Schml of informatics Comparison Dr XiaoFeng Wang lndiam Unnr39emiw School of informatics An Easy Problem An easy problem solvable in polynomial steps gt Given a sequence of integers Sa1 a2 an nd out if an integer a is in S gt How many steps are needed for a bruteforce search gt A bruteforce search takes n2 steps on average gt Better approaches need about logn steps Dr XiaoFeng Wang lndiam Unhr39am39w Schml of informatics A Easy Problem cont d S15 13 9 16 12 19 6 825 Problem size n9 8 S6 8 9 12 13 15 16 1925 Problem size n9 5 Dr XiaoFeng Wang Indiana in rmity School of informatics A Hard Problem A hard problem gt Given a number S nd out a am ati from S st sa at2 ati gt A bruteforce search takes 2 391 steps which cannot be done with a player having polynomial computing capabilities gt Do not know if there exists a polynomialstep solution Dr XiaoFeng Wang Indiana University Schml of informatics A Hard Problem cont d For example S15 13 9 16 12 19 6 8 25 Given a number 39 find out the numbers in 8 whose sum equals to 39 Bruteforce method takes 29391 steps on average Dr XiaoFeng Wang Indiana Link39smil School of informatics Modern Cryptography Cryptographic Hash Function and Message Authentication Code Dr XiaoFeng Wang lndiana in rmity School of informatics Oneway Function A fundamental concept of modern cryptography Definition A function f X gtYis caled oneway if given XEX computing fX is easy and given ye Y computing X such that yfX is hard Easy here means that computation will be completed in polynomial time Hard means that a polynomial player has only negligible probability to find out the right X Dr XiaoFeng Wang lndiam mm131W SChOOl of informatics Oneway Function cont d Oneway function Dr XiaoFeng Wang Indiana University School of informatics A Candidate Oneway Function A sequence of integers Sa1 a2 an An input V6Ct0l39FV1 v2 vn where vO or 1 fx a1 v1 a2 v2 an vn is oneway in general This is the famous Knapsack problem homework Dr XiaoFeng Wang Indiana Juniemin School of informatics A Candidate Oneway Function cont d For example S15 13 9 16 12 19 6 8 25 xO 1 00 0 00 10 fX 138 21 This is easy Now given fX 27 can you find X for me Why candidate gt There is no proof that the function is oneway Dr XiaoFeng Wang Indiana University School of informatics Oneway Hash Functions Arbitrary length input gt fixed length output gt h HM h has length m Given M easy to compute h Preimage resistance given h hard to compute M 2ndpreimage resistance Given M hard to find M M st HM HM Examples SHA MD4 MD5gt recently cracked by cryptographers Dr XiaoFeng Wang lndiam Juniemil Schml of informatics Oneway Hash Function V Oneway function Oneway function Dr XiaoFeng Wang lndiam llnn39asiW School of informatics A Security Problem How could Alice know M coming from Bob How could Alice know that no one except Bob changes M message Dr XiaoFeng Wang lndiam mmmil School of informatics Message Authentication Code MAC tFKM r M t Ii Alice Dr XiaoFeng Wang lndiana Univetsity School of informatics Message Authentication Code MAC A message authentication code scheme is a triple ltGTVgt of efficiently computable functions gt G outputs a secret key K gt T takes a key K and message M as input and outputs a tag t lt TKM gt Vtakes 1V1 tag t and key K as input and outputs a binary outcome 9 lt VKt Where 91 valid or 0 invalid gt Without knowing K it is hard computationally infeasible to generate tfor M st VKUWJFI Dr XiaoFeng Wang lndiana Univem39w School of informatics Message Authentication Code cont d J Oneway function Oneway function Dr XiaoFeng Wang Indiana University School of informatics Hashbased MAC HMAC Intuitively we can construct HMAC as follows gtt lt TKMHKMHKM gt b anew tHKM In practice HMAC is constructed as follows gt T KMHK A HK B M where A is built by repeating the byte 0X36 and B by repeating OXSC gt The reason is to make collision nding even more dif cult Dr XiaoFeng Wang Indiana in rmity School of informatics Friendor Foe Identification tHMA CK C 3 tR RHMACK C R Friend aircraft knows K so it can produce the correct response Dr XiaoFeng Wang Indiana Jim39smil Schml of informatics Modern Cryptography Publickey Crytosystems and Digital Signatures Dr XiaoFeng Wang lndiana inurenatty School of informatics Trapdoor Oneway Function Another cornerstone concept of modern cryptography Definition A trapdoor oneway function f is a oneway function with the additional property that given some extra information caled trapdoor information it becomes easy to nd X from fX Dr XiaoFeng Wang lndimm in rmity Schml of informatics Trapdoor oneway hash function Dr XiaoFeng Wang lndiam in rmity School of informatics Basic Basic Number Theory Concepts Primes and composites gt A prime is a number greater than 1 and is divisible only by itself and l gt For example 2 3 5 7 11 gt A number that is not a prime is a composite Dr XiaoFeng Wang Indiana in rmity School of informatics Basic Basic Number Theory Concepts cont d Modular arithmetic gt a 9 mod n means that n divides a b gt a is congruent to b with regards to modulo n gt For example 24 9 mod 5 249 15 divisible by 5 gt Property Ifa a1 mod n and b 91 mod n then abalbl mod n and ab albl mod n Dr XiaoFeng Wang Indiana Unhr39emitv Schml of informatics Basic Basic Number Theory Concepts cont d Greatest Common Divisor GCD gt The god of two number a and b is the largest integer that divides both a and b gt For example gcd15105 gt If gcda 9 1 a and b are relatively prime gt For example gcd5 61 so 5 and 6 are relatively prime Dr XiaoFeng Wang lndiam in rmity School of informatics Basic Basic Number Theory Concepts cont d Order gt Zn01 n1 gtZn ann gcdan 1 gt Z6 015 Z61 5 gt The order of Zn 0n is the number of elements in 2 gt What is the order of 26 062 gt If npq and both p and q are primes 0np1q1 gt For example 62gtlt3 0621312 homework Dr XiaoFeng Wang lndiam in rmity Schml of informatics Basic Basic Number Theory Concepts cont d Euler s Theorem gt If ann then a0 1 mod n gt For example 062 and 52ZS1 mod 6 gt If rs mod 0n then aras mod n gt Then for erpq x094qu 1 modpq gt For example 523913 1 1 mod 2x3 Dr XiaoFeng Wang Indiana in rmity SChOOl of informatics Basic Basic Number Theory Concepts cont d Cyclic groups gt Let geZn The order of g is the least positive number t st gt 1 mod n gt If the order of g is 0n then g is a generator of Zn That is using g we can generate the whole Zn Then Zn lt is called cyclic gt Cyclic group Zn g0 mod n g1 mod n g0 391 mod n gt Example ZSgt 2O mod 5 21 mod 5 22 mod 5 23 mod 5 l 2 4 3 Dr XiaoFeng Wang Indiana in rmity School of informatics A Candidate Trapdoor Oneway Function Setting gt n pq Where pq are distinct primes and gcde plq l1 The easy problem gt Given e and x compute y xe mod n The hard problem gt Given y and e compute x The trapdoor gt d st ed 1 mod p1ql gt Knowing p q allows one to ef ciently compute d Dr XiaoFeng Wang lndiam in rmity School of informatics A Candidate Trapdoor Oneway function cont d Use trapdoor d to compute Xfrom y gt yd mod n xed mod n xxed39l mod n xxkP391 1391mod n x mod n x This is the famous RivestShamir Adleman Trapdoor One way function Dr XiaoFeng Wang lndiana in rmity School of informatics Publickey Cryptosystems Public key known to everyone Secret key only known to individuals Encryption use public key decryption use private key gt Key distribution is easy Digital signature use secret key to sign use public key to verify gt Nonrepudiation none can deny her his signature Dr XiaoFeng Wang Indiana in rmity School of informatics Publickey Encryption An Informal Definition A key generation algorithm G gt Output a public key K and a secret key K 1 An encryption algorithm E gt Input public key K and plaintext M gt Output a ciphertext Clt EKM A decryption algorithm D gt Input a ciphertext C and a secret key K 1 gt Output a plaintext M lt DKA C If Clt EKIl0 then M lt DKI C If Clt EKIlD then C and K should reveal no information about M Dr XiaoFeng Wang lndiana University School of informatics RSA Proposed by Turing Prize Laureates Ron Rivest Adi Shamir and Leonard Adleman Security based on difficulty of factoring large numbers 100 digits gt Recovering plaintext from the public key and ciphertext is as hard as factoring the product of two primes A deterministic cryptosystem Dr XiaoFeng Wang Indiana Univemity School of informatics RSA Key Generation Choose 2 random large primes p and q gt Compute n pq Randomly choose encryption key e st gcde p1q11 Compute decryption key d st ed 1 mod p1q1 gt d e391 mod p1q1 Public key en Different users cannot share n ll Private key d Never reveal p and q Dr XiaoFeng Wang lndiam in rmity Schml of informatics RSA Encryption Encryption gt Divide M into block smaller than n gt cl ml mod n Decryption gt ml Cid mod n cidmod n ml6V mod n miedm dP391q391 mod n ml mod n Dr XiaoFeng Wang Indiana Univeth Schml of informatics RSA Example I p 2357 q 2551 I n pq 6012707 I p1q1 2356 gtlt2250 6007800 I Choose e 3674911 I d 422191 I Publish e n keep d secret I Encrypt 5234673 0 52346733674911 mod 6012707 3650502 I Decrypt 3650502 m 3650502422191 mod 6012707 5234673 Dr XiaoFeng Wang indium University School of informatics RSA Security Size of n gt 512bit n only offers marginal security gt For longterm security 1024bit or larger moduli should be used p and q should be about the same bitlength and sufficiently large pq shouldn t be too small Otherwise some efficient factoring algorithms may work Dr XiaoFeng Wang Indiana Univeth School of informatics El Gamal Proposed by Taher Elgamal Based on the intractability of DiffieHellman Problem An important probabilistic oryptosystem Dr XiaoFeng Wang lndiam Unhrem39w Schml of informatics Other hard problems Setting gt A prime p a generator g of 219 The discreteIogorithm problem gt Given g and yga modp nd a The DiffieHellman Problem gt Given g mod p and g modp nd gab mod p Dr XiaoFeng Wang Indiana University School of informatics El Gamal Key Generation Generate a large random prime p and a generator 9 of Zp Select a random integer a from Zp Compute y 93 mod p Public key is p g y private key is a Dr XiaoFeng Wang Indiana in rmity School of informatics El Gamal Encryption Encryption gt Randomly select an integer k from 219 gt Compute mod p gt Compute CMyk mod p gt The ciphertext is 7 C Decryption gt Knowing secret key a one can compute M Cyquot mod p Dr XiaoFeng Wang Indiana Univeth Schml of informatics Example p 2357 and a generator 9 2 of Z2357 Secret key a 1751 y21751mod 2357 1185 Encrypt message 2035 gt y 21520 mod 2357 1430 gt C 2035 x11851520 mod 2357 697 Decryption gt y 1430605 mod 2357 872 gtM 872 X 697 mod 2357 2035 Dr XiaoFeng Wang lndiana in rmity School of informatics El Gamal Intuitions DiffieHellman Problem What you know y 93 mod p 7 9396 mod p What you don t know a b What is hard to do from y and 7 to compute L gab mod p Do you believe it is hard Let s try 9 6 is the generator of 213 a lowlevel question what is 213 a little higher why answer i 012 3 4 5 6 7 8 91011 6 m0d13 610 8 9 2 12 7 3 5 4 11 A Now to the point I give you y 68 mod 13 12 7 6quot mod 13 5 Tell me what is L 63b mod 13 Dull solution search the table until you find the exponent for y How many step you need to take Is it an easy problem If we take the number of the bits of p as the problem size 13 1101 Dr XiaoFeng Wang lndiana Link smin School of informatics El Gamal Intuitions cont d I Dif e Hellman Problem What you know F ga mod p 7 9quot mod p What you don t know a b What is hard to do from y and 7 to compute L gab mod p i I El Gamal intuitions how to use the above problem to hide a message M I how about using L ML mod p I Public key y g p what every knows including bad guys I Secret key a you are the only person who know it I Encryption how to send you a text only you can recover I choose a secret b compute 7 9quot mod p I compute L ybmod p gab mod p I compute C ML mod p hide M using L I Decryption you know a so you can compute L right L ya then CL is what you want I Does this work Attacker knows neither a nor b what he can see is y and y Finding L from these Dr XiaoFeng Wang lndiana in rmity School of informatics El Gamal Security Size of p gt 512bitp provides only marginal security gt 1024bit or larger moduli should be used for longterm security It is critical to choose different random b for different messages gt Otherwise one can compute MlM2 mod p why Dr XiaoFeng Wang Indiana University School of informatics Chosen Plaintext Attack CPA The adversary has a public key K and encryption function E gt So for any plaintext 1V1 it can produce the corresponding C Given two known plaintext M0 and M1 one called test oracle randomly chooses one of them encrypts it and outputs C The adversary wants to know which message is encrypted Dr XiaoFeng Wang lndiam in rmity School of informatics CPA example are you going to sign the contract L y EKA 0 Yes or NO Adversary Dr XiaoFeng Wang Indiana in rmity Schml of informatics CPASecurity of RSA RSA is not CPAsecure gt Deterministic encryption encrypt the same plaintext twice the resulted ciphertexts are the same gt An adversary can always tell which plaintext the test oracle encypted Dr XiaoFeng Wang Indiana in rmity School of informatics CPASecurity of El Gamal El Gamal is CPAsecure gt Probabilistic encryption encrypt the same plaintext twice the resulted ciphertexts are different gt An adversary knowing public key will not be able to tell which plaintext the test oracle encrypted Dr XiaoFeng Wang Indiana in rmity School of informatics Publickey and secretkey encryption Publickey cryptosystem makes key distribution simple But its performance is much worse than secret key encryption Tradeoff Dr XiaoFeng Wang lndiana inurenatty School of informatics Digital Signature A key generation algorithm G gt Generate a public key K and a secret key K 1 A signing algorithm 8 gt Input a message M and the secret key K 1 gt Output a signature 039 lt S K4 M A verification algorithm V gt Input a message M and a public key K and a signature 039 gt Output a bit I blt VKM 039 Where b0 invalid and 71 valid Given a pair of message and signature it is computationally infeasible to compute signature for a different message unless the secret key is exposed Dr XiaoFeng Wang Indiana Univemity School of informatics Attacks on Signatures Existential Forgery Adversary succeeds in forging the signature of one message not necessarily of his choice Selective Forgery The adversary succeeds in forging the signature of some message of his choice Universal Forgery The adversary is able to forge the signature of any message Total Break The adversary computes the signer s secret key Dr XiaoFeng Wang Indiana inure lly Schml of informatics Vanilla RSA Signature Scheme Recall the public key is n e and the secret key is d Signing a message gt 0Md modn Verifying a signature gt M lt 06 mod n gt If M M return 1 else return 0 Is this scheme secure Dr XiaoFeng Wang lndiana in rmity Schml of informatics Vanilla RSA Signature Scheme cont d Given two signatures M W mod n m md mod n An adversary can construct the signature on a new message Mm Mmd mod n This signature scheme is not secure for the existential forgery attack Dr XiaoFeng Wang lndiana inuremin School of informatics RSA Signature Scheme Signing a message gt Take a oneway hash function H gt 039 HMd mod n Verifying a signature gt Compute M 0e mod n gt If M HM then output 1 else output 0 Is this scheme secure against the existential forgery attack HMm HMHm Dr XiaoFeng Wang Indiana University School of informatics El Gamal Signature Scheme Recall public key is p g y and private key is a Signing a message gt Select a random secret integer k from Z with gcdkp1 1 gt Compute rgk mod p gt Compute 1 mod pl gt Compute 5161 HM ar mod pl gt Signature on M r s Verifying a signature gt Verify that r eZp gt Compute 21er mod p gt Compute HM and v2 HQ mod p gt Accept the signature if and only if 121 v2 Dr XiaoFeng Wang lndiana University School of informatics El Gamal Signature Scheme cont d Different random k must be selected for each message signed If the hash function is not in use the scheme is subject to the existential forgery attack If Oltrltp is not checked then an adversary can sign a message of its choice provided it has one valid signature Digital Signature Standard DSS is an extension of this signature scheme Dr XiaoFeng Wang Indiana linhtemiw Schml of informatics Modern Cryptography Publickey Certification and Distribution Dr XiaoFeng Wang lndiana University School of informatics Publickey Certificate How to trust and distribute one s public key gt Without reliable method an adversary may cheat you into taking its key as some other party s key Certificate gt A digital document issued and signed by a trusted third party TTP to certify an entity s public key gt TTP Certi cation Authority CA gt Assumption the veri er knows CA s public key Dr XiaoFeng Wang Indiana Univemiw School of informatics Certificate Content X509 A validity period of the public key A serial number Algorithm ID Subject unique identifierfor whom this certificate was issued Public Key of subject CA s signature on a hash of all fields but the signature Dr XiaoFeng Wang Indiana inure lly Schml of informatics Creation of a Publickey Certificate A subject applies certificate from a CA The CA should take measures usually noncryptographic in nature to verify the claimed entity of the subject gt CA may create the key pair for the subject gt The subject may create its own key pair and securely transfer it to the CA Dr XiaoFeng Wang Indiana UnWE39TS f School of informatics Certificate Verification Verify the validity period in the certificate Verify the current validity of the CA s key itself Verify CA s signature on the subject s certificate Verify that the certificate has not been revoked Dr XiaoFeng Wang Ilndimta ljnhra39siw Schml of informatics Certificate Chain Certification Path Dr XiaoFeng Wang Indiana Juniemin School of informatics Pretty Good Privacy PGP An encryption program for email gt A defacto standard for email encryption Invented by Phil Zimmerman in 1991 gt Later developed and distributed by MIT ViaCrypt PGP Inc and now Network Associates Inc NAI gt The international version of PGP is PGPi Dr XiaoFeng Wang lndiana in rmity School of informatics PGP Use both publickey and symmetrickey cryptosystem gt RSA public key to encrypt a symmetric session key gt The session key encrypts the plaintext of an email gt Public keys could be retrieved from key servers Digital signature gt PGP implements RSA or DSA signature algorithms gt Compute a hash of the plaintext before signing Dr XiaoFeng Wang lndiana in rmity School of informatics PGP Key Distribution Key propagates through wordof mouth gt An alternative is key server httppgpmitedu Public keyring gt One gives a public key directly to another gt One may post a public key on the webpage gt A recipient may fetch the sender s key from key server gt One can give a second person s key to the third person so on and so forth gt A recipient of a key may ask the sender to sign the key gt A key could be signed by multiple parties Dr XiaoFeng Wang lndiam mm131W School of informatics Modern Cryptography Some Cryptographic Protocols and Threats Dr XiaoFeng Wang lndiana University School of informatics DiffieHellman Key Establishment Protocol How to establish a secret key between Alice and Bob gt A and B never met before gt Sam eavesdrops on the communication channel gt Sam is a passive attacker Passive vs Active Attackers gt Passive attacker only observes messages from a communication channel gt Active attacker may insert messages to the communication channel Dr XiaoFeng Wang Indiana mmmil School of informatics DH Key Establishment Draw a secret XeZp secret yeZp Compute 9w mod p Compute 90 mod p Dr XiaoFeng Wang Fall 2006 lndiana in rmity School of informatics Bit Commitment Alice and Bob want to flip a coin over the Internet gt If it is the head Alice Wins gt If it is the tail Bob wins Alice and Bob decide to do following gt Both of them choose a bit 0 or 1 gt If choices are the same Alice Wins gt If choices are different Bob wins However if Alice give Bob her choice first Bob may change his choice and vice versa Dr XiaoFeng Wang Indiana Urinemin School of informatics Bit Commitment EKAbA EKBbB KB Why does this work Can you design a new protocol using oneway hash function Dr XiaoFeng Wang lndiana University School of informatics Mental Poker Alice and Bob want to play the poker through the Internet gt Dif culty how to fairly deal the cards Ideas use a commutative encryption algorithm gt E1E2ME2E1M gt For example the El Gamal publickey algorithm with the common moduli gt Alice and Bob keep their public key secret at the beginning of the game Dr XiaoFeng Wang lndiam in rmity School of informatics Mental Poker Protocol EAM1 EAM52 L AEAMI1 EAMi5 EBEAij1 EBEAIWj5 EBIWj1 EBle5 Dr XiaoFeng Wang lndiam mmmil Schml of informatics Threat Replay Attacks sA1 OOtoX SA1OOtoX 100 Accoimt X Dr XiaoFeng Wang Indiana in rmity School of informatics Defense against Replay Attacks Timestamps gt Obtain a timestamp from local time or from a global trusted third party gt Cryptographically bind the timestamp to a message gt The recipient veri es the timestamp May require a loosely synchronized time Nonce number used once gt Randomly generate a number as a part of the plaintext gt The recipient records all the nonce used to detect replay Dr XiaoFeng Wang Indiana mm1311quot Chml of informatics How to beat two chess masters Dr XiaoFeng Wang lndiam mmmil Schml of informatics Another ManintheMiddle Attack Dr XiaoFeng Wang Indiana Unhr39emiw School of informatics Defense against ManintheMiddle Attacks Put some purposeidentity specifio information in the Challenge message gt For example M includes a string goldpurchase or from bank Is the friendandfoe protocol subject to this attack gt If so how to improve it Dr XiaoFeng Wang lndiam mmmil School of informatics Is the friendor foe identity protocol secure tHMACK C c RHMACltKCgt R tR Dr XiaoFeng Wang lndiam mmmil Schml of informatics Another example Miginthemiddle R RHMACK C Miginthe middle attack Dr XiaoFeng Wang lndiam mmmil Schml of informatics How to fix it tHMACKC Location C RHMACKC Location R tR Dr XiaoFeng Wang