4 ms·

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.

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.