side-channel-password-guessing.md

This was a comment I posted on bcrypt-ruby/bcrypt-ruby#43 (before I realized that issue was 5 years old!) which got deleted so I moved it here.

Let's make the attack concrete to see if it works. I have a dictionary of 2³² candidate passwords I want to try against a user account. I know the user's salt. There is no rate limiting. Ideally, it should take 2³² online queries to search through all of my candidate passwords. Here's the attack:

1. Using my knowledge of the salt, I hash ~2¹⁶ random preimages until I find one for every possible 2-byte prefix of the hash.
2. Now I send each of those 2¹⁶ preimages in turn to the server and observe the side-channel. I may have to repeat this a few times in order to improve the SNR, let's say 100 times. So in 100*2¹⁶ online queries I learn the first 2 bytes of the hash.
3. Now that I know the first 2 bytes of the hash, I do 2³² offline work to hash all of my candidate passwords and remove the ones that don't hash to those same first two bytes. This brings the size of the list down to about 2¹⁶.
4. Now I online query for each one of the candidate passwords remaining in the list.

This attack takes ~2³² offline work and 101*2¹⁶ online queries. This is better than the ideal of 2³² online queries that it should take.

It probably won't work in practice because the salts are kept secret and this library's API does a good job of ensuring salts would be changed if there was a breach and everyone got forced to change their password. But if we are being pedandic and assuming everything called a "salt" (instead of a "key") is known to the attacker, then it is a valid attack.