Report

KEY DERIVATION WITHOUT ENTROPY WASTE Yevgeniy Dodis New York University Based on joint works with B. Barak, H. Krawczyk, O. Pereira, K. Pietrzak, F-X. Standaert, D. Wichs and Y. Yu Key Derivation 2 Setting: application P needs m–bit secret key R Theory: pick uniformly random R {0,1}m Practice: have ”imperfect randomness” X {0,1}n physical sources, biometric data, partial key leakage, extracting from group elements (DH key exchange), … Need a “bridge”: key derivation function (KDF) h: {0,1}n {0,1}m s.t. R = h(X) is “good” for P … only assuming X has “minimal entropy” k Formalizing the Problem 3 Ideal Model: pick uniform R Um as the key Assume P is e–secure (against certain class of attackers A) Real Model: use R = h(X) as the key, where = H(X) ≥ k (Pr[X = x] 2− , for all x) Real Security e’ Ideal Security e n m h: {0,1} {0,1} is a (possibly probabilistic) KDF min-entropy(X) Goal: minimize k s.t. P is 2e–secure using R = h(X) minimize entropy loss L = k m (If possible, get information-theoretic security) Note: we design h but must work for any (n, k)-source X Equivalently, Formalizing the Problem 4 Ideal Model: pick uniform R Um as the key h Assume X P is e–secure (against certain class of attackers A) Real Model: use R = h(X) as the key, where = H(X) ≥ k (Pr[X = x] 2− ,Xfor all x) h: {0,1}n {0,1}m is a (possibly probabilistic) KDF min-entropy(X) Goal: minimize k s.t. P is 2e–secure using R = h(X) minimize entropy loss L = k m (If possible, get information-theoretic security) Note: we design h but must work for any (n, k)-source X Equivalently, Old Approach: Extractors 5 Tool: Randomness Extractor [NZ96]. Input: a weak secret X and a uniformly random seed S. Output: extracted key R = Ext(X; S). R is uniformly random, even conditioned on the seed S. (Ext(X; S), S) ≈ (Uniform, S) Many uses in complexity theory and cryptography. Well beyond key derivation (de-randomization, etc.) secret: X seed: S extracted key: Ext R Old Approach: Extractors 6 Tool: Randomness Extractor [NZ96]. Input: a weak secret X and a uniformly random seed S. Output: extracted key R = Ext(X; S). R is uniformly random, even conditioned on the seed S. (Ext(X; S), S) ≈ (Uniform, S) (k,e)-extractor: given any secret (n,k)-source X, outputs m secret bits “e–fooling” any distinguisher D: statistical distance | Pr[D(Ext(X; S), S) =1] – Pr[D(Um, S) =1] | e Extractors as KDFs 7 Lemma: for any e-secure P needing an m–bit key, (k,e)-extractor is a KDF yielding security e’ ≤ 2e LHL [HILL]: universal hash functions are (k,e)-extractors where k = m + 2log(1/e) Corollary: For any P, can get entropy loss 2log(1/e) RT-bound [RT]: for any extractor, k m + 2log(1/e) entropy … loss 2log(1/e) seems necessary or is it? Side-Stepping RT 8 Do we need to derive statististically random R? Yes for one-time pad … No for many (most?) other applications P ! Series of works “beating” RT [BDK+11,DRV12,DY13,DPW13] Punch line: Difference between Extraction and Key Derivation ! New Approach/Plan of Attack 9 Step1. Identify general class of applications P which work “well” with any high-entropy key R Interesting in its own right ! Step2. Build good condenser: relaxation of extractor producing high-entropy (but nonuniform!) derived key R = h(X) Unpredictability Applications 10 Sig, Mac, OWF, … (not Enc, PRF, PRG, …) Example: unforgeability for Signatures/Macs Entropy Assume: Pr[A forges with uniform key] ≤ e (= negl) deficiency Hope: Pr[A forges with high-entropy key] ≤ e’ Lemma: for any e-secure unpredictability appl. P, H(R) ≥ − e’ ≤ 2 e E.g., random R except first bit 0 e’ ≤ 2e Plan of Attack 11 Step1. Argue any unpredictability applic. P works well with (only) a high-entropy key R H(R) ≥ − e’ ≤ 2 e Step2. Build good condenser: relaxation of extractor producing high-entropy (but non-uniform!) derived key R = h(X) Randomness Condensers random 12 (k,d,e)-condenser: given (n, k)-source X, outputs m bits R “e–close” to some (m, m−d)-source Y : (Cond(X; S), S) ≈e (Y, S) and H(Y | S) ≥ m – d Cond + Step1 e’ ≤ (1 + 2 ) e Extractors: d = 0 but only for k m + 2log(1/e) Theorem [DPW13]: d = 1 with k = m + loglog(1/e) + 4 KDF: log(1/e)-independent hash function works! Unpredictability Extractors 13 Theorem: provably secure KDF with entropy loss loglog(1/e) + 4 for all unpredictability applications call such KDFs Unpredictability Extractors Example: CBC-MAC, e = 2-64, m = 128 LHL: k = 256 ; Now: k = 138 Indistinguishability Apps? 14 Impossible for one-time pad Still, similar plan of attack: Step1. Identify sub-class of indist. applications P which work well with (only) a high-entropy key R Weaker, but still useful, inequality: e’ ≤ e(2 − 1) Bonus: works even with “nicer” Renyi entropy Build good condensers for Renyi entropy Much simpler: universal hashing still works ! Step2. Square-Friendly Applications Hermitage State Museum 15 See [BDK+11,DY13] for (natural) definition… All unpredictability applications are SQF Non-SQF applications: OTP, PRF, PRP, PRG [BDK+11,DY13]: many natural indistinguishability applications are square-friendly ! CPA/CCA-enc, weak PRFs, q-wise indep. hash, … End Result (LHL’): universal hashing is provably secure SQF-KDF with entropy loss log(1/e) Square-Friendly Applications Hermitage State Museum 16 See [BDK+11,DY13] for (natural) definition… All unpredictability applications are SQF Non-SQF applications: OTP, PRF, PRP, PRG [BDK+11,DY13]: many natural indistinguishability Example: CBC Encryption, e = 2-64, m = 128 applications are square-friendly ! LHL: k = 256 ; LHL’: k = 192hash, … CPA/CCA-enc, weak PRFs, q-wise indep. End Result (LHL’): universal hashing is provably secure SQF-KDF with entropy loss log(1/e) Efficient Samplability? 17 Theorem [DPW13]: efficient samplability of X does not help to improve entropy loss below 2log(1/e) for all applications P (RT-bound) Affirmatively resolves “SRT-conjecture” from [DGKM12] log(1/e) for all square-friendly applications P loglog(1/e) for all unpredictability applications P Computational Assumptions? 18 Theorem [DGKM12]:,DPW13]: SRT-conjecture efficient Ext beating RT-bound for all computationally bounded D OWFs exist How far can we go with OWFs/PRGs/…? One of the main open problems Current Best [DY13]: “computational” extractor with entropy loss 2log(1/e) log(1/eprg) “Computational” condenser? Summary Difference between extraction and KDF loglog(1/e) loss for all unpredictability apps log(1/e) loss for all square-friendly apps (+ motivation to study “square security”) Efficient samplability does not help Good computational extractors require OWFs Main challenge: better “computational” KDFs