# Tag Info

22

It is not impossible, only harder. This is because of RAM. In a GPU, you have a number of cores which can do 32-bit operations. They will run at one operation per cycle and per core, as long as they operate on their respective registers. RAM access, however, is more troublesome. Each group of cores has access to a small amount of shared RAM, and all cores ...

9

Any time there is a choice and password search is an issue, one should prefer scrypt or perhaps bcrypt to stretched-md5, or even PBKDF2. The reason is that scrypt and bcrypt provide better security, by requiring a bigger investment in hardware (in particular, RAM) for the would-be password cracker, assuming parametrization yielding the same runtime for ...

9

OpenPGP's "Iterated and Salted S2K" is just a single hash instance over a very long input, which consists in the repeated concatenation of the salt and the password. This is extremely GPU-friendly, especially when using a hash function which is built over 32-bit elementary operations (this category includes MD5, SHA-1, SHA-256 and RIPEMD-160; GPU are not as ...

8

bcrypt uses Blowfish, which is a block cipher (albeit with a much enlarged key schedule). As such, Blowfish implements a permutation of the space of 64-bit blocks; and there should be no way to distinguish Blowfish (using a random key) from a permutation extracted at random, with uniform probability, from the set of permutations over 64-bit blocks (there are ...

8

Let's get terminology right. If you talk of "unknown s" then s is not a salt; when some piece of data is secret, we call it a key. And your "hash function" is then a MAC. In the context of "password hashing", such things are sometimes called "peppering" (as always, technical terminology is, at its core, a collection of bad puns). If your MAC is correct ...

7

Introduction BCrypt is a password-based KDF (far from state-of-the-art, but better than PBKDF2, because BCrypt requires sizable RAM, which greatly increases the cost of hardware-accelerated password search). Bcrypt is based on the blockcipher Blowfish, with the initial processing of the password reminiscent of Blowfish's key preprocessing. Bruce Schneier's ...

6

The plain hash itself does not give any indication of the number of iterations. But with practical schemes, such as most crypt based ones, the number of iterations is stored alongside hash and salt in the database. Keeping the number of iterations secret doesn't gain you much security in practice. Figuring out the number of iterations isn't that hard in ...

6

The answer to the original question would have been: Yes, it would be impossibly difficult to exhibit workfactor, salt, password0, password1 such that bcrypt(workfactor, salt, password0) = bcrypt(workfactor, salt, password1); but even if that was feasible, it would not matter much, because in normal use at least one of the password is unknown to an adversary ...

6

To increase the work factor, there are three approaches you could take: Rehash all passwords immediately, continue the same hash Take the hash currently stored in the password file, and hash it a few more times. We may (see below) be able to do this immediately with every entry in the password file. Example: let's switch from a work factor of 10 (i.e., ...

6

It's called a key derivation function because that's what you'd typically use its output for — as a key for some other cryptographic algorithm. (Of course, you can also use the output of Bcrypt for other purposes, e.g. storing it in a database as a password hash, but that's really a secondary use case.) In general, key derivation functions (KDFs) ...

5

The BCrypt password hash algorithm is based on a modified version of the Blowfish encryption algorithm. The $P$ values are the round subkeys (used for XORing with the data), and the $S$ values are components for substitution boxes, both used in a Feistel network. The initial values for $P$ and $S$ are the same as in the original Blowfish algorithm, and come ...

5

Points 3 and 4 are a secure way of storing the input to bcrypt (with appropriate choice of parameters for bcrypt). Points 1 and 2 aren't necessary but don't harm: they would add a small amount of extra computation for an attacker is possession of the password database that wants to do a dictionary attack; the attacker wouldn't be able to straight-out use ...

5

No you don't have to. The hashed bcrypt password includes the work factor that originally created it. You only include the work factor when you hash it originally, after that you pass in the supplied and hashed password. So you can increase the work factor when you create new hashes and add an update to upgrade the old hashes over time, when the user next ...

5

The threat model of password storage is that of server compromision, where the attacker gain access to the database and server code. The attacker can then run the code to test password candidates, possibly making modifications, porting to faster platform, etc. The attacker will not bother computing the fake hash and fake salt. So this scheme is twice as ...

4

It's called key derivation because it is used to obtain a "strong" key based on a key you own and is not so strong. Suppose a user has a password 12345 and an online service needs authentication. In order to verify the correctness the server doesn't store 12345 but it stores bcrypt(12345+salt) which further makes is more difficult for an attacker to break ...

