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.