Joel Alwen: Data-Independent Memory Hard Functions
Tuesday, May 17, 2016 - 4:00pm to 5:00pm
Location:
Patil/Kiva G449
Speaker:
Joel Alwen, IST Austria
Seminar group:
Abstract:
There is growing interest in the security community in Memory-Hard
Functions (MHF). Roughly speaking, an MHF has the properties that:
- Computing the MHF on any input, using a general purpose (sequential)
CPU requires a moderate amount of memory and time.
- Yet the MHF cannot be *repeatedly* computed in *parallel* with
significantly less memory and time amortized per instance. In
particular, using a dedicated application specific integrated circuit
(ASIC) to mount a brute-force attack still requires a moderate amount of
amortized (memory x time) per instance.
MHFs come in two flavours called data dependent (dMHF) or independent
(iMHF) depending on if they can be efficiently computed using an input
independent memory access pattern. While a secure dMHF seems easier to
construct an iMHF enjoys an added natural resistance to some kinds of
practical side-channel attacks such as cache time-attacks.
MHFs where initially used to build password-hashing and key-derivation
functions with the property that dictionary attacks become much less
cost-effective to implement in hardware. More recently, MHFs have also
been used in distributed proofs-of-work for cryptocurrencies (e.g.
Ethereum, Litecoin, etc.). In contrast to computational hardness based
currencies such as bitcoin, memory-hardness based ones are more
egalitarian in that the mining power per dollar spent is more similar
across computational devices. In particular, specialized mining rigs
used by a small number of power users have a smaller advantage over the
general purpose CPUs used by more casual users.
In this talk we survey the recent advancements concerning MHFs in the
area of provably secure cryptography. Beginning with the work of
Percival (BSDCan 2009) and Alwen and Serbinenko (STOC 2015) we motivate
and describe a formal definition of an MHF capturing the intuitive
properties we desire from such a function. We very briefly survey some
of the most important candidate construction from the literature. Then
we give an overview of recent foundational, negative and positive
results in the area.
Theoretical Foundations:
- Complexity measures for evaluating practical attacks vs. for proving
security.
- A powerful tool for proving security in the random oracle model, using
a simple pebbling game on a graphs.
- A fundamental connection between iMHFs and a combinatorial property of
graphs called depth-robustness.
Negative:
- A general non-trivial upper-bound on the memory-hardness of any iMHF.
- Attacks for almost all of the most prominent iMHF candidates known to
date. In most cases the attacks are practical for commonly used or
suggested parameter ranges.
Positive:
- A security proof for the most important dMHF (scrypt) based on a
combinatorial conjecture.
- A new provably secure iMHF with optimal memory-hardness.
- Security proofs for some of the most important iMHF candidates showing
that the above mentioned attacks are close to optimal.
Functions (MHF). Roughly speaking, an MHF has the properties that:
- Computing the MHF on any input, using a general purpose (sequential)
CPU requires a moderate amount of memory and time.
- Yet the MHF cannot be *repeatedly* computed in *parallel* with
significantly less memory and time amortized per instance. In
particular, using a dedicated application specific integrated circuit
(ASIC) to mount a brute-force attack still requires a moderate amount of
amortized (memory x time) per instance.
MHFs come in two flavours called data dependent (dMHF) or independent
(iMHF) depending on if they can be efficiently computed using an input
independent memory access pattern. While a secure dMHF seems easier to
construct an iMHF enjoys an added natural resistance to some kinds of
practical side-channel attacks such as cache time-attacks.
MHFs where initially used to build password-hashing and key-derivation
functions with the property that dictionary attacks become much less
cost-effective to implement in hardware. More recently, MHFs have also
been used in distributed proofs-of-work for cryptocurrencies (e.g.
Ethereum, Litecoin, etc.). In contrast to computational hardness based
currencies such as bitcoin, memory-hardness based ones are more
egalitarian in that the mining power per dollar spent is more similar
across computational devices. In particular, specialized mining rigs
used by a small number of power users have a smaller advantage over the
general purpose CPUs used by more casual users.
In this talk we survey the recent advancements concerning MHFs in the
area of provably secure cryptography. Beginning with the work of
Percival (BSDCan 2009) and Alwen and Serbinenko (STOC 2015) we motivate
and describe a formal definition of an MHF capturing the intuitive
properties we desire from such a function. We very briefly survey some
of the most important candidate construction from the literature. Then
we give an overview of recent foundational, negative and positive
results in the area.
Theoretical Foundations:
- Complexity measures for evaluating practical attacks vs. for proving
security.
- A powerful tool for proving security in the random oracle model, using
a simple pebbling game on a graphs.
- A fundamental connection between iMHFs and a combinatorial property of
graphs called depth-robustness.
Negative:
- A general non-trivial upper-bound on the memory-hardness of any iMHF.
- Attacks for almost all of the most prominent iMHF candidates known to
date. In most cases the attacks are practical for commonly used or
suggested parameter ranges.
Positive:
- A security proof for the most important dMHF (scrypt) based on a
combinatorial conjecture.
- A new provably secure iMHF with optimal memory-hardness.
- Security proofs for some of the most important iMHF candidates showing
that the above mentioned attacks are close to optimal.