Sustained Space Complexity Jol Alwen (IST Austria/Wickr) Jeremiah Blocki (Purdue) Krzysztof Pietrzak (IST Austria) Crypto Reading Group 2019 1 Motivation: Password Storage jblocki, 123456 Username Salt jblocki

+ 89d978034a3f 6 Hash 85e23cfe0021f584 e3db87aa72630a9 a2345c062 SHA1(12345689d978034a3f6)=85e2 3cfe0021f584e3db87aa72630a9a234 5c062

2 Offline Attacks: A Common Problem Password breaches at major companies have affected millions billions of user accounts. Offline Attacks: A Common Problem Password breaches at major companies have affected millions billions of user accounts. Goal: Moderately Expensive Hash Function Fast on PC and Expensive on ASIC?

(2013-2015) https://password-hashing.net/ We recommend that you use Argon2 (2013-2015) https://password-hashing.net/ We recommend that you use Argon2 (2013-2015)

https://password-hashing.net/ There are two main versions of Argon2, Argon2i and Argon2d. Argon2i is the safest against side-channel attacks Memory Hard Function (MHF) Intuition: computation costs dominated by memory costs vs. Goal: force attacker to lock up large amounts of memory for duration of computation Expensive even on customized hardware

Memory Hard Function (MHF) Intuition: computation costs dominated by memory costs vs. Memory Hard Function (MHF) Intuition: computation costs dominated by memory costs vs. Memory Hard Function (MHF) Intuition: computation costs dominated by memory costs vs. Data Independent Memory Hard Function (iMHF)

Memory access pattern should not depend on input Memory Hard Function (MHF) Intuition: computation costs dominated by memory costs vs. Data Independent Memory Hard Function (iMHF) Memory access pattern should not depend on input Data-Independent Memory Hard Function (iMHF) iMHF fG,H defined by H: (Random Oracle) DAG G

(encodes datadependencies) Maximum indegree: Input: pwd, salt 2 1 1= ( , ) 4 3 Output: fG,H (pwd,salt)= L4

3=( 2, 1) Evaluating an iMHF (pebbling) Input: 1 pwd, salt 2 1= ( , ) 4 Output: L4

3 3=( 2, 1) Pebbling Rules : =P1,,Pt s.t. Pi+1(need dependent values) nPt (must finish and output Ln)

Evaluating an iMHF (pebbling) 1 2 3 4 5 Evaluating an iMHF (pebbling)

1 P1 = {1} 2 3 4 5 (data value L1 stored in memory)

Pebbling Example 1 P1 = {1} P2 = {1,2} 2 3 4 5

(data values L1 and L2 stored in memory) Pebbling Example 1 P1 = {1} P2 = {1,2} P3 = {3} 2 3

4 5 Pebbling Example 1 P1 = {1} P2 = {1,2} P3 = {3} P4 = {3,4}

2 3 4 5 Pebbling Example 1 P1 = {1} P2 = {1,2}

P3 = {3} P4 = {3,4} P5 = {5} 2 3 4 5 Measuring Cost: Attempt 1 Space Time (ST)-Complexity

Rich Theory ST Cost m space Space-time tradeoffs But not appropriate for password hashing time t Amortization and Parallelism

space Problem: for parallel computation ST-complexity can scale badly in the number of evaluations of a function. S3 S1 ST1 = S1 T1 S3 T3 = ST3 cost of computing f once time

T1 T3 [AS15] function fn (consisting of n RO calls) such that: cost of computing f three times Measuring Pebbling Costs [AS15] Memory Used at Step i Cumulative Memory Cost

space Approximates Amortized Area x Time Complexity of iMHF iterations Measuring Pebbling Costs [AS15] Memory Used at [AS15] scale linearly with #passwordStep

guesses i times Pebbling Example: Cumulative Cost 1 P1 = {1} P2 = {1,2} P3 = {3} P4 = {3,4} P5 = {5}

2 3 4 5 Lessons from SCRYPT SCRYPT [Per09] CON: Data-Dependent Side-Channel Concerns

PRO: Proven to have high CC [ACPRT17] CC(SCRYPT) = Contrast: any iMHF has CC at most Maximally Memory Hard Egalitarian? 27 What Happened? CC(SCRYPT) = the function can be computed with low memory Each strategy below is easily feasible Evaluate with memory in time Evaluate with memory in time

Evaluate with memory in time SCRYPT ASIC miners opt for low memory + high computation options Goal: Ensure that low memory options are infeasible 28 Sustained Space Using memory is more costly than doing computation (at least for ASICs). Idea: Only charge for computational steps where a lot of

memory is being used. Definition: s-Sustained Space Time spent above memory threshold s space s-Sustained Space Intuition: trade-offs are free. s time

FACT: Wanted: A Moderately Hard Function Desiderata: Cost for honest & adversary roughly same: Honest Computational Model Sequential Computation Single Evaluation Cost measured in ST Complexity

Adversarial Model Parallel Computation Amortization across many evaluations Cost measured in s-SS (for some large s) Main Theorem For any n we give a function fn and prove that in the parallel Random Oracle Model (PROM): Honest Adversarial

Sequential Algorithm E parallel algs. A Time(E(fn)) = n s-SS(A(fn)) = (n) per eval. ST(E(fn)) = n2 for s = (n/log(n)) Bonus: fn is an iMHF. E runs in constant time and has data-independent memory access pattern

The Parallel Black Pebbling Game Parallel Black Pebbling Game: Same as Black Pebbling, except can touch many pebbles per iteration. Goal: Place a pebble on the sink. Rule 1: A node can be pebbled only if all parents contain a pebble. Rule 2: A pebble can always be removed. s-SS analogue: Count number of steps when at least s pebbles on graph. Want G with s-SS Complexity 1-SS = 3 2-SS = 1

