Re: password strengthening: salt vs. IVs
Before the bad old days of using DES, there was the old days of one- way functions. These one-way functions were not hash functions, they were one-way. They were in a sense related to hash functions, but perhaps more directly related to redundancy checks and similar polynomials. Except that those aren't one-way at all, just many-to-one, right? It seems to me that if the CRC poly is known than it's easy to come up with something with a particular CRC. Well, real hash functions are many-to-one. Consider the set of all 33- byte strings. Consider s', which is the set of all the 256-bit hashes of all of those strings. It doesn't matter what hash function you use, there will be duplicates. There must be duplicates. The functions we used in those pre-bad-old-days included the AUTODIN- II polynomial and the Purdy Polynomial (I had to go look it up, because those parts of my memory were put on the free list). AUTODIN- II had undesirable qualities, which is why things migrated to Purdy. But based upon my quick research, Purdy seems to still be good for its purpose, namely grinding up passwords. The way we used Purdy had to be improved, as time went on. There was a time in which you could bypass a password length limit by small bits of cleverness. If you had your favorite three-character password, and that mean old system manager set the minimum length to 6, you could bypass that by appending the string "" (that's 8x 'U' and 16x 'V') to your three- character password and poof it worked again. Why this worked and the fix are left as an exercise to the reader, but I'll note that the underlying issue is something that hash function designers still have to make sure they solve to this day. Joux and Kelsey have written a lot about this very same problem, the length extension attack. With salt, you want the number to be unique-ish, as the whole point is to stymie dictionary attacks. A counter is likely not such a great idea, because of collisions, Do you mean if everyone starts at zero, the adversary could generate dictionaries for 0..9 etc., or something else? I mean precisely that. If you use a counter, the dictionary low numbers is valuable. This is one of the many problems that came up in WEP. It seems to me that a single counter is ideal for preventing collisions. Randomly-generated numbers have collisions because of birthday paradox. Let's suppose you selected a "full-width" prime number, and your counter incremented (or multiplied) by that prime. That's better than 0, 1, 2, ... but only if everyone doesn't select the same prime. Thus you get back to using the RNG. If the width of your salt is wide enough, you don't have to worry about birthday attacks. If you have 8 bytes of salt, the chance of a single collision is .5 when you have about 4 billion numbers selected. 4 billion is a large number if it is the number of accounts on your mail server. If you are fortunate enough that it is not a large number, you can either go to 16 bytes of salt, or weasel out of the issue by observing that even with 100 billion accounts, the number of collisions is not so large that there is a clear advantage to the attacker who precomputes a single dictionary. (And how do they know which dictionary to compute, a priori?) When we're talking about precomputed rainbow tables, 2^64 is a large number. How does this design sound: Each system has a randomly-generated seed which should be unique to the computer. They may then either derive a system-specific seed from that, or use it directly. They then use CTR mode with that seed as a key to create a computationally-unpredictable sequence which is guaranteed to not repeat until it has exhaused the entire period. Aside: I have recently taken a job doing crypto for a financial institution. If anyone has any suggestions with respect to reading about this industry, or conferences to go to (I seem to recall a financial crypto conference of some kind), I'd greatly appreciate it. Simple is good. Why not just pull enough salt off of /dev/urandom and make a small handwave about how big "enough" needs to be? If you tell me that, I listen, nod, and we're done. With your scheme, I have to think before I understand. Having to think before understanding is not a feature. I think I can see a minor flaw, but I don't want to spend the brain power on it. The RNG is your friend. Eight bytes of salt is almost certainly fine. If you have to worry about single collisions, use 16 or 32 bytes of salt. In general, I recommend using a width of salt that is the size of an underlying block size. If you're using AES somewhere, just go with 16, because that's the natural amount. Jon - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: password strengthening: salt vs. IVs
On Oct 29, 2007, at 12:24 PM, travis+ml- [EMAIL PROTECTED] wrote: * PGP Signed by an unknown key So back in the bad old days when hashing was DES encryption of the zero vector with a fixed key, someone came up with salt as a password strengthening mechanism. I'm not quite sure why it was called salt. Before the bad old days of using DES, there was the old days of one- way functions. These one-way functions were not hash functions, they were one-way. They were in a sense related to hash functions, but perhaps more directly related to redundancy checks and similar polynomials. The belief was that storing passwords in plaintext was a bad idea. A related notion was that storing a password encoded through a symmetric function was essentially storing it in plaintext. The term salt comes from the metaphor of considering the process of one-waying a password to be like making hamburger out of meat, or stew out of ingredients, or some other cooking metaphor. The salt was introduced to address the issue of dictionary attacks and carried the observation that cooking is better if you add a little salt to it. The salt was a sprinkling of an arbitrary constant into the function to spice it up a bit. The people who worked on these password-grinding systems had a tendency to sneer at those who would use a cipher such as DES for that because DES is reversible. Using a reversible function is essentially storing the password in plaintext. Munging DES was seen by those people as inferior to designing one-way functions that were properly one-way. Eventually, these became a subset of what one would use a hash function for. The IV in a block cipher serves the same function as salt. It's called an IV, though because of the different path of development. The term "salt" gets used in other places, like with randomized hashing, which is often also called salting a hash, too. The question you had is how much entropy there should be in salt. The answer is none, but that's a very subtle answer. Salt is -arbitrary- as opposed to -random-. As it turns out, the best way to get a 256- bit arbitrary number is to pull it off your RNG. Arbitrary numbers like salt, don't have to worry about subtle issues that you'd want key material to worry about. Arbitrary numbers are in general public (or at least not secret), and key material is secret. With salt, you want the number to be unique-ish, as the whole point is to stymie dictionary attacks. A counter is likely not such a great idea, because of collisions, but there are all sorts of things you could do that would be very very bad with key material but are mostly okay with salt. Nonetheless, the easiest way to get salt with a system that has an RNG is to just pull the number off the RNG. But that doesn't mean it has entropy. Now as what to call it? I like "salt." Jon - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: password strengthening: salt vs. IVs
On Mon, 29 Oct 2007, [EMAIL PROTECTED] wrote: > So back in the bad old days when hashing was DES encryption of the > zero vector with a fixed key, someone came up with salt as a password > strengthening mechanism. > > I'm not quite sure why it was called salt. > > It perturbed the S-boxes in DES IIRC, but essentially it was a known > bit of text that was an input to the algorithm that varied between > entries, like an IV does with encryption. > > If there isn't already a term for this, I'm going to call this > general concept "individuation", or possibly "uniquification". > > Nowadays with strong hash algorithms, but rainbow tables and > low-entropy passwords as the threat, I'm wondering what the best > practice is. Use a good existing password hash (e.g. OpenBSD's bcrypt[1]) or some well reviewed KDF (e.g. PKCS #5 PBKDF2[2]). Perhaps I'm not imaginative enough, but I can't think of a use case that is not covered by these algorithms. Given decent salt they will not succumb to reverse (rainbow table) lookup and both include parametised computation complexity to drive up the cost of brute force attacks. -d [1] http://www.openbsd.org/papers/bcrypt-paper.ps [2] http://www.rsa.com/rsalabs/node.asp?id=2127 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: password strengthening: salt vs. IVs
On Mon, 29 Oct 2007 14:24:23 -0500 [EMAIL PROTECTED] wrote: > So back in the bad old days when hashing was DES encryption of the > zero vector with a fixed key, someone came up with salt as a password > strengthening mechanism. > > I'm not quite sure why it was called salt. > > It perturbed the S-boxes in DES IIRC, but essentially it was a known > bit of text that was an input to the algorithm that varied between > entries, like an IV does with encryption. > > If there isn't already a term for this, I'm going to call this > general concept "individuation", or possibly "uniquification". > > Nowadays with strong hash algorithms, but rainbow tables and > low-entropy passwords as the threat, I'm wondering what the best > practice is. > > I was thinking of simply prepending a block of text to each passphrase > prior to hashing, and storing it with the hash - similar to salts in > passwd entries. > > It should have at least as much entropy as the hash output, maybe a > little more in case there's collisions. If it were uniformly random, > you could simply XOR it with the passphrase prior to hashing and save > yourself some cycles, right? > > Would it be appropriate to call this salt, an IV, or some new term? That's an IV. I strongly suggest your read the Ritchie and Thompson paper on the reasons for the salt. While making sure that two identical passwords rarely hashed to the same value, it had another purpose: protecting against hardware attacks. Ritchie and Thompson assumed that there would be generic DES chips; they didn't want those to be used in a password-cracking machine. Accordingly, the salt was used to permute the E-box -- not the S-boxes -- to prevent that. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: password strengthening: salt vs. IVs
On Oct 30, 2007 6:24 AM, <[EMAIL PROTECTED]> wrote:
> So back in the bad old days when hashing was DES encryption of the
> zero vector with a fixed key, someone came up with salt as a password
> strengthening mechanism.
>
> I'm not quite sure why it was called salt.
>
> It perturbed the S-boxes in DES IIRC, but essentially it was a known
> bit of text that was an input to the algorithm that varied between
> entries, like an IV does with encryption.
>
> If there isn't already a term for this, I'm going to call this
> general concept "individuation", or possibly "uniquification".
>
> Nowadays with strong hash algorithms, but rainbow tables and
> low-entropy passwords as the threat, I'm wondering what the best
> practice is.
>
> I was thinking of simply prepending a block of text to each passphrase
> prior to hashing, and storing it with the hash - similar to salts in
> passwd entries.
well what you're describing is quite classically a salt, imho.
> It should have at least as much entropy as the hash output, maybe a
> little more in case there's collisions. If it were uniformly random,
> you could simply XOR it with the passphrase prior to hashing and save
> yourself some cycles, right?
well no. i mean to xor it (or probably what you mean: to otp it)
you'll need to have a "salt" who's length is equal to the input. that
would then mean that short inputs would result in short salts. i.e. a
password of "a" may result in the "salt" of "x". hash("a" ^ "x") is
hardly secure against a rainbow table.
so you're better off maintaining the salt in a separate location
(after all, the threat model is that someone takes the db and has a
list of all the hashes, and then calculates out the passwords) and
still prepend it on before the main passphase.
you may consider, however, that if this "salt" is as long as one block
of the input to the hash algorithm, it effectively becomes a new iv.
but what that has to do with anything; i don't know ...
> Would it be appropriate to call this salt, an IV, or some new term?
>
> --
> Life would be so much easier if it was open-source.
> http://www.subspacefield.org/~travis/> Eff the ineffable!
> For a good time on my UBE blacklist, email [EMAIL PROTECTED]
--
mike
http://lets.coozi.com.au/
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
password strengthening: salt vs. IVs
So back in the bad old days when hashing was DES encryption of the zero vector with a fixed key, someone came up with salt as a password strengthening mechanism. I'm not quite sure why it was called salt. It perturbed the S-boxes in DES IIRC, but essentially it was a known bit of text that was an input to the algorithm that varied between entries, like an IV does with encryption. If there isn't already a term for this, I'm going to call this general concept "individuation", or possibly "uniquification". Nowadays with strong hash algorithms, but rainbow tables and low-entropy passwords as the threat, I'm wondering what the best practice is. I was thinking of simply prepending a block of text to each passphrase prior to hashing, and storing it with the hash - similar to salts in passwd entries. It should have at least as much entropy as the hash output, maybe a little more in case there's collisions. If it were uniformly random, you could simply XOR it with the passphrase prior to hashing and save yourself some cycles, right? Would it be appropriate to call this salt, an IV, or some new term? -- Life would be so much easier if it was open-source. http://www.subspacefield.org/~travis/> Eff the ineffable! For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpsfGwr9Iy35.pgp Description: PGP signature
