Practical Aspects of Modern CryptographyJosh BenalohBrian LaMacchiaJohn ManferdelliMarch 7, 2006 Practical Aspects of Modern CryptographyAttacks♦ How are cryptosystems typically broken?– Back doors– Side doors– Side windows– Crawl spaces–…March 7, 2006 Practical Aspects of Modern CryptographySide Channel AttacksInformation about a secret key can often be divined by careful observation of a device using the key.♦ Timing♦ Power Analysis♦ Acoustic Emissions♦ Cache Usage♦ etc.March 7, 2006 Practical Aspects of Modern CryptographyTiming Attacks♦ RSA– 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.March 7, 2006 Practical Aspects of Modern CryptographyProtocol AttacksHastad Attack on RSAGivenE1(x) = x3mod n1E2(x) = x3mod n2E3(x) = x3mod n3one can easily compute x.March 7, 2006 Practical Aspects of Modern CryptographyProtocol AttacksBleichenbacher Attack on RSA PKCS#1PKCS#1 Message Format:00 01 XX XX ... XX 00 YY YY ... YYrandomnon-zerobytesmessageMarch 7, 2006 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 P1and P2can be easily teased apart.March 7, 2006 Practical Aspects of Modern CryptographyProtocol Attacks♦ It 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.March 7, 2006 Practical Aspects of Modern CryptographyProtocol Attacks♦ It 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.March 7, 2006 Practical Aspects of Modern CryptographyProtocol AttacksElectronic Code Book (ECB) EncryptionBlockCipherBlockCipherBlockCipherBlockCipherPlaintextCiphertextMarch 7, 2006 Practical Aspects of Modern CryptographyProtocol AttacksCipher Block Chaining (CBC) Encryption:BlockCipherBlockCipherBlockCipherBlockCipherPlaintextCiphertextIVMarch 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksHash Functions♦ Find 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.March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksBest differential probabilities to date♦ MD4: ¼♦ MD5: 1/240♦ SHA-1: 1/263March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksLow RSA decryption exponent♦ It turns out that if the RSA decryption exponent is less than n¼, then n can be trivially factored given only the encryption exponent.March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksFactoring♦ If n=pq – the product of distinct odd primes, then every square modulo n, has four distinct square roots.♦ If y=x2mod n, then x and –x are both square roots of y.♦ If y=x2mod n, then y=x2mod p and y=x2mod q.♦ There are four ways to “Chinese remainder” ±x mod p with ±x mod q.March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksFactoring♦ Suppose I have x1≠ ±x2such that x12= x22mod n.♦ Then x1≠ x2mod p and x1≠ –x2mod q (or vice-versa).♦ GCD(x1 – x2, n) will therefore produce a non-trivial factor of n.March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksFactoring♦ How can I get two distinct values that have the same square modulo n?♦ Try, x≈√n, x≈√2n, x≈√3n, …♦ If I get, say, x2mod n = 49, I’m really happy.March 7, 2006 Practical Aspects of Modern CryptographyDirect AttacksFactoring♦ If I get, x12mod n = 12 and x22mod n = 3, I’m happy too because (x1x2)2mod n = 36. ♦ In general, look for lots of values x such that x2mod n is “small” and try to combine the small values to get a square.March 7, 2006 Practical Aspects of Modern CryptographyFactoring12x6211x521112x4221x3212x2211x1213117532Note that (x1x3x5x6)2= 22×32×54×112= (2×3×52×11)2.March 7, 2006 Practical Aspects of Modern CryptographyLessons♦ New 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.March 7, 2006 Practical Aspects of Modern
View Full Document
Unlocking...