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;

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

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.

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.

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 - 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.

Anyway, my curiosity is satisfied for now, but thanks again for sharing, and keep posting about this stuff.