G 1. Size(G) = n 2. In-degree(G) = 2 3. -SS(G) = (n) Technical Ingredient #1 [PTC77] [PTC77] Built a constant indegree DAG G with n nodes

and proves that any sequential pebbling has at least one step in which there are at least pebbles on the graph. [Hopcroft77] Any constant indegree graph DAG G can be pebbled with space at most 33 Technical Ingredient #1 [PTC77] [PTC77] Built a constant indegree

DAG G space complexity Recursive Construction PTC2n contains 2 internal copies of PTCn Stronger Lemma used for Induction! For any sequential pebbling We can find an interval such that both 1. for each 2. At least source nodes are (re)pebbled during the interval

34 Technical Ingredient #1 [PTC77] [PTC77] Built a constant indegree DAG G space complexity Recursive Construction PTC2n contains 2 internal copies of PTCn Stronger Lemma used for Induction! For any parallel (sequential) pebbling Can find an interval such that 1. 2.

for each (lots of pebbles on the graph) At least source nodes are (re)pebbled during the interval Implication (): s-SS(P) Sequential Pebbling: (by (2) above) Parallel Pebbling: Could (re)pebble all in one step! 35 Depth Robustness [ABP17]

Definition: A DAG G=(V,E) is (e,d)-depth-robust for all s.t. we have Otherwise, we say that G is (e,d)-reducible. Example: (e=2,d=2)-reducible 1 2 3 4 5

6 Block Depth Robustness [ABP17] Definition: A DAG G=(V,E) is (e,d)-depth-robust for all s.t. we have Otherwise, we say that G is (e,d)-reducible. Example: (e=2,d=2)-reducible 1 2 3

4 5 6 Technical Ingredient #2 Definition: A DAG is -extremely depth robust if it is (e,d)-depth-robust for all . [EGS75] n node G with log(n) in-degree and ((n), (n))-depthrobust Problem: Constants too small e.g., and Problem: in-degree too high. [MMV13] -extremely depth robust DAG with log2(n) in-degree

and (e,d)-DR for any e+d < n(1-).). Problem: in-degree too high. 38 Technical Ingredient #2 Definition: A DAG is -extremely depth robust if it is (e,d)-depth-robust for all . [MMV13] -extremely depth robust DAG with indegree . Problem: in-degree too high. [NEW] -extremely depth robust DAG with indegree O(log (n)) Construction: similar to [EGS75] Many technical details to work out (see paper)

39 Technical Ingredient #2 Definition: A DAG is -extremely depth robust if it is (e,d)-depth-robust for all . [NEW] -extremely depth robust DAG with indegree O(log (n)) Construction: similar to [EGS75] Many technical details to work out (see paper) Useful Observation: Any subgraph of of size must contain a path of length Proof: Otherwise DAG is not -depth robust for and Contradiction, is extremely depth robust and 40 Technical Ingredient #2

Definition: A DAG is -extremely depth robust if it is (e,d)-depth-robust for all . Lemma: If legal (parallel) pebbling P1,,Pt of has at least one pebbling round j with space then there are at least distinct time rounds k with space Proof: Let i

of PTCn we can find an interval such that 1. for each (lots of pebbles on the graph) 2. At least source nodes are (re)pebbled during the interval [NEW] Now requires rounds since is -extremely depth robust 42

PTC Overlay (Attempt 1) Lemma [PTC77] In any pebbling of PTCn we can find an interval such that 1. for each (lots of pebbles on the graph) 2. At least source nodes are (re)pebbled during the interval [NEW] Overlay requires rounds since is -extremely depth robust Problems: Requires pebbles for rounds I promised pebbles for rounds) Indegree still too high i.e.,

I promised constant indegree O(1) 43 Technical Ingredient #3 Indegree Reduction [ABP17] deals with both problems simultaneously! 44 Technical Ingredient #3 Indegree Reduction [ABP17] deals with both problems simultaneously! Lemma [ABP17]: If is -depth robust then is -depth robust. Furthermore, and has nodes.

45 The Final Construction Theorem: Any (parallel) pebbling requires pebbles for rounds Technical Details in paper 46 Consequences of new Depth-Robust Graphs Logic: Parallel Black-White Pebbling Application: CNF formulas with very memory costly refutation resolution proofs.

MHFS: Applications: Optimal CC for any graph of size n even though only O(log(n)) in-degree Exact Constants! Complete DAG: (prior result is almost optimal!) Coding Theory: better locally detectable error detection codes [BGGZ19] Improved Proof-of-Sequential work (temporarily. See Simple Proofs of Sequential Work for construction without depth-robust graphs). A Few Open Questions Practical Construction of iMHF with high sustained space complexity? Analyze/improve constant factors in bounds

Computer Aided Analysis? Stronger Results for dMHFs? Hybrid Modes like Argon2id? Find constant indegree DAG with parallel space-time complexity or show that no such DAG exists Note: [AB16] pebbling shows that , but the pebbling attack P still has 48 A Few Open Questions Practical Construction of iMHF with high sustained space complexity? See upcoming crypto 2019 paper Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions (with Ben Harsha and Siteng Kang and Seunghoon Lee and Lu

Xing and Samson Zhou). Theorem: Any pebbling of (practical) DAG G either has 1. Cumulative Cost , or 2. At least pebbles for rounds 49 Junk E-mail? From: CRYPTO 2019 Chair Subject: Your submission was accepted to CRYPTO 2019 50

Thanks for Listening 51