Encryption: How to turn an 8 character string into a 128-bit key, 256-bit key, etc?

Question

I tried to research this, but there were still some questions left unanswered. I was looking into figuring out how an 8 character password gets turned into a high-bit encryption key. During my research I found articles that would talk about the salt value.

Assume you could get all 256 characters to play with, then an 8-character password would be 64-bits long. So, the remaining 64 bits is simply a salt value. And, correct me if I'm wrong, but this is done so that if someone was going to try to try ALL the possible values (brute force) they'd have to try all 128-bits since even the salt is unknown.

My questions really relate to this 'salt' value:

1. When someone makes an application, is the salt value hard-coded into it? And if so, can't it be obtained through reverse engineering the executable?
2. If the salt is generated at random, then I assume it must have some way to duplicate it. So, isn't that function that returns a random salt able to be reverse engineered to force it to duplicate itself to get the salt value?
3. This might be out of the scope, but if a salt value is generated on a server side (of a client/server relation), then wouldn't it have to be shared with the client so they can decrypt data sent by the server? And, if it's being sent over to the client, can't it be intercepted which makes it useless?
4. Is there some other method that is used besides this 'salt' value that can turn an 8-character string into a strong encryption key?

Answer 1

1) Each password is salted differently, and the salt is stored with the hash.

2) It's stored.

3) No, the client never decrypts anything. It sends the password, which the server salts, hashes and compares.

4) Yes, I'll add a few links.

Answer 2

As usual with security-related questions, this answer's going to be a long one.

First, the simple answer.
Q: How does one turn an 8-character string into a 128-bit key?
A: One doesn't.

This is a truthful answer. Now, one that's more appropriate to what you're asking:
A: Create a random 64-bit value, and store it with the password in the database. Now, the password is half the key, and the random value is the other half.

This one is a lie. Here's what you actually do:
A: Hash the password along with a random salt using a method producing 128-bit or longer output. Use 128 bits of that as the key. Store the salt.

Now to address your questions on salt. First off, the purpose of salt is not really to lengthen encryption keys. It is to prevent people building rainbow tables - mappings from hashed to unhashed forms. To see that your encryption is no stronger, just imagine the attacker knows your key-extending algorithm. Now, instead of guessing 128-bit keys, he just guesses your 64-bit password and then uses the same algorithm. Voila. If the salt is unknown to the attacker, yes, you've gained a bit, but they must already have your ciphertexts to attack them, and the salt must be stored in the plain along with the ciphertext. So this is an unlikely scenario.

1. Salt is random per encryption key.
2. Random means random. If you are insufficiently random when you use a cryptography algorithm which assumes unpredictable material, you are vulnerable. That's what /dev/random is for - the system entropy pool is very good. Get a better hardware RNG if you're worried.
3. Yes, if you salted the key, someone needs the salt to decrypt things you encrypted using the salted key's hashed value. No, sending the salt does not necessarily compromise your data; send the salt only to someone who has proved they already have the password, but it's stored in your database next to the ciphertext. As mentioned above, someone needs both the salt and the ciphertext to mount an attack. Again, the purpose of the salt is not to raise the strength of the encryption, it is only to prevent precomputation attacks against your hashes.
4. There are methods of key extension. But, fundamentally, your protection is only so strong as its weakest link, so to provide 100% unbreakable encryption you will need a one-time-pad (a truly random key as long as the data to be encrypted). In the real world, what is usually done is hashing the password along with a salt to produce unpredictable longer keying material.

Answer 3

1. Salts are generally not hardcoded, but they are generated at random, usually server-side, and never communicated to the user.

2. The salt would be stored in a database, separate from the passwords. The idea is that even if the password hash database is stolen, it would be very difficult to get the actual passwords (you'd have to try a lot of combinations), without having the salts as well. The salts would be generated at random, and different for each user, so even if you found it out for one, you'd still need to find all the others.

3. The salt is never sent, because the client never decrypts anything. The client sends the password to the server, the server adds the salt (which is randomly generated and stored for each user, and the user never know it).

So basically on this is what happens.

On registration:

1. User sends password to server.
2. Server adds a random salt to the password and then hashes it.
3. The salt and final hash are stored in separate tables.

On login:

1. User sends password to server.
2. Server fetches stored hash, and adds it to the password.
3. Server hashes the password and salt.
4. If the final hash matches the one in database, the user is logged in.

Answer 4

...Is there some other method that is used besides this 'salt' value that can turn an 8-character string into a strong encryption key?

YES but...

You can compute the hash of that 8-character string:

For example if you need a 256 bit key:

key-256bit = hash(8-character string) //use SHA-256 - very secure key-128bit = hash(8-character string) //use MD5 no more considered secure

"into a strong encryption key?" about strong.... depend how strong you need it because if you use only a 8-character string it mean that you could only create 2^8=256 different hash values and that's an easy task to brute force!!

conclusion: a salt would be of great value!

cheers

Daniel

Answer 5

The function that turns a password or passphrase into a cryptographic key is called a Key Derivation Function (this might help you searching for more information on the topic). Such functions take a password and a randomly generated salt, and produce a key through a process that is deliberately computationally intensive. To reproduce that key, you must have both the password and the salt - so you are correct, the salt must be stored or transmitted along with the encrypted data.

The reason that Key Derivation Functions use a salt is to increase the work factor for any attacker. If a salt was not used, then a given password will only ever produce one single key. This means that an attacker can easily create a dictionary of keys - one key for each word in his dictionary. If, on the other hand, a 64 bit salt is used then each password can produce ~2**64 different possible keys, which expands the size of the dictionary by the same factor. This essentially makes producing such a dictionary ahead-of-time impossible. Instead, the attacker has to wait until he's seen the salt value, and then start generating keys to test. Since the key derivation function is computationally expensive, this is slow, and he won't be able to get far through his dictionary in a reasonable timeframe.