1
$\begingroup$

I'm making a very simple encrypter in C# which is basically a Stream cipher. The user enters a key(password), converted to a seed for a pseudo-random generator, and the pseudo-random generator generates the numbers used to shift the characters. The decrypt process goes the same, but then in inverse.

Here's the pseudo-code I use:

1. Get the characters
2. Initialize a seed with the value 0
3. Loop through each character, adding the characters' value to the seed
4. Return the seed

But that has a problem. What if I have a (poor) password, like Hello. The encrypted output would be the same if I used eHlol or loeHl. You can write this password in 5! = 120 ways. That's not good!

So I came up with a solution:

1. Get the characters
2. Initialize a seed with the value 0
3. Loop through each character, adding the characters' value times it's position to the seed
4. Return the seed

But that's not good either. With a large password, you would get huge skips in numbers if you modify the last number. That's bad, because you want the most permutations possible for a random number generator.

Example:

Last character(12) has a value of 10
10 * 12 = 120
Then you change it to 11
11 * 12 = 132
          ^ gap of 12

Then I changed step 4 into this:

4. Return the seed divided by the length of the key

That's not a good option either, because with large passwords it wouldn't really matter what the value was of the first character in order to make a difference.

Example:

Password size: 10
1/10 = 0
8/10 = 0

So what's a good method for user-based passwords?

$\endgroup$
  • 2
    $\begingroup$ If you use a pseudorandom generator to generate the keystream, it's not a one-time pad. $\endgroup$ – yyyyyyy Jan 4 '15 at 15:07
  • $\begingroup$ @yyyyyyy I know, if you have a random seed, that is used for a PRNG, it's sort of time pad. That's why I said based, but I should rename it to inspired. Thanks. $\endgroup$ – joppiesaus Jan 4 '15 at 15:10
  • 2
    $\begingroup$ @joppiesaus: Just rename it to what it is: A stream cipher. ;) $\endgroup$ – Nova Jan 4 '15 at 15:15
  • 1
    $\begingroup$ To turn a password into a key, you need to perform key stretching using a Password-Based Key Derivation Function. Examples (from passable to good) are PBKDF2, BCrypt, and Scrypt. Anything lesser (like a hash) will be terribly vulnerable to password guessing. $\;$ (update) Turns out Giles just said it! $\endgroup$ – fgrieu Jan 4 '15 at 15:43
2
$\begingroup$

What you're looking for is called a key derivation function, and more specifically a key stretching function.

A key derivation function takes some variable-size material and turns it into a fixed-size key in a deterministic way, such that calling the same function on the same input yields the same key, and the original material cannot be reconstructed from the derived key except by trial and error.

A key stretching function is a particular kind of key derivation function that adds an element of slowness. This is necessary when the input consists of low-entropy data such as a password. The legitimate user only has to calculate the result once, but an attacker who attempts to guess the password has to make the calculation once per guess, so the slowness hurts the attacker more than the legitimate user. Note that the function must be designed so that each attempt requires a complete new calculation: there is no work that can be factored between computing f(Hello) and f(Hellp).

In addition to taking the password as input, you should pass a unique label (a string that doesn't need to be kept secret), so that if you ever want to derive a different key from that password, you can pick a different label. The label should typically include at least the name of your application, the user name or ID, and a version counter. The label also needs to be unique in that nobody else in the world uses the same label, because if the same label is reused many times, an attacker could pre-compute stretched keys for common passwords for that particular label.

A key stretching function is also known as a password-based key derivation function. These functions are also what is needed to hash passwords (the salt in password hashing corresponds to the label in key stretching). Common choices are PBKDF2, bcrypt and scrypt.

Note that the stretched key will not have more entropy than the password, only as much entropy as the password. That's the best you can hope for. Making the stretching operation slow reduces the impact of brute force attempts, but it cannot eliminate them. If you produce a 128-bit key from a password that's chosen from a 4000-word dictionary, the resulting key still only has 12 bits of entropy — less if the password wasn't chosen randomly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.