7
$\begingroup$

Modern key stretching functions (password-based key derivation functions, also used for password hashing) are memory-hard to mitigate parallel attacks, and as far as I know this is working well. Last year there was the password hashing competition (PHC 2015) where new password hashing functions were presented, Argon2 is going to be the new recommended password hash.

In the last few years Intel introduced its Xeon Phi coprocessors, which are devices with a moderate numbers of cores and great memory. At first sight this seems to be the perfect weapon for a hardware-accelerated dictionary attack (or brute-force) on these memory-hard KDF.

Is it really feasible? How?

If yes, is there a way to emulate this architecture's behaviour on such tasks?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ "Xeon Phi Coprocessors, devices with a moderate numbers of cores and great memory". We're talking about >= 64 low frequency cores here and 384 GB of memory max, with 4 threads per core. I would not call that a moderate number of cores. This sounds very familiar; it's basically an x64 Sparc Tx chip (without the connectivity and crypto goodness). $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 7, 2016 at 11:35
  • $\begingroup$ Please consider something like this cineca.it/it/content/galileo (768 * 61 total cores) $\endgroup$
    – refex
    Commented Aug 7, 2016 at 12:44
  • $\begingroup$ @MaartenBodewes it is a moderate amount of cores if you compare it to their direct competitors in super-computing: GPUs (especially NV Teslas) with thousands of cores. $\endgroup$
    – SEJPM
    Commented Aug 7, 2016 at 12:48
  • $\begingroup$ Refex, you cannot compare a single CPU to a supercomputer. Neither is it fair to compare a thread of a GPU with a general purpose core of a CPU, @SEJPM, apples and oranges. For a CPU it has a very high number of cores; this should at least be made clear in the question IMHO. $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 7, 2016 at 13:17
  • $\begingroup$ Slow cores mean you occupy the memory for each function for longer. $\endgroup$
    – CodesInChaos
    Commented Aug 7, 2016 at 13:35

1 Answer 1

Reset to default
6
$\begingroup$

The key idea of memory-hard functions like scrypt and Argon2, as I understand them, is to analyze the cost to the attacker in terms of a time-area product. Time is how much time the attacker spends. Area is how much silicon they use for the attack. The attacker is going to allocate a given area, but once that amount is fixed:

  • More cores means less memory dedicated to each core;
  • More memory dedicated to each core means fewer cores.

This sort of analysis should still apply to the coprocessors you bring up. Since they offer lots of memory per core, this must inevitably come at the cost of fewer cores than could otherwise be put in the same area of silicon. But if the functions' time-area product cost analysis is correct, the attacker should be unable to gain an advantage this way; the speed each core gains from its generous memory allocation should come at a corresponding loss in parallelism.

Note in passing that:

  • Memory complexity implies time complexity (using memory requires time). So algorithms that use a lot of memory are by necessity going to be (at least) proportionately slow.
  • Argon2 supports tuning the memory and time cost more or less independently. I.e., for a given amount of memory, we can always raise the time cost further to thwart a high-memory but low-parallelism attacker.
Improve this answer
$\endgroup$
3
  • $\begingroup$ I understand your analysis, but what if our hw references are classic GPU and CPU (x86)? Coprocessors have more cores than CPU and obviously they come with less memory per core. In the meantime they have less cores than GPU but more memory per core. So with this premise I'm assuming that these piece of hardware could exceed CPU & GPU performances on certain tasks such memory hard KDFs that requires both resources. Am i right? $\endgroup$
    – refex
    Commented Aug 13, 2016 at 22:17
  • $\begingroup$ @refex: It's not enough for the attacker to exceed the performance that the defender achieves—the attacker needs to massively exceed that performance at an affordable cost. The time-area analysis is, indirectly, about maximizing that cost for the attacker. Check out for example section 8 of Percival's scrypt paper where he attempts to quantify the attacker's cost in *dollars*—estimated cost of the hardware needed to attack a password of a given strength. $\endgroup$
    – Luis Casillas
    Commented Aug 14, 2016 at 1:36
  • $\begingroup$ Is it possible to do also some quantitative prevision? $\endgroup$
    – refex
    Commented Sep 22, 2016 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.