This was a comment I posted on https://github.com/codahale/bcrypt-ruby/pull/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 232 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 232 online queries to search through all of my candidate passwords. Here's the attack:
- Using my knowledge of the salt, I hash ~216 random preimages until I find one for every possible 2-byte prefix of the hash.
- Now I send each of those 216 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*216 online queries I learn the first 2 bytes of the hash.
- Now that I know the first 2 bytes of the hash, I do 232 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 216.
- Now I online query for each one of the candidate passwords remaining in the list.
This attack takes ~232 offline work and 101*216 online queries. This is better than the ideal of 232 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.