---
res:
bibo_abstract:
- 'We show attacks on five data-independent memory-hard functions (iMHF) that were
submitted to the password hashing competition (PHC). Informally, an MHF is a function
which cannot be evaluated on dedicated hardware, like ASICs, at significantly
lower hardware and/or energy cost than evaluating a single instance on a standard
single-core architecture. Data-independent means the memory access pattern of
the function is independent of the input; this makes iMHFs harder to construct
than data-dependent ones, but the latter can be attacked by various side-channel
attacks. Following [Alwen-Blocki''16], we capture the evaluation of an iMHF as
a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of
this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC.
Ideally, one would like the complexity of a DAG underlying an iMHF to be as close
to quadratic in the number of nodes of the graph as possible. Instead, we show
that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,
TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show
that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have
exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial
property of each underlying DAG (called its depth-robustness. By establishing
upper bounds on this property we are then able to apply the general technique
of [Alwen-Block''16] for analyzing the hardware costs of an iMHF.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joel F
foaf_name: Alwen, Joel F
foaf_surname: Alwen
foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Peter
foaf_name: Gazi, Peter
foaf_surname: Gazi
- foaf_Person:
foaf_givenName: Chethan
foaf_name: Kamath Hosdurg, Chethan
foaf_surname: Kamath Hosdurg
foaf_workInfoHomepage: http://www.librecat.org/personId=4BD3F30E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Karen
foaf_name: Klein, Karen
foaf_surname: Klein
foaf_workInfoHomepage: http://www.librecat.org/personId=3E83A2F8-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Georg F
foaf_name: Osang, Georg F
foaf_surname: Osang
foaf_workInfoHomepage: http://www.librecat.org/personId=464B40D6-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8882-5116
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Lenoid
foaf_name: Reyzin, Lenoid
foaf_surname: Reyzin
- foaf_Person:
foaf_givenName: Michal
foaf_name: Rolinek, Michal
foaf_surname: Rolinek
foaf_workInfoHomepage: http://www.librecat.org/personId=3CB3BC06-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Michal
foaf_name: Rybar, Michal
foaf_surname: Rybar
foaf_workInfoHomepage: http://www.librecat.org/personId=2B3E3DE8-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1145/3196494.3196534
dct_date: 2018^xs_gYear
dct_identifier:
- UT:000516620100005
dct_language: eng
dct_publisher: ACM@
dct_title: On the memory hardness of data independent password hashing functions@
...