4

The scrypt function is specifically designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs, making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of paralleling ...

4

Instead of that home-grown scheme, I would use PBKDF2 instead if you simply are sold on the idea of iterated hash schemes. It uses an such a scheme, although not exactly the one you have described, and is well-studied and considered secure. However, PBKDF2 doesn't offer many advantages over bcrypt, as PBKDF2 is still vulnerable to GPU and FPGA/ASIC ...

4

You have two algorithms, $A$ and $B$, that claim to compute two (essentially) injective, hard-to-invert and costly-to-compute functions $F$ and $G$. Your fear is that either of the algorithms instead compute functions $F'$ and $G'$, that may be neither injective, hard-to-invert, nor costly-to-compute. This may happen because of programming mistakes or (these ...

3

What I did in one of my password generators is that given a secret key $K$, public data $\text{Pub}$, I first generate a solid "master key" $K_m$ via key-stretching the secret key using PBKDF2 (any other key derivation function would work, I just happened to have that lying around): $$K_m = PBKDF2(K, \text{salt, iterations, } \cdots)$$ And then derive ...

3

About the best you can do is have a master public/private key pair where the public key is stored on your server and the private key is stored offline. When you generate a new private key, encrypt it with the master public key and store that in the database. That way, if a password is ever lost, you can recover the user's private key by using the master ...

3

For a penetration tester, I do not know of any easy way to determine the number of iterations given only black-box access to the application -- unless you find some other vulnerability that gives you an "in" to access this information. If you find some other vulnerability that gives you access to the database, you can read the number of iterations from the ...

3

To begin with, I see four potential problems with your key file. The work factor (8) is probably too low. If we presume you pick your pass phrase by selecting $c$ words at random from a list of $2^{13}$ distinct words (e.g. correct horse battery staple) you get a pass phrase with $13c$ bits of entropy. (AFAIK the dictionary used by Diceware only barely ...

3

According to http://www.oid-info.com/ bcrypt has no official OID. You could register a private enterprise number with IANA and assign your own OID for your purpose. But that's going to make interaction with 3rd party application more complicated. Or you could use PBKDF2 instead of bcrypt. PBKDF2 is a public-key cryptography standards. Libraries such as ...

3

Is it bad to use this method to store passwords? Yes. It is bad. Why? It's bad because you're rolling your own crypto, which is generally considered a bad choice. It's bad because SHA-3 is slow in software (e.g. on servers and consumer PCs) and fast in hardware (e.g. FPGAs, ASICs) and hence attackers can relatively fast try out many passwords. So ...

2

From the answer you linked to: For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward ...

2

It is not really clear what you propose instead of the original algorithm - using ExpandKey(state, salt, key) instead of ExpandKey(state, 0, key)? What about the second call ExpandKey(state, 0, salt)?. You are right, each ExpandKey(state, 0, xxx) contains one XOR-ing of xxx into the P-array, and then Blowfish-encrypting multiple 64-bit blocks of zeros – in ...

2

First, separate the idea of "salt" from "hash". Salting is no more than a process applied to the message in a known way, such as appending the salt value to the end of the original data, yielding a "salted" message that differs from the original message. The hash algorithm is then performed using the salted message as input, yielding a digest value. A ...

2

In the first part of your question, you appear to be describing a password hashing scheme. A common (or, at least, commonly recommended) way to construct such schemes is based on a message authentication code (MAC). Specifically, let $\operatorname{MAC}_K(m)$ be a message authentication code with key $K$ and message $m$, and let $H(s,r) = d = (r, c)$, ...

2

The point of SRP is to remove the need for the SSL/TLS certificates. With SRP integrated into SSL/TLS (as per RFC 5054), you get mutual client/server password-based authentication and can do without any of the dreadful certificate business; and yet the protocol is still resilient to offline dictionary attacks. If your SSL/TLS still uses a server certificate ...

2

So your idea is that the client does the work in calculating the slow hash $B(P)$, and proves that to the server by using a hash as an encryption key. It is definitely not a standard way to do things, and has some problems. In particular, any eavesdropped can trivially launch an offline dictionary attack on the password, so it is like your normal password ...

Only top voted, non community-wiki answers of a minimum length are eligible