# Tag Info

14

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

8

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

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

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

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

5

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

5

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

5

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

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

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

4

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

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

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

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

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

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

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

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

1

The scheme you described above has some flaws. Because you aren't seeding the hash input each iteration, you are really increasing your chance of getting collisions. This is a great example of why you should try to avoid implementing these things yourself. It's really easy to overlook something subtle that undermines your system's security. As previously ...

1

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)$, ...

1

If I understand the question correctly, you got an unknown value $s$, and known values $d$ and $r$, such that, for some one way function $H$, $H(s,r) = d$. You want to find both a function $G:\{0,1\}^*\times\{0,1\}^*\to \{0,1\}^*$ and a function $V:\{0,1\}^*\times\{0,1\}^*\to \{0,1\}$ such that for any $x$, $V(G(d,r'),s) = V(d,s) = 1$. Technically, at ...

1

Something similar as what you suggest is already known as "Expensive key schedule Blowfish", or "EksBlowfish". It is the encryption algorithm in the core of Bcrypt (a slow hash function designed for password hashing). It also incorporates a salt, and its setup function is like this (retyped from the paper): EksBlowfishSetup(cost, salt, key): state ← ...

1

A problem with your proposed solution is that the digest of the password is now "password equivalent". So, what does hashing it before sending it gain you? That said, I don't think either of your concerns are concerning (or should be concerning). For the first, see this. If anything, most passwords will have less than 256 bits of entropy anyways. For ...

1

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

1

Most hash functions ( it appears this includes S2k) are not memory intensive. As such you can run a bunch of computations of their iterated variants on a GPU very cheaply. Scrypt, however, is designed to be memory intensive, so you can't really run it effectively in parallel without huge memory requirements.

1

I am no expert at bcrypt, but looking at the pseudocode on Wikipedia makes be believe that you would. The reason being is that the cost value is used to calculate the state in EksBlowfishSetup. That state is never saved, so to recover it, you would have to recompute from the beginning. If the state were saved, it would seem you could start the loop up again ...

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