密码学Outline.ppt

1、曹天杰 Tianjie Cao College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.16,Outline,Attacks, Services, and Mechanisms,* Security Attack: Any action that compromises the security of information. * Security Mechanism: A mechanism that

2、 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.,Cryptosystem,A cryptosystem is a five -tuple (P, C, K, E

3、, D), where the following conditions are satisfied: 1. P is a finite set of possible plain texts 2. C is a finite set of possible ciphertexts 3. K, the keyspace, is a finite set of possible keys 4. For each kK, there is an encryption rule eK E. and a corresponding decryption rule dK D). Each eK : P

4、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 functions,One-way permutations,Random sequences,Symmetric-key ciphers,Arbitrary length hash functions(MACs),Signatures,Pseudorandom sequences,Identification primit

5、ives,Public-key ciphers,Signatures,Identification primitives,Unkeyed Primitives,Symmetric-key Primitives,Public-key Primitives,Security Primitives,Block ciphers,Stream ciphers,Background on Functions (ctd),one-way function if f(x) is easy to compute for all x X, but it is computationally infeasible

6、to find any x X such that f(x) =y. trapdoor one-way function if given trapdoor information, it becomes feasible to find an x X such that f(x) =y.,Cryptanalysis - Types of Attacks,Ciphertext-Only Attack Attacker knows ciphertext of several messages encrypted with the same key and/or several keys Reco

7、ver 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 Attack Known ciphertext / plaintext pair of several messages Deduce

8、the key or an algorithm to decrypt further messages Given: 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 Attacks,Chosen-Plaintext Attack Attacker can choose the plaintext that gets encrypted thereby pot

9、entially getting more information about the key Given: 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 Attack Attacker can choose a series of plaintexts,

10、 basing choice on the result of previous encryption differential cryptanalysis! Chosen-ciphertext attack Given: C1, P1 = Dk(C1), C2, P2 = Dk(C2),.Ci, Pi = Dk(Ci) Deduce: k,Models for evaluating security,Unconditional security (perfect secrecy) Adversaries have unlimited computational resources Obser

11、vation of the ciphertext provides no information to an adversary One time pad Complexity-theoretic security Adversaries have polynomial computational power. Asymptotic analysis and usually also worst-case analysis is used Provable security provably secure if the difficulty of defeating crypto system

12、 can be shown to be as difficult as solving a well-known number-theoretic problem,Models 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

13、 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

14、of ciphertext). Ad hoc security (heuristic security) any variety of convincing computational security unforeseen attacks may remain,Shannons Definition of Perfect Secrecy,m,The One-Time Pad Ek(m) = m k,k,Integrity of Documents and Messages,Detection of corrupted documents and messages Detection of b

15、it 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 co

16、rresponding 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 cipher,Definition An n-bit bl

17、ock 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.,Iteratin

18、g Block ciphers,Definition 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 r

19、ound 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

20、-Permutation Networks: SPN,Substitution 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.,Defi

21、nition A substitution-permutation (SP) network is a product cipher composed of a number of stages each involving substitutions and permutations,Linear Cryptanalysis,Linear cryptanalysis tries to take advantage of high probability occurrences of linear expressions involving plaintext bits, ciphertext

22、 bits (actually we shall use bits from the 2nd last round output), and subkey bits. It is a known plaintext attack.,Differential Cryptanalysis,Differential cryptanalysis exploits the high probability of certain occurrences of plaintext differences and differences into the last round of the cipher. D

23、ifferential 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 Networks,f1, , fk : 0,1n 0,1n Arbitrary functions Not necessarily invertible,f1,f2,fk-1,fk,L0 :,R0 :,L1 :,R1 :,Lk-2 :,Rk-2 :,Lk-1 :,

24、Rk-1 :,Lk :,Rk :,n bits,n bits,Round 1,Round 2,Round k-1,Round k,Li = Ri-1 Ri = Li-1 fi(Ri-1),Inverting a Feistel Network,f1,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 = Li,Theorem For any f1, , fk : 0,1n 0,1n, a Feistel network computes a permutation

25、p : 0,1n 0,1n,Inverse:,Inside DES,x0 = 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 DES,Feistel Network,Avoiding Exhaustive S

