4 ms·

You're right, there's a hard limit on password length. That might be fatal if you're using diceware, I don't know if you could accommodate passwords that big.

You're right, there's a hard limit on password length. That might be fatal if you're using diceware, I don't know if you could accommodate passwords that big. As for the set of strings, just assume it's every string possible, so 256^8 strings for an 8 byte password. That's only 16384 petabytes. All of the perfect hash functions I've found require knowing all of the keys ahead of time. You might not be able to fit 16384 PB on your hard drive or in memory. (Hey, I don't know. You could work at LLNL.) But I think that if you knew you might use any key in the space, and you didn't insist on a minimal perfect hash, i.e. one where there is a 1:1 mapping from hashes back to keys, that you could write such a function without having all of the keys. If you did this, you'd also need to prove you were generating a unique and effectively random hash. If I was a crypto academic, that might be an interesting line of research. I'd be kind of surprised if nobody ever tried this though, and there's probably a decent amount of literature to pore over. I guess most people use perfect hashes for hashtables and not as a defense against timing attacks.

TheLoneWolfling 11y ago
Congratulations. You've just described the standard method of password hashing. (Well, you've missed the common extensions of salt / pepper, but meh.) If you pick a cryptographically secure hash that's long enough, you don't need to worry about collisions. The birthday problem dictates that you start getting collisions after ~sqrt(D) random entries. So if you pick a 128+ bit hash you should be fine on that front (128 bits -> ~2^64 entries before a collision on average, which shouldn't be a problem.) However, as I've mentioned elsewhere, all this does is punt the constant-time problem off to the hash function.
- ectoplasm 11y ago
  Wow, maybe I have a future in cryptography! Anyway, why exactly isn't the hash function constant-time? I don't understand this, the hashes I've played with for hashtables are just a bunch of bit shifts. Is it only message length?
  - TheLoneWolfling 11y ago
    Maybe you do... The hashes generally used for things like hash tables don't need to be cryptographically secure, and as such can be substantially simpler. When you start getting into cryptographically secure hashes things get complex enough that you start ending up with timing variations if you're not very careful. Especially once you start talking about table lookups / etc (although that's more common with encryption algorithms than straight hash algorithms). And the compiler - with C and C++ at least - is free to optimize in ways that introduce timing variations. Which is what sparked this conversation in the first place. So even if your source code doesn't take data-dependent time, the compiler may make the compiled output take data-dependent time. And there's no way around that in pure C / C++.
    - ectoplasm 11y ago
      Ok, fine, so there are no real-time, optimization, or scheduling guarantees in C / C++ and it's better to be safe than sorry. But why does it actually matter if either the hash function or hash value comparison takes data-dependent time? How can you use that information to recover the password?
      - TheLoneWolfling 11y ago
        Let's say the hash value comparison short-circuits by hex digit: char[] entered+_hash = ... char[] password_hash = ... for (int i = 0; i < entered_hash.length; i++) if entered_hash[i] != password_hash[i]: return false; return true; This is a modification of a dictionary attack. as such, it assumes that the person has used a known password. I take a standard password dictionary and hash everything. I arrange it into a Trie or somesuch by the hash. I start trying passwords. Specifically: I try passwords where the first character of the hash is different. So, for instance, with SHA256, I try: 12345 5994471abb01112afcc18159f6cc74b4f511b99806da59b3caf5a9c173cacfc5 abc123 6ca13d52ca70c883e0f0bb101e425a89e8624de51db2d2392593af6a84118090 computer aa97302150fce811425cd84537028a5afbe37e3f1362ad45a51d467e17afdc9c 123456 8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92 1234 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4 a1b2c3 4f32044a655f32e8528edea64dbfd11cba810b8790e6e6e23d28ad3a75980734 xxx cd2eb0837c9b4c962c22d2ff8b5441b7b45805887f051d39bf133b583baf6860 test 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08 carmen f3c2ce176290b0c384cb4881eb714f2db58f630c33863d91c9bedf58d36007db mickey 33c614ca3cf78827a85dc0d8d06bfcf8c4d923fd23c813acd50b80ed2d4d4fb3 secret 2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b summer e83664255c6963e962bb20f9fcfaad1b570ddf5da69f5444ed37e5260f3ef689 ranger dbc4a04327176e6577b4da46df04564150053960eba5d89587dad1f76a818d80 letmein 1c8bfe8f801d79745c4631d09fff36c82aa37fc4cce4fc946683d7b336b63032 mindy 7376c22801fbd6e01009830a70028820f280958165e6d3c2bac9683dab28feb7 bear bc98bb50e8094b2ac3ceb90ba2512587c0513cd294a07efcfdcf467198da6266 One of these should take slightly more time than the others. Let's say it's 'carmen'. I now know that the first character of the password hash is 'f'. I then try passwords where the first character of the password hash is 'f' and the second is different. Repeat until I have the entire password. Note that this can also turn an online brute-force attack into an offline brute-force attack with a small online component. (The only difference being instead of a password dictionary, you brute-force for hashes with the known bits.) Note that a salt - if the salt is never leaked - prevents this attack. (Except that if you have an account yourself you can do a timing attack against your own account to try to figure out the salting scheme!) -------- If the password hash itself takes data-dependent time... There are plenty of ways to go from that to breaking passwords. I could elaborate if you wish.

TheLoneWolfling 11y ago

Congratulations. You've just described the standard method of password hashing. (Well, you've missed the common extensions of salt / pepper, but meh.) If you pick a cryptographically secure hash that's long enough, you don't need to worry about collisions. The birthday problem dictates that you start getting collisions after ~sqrt(D) random entries. So if you pick a 128+ bit hash you should be fine on that front (128 bits -> ~2^64 entries before a collision on average, which shouldn't be a problem.) However, as I've mentioned elsewhere, all this does is punt the constant-time problem off to the hash function.

ectoplasm 11y ago
Wow, maybe I have a future in cryptography! Anyway, why exactly isn't the hash function constant-time? I don't understand this, the hashes I've played with for hashtables are just a bunch of bit shifts. Is it only message length?
- TheLoneWolfling 11y ago
  Maybe you do... The hashes generally used for things like hash tables don't need to be cryptographically secure, and as such can be substantially simpler. When you start getting into cryptographically secure hashes things get complex enough that you start ending up with timing variations if you're not very careful. Especially once you start talking about table lookups / etc (although that's more common with encryption algorithms than straight hash algorithms). And the compiler - with C and C++ at least - is free to optimize in ways that introduce timing variations. Which is what sparked this conversation in the first place. So even if your source code doesn't take data-dependent time, the compiler may make the compiled output take data-dependent time. And there's no way around that in pure C / C++.
  - ectoplasm 11y ago
    Ok, fine, so there are no real-time, optimization, or scheduling guarantees in C / C++ and it's better to be safe than sorry. But why does it actually matter if either the hash function or hash value comparison takes data-dependent time? How can you use that information to recover the password?
    - TheLoneWolfling 11y ago
      Let's say the hash value comparison short-circuits by hex digit: char[] entered+_hash = ... char[] password_hash = ... for (int i = 0; i < entered_hash.length; i++) if entered_hash[i] != password_hash[i]: return false; return true; This is a modification of a dictionary attack. as such, it assumes that the person has used a known password. I take a standard password dictionary and hash everything. I arrange it into a Trie or somesuch by the hash. I start trying passwords. Specifically: I try passwords where the first character of the hash is different. So, for instance, with SHA256, I try: 12345 5994471abb01112afcc18159f6cc74b4f511b99806da59b3caf5a9c173cacfc5 abc123 6ca13d52ca70c883e0f0bb101e425a89e8624de51db2d2392593af6a84118090 computer aa97302150fce811425cd84537028a5afbe37e3f1362ad45a51d467e17afdc9c 123456 8d969eef6ecad3c29a3a629280e686cf0c3f5d5a86aff3ca12020c923adc6c92 1234 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4 a1b2c3 4f32044a655f32e8528edea64dbfd11cba810b8790e6e6e23d28ad3a75980734 xxx cd2eb0837c9b4c962c22d2ff8b5441b7b45805887f051d39bf133b583baf6860 test 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08 carmen f3c2ce176290b0c384cb4881eb714f2db58f630c33863d91c9bedf58d36007db mickey 33c614ca3cf78827a85dc0d8d06bfcf8c4d923fd23c813acd50b80ed2d4d4fb3 secret 2bb80d537b1da3e38bd30361aa855686bde0eacd7162fef6a25fe97bf527a25b summer e83664255c6963e962bb20f9fcfaad1b570ddf5da69f5444ed37e5260f3ef689 ranger dbc4a04327176e6577b4da46df04564150053960eba5d89587dad1f76a818d80 letmein 1c8bfe8f801d79745c4631d09fff36c82aa37fc4cce4fc946683d7b336b63032 mindy 7376c22801fbd6e01009830a70028820f280958165e6d3c2bac9683dab28feb7 bear bc98bb50e8094b2ac3ceb90ba2512587c0513cd294a07efcfdcf467198da6266 One of these should take slightly more time than the others. Let's say it's 'carmen'. I now know that the first character of the password hash is 'f'. I then try passwords where the first character of the password hash is 'f' and the second is different. Repeat until I have the entire password. Note that this can also turn an online brute-force attack into an offline brute-force attack with a small online component. (The only difference being instead of a password dictionary, you brute-force for hashes with the known bits.) Note that a salt - if the salt is never leaked - prevents this attack. (Except that if you have an account yourself you can do a timing attack against your own account to try to figure out the salting scheme!) -------- If the password hash itself takes data-dependent time... There are plenty of ways to go from that to breaking passwords. I could elaborate if you wish.