Practical Aspects of Modern CryptographyAttacksSide Channel AttacksTiming AttacksProtocol AttacksSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Direct AttacksSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18FactoringLessonsSlide 21Practical Aspects of Modern CryptographyJosh BenalohBrian LaMacchiaJohn ManferdelliJanuary 14, 2019 Practical Aspects of Modern CryptographyAttacksHow are cryptosystems typically broken?–Back doors–Side doors–Side windows–Crawl spaces–…January 14, 2019 Practical Aspects of Modern CryptographySide Channel AttacksInformation about a secret key can often be divined by careful observation of a device using the key.TimingPower AnalysisAcoustic EmissionsCache Usageetc.January 14, 2019 Practical Aspects of Modern CryptographyTiming AttacksRSA–Each bit of the decryption exponent indicates whether or not to perform a “side multiply”.–“Chinese remaindering” time varies as the argument crosses from slightly below p to slightly above p.AES–Selective flushing of cache lines can cause access times to vary depending on key bits.January 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksHastad Attack on RSAGivenE1(x) = x3 mod n1E2(x) = x3 mod n2E3(x) = x3 mod n3one can easily compute x.January 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksBleichenbacher Attack on RSA PKCS#1PKCS#1 Message Format:00 01 XX XX ... XX 00 YY YY ... YYrandomnon-zerobytesmessageJanuary 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksIf two plaintexts are ever encrypted with the same stream cipher and keyC1 = K P1C2 = K P2an attacker can easily computeC1 C2 = P1 P2from which P1 and P2 can be easily teased apart.January 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksIt is easy for an adversary (even one who can’t decrypt the ciphertext) to alter the plaintext in a known way.Bob to Bob’s Bank: Please transfer $0,000,002.00 to the account of my good friend Alice.January 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksIt is easy for an adversary (even one who can’t decrypt the ciphertext) to alter the plaintext in a known way.Bob to Bob’s Bank: Please transfer $1,000,002.00 to the account of my good friend Alice.January 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksElectronic Code Book (ECB) EncryptionBlockCipherBlockCipherBlockCipherBlockCipherPlaintextCiphertextJanuary 14, 2019 Practical Aspects of Modern CryptographyProtocol AttacksCipher Block Chaining (CBC) Encryption:BlockCipherBlockCipherBlockCipherBlockCipherPlaintextCiphertextIVJanuary 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksHash FunctionsFind a “low-Hamming-weight differential” Δ (a vector of almost all zeros) such that for messages M, the probability that h(MΔ) = h(M) is larger than it should be.January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksBest differential probabilities to dateMD4: ¼MD5: 1/240SHA-1: 1/263January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksLow RSA decryption exponentIt turns out that if the RSA decryption exponent is less than n¼, then n can be trivially factored given only the encryption exponent.January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksFactoringIf n=pq – the product of distinct odd primes, then every square modulo n, has four distinct square roots.If y=x2 mod n, then x and –x are both square roots of y.If y=x2 mod n, then y=x2 mod p and y=x2 mod q.There are four ways to “Chinese remainder” ±x mod p with ±x mod q.January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksFactoringSuppose I have x1 ≠ ±x2 such that x12 = x22 mod n.Then x1 ≠ x2 mod p and x1 ≠ –x2 mod q (or vice-versa).GCD(x1 – x2, n) will therefore produce a non-trivial factor of n.January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksFactoringHow can I get two distinct values that have the same square modulo n?Try, x≈√n, x≈√2n , x≈√3n , …If I get, say, x2 mod n = 49, I’m really happy.January 14, 2019 Practical Aspects of Modern CryptographyDirect AttacksFactoringIf I get, x12 mod n = 12 and x22 mod n = 3, I’m happy too because (x1x2)2 mod n = 36. In general, look for lots of values x such that x2 mod n is “small” and try to combine the small values to get a square.January 14, 2019 Practical Aspects of Modern CryptographyFactoring2 3 5 7 11 13x121 1x222 1x321 2x422 1 1 1x521 1x622 1Note that (x1x3x5x6)2 = 223254112= (235211)2.January 14, 2019 Practical Aspects of Modern CryptographyLessonsNew attacks must be recognized as a fact of cryptography.This makes cryptographic code unique in that a carefully-built, closed system that works perfectly today may become vulnerable tomorrow.Cryptographic constructs must be built with agility in mind so that they can be easily updated if and when it becomes necessary.January 14, 2019 Practical Aspects of Modern
View Full Document