26、earch3DES,3DESk1,k2(m) = Ek1(Dk2(Ek1(m) Key length: 112 bits Very popular,DESencryption,DESencryption,DESdecryption,TDEA encryption operation O = EK3(DK2(EK1(m). 2. TDEA decryption operation O = DK1(EK2(DK3(c),1. K1, K2 and K3 are independent keys; 2. K1 and K2 are independent keys and K3 = K1; 3. K

27、1 = K2 = K3.,Theory of Block Cipher Design,Choosing good S-boxes : They should not be linear or affine, nor even close to linear or affine. There should be a balance of zeros and ones, and no correlations between different combinations of bits. One property that seems very important is the avalanche

28、 effect. The strict avalanche criteria (SAC) guarantees that exactly half of the output bits change when one input bit changes. 1.Choose randomly. 2.Choose and test. 3.Man-made. 4.Math-made.,Modes of operation,Five basic modes of operation are available for block ciphers: Electronic codebook mode: E

29、CB Cipher block chaining mode: CBC Cipher feedback mode: CFB Output feedback mode: OFB Counter Mode:CTR,Rounds : depend on block size and key length,The AES Cipher,Add Round Key,Inverse mix cols,Add round key,Inverse sub bytes,Inverse shift rows,Add round key,Mix Columns,Shift Rows,Add Round Key,Inv

30、erse sub bytes,Inverse shift rows,Inverse mix cols,Add round key,Inverse sub bytes,Inverse shift rows,Add round key,Substitute Bytes,Add round key,Shift Rows,Substitute Bytes,Add round key,Substitute Bytes,Shift Rows,Mix Columns,Expand Key,. . .,. . .,w0,3,w4,7,w36,39,w40,43,Plaintext,Plaintext,Ciph

31、ertext,Ciphertext,Round 1,Round 9,Round 10,Round 1,Round 9,Round 10,Keyed 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 h

32、ash function hK: X Y in H Assume |X| = |Y| (even better, 2|X| = |Y|),Unkeyed hash functions,An unkeyed hash function is a mapping h: X Y, where X is a set of possible messages Y is the set of possible message digests,Unkeyed hash function |K| = 1 Ex. SHA-1 (successor of MD4),Ideal hash functions,it

33、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 be,Messa

34、ge Authentication codes (MACs),Source (K),Destination (K),Message m y = hk(m),Check y = hk(m),m, tag y,HMAC,nested MAC algorithm (proposed standard) based on SHA-1 uses 512-bit key k 2 512-bit constants, ipad and opad 160-bit MAC HMACk(x) = SHA-1(k opad) | SHA-1(K ipad) | x) ipad component resistant

35、 against unknown-key collision attack,CBC MAC,Public-Key Applications,can classify uses into 3 categories: encryption/decryption (provide secrecy) digital signatures (provide authentication) key exchange (of session keys) some algorithms are suitable for all uses, others are specific to one. Only th

36、ree algorithms work well for both encryption and digital signatures: RSA, ElGamal, and Rabin. All of these algorithms are slow.,Security of Public-Key Algorithms,Since a cryptanalyst has access to the public key, he can always choose any message to encrypt. Eve can generate a database of all possibl

37、e 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 en

38、cryption 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,RSA Encryption,RSA Signature,p, q: primes, n = pq, ed = 1 mod (n), e, n: pub

39、lic key, d: secret key, (factoring, n: 1024 bits) M: message, M in 0,1,. , n-1.,Signing: S = Md mod n,Verification: M = Se mod n,Key generation: p = 3, q = 5, n = 15, e = 3 = d = 3 Signing: M = 13, S = 13d mod n, = S = 7 Verification: Checking M = Se mod n,Semantic security,Total break The adversary

40、 can determine the private key of a public key cryptosystem, or the secret key of a symmetric key encryption system. Partial break The adversary is able with non-negligible probability to decrypt a previously unseen ciphertext (without knowing the private/secret key), or determine some specific info

41、rmation about the plaintext given the ciphertext.,Semantic security,Distinguishability of ciphertexts The adversary is able to distinguish with probability greater than , encryptions of different plaintexts, or encryptions of a given plaintext and a random string. A public key cryptosystem in which

42、the adversary cannot (in polynomial time) distinguish ciphertexts, under certain computational assumptions hold, is said to achieve semantical security.,Perfect vs. Semantic security,perfect secrecy: a passive adversary, even with infinite computational resources can learn nothing about plaintext fr

43、om ciphertext, except its length Limitation: cannot be achieved unless key is as long as message semantic security: polynomially bounded perfect secrecy a passive adversary with poly. bounded resources can learn nothing,Alice ga mod p Bob gb mod p The private key is: gab mod p where p is a prime and

44、 g is a generator of Zp,Diffie-Hellman,R = P + Q,Group set: All points P(x,y) lyingon an elliptic curve,Group operation: Point addition,Points P(x,y) on an Elliptic Curve form a Group,Inverse element: P(x,-y) = P(x,y) is mirrored on x-axis,Point addition with inverse element: P + P = O results in a

45、neutralelement O(x,) at infinity,O,Neutral element: P + O = P,Neutral and Inverse Elements,R = P + P,Point Doubling: Form the tangent in Point P(x,y),Point Doubling Adding a point to itself,kP = P + P + . + P,Point Iteration:,Point Iteration Adding a point k-1 times to itself,Definition of an Ellipt

46、ic Curve Cryptosystem,versionis currently v1 fieldIDidentifies the finite field over which curve is defined curvecoefficients a and b of the elliptic curve basespecifies the base point P. a point P in the elliptic curve group defined over GF(p) orderthe order n of the base point,Public Key Cryptogra

47、phySignature schemes,Let P be the set of all messages A be the set of signatures K be the set of all keys,Basic Mechanism of Signature Schemes,K: 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 s

48、ignature for the message as output Ver 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 models,Total Breaking Attack -The attacker knows the public key. He tries to recover t

49、he corresponding secret key. Forgery Attack - The attacker knows the public key. He tries to find the signature for a given message. Existential Forgery Attack - The attacker knows the public key. He tries to find a pair of a message and its signature. Chosen Message Attack (CMA) - The attacker is a

50、ble to sign messages but does not know the key used. He tries to perform the (existential) forgery or to obtain the secret key.,definitions,A 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

51、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 Key,Needham Schroeder Symmetric Key 1. A - S : A, B, Na 2. S - A : Na, B, Kab, Kab, AKbsKas 3. A - B : Kab,AKbs 4. B - A : NbKab 5. A - B : dec(Nb)Kab,Freshness Attacks(3),Needham Schroeder Symmetric Key i.1. A - S : A, B, Na i.2. S - A : Na, B, Kab, Kab, AKbs Kas i.3. A - I(B) : Kab,AKbs assume that Kab is compromised ii.3. I(A) - B : Kab,AKbs ii.4. B - I(A) : NbKab ii.5. I(