3 ms·

To illustrate the level of idiocy we reached with slow hash functions. The official NIST recommendation #800-132 is to use 10k iterations for PBKDF2, or 10M ite

To illustrate the level of idiocy we reached with slow hash functions. The official NIST recommendation #800-132 is to use 10k iterations for PBKDF2, or 10M iterations for important keys. 10k iterations was half a second when we tried it on our server. 10M iterations took 8 minutes for a single hash.

chowells 9y ago
Were you using it to hash data for integrity? Or even worse, were you abusing it as a MAC [1]? That's the only way I can see it being so slow. PBKDF2 is a password-based key derivation function (it says so, right in the name), not a data integrity verification function. You should only ever be feeding a password and high-entropy salt into it. It's something of a disservice to call all these things "hash functions". It makes people think they're interchangeable, but that's very far from true. [1] The reason I say using it as a MAC is even worse than using it for data integrity is that was never intended to work as a MAC. A KDF doesn't care (in theory) if the salt input can be derived by looking at its output. For the intended use case of a KDF, the salt is stored with the output anyway. So a cryptanalysis of a KDF wouldn't see the revelation of information about the key by the output as a theoretical flaw. But that would be a huge flaw in a MAC, where the output is often conveyed by an untrusted party between two parties who keep the key secret. From a practical standpoint, a KDF that did leak details of its key in its output is inefficient (redundant use of storage space), but it isn't sufficient by itself to break the security properties.
- user5994461 9y ago
  It's hashing a password. It's used exactly the way it's supposed to be.
minitech 9y ago
> 10M iterations took 8 minutes for a single hash. ~: time node -p 'crypto.pbkdf2Sync("password", "salt", 10e6, 32, "sha256").toString("hex")' 3c0873fa17659d22450cfcc4a7dd8e51e66db276a0d594cc729baba5af5cedd8 node -p 6.55s user 0.02s system 99% cpu 6.576 total 10 million iterations in 6.5 seconds on a cheap laptop. Not sure what caused your numbers, but spending a few seconds on a password hash is not “idiocy”.
- rocqua 9y ago
  Maybe it was a javascript implementation?
  - user5994461 9y ago
    It was a java library, not sure if the implementation was in C.
    - timv 9y ago
      Either the library you were using was terrible, your servers were powered by hamsters, or you were feeding the wrong parameters into the algorithm. The code below takes ~15 seconds on 1 year old MacBook running Java 1.8.0_111-b14 and uses no 3rd party libraries: PBEKeySpec spec = new PBEKeySpec(password.toCharArray(), salt, 10_000_000, 256); SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256"); byte[] hash = skf.generateSecret(spec).getEncoded();
      - user5994461 9y ago
        It was some years ago on first or second gen Xeon. Wouldn't be surprised if your new CPU is twice as fast. There is a vulnerability in PBKDF2 that halved the amount of operations. New libraries make use of it but it wasn't known at the time. That 15+ seconds would be 1+ minute back then. Assume the first implementations were poorly optimized and that's multiple minutes.

chowells 9y ago

Were you using it to hash data for integrity? Or even worse, were you abusing it as a MAC [1]? That's the only way I can see it being so slow. PBKDF2 is a password-based key derivation function (it says so, right in the name), not a data integrity verification function. You should only ever be feeding a password and high-entropy salt into it. It's something of a disservice to call all these things "hash functions". It makes people think they're interchangeable, but that's very far from true. [1] The reason I say using it as a MAC is even worse than using it for data integrity is that was never intended to work as a MAC. A KDF doesn't care (in theory) if the salt input can be derived by looking at its output. For the intended use case of a KDF, the salt is stored with the output anyway. So a cryptanalysis of a KDF wouldn't see the revelation of information about the key by the output as a theoretical flaw. But that would be a huge flaw in a MAC, where the output is often conveyed by an untrusted party between two parties who keep the key secret. From a practical standpoint, a KDF that did leak details of its key in its output is inefficient (redundant use of storage space), but it isn't sufficient by itself to break the security properties.

user5994461 9y ago
It's hashing a password. It's used exactly the way it's supposed to be.

minitech 9y ago

> 10M iterations took 8 minutes for a single hash. ~: time node -p 'crypto.pbkdf2Sync("password", "salt", 10e6, 32, "sha256").toString("hex")' 3c0873fa17659d22450cfcc4a7dd8e51e66db276a0d594cc729baba5af5cedd8 node -p 6.55s user 0.02s system 99% cpu 6.576 total 10 million iterations in 6.5 seconds on a cheap laptop. Not sure what caused your numbers, but spending a few seconds on a password hash is not “idiocy”.

rocqua 9y ago
Maybe it was a javascript implementation?
- user5994461 9y ago
  It was a java library, not sure if the implementation was in C.
  - timv 9y ago
    Either the library you were using was terrible, your servers were powered by hamsters, or you were feeding the wrong parameters into the algorithm. The code below takes ~15 seconds on 1 year old MacBook running Java 1.8.0_111-b14 and uses no 3rd party libraries: PBEKeySpec spec = new PBEKeySpec(password.toCharArray(), salt, 10_000_000, 256); SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256"); byte[] hash = skf.generateSecret(spec).getEncoded();
    - user5994461 9y ago
      It was some years ago on first or second gen Xeon. Wouldn't be surprised if your new CPU is twice as fast. There is a vulnerability in PBKDF2 that halved the amount of operations. New libraries make use of it but it wasn't known at the time. That 15+ seconds would be 1+ minute back then. Assume the first implementations were poorly optimized and that's multiple minutes.