[PHC] Analysis of Argon2i

[Dmitry Khovratovich]

Dear all,

we have looked at the recent paper by Corrigan-Gibbs et al., which claims
several attacks on Argon2i.
First of all we don't agree with authors regarding "provable" aspect of
their and our scheme. We have a reductionist proof that all the blocks are
different and this paper does not undermine it, we could shape Argon paper
more in definition-proof style but we found it unnecessary.

IDEA: The main observation exploits the known fact that the pseudo-random
memory block addresses, used by the Argon2i function to pull random blocks
from memory, are known in advance and thus the blocks that are not used
(till they are overwritten later) can be discarded.

WHAT IS AFFECTED: Argon2i only (even Argon2id is not affected).

WHAT IS ATTACKER's GAIN: On custom hardware it is possible to run 1-pass
Argon2i with 0.2 of memory and no time penalty, while N-pass Argon2i can be
run with 0.37 of memory. We expect that this effect to be less of a problem
for GPU/FPGA.

WHAT IS NEW: This observation was known for 1-pass Argon2i (ex. noticed by
Bill Cox) and thus it was the reason why 3 passes for Argon2i were already
recommended. The effect for N-pass Argon2i is new.

CAN IT BE PATCHED: Yes, at a cost of quite small performance/code
difference. We are testing several countermeasures at this point, for
example a simple XOR into the memory instead of overwrite (around 10%
slowdown).

WHAT WILL BE DONE: We will discuss whether this memory reduction should be
mitigated (0.37 is not a big advantage anyway), and will come up with the
best alternative and its design rationale within a few weeks.

[Bill Cox]

Post by Dmitry Khovratovich
CAN IT BE PATCHED: Yes, at a cost of quite small performance/code
difference. We are testing several countermeasures at this point, for
example a simple XOR into the memory instead of overwrite (around 10%
slowdown).

I like the idea of XORing over memory for Argon2i. Both Lyra2 and Gambit
did this.

Bill

[Krisztián Pintér]

I like the idea of XORing over memory for Argon2i.  Both Lyra2 and Gambit did this.

and for a reason!

in http://article.gmane.org/gmane.comp.security.phc/1386 i wrote:

"if you overwrite, the slot becomes unused for a while. i mean, once
it has been read, and until it gets a new value, it just sits there
unused. at any point in time, a certain fraction of the memory (and a
quite huge fraction) is in this idle state. if you cleverly reuse
memory slots, you can run the algorithm with smaller memory footprint.
i prevent this by never discarding any value."