Advanced Cryptography.ppt

1、Advanced Cryptography,Security Computer Science Tripos part 2 Ross Anderson,Advanced Crypto Engineering,Once we move beyond vanilla encryption into creative used of asymmetric crypto and hash functions, all sorts of tricks become possible Its also very easy to shoot your foot off! Framework: Whats t

2、ricky about the maths Whats tricky about the implementation Whats tricky about the protocols etc To roll your own crypto, you need specialist help,Hash Functions,If we want to compute a MAC without using a cipher (e.g. to avoid export controls) we can use HMAC (hash-based message authentication code

3、):HMAC(k,M) = h(k1, h(k2, M)where k1 = k xor 0x5c5c5c5c5c, and k2 = 0x3636363636 (why?) Another app is tick payments make a chain h1 = h(X), h2 = h(h1), ; sign hk; reveal hk-1, hk-2, to pay for stuff A third is timestamping; hash all the critical messages in your organisation in a tree and publish t

4、he result once a day,Public Key Crypto Revision,Digital signatures: computed using a private signing key on hashed data Can be verified with corresponding public verification key Cant work out signing key from verification key Typical algorithms: DSA, elliptic curve DSA Well write sigAX for the hash

5、ed data X signed using As private signing key,Public Key Crypto Revision (2),Public key encryption lets you encrypt data using a users public encryption key She can decrypt it using her private decryption key Typical algorithms Diffie-Hellman, RSA Well write XA Big problem: knowing whose key it is!,

6、PKC Revision Diffie-Hellman,Diffie-Hellman: underlying metaphor is that Anthony sends a box with a message to Brutus But the messengers loyal to Caesar, so Anthony puts a padlock on it Brutus adds his own padlock and sends it back to Anthony Anthony removes his padlock and sends it to Brutus who can

7、 now unlock it Is this secure?,PKC Revision Diffie-Hellman (2),Electronic implementation:A B: MrAB A: MrArBA B: MrB But encoding messages as group elements can be tiresome so instead Diffie-Hellman goes:A B: grAB A: grBA B: MgrArB,PKC Revision El Gamal,Encryption DH can use long-term keys, say priva

8、te key xA and public key yA = gxA The Bob looks up yA and makes the long-term shared key yAxA = gxAxB = yBxA In El Gamal, combine with a transient private key k Bob encrypts M as M.yAk, gk Alice decrypts by forming yAk as (gk)xA,PKC Revision El Gamal (2),Signature trick: given private key xA and pub

9、lic key yA = gxA, and transient private key k and transient public key r = gk, form the private equation rxA + sk = m The digital signature on m is (r,s) Signature verification isg(rxA + sk) = gm i.e. yAr.rs = gm,PKC Revision DSS,The Digital Signature Standard is ElGamal with a few technical weaknes

10、ses fixed p: a prime of 1024 bits; q: a prime dividing p-1; g: an element of order q in the integers mod p Signature on m is (r,s) such thatr = (gk mod p) mod qh(M) = xAr + ks Verification: exercise Only known vuln: choose q = h(M1) - h(M2),Public Key Crypto Revision (3),One way of linking public ke

11、ys to principals is for the sysadmin to physically install them on machines (common with SSH, IPSEC) Another is to set up keys, then exchange a short string out of band to check youre speaking to the right principal (STU-II, Bluetooth simple pairing) Another is certificates. Sam signs Alices public

12、key (and/or signature verification key) CA = sigSTS,L,A,KA,VA But this is still far from idiot-proof,The Denning-Sacco Protocol,In 1982, Denning and Sacco pointed out the revocation problem with Needham-Schroder and argued that public key should be used instead A S: A, B S A: CA, CB A B: CA, CB, sig

13、ATA, KABKB Whats wrong?,The Denning-Sacco Protocol (2),Twelve years later, Abadi and Needham noticed that Bob can now masquerade as Alice to anyone in the world! A S: A, B S A: CA, CB A B: CA, CB, sigATA, KABKB B S: B, C S B: CB, CC B C: CA, CC, sigATA, KABKC,Encrypting email,Standard way (PGP) is t

14、o affix a signature to a message, then encrypt it with a message key, and encrypt the message with the recipients public key A B: KMB, M, sigAh(M)KM X.400 created a detached signature A B: KMB, M KM, sigAh(M) And with XML you can mix and match e.g. by signing encrypted data. Is this good?,Public-key

15、 Needham-Schroeder,Proposed in 1978: A B: NA, AKB B A: NA, NBKA A B: NBKB The idea is that they then use NANB as a shared key Is this OK?,Public-key Needham-Schroeder (2),Attack found eighteen years later, in 1996: A C: NA, AKC C B: NA, AKB B C: NA, NBKA C A: NA, NBKA A C: NBKC C B: NBKB Fix: explic

16、itness. Put all names in all messages,Public Key Protocol Problems,Its also very easy to set up keys with the wrong people man-in-the-middle attacks get more pervasive. Assumptions are slippery to pin down Technical stuff too if the math is exposed, an attacker may use it against you! So data being

17、encrypted (or signed) must be suitably packaged Many other traps, some extremely obscure,PKC Revision RSA,Recall from 1a discrete maths: private key is two large primes p, q Public key is n = pq plus public exponent e Encryption: c = me (mod n) Decryption: m = cd (mod n) This works iff de = 1 (mod(p

18、1)(q-1) Proof: med = m(1+k(p-1)(q-1) = m.1 (mod n) by Eulers theorem Similarly signature s = md (mod n),Extra Vulnerabilities of RSA,Decryption = signature, so sign this to prove who you are is really dangerous Multiplicative attacks: if m3 = m1.m2 then s3 = s1.s2 so its even more important to hash

19、 messages before signature Also before encrypting: break multiplicative pattern by Optimal asymmetric encryption padding. Process key k and random r to X, Y asX = m h(r)Y = r h(X),Fancy Cryptosystems (1),Shared control: if all three directors of a company must sign a cheque, set d = d1 + d2 + d3 Thr

20、eshold cryptosystems: if any k out of l directors can sign, choose polynomial P(x) such that P(0) = d and deg(P) = k-1. Give each a point xi, P(xi) Lagrange interpolation: P(z) = xi(z-xi)/(xj-xi) So signature h(M)P(0) = h(M)xi(z-xi)/(xj-xi) = h(M)xi(),Fancy Cryptosystems (2),Identity-based cryptosys

21、tems: can you have the public key equal to your name? Signature (Fiat-Shamir): let the CA know the factors p, q of n. Let si = h(name,i), and the CA gives you i = si (mod n) Sign M as r2, s = rhi(M)=1 i (mod n) where hi(M) is 1 if the ith bit of M is one, else 0 Verify: check that r2hi(M)=1 si = s2

22、mod n) (Why is the random salt r used here, not just the raw combinatorial product?),Fancy Cryptosystems (3),Elliptic curve cryptosystems use a group of points on an elliptic curve y2 = x3 + ax + b rather than a group mod p Group law: if P, Q, R on a line then P+Q+R = 0 (the point at ) DH, DSA etc

23、go over,Fancy Cryptosystems (4),Elliptic curve crypto makes it even harder to choose good parameters (curve, generator) Also: a lot of implementation techniques are covered by patents held by Certicom OTOH: you can use smaller parameter sizes, e.g. 128-bit keys for equivalent of 64-bit symmetric key

24、s, 256-bit for equivalent of 128 Encryption, signature run much faster Being specified for next-generation Zigbee Also: can do tricks like identity-based encryption,Fancy Cryptosystems (5),Identity-based encryption: some pairs of elliptic curves have bilinear pairing G1 x G1 G2 such that e(aP,bQ) =

25、e(P,Q)ab System secret s; public point P on G1; public key W = sP; user public key gID = e(h(ID),W); private key dID = sID Encrypt M: C = (rW, Mh(gIDr) = (U,V) Decrypt U,V: M = Vh(e(dID,U)= Vh(e(sID,rW)= Vh(e(ID,W)r)= Vh(gID)r,Fancy Cryptosystems (6),Forward secure encryption equipment capture shoul

26、d not compromise old traffic First option: DH to create transient key, then authenticate this Second option (US Defense Messaging System): create one-time ElGamal keys signed using your DSA key and serve them up Third option: use an identity-bases scheme to create a key of the day for each future da

27、y and destroy the corresponding private keys as they expire Can trade algorithms / interactivity / infrastructure,Fancy Cryptosystems (7),Blind signatures: suppose Alice wants Bob the banker to sign a banknote without knowing its serial number. With RSA she sends himM = M.Re (mod n) He sends her S =

28、 Md (mod n) She divides by R to recover Md (mod n) Such digital cash in general illegal, but similar ideas used in digital elections, and in crypto toolkits to combat side-channel attacks,General Problems with PKC,Keys need to be long we can factor / do discrete log to about 700 bits. For DSA/RSA, 1

29、024 is marginal, 2048 considered safe for now Elliptic curve variants can use shorter keys but are encumbered with patents Computations are slow several ms on Pentium, almost forever on 8051 etc Power analysis is a big deal: difference between squaring and doubling is visible. Timing attacks too For

30、 many applications PKC just isnt worth it,TLS,Formerly SSL, became TLS after many bugs fixed: C S: C, C, NC client hello S C: S, S, NS CS server hello C S: k0KS k0 = pre-master secret C S: finished, MACK1(everything to date) S C: finished, MACK2(everything to date) K1, K2 hashed from master secret K

31、1 = h(k0, NC , NS) Formally verified to work but still often used inappropriately (more later),TLS (2),Why doesnt TLS stop phishing? Noticing an absent padlock is hard Understanding URLs is hard Websites train users in bad practice In short, TLS as used in e-commerce dumps compliance costs on users,

32、 who cant cope There are solid uses for it though,Chosen protocol attack,Suppose that we had a protocol for users to sign hashes of payment messages (such a protocol was proposed in 1990s): C M: order M C: X = hash(order, amount, date, ) C M: sigKX How might this be attacked?,Chosen protocol attack (2),The Mafia demands you sign a random challenge to prove your age for porn sites!,