Transcription
Online Cryptography CourseDan BonehStream ciphersThe One Time PadDan Boneh
Symmetric Ciphers: definitionDef: a cipher defined overis a pair of “efficient” algs (E, D) where E is often randomized.D is always deterministic.Dan Boneh
The One Time Pad(Vernam 1917)First example of a “secure” cipherkey (random bit string as long the message)Dan Boneh
The One Time Pad(Vernam 1917)msg: 0 1 1 0 1 1 1key: 1 0 1 1 0 1 0 CT:Dan Boneh
You are given a message (m) and its OTP encryption (c).Can you compute the OTP key from m and c ?No, I cannot compute the key.Yes, the key is k m c.I can only compute half the bits of the key.Yes, the key is k m m.Dan Boneh
The One Time Pad(Vernam 1917)Very fast enc/dec !! but long keys (as long as plaintext)Is the OTP secure? What is a secure cipher?Dan Boneh
What is a secure cipher?Attacker’s abilities: CT only attack(for now)Possible security requirements:attempt #1: attacker cannot recover secret keyattempt #2: attacker cannot recover all of plaintextShannon’s idea:CT should reveal no “info” about PTDan Boneh
Information Theoretic Security(Shannon 1949)Dan Boneh
Information Theoretic SecurityDef: A cipher (E,D) over (K,M,C) has perfect secrecy if m0, m1 M ( m0 m1 ) and c CPr[ E(k,m0) c ] Pr[ E(k,m1) c ]where k KRDan Boneh
Lemma: OTP has perfect secrecy.Proof:Dan Boneh
None12Dan Boneh
Lemma: OTP has perfect secrecy.Proof:Dan Boneh
The bad news Dan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersPseudorandomGeneratorsDan Boneh
ReviewCipher over (K,M,C): a pair of “efficient” algs (E, D) s.t. m M, k K: D(k, E(k, m) ) mWeak ciphers: subs. cipher, Vigener, A good cipher: OTPM C K {0,1}nE(k, m) k m ,D(k, c) k cLemma: OTP has perfect secrecy (i.e. no CT only attacks)Bad news: perfect-secrecy key-len msg-lenDan Boneh
Stream Ciphers: making OTP practicalidea: replace “random” key by “pseudorandom” keyDan Boneh
Stream Ciphers: making OTP practicalDan Boneh
Can a stream cipher have perfect secrecy?Yes, if the PRG is really “secure”No, there are no ciphers with perfect secrecyYes, every cipher has perfect secrecyNo, since the key is shorter than the message
Stream Ciphers: making OTP practicalStream ciphers cannot have perfect secrecy !! Need a different definition of security Security will depend on specific PRGDan Boneh
PRG must be unpredictableDan Boneh
PRG must be unpredictablenWe say that G: K {0,1} is predictable if:Def: PRG is unpredictable if it is not predictable i: no “eff” adv. can predict bit (i 1) for “non-neg” εDan Boneh
Suppose G:K {0,1}n is such that for all k: XOR(G(k)) 1Is G predictable ?Yes, given the first bit I can predict the secondNo, G is unpredictableYes, given the first (n-1) bits I can predict the n’th bitIt dependsDan Boneh
Weak PRGs(do not use for crypto)glibc random():r[i ( r[i-3] r[i-31] ) % 232output r[i] 1Dan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersNegligible vs.non-negligibleDan Boneh
Negligible and non-negligible In practice: ε is a scalar and– ε non-neg:ε 1/230(likely to happen over 1GB of data)– ε negligible:ε 1/280(won’t happen over life of key) In theory: ε is a function ε: Z 0 R 0 and– ε non-neg: d: ε(λ) 1/λd inf. often(ε 1/poly, for many λ)– ε negligible: d, λ λd: ε(λ) 1/λd(ε 1/poly, for large λ)Dan Boneh
Few Examplesε(λ) 1/2λ : negligibleε(λ) ε(λ) 1/λ1000 : non-negligible1/2λfor odd λ1/λ1000 for even λNegligibleNon-negligibleDan Boneh
PRGs: the rigorous theory viewPRGs are “parameterized” by a security parameter λ PRG becomes “more secure” as λ increasesSeed lengths and output lengths grow with λFor every λ 1,2,3, there is a different PRG Gλ:Gλ : Kλ {0,1}n(λ)(in the lectures we will always ignore λ )Dan Boneh
An example asymptotic definitionWe say that Gλ : Kλ {0,1}n(λ)is predictable at position i if:there exists a polynomial time (in λ) algorithm A s.t.Prk Kλ[ A(λ, Gλ(k)) 1, ,iGλ(k)i 1] 1/2 ε(λ)for some non-negligible function ε(λ)Dan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersAttacks on OTP andstream ciphersDan Boneh
ReviewOTP:E(k,m) m k,D(k,c) c kMaking OTP practical using a PRG:Stream cipher:G: K {0,1}nE(k,m) m G(k)Security: PRG must be unpredictable,D(k,c) c G(k)(better def in two segments)Dan Boneh
Attack 1: two time pad is insecure !!Never use stream cipher key more than once !!C1 m1 PRG(k)C2 m2 PRG(k)Eavesdropper does:C1 C2 m1 m2Enough redundancy in English and ASCII encoding that:m1 m2 m1 , m 2Dan Boneh
Real world examples Project Venona MS-PPTP (windows NT):kkNeed different keys for C S and S CDan Boneh
Real world examples802.11b WEP:mkCRC(m)PRG( IV ll k )IVkciphetextLength of IV: 24 bits Repeated IV after 224 16M frames On some 802.11 cards: IV resets to 0 after power cycleDan Boneh
Avoid related keys802.11b WEP:mkPRG( IV ll k ) kciphetextIVkey for frame #1:key for frame #2:CRC(m)(1 ll k)(2 ll k)Dan Boneh
A better constructionkkPRG now each frame has a pseudorandom keybetter solution: use stronger encryption method (as in WPA2)Dan Boneh
Yet another example: disk encryptionDan Boneh
Two time pad: summaryNever use stream cipher key more than once !! Network traffic: negotiate new key for every session (e.g. TLS) Disk encryption: typically do not use a stream cipherDan Boneh
Attack 2: no integritymenc ( k )(OTP is malleable)m kpm pdec ( k ) (m k) pModifications to ciphertext are undetected andhave predictable impact on plaintextDan Boneh
Attack 2: no integrityFrom: Bobenc ( k )(OTP is malleable)From: Bob From: Evedec ( k ) From: EveModifications to ciphertext are undetected andhave predictable impact on plaintextDan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersReal-world StreamCiphersDan Boneh
Old example (software): RC4128 bits(1987)2048 bitsseed1 byteper round Used in HTTPS and WEP Weaknesses:1. Bias in initial output: Pr[ 2nd byte 0 ] 2/2562. Prob. of (0,0) is 1/2562 1/25633. Related key attacksDan Boneh
Old example (hardware): CSS(badly broken)Linear feedback shift register (LFSR):DVD encryption (CSS): 2 LFSRsGSM encryption (A5/1,2): 3 LFSRsBluetooth (E0): 4 LFSRsall brokenDan Boneh
Old example (hardware): CSSCSS:(badly broken)seed 5 bytes 40 bitsDan Boneh
Cryptanalysis of CSS17-bit LFSR8 25-bit LFSR(mod 256)88(217 time attack) encrypted movieprefixCSS prefixFor all possible initial settings of 17-bit LFSR do: Run 17-bit LFSR to get 20 bytes of output Subtract from CSS prefix candidate 20 bytes output of 25-bit LFSR If consistent with 25-bit LFSR, found correct initial settings of both !!Using key, generate entire CSS outputDan Boneh
Modern stream ciphers:PRG:eStream{0,1}s R {0,1}nNonce: a non-repeating value for a given key.E(k, m ; r) m PRG(k ; r)The pair (k,r) is never used more than once.Dan Boneh
eStream: Salsa 20(SW HW)Salsa20: {0,1} 128 or 256 {0,1}64 {0,1}n(max n 273 bits)Salsa20( k ; r) : H( k , (r, 0)) ll H( k , (r, 1)) ll kri32 bytesτ0kτ1rhiτ2(10 rounds)kτ3 64 bytes 64 byteoutput64 bytesh: invertible function. designed to be fast on x86 (SSE2)Dan Boneh
Is Salsa20 secure(unpredictable) ? Unknown: no known provably secure PRGs In reality: no known attacks better than exhaustive searchDan Boneh
Performance:AMD Opteron, 2.2 GHzeStreamCrypto 5.6.0[ Wei Dai ]( Linux)PRGSpeed (MB/sec)RC4126Salsa20/12643Sosemanuk727Dan Boneh
Generating Randomness(e.g. keys, IV)Pseudo random generators in practice: (e.g. /dev/random) Continuously add entropy to internal state Entropy sources: Hardware RNG: Intel RdRand inst. (Ivy Bridge). 3Gb/sec. Timing: hardware interrupts (keyboard, mouse)NIST SP 800-90:NIST approved generatorsDan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersPRG Security DefsDan Boneh
Let G:K {0,1}n be a PRGGoal: define what it means thatis “indistinguishable” fromDan Boneh
Statistical TestsStatistical test on {0,1}n:an alg. A s.t. A(x) outputs “0” or “1”Examples:Dan Boneh
Statistical TestsMore examples:Dan Boneh
AdvantageLet G:K {0,1}n be a PRG and A a stat. test on {0,1}nDefine:A silly example: A(x) 0 AdvPRG [A,G] 0Dan Boneh
Suppose G:K {0,1}n satisfies msb(G(k)) 1 for 2/3 of keys in KDefine stat. test A(x) as:if [ msb(x) 1 output “1” else output “0”ThenAdvPRG [A,G] Pr[ A(G(k)) 1]- Pr[ A(r) 1 ] 2/3 – 1/2 1/6Dan Boneh
Secure PRGs: crypto definitionnDef: We say that G:K {0,1}is a secure PRG ifAre there provably secure PRGs?but we have heuristic candidates.Dan Boneh
Easy fact:We show:a secure PRG is unpredictablePRG predictable PRG is insecureSuppose A is an efficient algorithm s.t.for non-negligible ε (e.g. ε 1/1000)Dan Boneh
Easy fact:a secure PRG is unpredictableDefine statistical test B as:Dan Boneh
Thm (Yao’82):an unpredictable PRG is secureLet G:K {0,1}n be PRG“Thm”:if i ,0, , n-1} PRG G is unpredictable at pos. ithen G is a secure PRG.If next-bit predictors cannot distinguish G from randomthen no statistical test can !!Dan Boneh
Let G:K {0,1}n be a PRG such thatfrom the last n/2 bits of G(k)it is easy to compute the first n/2 bits.Is G predictable for some i ,0, , n-1} ?YesNo
More GenerallyLet P1 and P2 be two distributions over {0,1}nDef: We say that P1 and P2 arecomputationally indistinguishable (denoted)RExample: a PRG is secure if { k K: G(k) } p uniform({0,1}n)Dan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersSemantic securityGoal: secure PRG “secure” stream cipherDan Boneh
What is a secure cipher?Attacker’s abilities: obtains one ciphertext(for now)Possible security requirements:attempt #1: attacker cannot recover secret keyattempt #2: attacker cannot recover all of plaintextRecall Shannon’s idea:CT should reveal no “info” about PTDan Boneh
Recall Shannon’s perfect secrecyLet (E,D) be a cipher over (K,M,C)(E,D) has perfect secrecy if{ E(k,m0) } m0, m1 M ( m0 m1 ) { E(k,m1) }(E,D) has perfect secrecy ifwhere k K m0, m1 M ( m0 m1 ){ E(k,m0) } p { E(k,m1) }where k K but also need adversary to exhibit m0, m1 M explicitlyDan Boneh
Semantic Security (one-time key)For b 0,1 define experiments EXP(0) and EXP(1) as:bChal.k KAdv. Am0 , m1 M : m0 m1 c E(k, mb)for b 0,1: Wb : [ event that EXP(b) 1 ]AdvSS[A,E] : Pr[ W0 Pr[ W1 ] b’ {0,1} [0,1]Dan Boneh
Semantic Security (one-time key)Def: E is semantically secure if for all efficient AAdvSS[A,E]is negligible. for all explicit m0 , m1 M :{ E(k,m0) } p{ E(k,m1) }Dan Boneh
ExamplesSuppose efficient A can always deduce LSB of PT from CT. E (E,D) is not semantically secure.b {0,1}Chal.k Km0,m1,LSB(m0) 0LSB(m1) 1C E(k, mb)Adv. B (us)CAdv. A(given)LSB(mb) bThen AdvSS[B, E] Pr[ EXP(0) 1 Pr[ EXP(1) 1 ] 0 – 1 1Dan Boneh
OTP is semantically secureEXP(0):Chal.k Km0 , m1 M : m0 m1 Adv. Ac k m0b’ {0,1}identical distributionsEXP(1):Chal.k Km0 , m1 M : m0 m1 c k m1Adv. Ab’ {0,1}For all A: AdvSS[A,OTP] Pr[ A(k m0) 1 Pr[ A(k m1) 1 ] 0Dan Boneh
End of SegmentDan Boneh
Online Cryptography CourseDan BonehStream ciphersStream ciphers aresemantically secureGoal: secure PRG semantically secure stream cipherDan Boneh
Stream ciphers are semantically secureThm: G:K {0,1}n is a secure PRG stream cipher E derived from G is sem. sec. sem. sec. adversary A , a PRG adversary B s.t.AdvSS*A,E 2 AdvPRG[B,G]Dan Boneh
Proof: intuitionchal.k Km0 , m1adv. Ac m0 G(k) pchal.r {0,1}nm0 , m1c m0 rb’ 1 pchal.k Km0 , m1adv. Ac m1 G(k)b’ 1 pchal.r {0,1}nadv. Am0 , m1b’ 1adv. Ac m1 rb’ 1Dan Boneh
Proof: Let A be a sem. sec. adversary.Chal.bk Kr {0,1}nm0 , m1 M : m0 m1 Adv. Ac mb G(k)b’ {0,1}For b 0,1: Wb : * event that b’ 1 .AdvSS[A,E] Pr[ W0 Pr[ W1 ] Dan Boneh
Proof: Let A be a sem. sec. adversary.Chal.bk Kr {0,1}nm0 , m1 M : m0 m1 Adv. Ac mb rb’ {0,1}For b 0,1: Wb : * event that b’ 1 .AdvSS[A,E] Pr[ W0 Pr[ W1 ] For b 0,1: Rb : * event that b’ 1 ]Dan Boneh
Proof: Let A be a sem. sec. adversary.Claim 1:Claim 2:0 Pr[R0] – Pr[R1] B: Pr[Wb] – Pr[Rb] Pr[W0]Pr[Rb]Pr[W1]1 AdvSS[A,E] Pr[W0] – Pr[W1] 2 AdvPRG[B,G]Dan Boneh
Proof of claim 2: B: Pr[W0] – Pr[R0] AdvPRG[B,G]Algorithm B:y {0,1}nPRG adv. B (us)m0, m1b’ {0,1}c m0 yAdv. A(given)AdvPRG[B,G] Dan Boneh
End of SegmentDan Boneh
all broken . Dan Boneh Old example (hardware): CSS (badly broken) CSS: seed 5 bytes 40 bits . Dan Boneh Cryptanalysis of CSS . In reality: no known attacks better than exhaustive search . Dan Boneh Performance: Crypto 5.6.0 [ Wei Dai ] AMD Opteron, 2.2 GHz ( Linux) PRG .