1、Chaffing & Winnowing Confidentiality without Encryption !,Ronald Rivest Cryptobytes, Summer 1998, p12-17ftp:/ - worthless parts To Winnow - to separate out the chaff,Add MACs Add Chaff,No Encryption, no decryption ! No Export control ?,Chaffing,1, Hi Bob, 462312 2, Meet me at, 782290 3, 7 PM, 238291
2、 4, Love Alice, 839128,1, Hi Bob, 462312 1, Hi Larry, 388231 2, Ill call you at, 562381 2, Meet me at, 782290 3, 7 PM, 238291 3, 6 PM, 823911 4, Yours Sue, 728377 4, Love Alice, 839128,Wheat - Good packets Chaff - Bad packets,Chaffing - adding fake packets with bogus MACs. MAC based on sequence numb
3、er and message. Winnowing - discarding packets with bogus MACs,Security,Security depends on difficulty (for the adversary) of distinguishing the chaff from the wheat Chaffing will normally add at least one chaff packet for each wheat packet. We also need to make wheat packets unintelligible. How can
4、 we do this?,Make Wheat packets a single byte or bit !,1, 1, 462312 1, 0, 823231 2, 1, 562381 2, 0, 782290 3, 0, 238291 3, 1, 823911 4, 1, 728377 4, 0, 839128,Which bits are bogus? Which bits are authentic?,Note: adding a bogus MAC is trivial, just add a random number (e.g. 64 bits). For efficiency
5、would like to process many bits per packet instead of one or 8. Can use a so-called package transform that transforms message such that receiver can only produce original if he receives entire transformed message (transform is keyless).,Variations on a Theme,Creating chaff can be done by a 3rd party
6、, who doesnt know any secret MAC keys!Alice & Bob may not even be aware of the chaff maker!Charles the Chaff Maker could multiplex Alice-to-Bob packets and David-to-Elaine packets. Alice can hide messages. So could use 2 (or more MACs). If asked to reveal MAC, she reveals MAC for innocuous message.,
7、Public Key Cryptography & Digital Signatures,Michael Huth M.Huthdoc.ic.ac.ukwww.doc.ic.ac.uk/mrh/430/,Introduction,Also known as ASYMMETRIC KEY, TWO KEY encryption Based on mathematics rather than on substitution or transposition ciphers Different keys for encryption and for decryption. One key is k
8、ept private (secret), the other can be made public (not secret). Private and Public keys are related mathematically,PUBLIC-KEY vs SYMMETRIC-KEY Public-Key cryptography is not “better” than Symmetric-KeySymmetric-Key cryptography is much faster than Public-Key version - up to 1000 times fasterPublic-
9、Key cryptography used for: authentication, digital signatures, and key-managementSymmetric-Key cryptography used for: bulk encryption, e.g. high-volume packet flow on network,Merkles Puzzles (has applications in electronic contract signing),PuzzleNo: 6248 128-bit Key: 10010.01101,1 Million Encrypted
10、 Puzzles. Each encrypted with a diff. 20-bit key, each holds a diff. 128-bit key. Puzzle order is random.,Randomly picks 1 puzzle to crack, cracks it,PuzzleNo: 6248 Msg: EK128(“Hello“),Looks up 128-bit key for Puzzle 6248,EK20(6248, K128),6248, EK128(“Hello“),Attacker needs to crack 0.5 million puzz
11、les!,Confidentiality (Secrecy),E,C,P,D,P,Receivers (Bobs) private key,C,Authentication,S,E,P,Senders (Alices) private key,D,P,Senders (Alices) public key,S,sign,verify,Confidentiality with Authentication,E,P,Senders (Alices) private key,S,E,C,Receivers (Bobs) public key,P,D,Receivers (Bobs) private
12、key,D,S,Senders (Alices) public key,C,sign,verify,Requirements for Public-Key Cryptography,Should be easy & efficient to generate keys (public and private) Should be easy & “efficient” to encrypt and decrypt Should be hard to compute PRIVATE-KEY from PUBLIC-KEY Should be hard to compute PLAINTEXT fr
13、om PUBLIC-KEY and CIPHERTEXT Encryptions, Decryption might be applied in either order,ONE-WAY FUNCTION fC = f (P) “Easy” P = f-1 (C) InfeasibleTRAP-DOOR 1-WAY FUNCTION f C = f (K, P) “Easy” if K & P knownP = f-1 (K, C) “Easy” if K & C knownP = f-1 (K, C) “Infeasible” if K not known, C known,Diffie-H
14、ellman Key Exchange,A and B agree on two numbers (r, p) A picks a secret number a A computes f(r, p, a) Call result fA A sends B the value fA A computes f(fB, p, a) call result kA,r and p can be public B picks a secret number b B computes f(r, p, b) Call result fB B sends A the value fB B computes f
15、(fA, p, b) call result kB,Correct protocol should ensure that kA = kBkA & kB shoud be hard to predict, knowing r, p, fA, fB and f,But what is f ?,Exercise,Try out kA and kB for f (r, p, x) = r + p + x, r = 3 and p = 12Now crack f (r, p, x) = (r * x) mod p , r = 4, p = 10, fA = 8, fB=6,Discrete Logs,
16、Find x where 3x = 13 mod 17Find x where 3x = 7 mod 13,For: gx =f mod pgiven integers g, f and prime p it is computationally expensive to calculate the discrete log x if p is large, e.g. 200 digits(and if p meets some other conditions hold that shield against know discrete-logarithm attacks),Backgrou
17、nd: primitive roots,Let n be a natural number. Recall: m is co-prime to n iff greatest common divisor of n and m is 1. Example: 5 and 6 are co-prime wheras 3 and 6 are not.Definition: A primitive root modulo n is some integer g such that any number co-prime to n is some power of g modulo n. Formally
18、, g is primitive root of n iff for all m with gcd(n,m) = 1, there is some k such that gk = m (mod n).FACT: Every prime number has a primitive root.Example: 3 is a primitive root of 7. (Verify this.),Diffie-Hellman Key Exchange,r = 5, p = 563,f (r, p, x) = rx mod p p is a very large prime r is a prim
19、itive root of p,kA = (fB)a mod p kA = (rb )a mod p kA = rba mod p,a = 9 fA = ra mod p fA = 59 = 78 mod 563,b = 14 fB = rb mod p fB = 514 = 534 mod 563,kB = (fA)b mod p kB = (ra)b mod p kB = rab mod p,Question,To ensure the correctness of the Diffie-Hellman exchange protocol:What is the key algebraic
20、 property of the function that sends x to rx mod p ?,RSA (Rivest-Shamir-Adleman),Observation: easy to multiply two large primes, p and q: p * q = NVery difficult to factorise N back into p and q.Instrumentation of plain-text prior to encryption: Split large messages into blocks less than p*q in valu
21、e, e.g. for N = 7 * 5 you could use 4-bit blocks,RSA patent expired in September 2000. Hardware RSA 1000 times slower than hardware DES. Software RSA 100 times slower than software DES(similar factors for AES)Remaining question: how to efficiently generate large prime numbers p and q? (You are welco
22、me to research this. E.g. Miller-Rabin randomized algorithm.),RSA,KEY GENERATION Pick two large primes, p and q (keep p and q secret) Calculate N = p * q (result not secret) Calculate (N) = (p 1) * (q 1) Calculate E and D such that E * D = 1 mod (N). E and D must be co-prime to (N) Public Key = (E,
23、N) Private Key = (D, N) ENCRYPTION C = PE mod N DECRYPTION P = CD mod N,Example: KEY GENERATION p = 47, q = 71 N = 47 * 71 = 3337 (N) = (471) * (711) = 3220 E * D = 1 mod 3220 e.g. Encryption key E = 79 e.g. Decryption key D = 1019 Public Key = (79, 3337) Private Key = (1019, 3337) ENCRYPT P = 688 C
24、 = 68879 = 1570 mod 3337 DECRYPT C = 1570 P = 15701019 = 688 mod 3337,RSA,p and q can be destroyed after N, E, and D are generated. Useful for private key holder to keep p and q for faster decryption - can use the Chinese Remainder Theorem to perform calculations mod p and mod q instead of mod pq (N
25、) is Eulers totient function applied to N: the number of numbers less than N that are co-prime to N, e.g. (p*q) = (p-1)*(q-1)Relatively prime means “co-prime”, i.e. that x and y share no common factors, i.e. GCD (x,y)=1,If (N) can be computed efficiently from N, this breaks RSA, how so?,Explanation
26、of equations relating D and E,C = PE mod N P = CD mod N P = (PE)D mod N P = PED mod N (P N) Can we find E, D and N such thatP = PED mod N and also such that it is “Easy” to compute PE and CD, but infeasible to get D given E and N?,Euler showed that P = Pk*(pq)+1 mod (pq) So ED = k*(pq) + 1 Which is
27、equivalent to: ED = 1 mod (pq) D = E-1 mod (pq) D = E-1 mod (p-1)(q-1),Issues,IMPLEMENTATION How to pick two large random primes? (Algorithms are based on probabilistic testing). How to derive E & D? How to quickly compute XY mod N ?(Iterative squaring)UNCONDITIONAL SECURITY A public-key cryptosyste
28、m can never provide Unconditional Security! Why?,ATTACKS Factorise N. Very hard if N is large, e.g. if N has 1024 bits we would need 1015 MIP years. For N having 431 bits, about 500 MIP years Reverse engineer and try to break prime-number generator Timing attacks (ciphertext only). Determine how lon
29、g decryption operations take and make inferences on resulting bits. Counter-measures? Code obfuscation, etc.,Hybrid Cryptosystem,Use RSA to pass an encrypted AES session key, then use AES to encrypt-decrypt subsequent messages,sessionK,C1,C2,RSA,Bobs publicK,C1,RSA,Bobs privateK,sessionK,P,C2,AES,P,
30、AES,Authentication, Integrity, Non-repudiation,AUTHENTICATION Verify the source of a message. - MACs, Digital SignaturesINTEGRITY Has message been tampered with? - MACs, 1-Way Hash Functions, Digital SignaturesNON-REPUDIATION Prevent sender/receiver from later denying sending/receiving a message. -
31、Arbitrated Digital Signatures, Digital Certified Email, Simultaneous Contract Signing,Message Authentication Code (MAC): think of it as a key-based hash functionOne-Way Hash Functions e.g. MD5, SHA (Secure Hash Algorithm)Digital Signatures e.g. RSA, DSS (Digital Signature Standard)Authentication Pro
32、tocols,Symmetric-Key Authentication,AUTHENTICATION Only sender and receiver know secret key. If decrypted message appears “valid” then sender must have sent it? What if message is binary data or is hard to “validate”? We could add a checksum and/or other checks to message (e.g. sequence numbers, tim
33、estamps) to reduce chances that we do not accept a bogus message Such authentication protects A and B from C, but not from each other - Arbitration, Authentication Protocols.,Message Authentication Code (MAC) Also known as a Cryptographic Checksum. Provides Authentication and Integrity Use a secret
34、key to generate a small output block from Message e.g. use AES in CBC mode; last encrypted block acts as a MAC. Best if MAC key is different from secret key MACs are similar to, but not identical with, hash functions,Key,AES,Message P (10 Mb),MAC (128-bits),Digital Signatures,Hand-written Signatures
35、:Do they satisfy these properties?Are their feature needed for digital signatures that have no equivalent or need for hand-written signatures?,AUTHENTIC: Can verify who signed msgUNFORGEABLE: Only signer could have signed msgNOT REUSABLE: Cannot bind signature to different msgUNALTERABLE: Cannot alt
36、er msg without affecting its signature CANNOT BE REPUDIATED: Signer cannot later deny signing.,Digital Signatures,Digital Signatures can be used for encrypted and unencrypted messages.Symmetric-Key digital signature schemes exist but are not elegant (We wont cover them.) Encrypting a message with on
37、es RSA private key yields a digital signature, but signature is as long as the message !,Should be message-dependentShould be sender-dependent (Dependent on information unique to sender)Should be easy to produceShould be easy to verifyShould be infeasible to forgeUseful if signatures can be stored s
38、eparately from signed message,One-Way Hash Functions,Also known as SECURE HASH FUNCTIONS, MESSAGE DIGESTS Provide INTEGRITY only, no key needed (unlike MACs),EXAMPLES MD5 (Message Digest 5) SHA (Secure Hash Algorithm),One-Way Hash Function,Plaintext P (e.g. 10Mb),Hash Value H (e.g. 256 bits),Easy to
39、 produce H from P Size of P Size of H (Compression) Infeasible to produce P from H (One-Way) find P2 such that Hash (P2) = H (Weak Collision Resistance) find P1 & P2 such that Hash(P1)=Hash(P2) (Strong Collision Resistance),Birthday Attack,If hash value is too short then we can employ a birthday att
40、ack. If an element can take on N different values, then we can expect a collision after about sqrt(N) random elements. For N= 2M , we have a collision after about 2M/2 Given a hash value H, to find P, such that Hash (P) = H requires 2M random messages. However to find two P1, P2 such that Hash(P1) a
41、nd Hash(P2) produce the same hash value only requires 2M/2 random messages.,Generate 2M/2 variations of non-fraudulent messageGenerate 2M/2 variations of fraudulent messageProbability of finding a non-fraudulent/fraudulent pair 0.5 Note we can insert space-space-backspace-newline (etc.) sequences to
42、 generate variations CONCLUSION: Use lengthy hash values, e.g. 256 bits Caution: even 265 bits may be insecure, e.g. attacks on SHA-1,Digital Signature,1-Way Hash Function,Plaintext P,Encrypt,Alices Private Key,Signature S,Common technique is to encrypt a one-way Hash Value with Signers Private (Sig
43、ning) Key - AUTHENTICATION + INTEGRITY,Timestamps are often hashed along with message P. Why?,Verifying a Digital Signature,Decrypt,Alices Public Key,1-Way Hash Function,Hash Value H2,H1=H2?,SIGN,Signed Messages,Append,VERIFY,AlicePrivK,E,HF,S,=,AlicePubK,D,HF,Split,S,P,P,P,P,S,P,S,Sending a Signed
44、Encrypted Message,sessionK,RSA,Bobs publicK,C1,C2,AES,P,S,Sign,AlicePrivK,AES,P,S,P,P,AlicePubK,Verify,C1,C2,RSA,Bobs privateK,sessionK,Public-Key Certificates,Combination of a name and Public Key signed by a more trusted, third party,Sign,Alices Name & Public Key,Alices Certificate,Certificates inc
45、lude additional information, e.g. expiration date of public key. What other information would be of interest?,Disavowed Signatures,What if the sender wants to disavow sending a message, e.g. the sender anonymously publishes her private key and then falsely claims that her private key was lost or sto
46、len and that someone else has forged her signature on sent messages e.g. a contract to buy shares which then fall in price?Timestamp messages?,Best if Private Keys are held in tamper-proof devices.,Arbitrated Digital Signature (Unencrypted),1) A T: idA, signA ( idA, signA (P) T: check (idA)verifyA (
47、idA, signA (P)2) T B: signT (timestamp, idA, signA (P)B: verifyT (timestamp, idA, signA(P) check (idA) check (timestamp) verifyA (P)T should also send the second message to A. If A did not originate it, A should own up immediately.,2,1,T,A,B,Some variants of digital signatures,Blind Signatures Sign
48、documents without seeing contents. Undeniable Signatures Cannot be verified without signers consent. Proxy Signatures Pass power to sign to someone else. Group Signatures Any member of a group can sign. Fail-stop Signatures Each public key has many private keys.,Simultaneous Contract Signing Neither party wishes to sign unless others sign as well i.e. simultaneously Digital Certified Mail Receiver must sign a receipt before reading mail Secure Electronic Voting Digital Cash Zero Knowledge, Anonymous Broadcast, Encrypted Computation,Elliptical Curve Cryptography,
