3 ms·

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 i

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.
- ectoplasm 11y ago
  Hey this is pretty interesting. Thanks for taking the time to explain. My first reaction was that you have to know the hash function for this attack to work, but I guess the salt serves the same purpose as hiding the hash function, and is more practical since then you can use a generic hash. Presumably someone figured out a way to prevent timing attacks against your own account - what is it? Sure, assume that the hash takes data-dependent time, but that's the only vulnerability. I can see that this might reveal password length, but not easily beyond that. How does it work? Does SHA256 with salt take constant time? In general, what is the most secure password scheme if you're looking to prevent timing attacks? Do you need real-time guarantees? You have enough material for a nice "evolution of secure password authentication" article here, if you ever wanted to write it up.
  - TheLoneWolfling 11y ago
    > Presumably someone figured out a way to prevent timing attacks against your own account - what is it? As long as the salt has sufficient entropy, this isn't a problem. So instead of generating the salt from the username / etc, you use a random salt and store it. > How does it work? Effectively, by leaking internal state of the cypher / hash through timing variations. The most common ways of doing so are either through data-dependent table lookups or through operations that may be microcoded or otherwise take variable time (multiplications, rotations sometimes, divisions, modulo, squaring). See, for instance, http://cr.yp.to/streamciphers/leaks.html http://cr.yp.to/streamciphers/leaks.html - although note that this is dealing with stream cyphers not hash functions. In particular, the linked paper describes an effective timing attack against AES by taking advantage of processor cache effects on a data-dependent table lookup. I'd give it a read - it's quite interesting. SHA256 is pretty good w.r.t. being close to constant time for a fixed input length. Not perfect, but meh. It uses bitwise xor and and, rotates, shifts, and addition, none of which are generally variable-time (although note that on some platforms rotates are variable-time). For most things, SHA2, by which I mean the newer variants, works reasonably well. In particular, you store SHA2(password xor random_salt xor pepper) and discard the original password. Store the salt in the database with the user, and if you want to get really fancy you embed a single random value ("pepper") in the application code - this is a kind of last-ditch effort to hopefully prevent user passwords from being leaked even if the database is leaked. If you really want to get fancy, you also embed a couple "canary" accounts (random made-up accounts) in your database, with a passive device on the network that screams bloody murder if any of those accounts ever get successfully logged in to. However, that being said, that doesn't really answer your question. A couple things: 1) You don't want to use SHA, generally. You want to use a proper KDF (key derivation function). Why? Standard hash functions are designed to be fast and not take much memory. Which means it is a whole lot easier to crack. 2) If any of the user authentication is in a language that you cannot disable optimizations in, and you cannot look at the assembly code coming out, you cannot prevent timing attacks. You may be able to mitigate them, but that is all. 3) In general, if a KDF / hash function doesn't use any data-dependent table lookups / pointer chasing / control flow, and doesn't do any complex functions (multiplication, etc), it's probably relatively safe from timing attacks. Otherwise... Not so much. 4) Theoretically, you need cooperation of the kernel, etc, to truly be safe from timing attacks. Among other things, context switches could leak information. In actuality... It's definitely possible but I don't know of anyone who has made it work.

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.

ectoplasm 11y ago
Hey this is pretty interesting. Thanks for taking the time to explain. My first reaction was that you have to know the hash function for this attack to work, but I guess the salt serves the same purpose as hiding the hash function, and is more practical since then you can use a generic hash. Presumably someone figured out a way to prevent timing attacks against your own account - what is it? Sure, assume that the hash takes data-dependent time, but that's the only vulnerability. I can see that this might reveal password length, but not easily beyond that. How does it work? Does SHA256 with salt take constant time? In general, what is the most secure password scheme if you're looking to prevent timing attacks? Do you need real-time guarantees? You have enough material for a nice "evolution of secure password authentication" article here, if you ever wanted to write it up.
- TheLoneWolfling 11y ago
  > Presumably someone figured out a way to prevent timing attacks against your own account - what is it? As long as the salt has sufficient entropy, this isn't a problem. So instead of generating the salt from the username / etc, you use a random salt and store it. > How does it work? Effectively, by leaking internal state of the cypher / hash through timing variations. The most common ways of doing so are either through data-dependent table lookups or through operations that may be microcoded or otherwise take variable time (multiplications, rotations sometimes, divisions, modulo, squaring). See, for instance, http://cr.yp.to/streamciphers/leaks.html http://cr.yp.to/streamciphers/leaks.html - although note that this is dealing with stream cyphers not hash functions. In particular, the linked paper describes an effective timing attack against AES by taking advantage of processor cache effects on a data-dependent table lookup. I'd give it a read - it's quite interesting. SHA256 is pretty good w.r.t. being close to constant time for a fixed input length. Not perfect, but meh. It uses bitwise xor and and, rotates, shifts, and addition, none of which are generally variable-time (although note that on some platforms rotates are variable-time). For most things, SHA2, by which I mean the newer variants, works reasonably well. In particular, you store SHA2(password xor random_salt xor pepper) and discard the original password. Store the salt in the database with the user, and if you want to get really fancy you embed a single random value ("pepper") in the application code - this is a kind of last-ditch effort to hopefully prevent user passwords from being leaked even if the database is leaked. If you really want to get fancy, you also embed a couple "canary" accounts (random made-up accounts) in your database, with a passive device on the network that screams bloody murder if any of those accounts ever get successfully logged in to. However, that being said, that doesn't really answer your question. A couple things: 1) You don't want to use SHA, generally. You want to use a proper KDF (key derivation function). Why? Standard hash functions are designed to be fast and not take much memory. Which means it is a whole lot easier to crack. 2) If any of the user authentication is in a language that you cannot disable optimizations in, and you cannot look at the assembly code coming out, you cannot prevent timing attacks. You may be able to mitigate them, but that is all. 3) In general, if a KDF / hash function doesn't use any data-dependent table lookups / pointer chasing / control flow, and doesn't do any complex functions (multiplication, etc), it's probably relatively safe from timing attacks. Otherwise... Not so much. 4) Theoretically, you need cooperation of the kernel, etc, to truly be safe from timing attacks. Among other things, context switches could leak information. In actuality... It's definitely possible but I don't know of anyone who has made it work.