Class 25: Class 25: Security Security through through Complexity?Complexity?Karsten NohlKarsten Nohlcs302: Theory of Computationcs302: Theory of ComputationUniversity of Virginia, Computer ScienceUniversity of Virginia, Computer SciencePS6 is due today.Lorenz cipher used in WWII2Lecture 25: Complex --> Secure?Motivation• Many applications require certain tasks to be easy for some and hard for others• Example: Decryption of encrypted message is easy only when given a secret keyCryptography is concerned with constructing algorithms that withstand abuse. -GoldreichComplexity is a powerful tool to “lock out” adversaries.Basic Idea: Require hard problem to be solved, give hint as key.3Lecture 25: Complex --> Secure?NP can be useful• So far, you learnt how to detect “unsolvable”problems (in NP) and solve them anyway by approximation (in P)• For cryptography we want the opposite:problems that are almost always hard, i.e., cannot be approximated in P 4Lecture 25: Complex --> Secure?[Breaking a strong cipher should require]“as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type”- Shannon, ‘49 Sounds NP-Complete, doesn’t it?5Lecture 25: Complex --> Secure?Goal: Encryption• For almost all security schemes we need:– Encryption / one-way functioneasy to compute:hard to find any part of:• Often also required:– Decryptionenc(x,k)→yx,k = enc−1( y)secret keydec(y,k)→xMake this an NP problem6Lecture 25: Complex --> Secure?Encryption build on Hardness• Knapsack problem is NP-Complete– Problem of filing bag with best selection of items– Recall: Reducible from Subset-Sum• Enable Encryption: Keep message secret by hiding it in a Knapsack instance ∑==niiiaxs1bits of encryption key = knapsack instancemessage bitsDecryption possible by knowing easy knapsack instance (secret key) that provides shortcut.7Lecture 25: Complex --> Secure?Flawed Security Argument• Subset Sum is NP-Complete• Breaking knapsack cipher involves solving a subset sum problem• Therefore, knapsack cipher is secureFlaw: NP-Complete means there is no fast general solution. Some instances may be solved quickly.(Note: Adi Shamir broke knapsack cipher [1982])8Lecture 25: Complex --> Secure?Cipher Design• NP-Completeness is not sufficient for cryptographic hardness Worst-case complexity• Need solution to usually be hardAverage complexity• Captured in new complexity class:All tractable problems are in BPP(which only makes sense if P≠NP)probabilistic: can flip coins9Lecture 25: Complex --> Secure?Cipher Design (cont.)• A “strong” cipher cannot be broken faster than exhaustive key search (brute force)• Only possible shortcut:Trade space for time; e.g.:Θ(2n) timeΘ(2n⋅⅔) time + space10Lecture 25: Complex --> Secure?Results of Insufficient Hardness• All broken cipher have a gap between worst-case and average hardness• Estimating average hardness is often impossible (= finding best algorithm for instances of NP-complete problem)• Next: Analyze cipher, identify complexity, and break it by finding tractable average solution. 11Lecture 25: Complex --> Secure?Proprietary Cryptography(or: why “security-by-obscurity” never works)12Lecture 25: Complex --> Secure?First: Disclosure• Secret algorithm can often be found:– Disassembling software– Hardware reverse-engineeringIDA ProThis talk: Breaking a cipher once we found it.This talk: Breaking a cipher once we found it.13Lecture 25: Complex --> Secure?Then: Exploitation• Most secret ciphers are broken after disclosure• Flaws are very similar in all DIY ciphers(and cryptanalyst spot them in a glimpse)“No more weak ciphers. No more paranoia.”Sean O’Neil14Lecture 25: Complex --> Secure?The crux of most flaws• Most weaknesses caused by insufficient non-linearity.• At the heart of the problem:LFSRs (linear feedback shift register)tmp = x[12]^x[15]^x[16]^x[17];for i=17:-1:1 x[i]=x[i-1];x[0] = tmp;tmp = x[12]^x[15]^x[16]^x[17];for i=17:-1:1 x[i]=x[i-1];x[0] = tmp;15Lecture 25: Complex --> Secure?Non-Linearity• System of equations that desribes n-bit cipher can have up to O(2n) terms.• Only O(n) of these terms are linear.Linear ≈ PNon-linear ≈ NP16Lecture 25: Complex --> Secure?Mifare Crypto-1fc(∙)fc(∙)…High degree (20) generator, very non-linear! ✔High degree (20) generator, very non-linear! ✔Many taps in LFSR ✔Still linear ✗Many taps in LFSR ✔Still linear ✗Cascaded structure allows for low degree description after all! :PCascaded structure allows for low degree description after all! :PWork with Nicolas Courtois, Sean O’Neil17Lecture 25: Complex --> Secure?fc(∙)fc(∙)a[0] a[1] a[2] a[3] a[4]tmp = x[0]^...^x[43];for i=1:47 x[i]=x[i+1];x[48] = tmp;tmp = x[0]^...^x[43];for i=1:47 x[i]=x[i+1];x[48] = tmp;a[0] = fa(x[7],x[9],x[11],x[13]);a[1] = ......y = fc(a[0],a[1],a[2],a[3],a[4]) a[0] = fa(x[7],x[9],x[11],x[13]);a[1] = ......y = fc(a[0],a[1],a[2],a[3],a[4]) Compute equations for first output bit:Before computing next bit, shift LFSR:yDescribes cipher as system of equations with 48+r5 unknowns, terms with degree ≤ 4!Describes cipher as system of equations with 48+r5 unknowns, terms with degree ≤ 4!18Lecture 25: Complex --> Secure?Almost there …1. Describe weak parts of cipher as system of equations2. Brute-Force through complex parts:Guess-and-Determine attack.3. Solve system of equations: MiniSAT is our friendSolving for 48-bit Crypto-1 key takes 12 seconds;compared to month for brute-force.19Lecture 25: Complex --> Secure?Lessons Learned (Crypto)• Obscurity and proprietary crypto add security only in the short-run– (but lack of peer-review hurts later)• Constraints of small devices make good crypto extremely hard– Where are the best trade-offs?– How much security is needed?– How can we best introduce non-linearity?20Lecture 25: Complex --> Secure?Lessons Learned (Complexity)• Cannot rely on hardness of problems; gap between average and worst-case instances often significant• This is good news unless you are building cryptography: – Can solve many instances of NP-complete problems in limited time• Mathematicians have done most of the work already: start using MiniSAT21Lecture 25: Complex --> Secure?Don’t forget to hand in