Bcrypt Step-by-Step
qvault.io
qvault.io
Most probably just a nod to OpenBSD (look at the initials), since the algorithm was made for it. Here[1] is the original commit that introduced the string.
[0]: https://security.stackexchange.com/a/237690/2876
[1]: https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt...
Back in the days before hashed or encrypted passwords, there was an interesting security hole in TOPS-10 on the PDP-10 due to direct password comparison.
Guess the password "aaaaaaaa", but put it in memory so that a page boundary falls between the first and second "a", and the second page is not resident.
TOP-10 allowed a user process to ask to handle its own page faults. Do that.
Now get the system to check the password. If your page fault handler gets called, you know that the password comparison got past the first "a" and tried to check the second "a". If you get a "wrong password" error, you know that the first "a" was wrong.
In the latter case, bump the first character and try again. You can discover the first character this way in at most N tries, where N is the number of characters in the character set used for passwords.
One you have the first character, repeat, this time with the page boundary between the second and third characters. Similar for the rest of the characters.
TOP-10 had lots of interesting security oversights. For example, the login system call, which was used by the login program to actually log you in once it verified your credentials, did not actually require any privileges. Its only restriction was that it only worked when executed by a process that was not logged in.
It turned out the login program was not the only program that could be run without logging in. You could also run the program to show the print queue. That program had a command to run other programs. Thus, you could walk up to any terminal that no one was logged in on, run the queue program telling it to run the debugger, and then from the debugger execute a login system call to login to any account you wanted. Oops.
TOP-10 also had some security things it did way better than Windows or Unix do today, such as access control lists. It used a totally different model than the "ACL as part of the file metadata for the file the ACL controls" model.
Instead, the way ACLs worked is that first the system checked the normal file permissions. If they allowed the access, it was allowed. If they denied the access, it then checked a flag that said the caller wanted to check ACLs. If that flag was not set, the access failed. If the flag was set, the kernel sent a message to a user-mode daemon, FILDAE, describing the desired access. FILDAE then got to decide if the access should be allowed or not.
The way FILDAE worked is that a user could have a file, ACCESS.USR, which FILDAE consulted. I don't remember if it looked for ACCESS.USR in the same directory as the file someone was trying to access, or the home directory of the file owner, or something else.
ACCESS.USR contained access rules, one per line. An access rule could specify a file or files (wildcards were allowed), a user (wildcards allowed), a group (wildcards allowed), an accessing program (wildcards allowed), type of access, and whether it was allowed or not.
So for example, if you wrote a game and wanted to maintain a high score file, you could put rules in ACCESS.USR that specified that anyone could write to that specific file if and only if they were running your game.
You could develop simple naming conventions that fit your security model, such as files whose name started with "pub" in a directory were publicly readable, and files whose names started with "prv" were not, and you could easily make exceptions for particular files or people or programs.
I think this fits in a lot better with the way most people naturally thing about access rules, making it a lot easier to avoid ACL mistakes.
I'd like to see a FILDAE for current systems. (Although to be fair, it does add some complexity that ACLs in metadata do not have. Because it was a separate daemon, there was the issue of communication between it and the kernel. People found some bugs that let them get FILDAE and the kernel confused about which FILDAE replies went with which requests).
Step 2) There is no step 2
Side note, I've seen a number of places (including the Scrypt repo) compare bcrypt brute-force benchmarks without specifying the bcrypt work factor.
It's very frustrating to see this, considering the time to compute a single bcrypt hash can be < 0.01 seconds (ie. work factor 7 or 8), or more than 1 minute (ie. work factor 20).
I'm not familiar with scrypt, but it looks like instead of providing a work factor, you can provide inputs like "max time to compute hash" and "max percent of ram to use computing hash" which presumably scales up as hardware becomes more powerful?
It's specified implicitly in the scrypt README file: "if 5 seconds are spent computing a derived key". It's explicit in the conference paper (cost = 16).
The command-line binary generally takes "max time" and "max ram" (as percent and/or raw value) and estimates appropriate cost values. As of version 1.3.1, you can manually specify cost values for the binary if you want.
Also, it's not a good idea to base your security parameters on the compute power of the most underpowered device in the chain.
That being said, for these cases you could use Argon2 which is mostly (entirely?) based on ARX constructs and will work well on embedded/underpowered devices
There are also some symmetric encryption shenanigans that can be done, but if you can use something other than password-based auth you're free from pretty much all of these problems, with probably much better security
It's not generally productive to nitpick between secure password hashing/key derivation functions. Unless you specifically know you can't use one of these in particular, you should just pick whichever one has a safe implementation in a secure cryptographic library that you can use.
Basically, just don't use MD5, SHA1, SHA2, SHA3 (including Keccak and the other contenders) or some non-cryptographic hash function.
> For the vast majority of developers, bcrypt, scrypt, argon and PBKDF2 provide functionally equivalent security
1) The "vast majority of developers" should not be implementing login systems, period. The chances most people have of not falling for any OWASP gotcha, making sound security choices, and implementing them correctly, is pretty much nil. Leveling the argument to this makes many things that should not be done sound passable.
2) They do not, categorically, provide "functionally equivalent security" (especially not for bare PBKDF2). This is a myth people believe in because they normalize their perception of deviant behaviour[0], and frame the situation as "if my database never gets pwned, any one of these is fine", which is just an argument based on wishful thinking, akin to "I can drive recklessly as long as I don't crash", but we don't use this reasoning to nullify seat-belts: the choice of algorithm is important precisely, and perhaps exclusively, for when all your other security mechanisms failed.
The reality though, is that more often than not, when databases gets pwned you never find out about it because monitoring and security practices is often lackluster, and then you keep believing that these things don't matter.
[0] https://en.wikipedia.org/wiki/Normalization_of_deviance
As a general rule for their security properties: Scrypt > Argon2 > Bcrypt, and PBKDF2 should be avoided. You should prefer the first one of these you can find with a robust implementation (which as @lanecwagner pointed out may not always be Scrypt, and that's fine, as is Bcrypt if you have implementation constraints)
Because password may be thought of as a first line of defense, folks have trouble with the notion of your password encryption being the last line of defense.
There are quite a few things we do that “bookend” other operations. I’ve certainly seen my fair share of people getting those wrong too (eg, teardown should often happen in the reverse order of setup, FILO)
Yep, agree. This also supports the idea that you shouldn't get too hung up on which to use, because hopefully that decision was made for you and one of these was selected.
> They do not, categorically, provide "functionally equivalent security"
Eh, disagree, if your database is breached and your digests are salted, any of these is fine. Of course there are technical differences because these are literally different algorithms, the actual difference in security provided by each is one of degree, not category. Unhashed vs hashed, and SHA2 vs bcrypt are what I'd call differences of category.
There are differences among them between classes of attacks they're susceptible to, provable security properties, and how paranoid should you should be in respect to advances cryptanalysis.
I tend to weigh these as significant factors given that the dynamics of password-based auth can very well lead to a database leak screwing someone over 20 years into the future, although I admit that you can't get too picky nowadays and I'd be very glad if we, as a species, could have what you described as a lower-bound (with the exception of PBKDF2, of course :P)
The password hashes buy you an improvement for the narrow range of passwords that are bad but not that bad against adversaries who are powerful but not that powerful. It's pretty much the definition of a marginal win. Which hash you choose slightly tweaks the margin.
It's essentially impossible that this is the lowest hanging fruit for your system security and so "use a different password hash" ought to be nowhere near close enough to the top of the TODO pile to get done if you're already using any of these decent password hashes listed such as PBKDF2.
If your users have strong passwords (e.g. a 20 alphanumeric random password from a typical password manager) it makes no difference at all. Even plain MD5() of such a password is as safe for the user and for you as Scrypt or Argon2 or other choices.
If your users have very weak passwords then once again it makes no difference. Your heavily tuned Scrypt password hashing doesn't prevent me guessing that Steevo412's password on your site might be something obvious like "letmein" - on a lowly mid-range laptop before I get bored.
So all this work is to achieve a marginal improvement in the middle. Maybe if Steevo412 has picked "LetMeInNOW" and maybe the script kiddies who stole the database ran out of stolen Amazon credits, they don't "crack" his password this time. Maybe.
And none of this makes you any safer from inadvertently leaking the plaintext passwords, which your system unavoidably needs to know during authentication, or numerous other pitfalls that have nothing to do with dick-measuring contests about which hash is better.
OR if security actually is important you could deploy something that's actually a clear improvement such as WebAuthn and stop trying to sweep the problems with password storage under increasingly complicated rugs.
Yes, but only if you assume that an adversary's power is stable over time, and that it's safe to amortize the risk over an extended period of time, both of which are wrong assumptions.
> If your users have strong passwords (e.g. a 20 alphanumeric random password from a typical password manager) it makes no difference at all
Yes, except that is not the world we live in, which makes this a pointless argument.
> If your users have very weak passwords then once again it makes no difference. Scrypt password hashing doesn't prevent me guessing that Steevo412's password might be something obvious
> None of this makes you any safer from inadvertently leaking the plaintext passwords, which your system unavoidably needs to know during authentication
Yes, if you frame the question as "being able to defend against threat models you can't effectively defend against under this authentication model" then indeed none of this matters, but that's a self-propelling argument, and also not the discussion we're having.
The discussion we're having is that given we know password-based auth is a bad security model, and that people have shit security practices, how do we squeeze the most value out of whatever entropy is given to us, in a way that will last as much as possible, since passwords are often recycled, rarely rotated, and you can get pwned decades into the future because of a leak that happened in 2004.
Password-based auth is a reality, and will keep on being for a long time. It's just not a defensible position to argue that there is no point in leveraging given entropy to the max because "we're all doomed anyways", or that since it's a bad model we shouldn't care.
The goal is explicitly to protect knowingly reckless users from themselves. Saying that "if they all used random passwords from a password manager it wouldn't matter" is not realistic or helpful.
> If security actually is important you could deploy something that's actually a clear improvement such as WebAuthn
I don't think anyone at any point in this thread defended passwords as a solid threat model, and I made this same point in another comment. WebAuthn is awesome, but passwords are a reality and will keep on being for a foreseeable future, we just have to deal with it
If you're on Golang, Rust, or C though: leverage your options!
Main page, including the signed tarball: http://www.tarsnap.com/scrypt.html