密码学Outline.ppt
曹天杰Tianjie Cao College of Computer Science andTechnology,China University of Mining and Technology,Xuzhou,China中国矿业大学计算机科学与技术学院2003.6.16Outline Attacks,Services,and Mechanisms*Security Attack:Any action that compromises the security of information.*Security Mechanism:A mechanism that is designed to detect,prevent,or recover from a security attack.*Security Service:A service that enhances the security of data processing systems and information transfers.A security service makes use of one or more security mechanisms.CryptosystemA cryptosystem is a five-tuple(P,C,K,E,D),where the following conditions are satisfied:1.P is a finite set of possible plain texts2.C is a finite set of possible ciphertexts3.K,the keyspace,is a finite set of possible keys4.For each kK,there is an encryption rule eK E.and a corresponding decryption rule dK D).Each eK:P C and dK:C P are functions such that dK(eK(x)=x for every plaintext x P.Taxonomy of cryptographic primitives.Arbitrary length hash functionsOne-way permutationsRandom sequencesSymmetric-key ciphersArbitrary length hash functions(MACs)SignaturesPseudorandom sequencesIdentification primitivesPublic-key ciphersSignaturesIdentification primitivesUnkeyedPrimitivesSymmetric-keyPrimitivesPublic-keyPrimitivesSecurityPrimitivesBlockciphersStreamciphersBackground on Functions(ctd)one-way function iff(x)is easy to compute for all x X,but it is computationally infeasible to find any x X such that f(x)=y.trapdoor one-way function ifgiven trapdoor information,it becomes feasible to find an x X such that f(x)=y.Cryptanalysis -Types of AttacksCiphertext-Only AttackAttacker knows ciphertext of several messages encrypted with the same key and/or several keysRecover the plaintext of as many messages as possible or even better deduce the key(or keys)Given:C1=Ek(P1),C2=Ek(P2),.Ci=Ek(Pi)Deduce:Either P1,P2,.Pi;k;or an algorithm to infer Pi+1 from Ci+1=Ek(Pi+1)Known-Plaintext AttackKnown ciphertext/plaintext pair of several messagesDeduce the key or an algorithm to decrypt further messagesGiven:P1,C1=Ek(P1),P2,C2=Ek(P2),.Pi,Ci=Ek(Pi)Deduce:Either k,or an algorithm to infer Pi+1 from Ci+1=Ek(Pi+1)Cryptanalysis -Types of AttacksChosen-Plaintext Attack Attacker can choose the plaintext that gets encrypted thereby potentially getting more information about the keyGiven:P1,C1=Ek(P1),P2,C2=Ek(P2),.Pi,Ci=Ek(Pi),where the cryptanalyst gets to choose P1,P2,.Pi Deduce:Either k,or an algorithm to infer Pi+1 from Ci+1=Ek(Pi+1)Adaptive Chosen-Plaintext AttackAttacker can choose a series of plaintexts,basing choice on the result of previous encryption differential cryptanalysis!Chosen-ciphertext attackGiven:C1,P1=Dk(C1),C2,P2=Dk(C2),.Ci,Pi=Dk(Ci)Deduce:k Models for evaluating securityUnconditional security(perfect secrecy)Adversaries have unlimited computational resourcesObservation of the ciphertext provides no information to an adversaryOne time padComplexity-theoretic securityAdversaries have polynomial computational power.Asymptotic analysis and usually also worst-case analysis is usedProvable securityprovably secure if the difficulty of defeating crypto system can be shown to be as difficult as solving a well-known number-theoretic problemModels for evaluating security(ctd)Computational security(Practical security)We might define a cryptosystem to be computationally secure if the best algorithm for breaking it requires at least N operations,where N is some specified,very large number.The problem is that no known practical cryptosystem can be proved to be secure under this definition.neither the Shift Cipher,the Substitution Cipher nor the Vigenke Cipher is computationally secure against a ciphertext-only attack(given a sufficient amount of ciphertext).Ad hoc security(heuristic security)any variety of convincing computational securityunforeseen attacks may remainShannons Definition of Perfect Secrecy mciphertext COne-Time Padk bits of random key K1 0 0 1 1 0 1 0 1 00 1 1 1 0 1 1 0 1 11 1 0 1 0 0 0 1 1 1use random key sequenceonly once and then discard it!The One-Time PadEk(m)=m kkIntegrity of Documents and MessagesDetection of corrupted documents and messagesDetection of bit errors caused by unreliable transmission links or faulty storage media.Solution:Message Digest acting as a unique fingerprint for the document(similar function as CRC).Protection against unauthorized modification Without protection a forger could create both an alternative document and its corresponding correct message digest.Symmetric Key Solution:Message Authentication Code(MAC)formed by using a keyed message digest function.Asymmetric Key Solution:Digital Signature formed by encrypting the message digest with the document authors private key.Block cipherDefinition An n-bit block cipher is a function E:VnKVn,such that for each key K K,E(P;K)is an invertible mapping(the encryption function for K)from Vn to Vn,written EK(P).The inverse mapping is the decryption function,denoted DK(C).P denotes that ciphertext results from encrypting plaintext P under K.Iterating Block ciphersDefinition A product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components.Definition An iterated block cipher is a block cipher involving the sequential repetition of an internal function called a round function.Parameters include the number of rounds Nr,the block bitsize n,and the bitsize k of the input key K from which Nr subkeys Ki(round keys)are derived.For invertibility(allowing unique decryption),for each value Ki the round function is a bijection on the round input.Substitution-Permutation Networks:SPNSubstitution pS:0,1l 0,1l Permutation pP:1,lm 1,lm The plaintext has lm bits:x=x(1)|.|x(m)where:x(i)=(x(i-1)l+1,.,xil)The SPN has Nr rounds,in which we perform on x m substitutions pS followed by one permutation pP,to get the ciphertext y.Definition A substitution-permutation(SP)network is a product cipher composed of a number of stages each involving substitutions and permutationsLinearCryptanalysisLinear cryptanalysis tries to take advantage of high probability occurrences of linear expressions involving plaintext bits,ciphertext bits(actually we shall use bits from the 2nd last round output),and subkey bits.It is a known plaintext attack.DifferentialCryptanalysisDifferential cryptanalysis exploits the high probability of certain occurrences of plaintext differences and differences into the last round of the cipher.Differential cryptanalysis is a chosen plaintext attack,meaning that the attacker is able to select inputs and examine outputs in an attempt to derive the key.Feistel Networksf1,fk:0,1n 0,1n Arbitrary functionsNot necessarily invertiblef1 f2 fk-1 fk L0:R0:L1:R1:Lk-2:Rk-2:Lk-1:Rk-1:Lk:Rk:n bitsn bitsRound 1Round 2Round k-1Round kLi=Ri-1Ri=Li-1 fi(Ri-1)Inverting a Feistel Networkf1 f2 fk-1 fk L0:R0:L1:R1:Lk-2:Rk-2:Lk-1:Rk-1:Lk:Rk:Li-1=Ri fi(Li)Ri-1=LiTheoremFor any f1,fk:0,1n 0,1n,a Feistel network computes a permutation p:0,1n 0,1n Inverse:Inside DESx0=IP(m)=L0R0.16 Rounds,i=1,2,16:Li:=Ri-1,Ri:=Li-1 f(Ri-1,Ki),wheref(Ri-1,Ki)=P(S(E(Ri-1)Ki),with operations E(expansion),S(S-box lookup),and P some(permutation).c=IP-1(L16R16).One Round of DESExpansion Permutation48P-Box PermutationS-Box Substitution32ShiftShift48Compression PermutationFeistel Network563232Keyi-1Ri-1Li-1KeyiRiLi323256Avoiding Exhaustive Search3DES3DESk1,k2(m)=Ek1(Dk2(Ek1(m)Key length:112 bitsVery popularDESencryptionDESencryptionDESdecryption1.TDEA encryption operation2.O=EK3(DK2(EK1(m).2.TDEA decryption operationO=DK1(EK2(DK3(c)1.K1,K2 and K3 are independent keys;2.K1 and K2 are independent keys and K3=K1;3.K1=K2=K3.Theory of Block Cipher DesignChoosinggoodS-boxes:Theyshouldnotbelinearoraffine,norevenclosetolinearoraffine.Thereshouldbeabalanceofzerosandones,andnocorrelationsbetweendifferentcombinationsofbits.Onepropertythatseemsveryimportantistheavalancheeffect.Thestrictavalanchecriteria(SAC)guaranteesthatexactlyhalfoftheoutputbitschangewhenoneinputbitchanges.1.Chooserandomly.2.Chooseandtest.3.Man-made.4.Math-made.Modes of operationFive basic modes of operation are available for block ciphers:Electronic codebook mode:ECBCipher block chaining mode:CBCCipher feedback mode:CFBOutput feedback mode:OFBCounter Mode:CTRRounds:depend on block size and key length Block sizeKey size128 bits(Nb=4)192 bits(Nb=6)256 bits(Nb=8)128 bits(Nk=4)101214192 bits(Nk=6)121214256 bits(Nk=8)141414The AES CipherAdd Round KeyInverse mix colsAdd round keyInverse sub bytesInverse shift rowsAdd round keyMix ColumnsShift RowsAdd Round KeyInverse sub bytesInverse shift rowsInverse mix colsAdd round keyInverse sub bytesInverse shift rowsAdd round keySubstitute BytesAdd round keyShift RowsSubstitute BytesAdd round keySubstitute BytesShift RowsMix ColumnsExpand Key.w0,3w4,7w36,39w40,43PlaintextPlaintextCiphertextCiphertextRound 1Round 9Round 10Round 1Round 9Round 10Keyed hash functions(X,Y,K,H)is a keyed hash family,where X is a set of possible messages Y is the set of possible message digests,or authentication tags K is the keyspace H is a set of hash functions For each key K there is a hash function hK:X Y in HAssume|X|=|Y|(even better,2|X|=|Y|)Unkeyed hash functionsAn unkeyed hash function is a mapping h:X Y,where X is a set of possible messages Y is the set of possible message digestsUnkeyed hash function|K|=1Ex.SHA-1(successor of MD4)Ideal hash functionsit is a simple matter to compute the probability that k random elements z1,.,zk Z are distinct.The first choice z1 is arbitrary;the probability that z2!=z1 is 1-l/n;the probability that z3 is distinct from z1 and z2 is 1-2/n,etc.we estimate the probability of no collisions to beMessage Authentication codes(MACs)Source(K)Destination(K)Message my=hk(m)Checky=hk(m)m,tag yHMACnested MAC algorithm(proposed standard)based on SHA-1uses 512-bit key k2 512-bit constants,ipad and opad160-bit MACHMACk(x)=SHA-1(k opad)|SHA-1(K ipad)|x)ipad component resistant against unknown-key collision attackCBC MACx1+IVx2x3x4y4y3y2y1DESDESDESDESPublic-Key Applicationscan classify uses into 3 categories:encryption/decryption(provide secrecy)digitalsignatures(provide authentication)keyexchange(of session keys)some algorithms are suitable for all uses,others are specific to one.Only three algorithms work well for both encryption and digital signatures:RSA,ElGamal,and Rabin.All of these algorithms are slow.Security of Public-Key AlgorithmsSince a cryptanalyst has access to the public key,he can always choose any message to encrypt.Eve can generate a database of all possible session keys encrypted with Bobs public key.most public-key algorithms are particularly susceptible to a chosen-ciphertext attack In systems where the digital signature operation is the inverse of the encryption operation,this attack is impossible to prevent unless different keys are used for encryption and signatures.Public Key:n product of two primes,p and q(p and q must remain secret)e relatively prime to(p-1)(q-1)Private Key:d e-1 mod(p-1)(q-1)Encrypting:c=me mod n Decrypting:m=cd mod n RSAEncryptionRSA Signature p,q:primes,n=pq,ed=1 mod (n),e,n:public key,d:secret key,(factoring,n:1024 bits)M:message,M in 0,1,.,n-1.Signing:S=MdmodnVerification:M=SemodnKey generation:p=3,q=5,n=15,e=3=d=3Signing:M=13,S=13d mod n,=S=7Verification:Checking M=Se mod n Semantic securityTotal breakThe adversary can determine the private key of a public key cryptosystem,or the secret key of a symmetric key encryption system.Partial breakThe adversary is able with non-negligible probability to decrypt a previously unseen ciphertext(without knowing the private/secret key),ordetermine some specific information about the plaintext given the ciphertext.Semantic securityDistinguishability of ciphertextsThe adversary is able to distinguish with probability greater than ,encryptions of different plaintexts,orencryptions of a given plaintext and a random string.A public key cryptosystem in which the adversary cannot(in polynomial time)distinguish ciphertexts,under certain computational assumptions hold,is said to achieve semantical security.Perfect vs.Semantic securityperfect secrecy:a passive adversary,even with infinite computational resourcescan learn nothing about plaintext from ciphertext,except its length Limitation:cannot be achieved unless key is as long as messagesemantic security:polynomially bounded perfect secrecya passive adversary with poly.bounded resources can learn nothingAlice ga mod p Bob gb mod p The private key is:gab mod p where p is a prime and g is a generator of ZpDiffie-HellmanR=P+QGroup set:All points P(x,y)lyingon an elliptic curveGroup operation:Point additionRRPQPoints P(x,y)on an Elliptic Curve form a GroupInverse element:P(x,-y)=P(x,y)is mirrored on x-axisPoint addition with inverse element:P+P=Oresults in a neutralelement O(x,)at infinityPONeutral element:P+O=PPNeutral and Inverse ElementsR=P+PPoint Doubling:Form the tangent inPoint P(x,y)RRPPoint Doubling Adding a point to itselfkP=P+P+.+PPoint Iteration:3P2PPPoint Iteration Adding a point k-1 times to itselfDefinition of an Elliptic Curve Cryptosystemversionis currently v1fieldIDidentifies the finite field over which curve is defined curvecoefficients a and b of the elliptic curvebasespecifies the base point P.a point P in the elliptic curve group defined over GF(p)orderthe order n of the base pointPublic Key CryptographySignature schemesLet P be the set of all messages A be the set of signaturesK be the set of all keysBasic Mechanism of Signature SchemesK:A key generation algorithm to randomly select a public key pair.Sig K:A signature algorithm that takes message+private key as input and generates a signature for the message as outputVer K:A signature verification algorithm that takes signature+public key as input and generates information bit according to whether signature is consistent as output.Attack modelsTotalBreakingAttack -The attacker knows the public key.He tries to recover the corresponding secret key.ForgeryAttack -The attacker knows the public key.He tries to find the signature for a given message.ExistentialForgeryAttack -The attacker knows the public key.He tries to find a pair of a message and its signature.ChosenMessageAttack(CMA)-The attacker is able to sign messages but does not know the key used.He tries to perform the(existential)forgery or to obtain the secret key.definitionsA protocol is said to have perfect forward secrecy if compromise of long term keys does not compromise past(short term)session keys.A protocol is vulnerable to a known-key attack if compromise of past session keys allows an attacker to compromise of future session keys(including actively impersonating)Needham Schroeder Symmetric KeyNeedham Schroeder Symmetric Key1.A-S:A,B,Na2.S-A:Na,B,Kab,Kab,AKbsKas3.A-B:Kab,AKbs4.B-A:NbKab5.A-B:dec(Nb)KabABSFreshness Attacks(3)Needham Schroeder Symmetric Keyi.1.A-S:A,B,Nai.2.S-A:Na,B,Kab,Kab,AKbs Kasi.3.A-I(B):Kab,AKbsassume that Kab is compromisedii.3.I(A
