4 ms·

I admit I didn't read the entire article, I've been reading only the text around instances of argon and PBKDF, but: can someone ELI5 how they do 882 hashes per

I admit I didn't read the entire article, I've been reading only the text around instances of argon and PBKDF, but: can someone ELI5 how they do 882 hashes per second if PBKDF2 is set up to take 2 seconds, for example? What's so broken about PBKDF2 that they get a > 1000x speedup?

simcop2387 7y ago
It's trivially parrallelizable so I suspect that they're doing it on a gpu or something like that.
- wongarsu 7y ago
  Which is a known "vulnerability" of PBKDF2. In any modern setup you are better served by Argon2 (or if that's not available at least scrypt). CPU time is cheap to parallelize, memory bandwidth is much harder to scale.
  - Aardwolf 7y ago
    There must, in addition to memory, be other things that are hard to parallelize on GPU's, right? How would 64-bit integer division do on a GPU? The GPU does not have 1000x more transistors than a CPU, it can't be 1000x faster for everything, right? The annoying thing is LUKS1 only supports PBKDF2, but LUKS2 comes with a JSON parser, and no full support everywhere yet
    - simcop2387 7y ago
      The best targets are stuff that is data dependant for behavior and memory size for current gpus. Larger number sizes will help but maybe not as much as you think, since those work well for FPGA or asic devices. Data dependency helps because it can kill cache behavior and branch prediction which are key features for fast speed on fpga and gpu devices. Combined with memory size which limits the number of possible attempts on devices thats where the protection comes from. N.B. sorry for typos, have a cat in the way
    - wongarsu 7y ago
      GPUs are essentially wide SIMD processors. If cores take different branches that can slow them down dramatically, in the worst case all cores have to execute all branches. The other thing that slows them down is memory access. Caches are small because everything adds up quickly once you multiply it by a few thousand. They are optimized for access patterns typical in graphics, which is mostly sequential or every-x-bytes. The main memory might be GDDR5 or GDDR6, but even the 600GB/s memory bandwidth of the RTX 2080TI is quickly used up once you have 8000 threads requesting random bytes from memory. Apart from branching and memory I don't think GPUs have many weaknesses. They can save a lot of transistors because they don't care about single-core performance. For example instead of doing sophisticated instruction reordering to hide memory latency they just switch to a different set of threads whenever they would otherwise wait for memory. There are some tasks that Intel CPUs have transistors dedicated to like AES or 64bit integers and they do loose some speed on those, but at the same time these things are easy to do in silicon so your CPU loses to ASICs. And even a GPU eventually has enough cores that the software implementation run 4000 times in parallel will beat the CPU by a wide margin again.
  - lucb1e 7y ago
    > In any modern setup you are better served by Argon2 (or if that's not available at least scrypt). I recently wanted to do exactly that in JavaScript. Browser crypto only does PBKDF2... quite disappointing. One still has to use third party libraries for all practical purposes, there might as well not be a crypto API at all except for providing a CSPRNG.
xwvvvvwx 7y ago
some more details on the LUKS support in hashcat here: https://hashcat.net/forum/thread-6225.html https://hashcat.net/forum/thread-6225.html
loeg 7y ago
Not really ELI5, but simplified version is: * The "2 seconds" is used measure a specific number of algorithm iterations running a specific software implementation on the host CPU when the volume is initialized. This count is static after initialization. * If an attacker has a faster device, or a lot of cores, or both (GPU), the attacker can do more iterations per second. Thus, it takes them fewer seconds (potentially fractions of a second) per guess. > What's so broken about PBKDF2 that they get a > 1000x speedup? Nothing in particular; it lacks some of the memory hardness that newer KDFs have. The attacker gets 1000x speedup by throwing something like 1000x the compute at the problem. (This is a little cheaper than it might seem because the problem is tractable on GPU.)
mrb 7y ago
They get a 882x speedup because hashcat's heavily optimized implementation of luks1 (aes, cbc-essiv:sha256, sha1) on a R9 290x GPU really is 882x faster than cryptsetup's ordinary implementation of this algo which runs on a single CPU thread when the LUKS key is encrypted during initialization. Note that LUKS by default sets the number of PBKDF2 iterations to take 1 second, not 2.

simcop2387 7y ago

It's trivially parrallelizable so I suspect that they're doing it on a gpu or something like that.

wongarsu 7y ago
Which is a known "vulnerability" of PBKDF2. In any modern setup you are better served by Argon2 (or if that's not available at least scrypt). CPU time is cheap to parallelize, memory bandwidth is much harder to scale.
- Aardwolf 7y ago
  There must, in addition to memory, be other things that are hard to parallelize on GPU's, right? How would 64-bit integer division do on a GPU? The GPU does not have 1000x more transistors than a CPU, it can't be 1000x faster for everything, right? The annoying thing is LUKS1 only supports PBKDF2, but LUKS2 comes with a JSON parser, and no full support everywhere yet
  - simcop2387 7y ago
    The best targets are stuff that is data dependant for behavior and memory size for current gpus. Larger number sizes will help but maybe not as much as you think, since those work well for FPGA or asic devices. Data dependency helps because it can kill cache behavior and branch prediction which are key features for fast speed on fpga and gpu devices. Combined with memory size which limits the number of possible attempts on devices thats where the protection comes from. N.B. sorry for typos, have a cat in the way
  - wongarsu 7y ago
    GPUs are essentially wide SIMD processors. If cores take different branches that can slow them down dramatically, in the worst case all cores have to execute all branches. The other thing that slows them down is memory access. Caches are small because everything adds up quickly once you multiply it by a few thousand. They are optimized for access patterns typical in graphics, which is mostly sequential or every-x-bytes. The main memory might be GDDR5 or GDDR6, but even the 600GB/s memory bandwidth of the RTX 2080TI is quickly used up once you have 8000 threads requesting random bytes from memory. Apart from branching and memory I don't think GPUs have many weaknesses. They can save a lot of transistors because they don't care about single-core performance. For example instead of doing sophisticated instruction reordering to hide memory latency they just switch to a different set of threads whenever they would otherwise wait for memory. There are some tasks that Intel CPUs have transistors dedicated to like AES or 64bit integers and they do loose some speed on those, but at the same time these things are easy to do in silicon so your CPU loses to ASICs. And even a GPU eventually has enough cores that the software implementation run 4000 times in parallel will beat the CPU by a wide margin again.
- lucb1e 7y ago
  > In any modern setup you are better served by Argon2 (or if that's not available at least scrypt). I recently wanted to do exactly that in JavaScript. Browser crypto only does PBKDF2... quite disappointing. One still has to use third party libraries for all practical purposes, there might as well not be a crypto API at all except for providing a CSPRNG.

xwvvvvwx 7y ago

some more details on the LUKS support in hashcat here: https://hashcat.net/forum/thread-6225.html https://hashcat.net/forum/thread-6225.html

loeg 7y ago

Not really ELI5, but simplified version is: * The "2 seconds" is used measure a specific number of algorithm iterations running a specific software implementation on the host CPU when the volume is initialized. This count is static after initialization. * If an attacker has a faster device, or a lot of cores, or both (GPU), the attacker can do more iterations per second. Thus, it takes them fewer seconds (potentially fractions of a second) per guess. > What's so broken about PBKDF2 that they get a > 1000x speedup? Nothing in particular; it lacks some of the memory hardness that newer KDFs have. The attacker gets 1000x speedup by throwing something like 1000x the compute at the problem. (This is a little cheaper than it might seem because the problem is tractable on GPU.)

mrb 7y ago

They get a 882x speedup because hashcat's heavily optimized implementation of luks1 (aes, cbc-essiv:sha256, sha1) on a R9 290x GPU really is 882x faster than cryptsetup's ordinary implementation of this algo which runs on a single CPU thread when the LUKS key is encrypted during initialization. Note that LUKS by default sets the number of PBKDF2 iterations to take 1 second, not 2.