On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i
Argon2i is a data-independent memory hard function that won the password hashing competition. The password hashing algorithm has already been incorporated into several open source crypto libraries such as libsodium. In this paper we analyze the cumulative
- PDF / 403,298 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 165 Views
Abstract. Argon2i is a data-independent memory hard function that won the password hashing competition. The password hashing algorithm has already been incorporated into several open source crypto libraries such as libsodium. In this paper we analyze the cumulative memory cost of computing Argon2i. On the positive side we provide a lower bound for Argon2i. On the negative side we exhibit an improved attack against Argon2i which demonstrates that our lower bound is nearly tight. In particular, we show that (1) An Argon2i DAG is e, O n3 /e3 )-reducible. (2) The cumulative pebbling cost for Argon2i is at most O n1.768 . This 1.8 [AB17]. improves upon the previous best upper bound of O n ˜ n3 /e3 -depth robust. By contrast, analysis (3) Argon2i DAG is e, Ω ˜ n2 /e2 -depth of [ABP17a] only established that Argon2i was e, Ω robust. ˜ n1.75 . (4) The cumulative pebbling complexity of Argon2i is at least Ω 1.66 [ABP17a] and This improves on the previous best bound of Ω n demonstrates that Argon2i has higher cumulative memory cost than competing proposals such as Catena or Balloon Hashing. We also show that Argon2i has high fractional depth-robustness which strongly suggests that data-dependent modes of Argon2 are resistant to space-time tradeoff attacks.
1
Introduction
Memory-hard functions (MHFs) are a promising primitive to help protect low entropy user passwords against offline attacks. MHFs can generally be divided into two categories: data-dependent (dMHF) and data-independent (iMHF). A data-independent MHF (iMHF) is characterized by the property that the memory-access pattern induced by an honest evaluation algorithm is not dependent on the input to the function (e.g., the password). In contexts such as password hashing, iMHFs are useful for their resistance to side-channel attacks such as cache-timing [Ber]1 . 1
Unfortunately, this resistance to side-channel attacks has a price; we now know that the dMHFs scrypt enjoys strictly greater memory-hardness [ACP+17] than can possibly be achieved for a very broad class of iMHFs [AB16].
c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 445–465, 2017. https://doi.org/10.1007/978-3-319-70500-2_15
446
J. Blocki and S. Zhou
Both in theory and in practice, iMHFs (e.g.,[BDK16,CGBS16,CJMS14, Cox14,Wu15,Pin14,AABSJ14]) can be viewed as a directed acyclic graph (DAG) which describes how inputs and outputs of various calls to an underlying compression function are related. That is, the function fG,h can be fully specified in terms of a DAG G and a round function h. The input to the function is the label of the source node(s) and the output of the function is the label of the sink node(s). The label of node v is computed by applying the round function h to the labels of v’s parents. The goal of a MHF is to ensure that it is cost prohibitive for an attacker to evaluate fG,t millions or billions of times even if the attacker can use customized hardware (e.g., FPGAs, ASICs).
Data Loading...
