1
$\begingroup$

I need to get an int, derived by a given password, to feed it to a deterministic PRNG as a seed. The derived int should not give away any clues about the password.

How can I achieve this without getting too many collisions? (Because the integers are derived from a string that is much larger, I suspect that there will be many possible collisions, yet I want to minimize the chance of their occurrence.)

I have tried a few solutions and my current function strikes me as being too kludgy.

Here is the pseudocode of what I am doing right now:

password := getPasswordFromUser()
salt_len := 16
salt := getRandomBytes(salt_len)
// the password and salt is then put through a Key Derivation
// function. The key will be used for encryption.

// Here comes the part I have trouble with; to "randomize" the
// order in which the data will be stored, I am using a deterministic
// PRNG, which is seeded as follows:

// Create a long string that contains the password:
orderPasswd := password + "abcdefghijklmnopqrstuvwxyz" +
    "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ.,;:#+!§$%&/()=?"
// Create a sha256 sum of this string, feed it to the
// deterministic PRNG as seed and shuffle the string:
orderPwHash := sha256sum(orderPasswd)
// derive an int from the hash by converting it
orderPwSeed := int64(binary.BigEndian.Uint64(orderPwHash))
// shuffle orderPasswd using the Fisher-Yates shuffle algorithm
orderPasswd = shuffle(orderPasswd, orderPwSeed)
// Put orderPasswd through the KDF, hash the key and shuffle
// the order with an integer derived from the hash:
orderKey := getKey(string(orderPasswd[salt_len:]),
            orderPasswd[:salt_len])
orderKeyHash := sha256sum(orderKey)

// convert that hash to an integer to finally get the seed
// that will be used to determine the order
orderSeed := int64(binary.BigEndian.Uint64(orderKeyHash))

// seed the PRNG with orderSeed... shuffle the order...

Edit:

I have accepted Ilmari Karonen's answer, because he put a lot of effort into it and it contains vital information for anyone trying to implement cryptography.

I have dismissed the idea of shuffling the message, as it would unnecessarily complicate my code and increase the likeliness of mistakes without adding to the security, which is especially bad in this context.

Because the message, once encrypted with AES256 and a key derived with scrypt set with N=65536 and p=2, will look like random noise, this ought to be sufficient.

$\endgroup$
  • 1
    $\begingroup$ This is too broad. Could you share your code with us and show where you are getting the most collisions? $\endgroup$ – Robert Columbia Aug 19 '16 at 2:32
  • $\begingroup$ Is this for a game or something where it doesn't matter too much if the "security" of your scheme is broken? Because you won't be able to maintain security in the face of a modestly sophisticated attacker under these constraints (no salt, small seed, insecure RNG). $\endgroup$ – erickson Aug 19 '16 at 16:51
2
$\begingroup$

Based on your code, it seems that the seed value you're deriving from the password is 64 bits long. This implies that:

  1. due to the birthday paradox, you will likely see seed collisions after about 233 passwords, and

  2. with modern hardware, a reasonably motivated attacker could enumerate the entire 64-bit seed space, and thus break your encryption regardless of how secure your passwords and key derivation process are.

You really should consider making the seed longer: at least 128 bits, but if you want to be extra safe, going to 256 bits won't hurt. Of course, you also need to make sure that your PRNG actually uses that whole seed.

Also, you don't say what PRNG you're using, but unless it's specifically designed for cryptographic use, it's likely that an attacker can relatively easily compute the seed based on even just a small number of outputs.

In the comments, you also mention that you're using scrypt as part of your key derivation process. This is good, but based the rest of your design, it seems likely to be a bit like putting a steel vault door on a flimsy wooden outhouse. Fix all the other parts of your system to be as secure as scrypt, and you might actually end up with a safe cryptosystem.

In any case, given that you're using scrypt, there's absolutely no need for all the ad hoc shuffling and other klugy stuff in your key derivation code. Scrypt will shuffle your passwords far more thoroughly and efficiently anyway, and will yield a collision rate as close to the theoretical ideal as practically possible.

Just remember to set the parameters to scrypt appropriately (i.e. set the parallelism factor to something close to the typical number of cores on a modern CPU, and the cost parameter as high as you can make it while keeping key derivation time reasonable). And, again, remember that scrypt is almost certainly not the weakest link in your system.

$\endgroup$
  • $\begingroup$ Those points are all valid, and I have considered them before. The encryption itself is done with AES, using a 256bit key derived from the password and a salt generated by golang's crypto/rand by using scrypt. What I am trying to achieve is to obfuscate the order of the ciphertext with prepended salt by shuffling it with golang's math/rand which takes an int64 as seed. - Based on what has been said so far, could I use the password to also derive this int64, or would that be a BadThing™? $\endgroup$ – Manuel Aug 19 '16 at 16:44
  • $\begingroup$ @Manuel Shuffle the cipher text? What? Do you mean you are shuffling blocks of a single message, or what? Why isn't using a proper cryptographic mode sufficient? $\endgroup$ – erickson Aug 19 '16 at 16:55
  • $\begingroup$ @Manuel: Yes, you can use scrypt to derive, say, 256 + 64 = 320 bits of key material, and split that into your AES key and RNG seed. What I'm not so sure about is why you want to "obfuscate the order of the ciphertext". Presumably, you think that will help achieve some security goal, or you wouldn't be doing it. But if so, it would likely help if you told us what that goal is. $\endgroup$ – Ilmari Karonen Aug 19 '16 at 16:59
  • $\begingroup$ @erickson I want to shuffle the bytes of a single message, to make brute-forcing even more expensive, computationally. If implemented, it will be part of a steganography tool I am writing, where it is all about obfuscation. $\endgroup$ – Manuel Aug 19 '16 at 17:03
3
$\begingroup$

If you have access to a PBKDF2 implementation, I'd just take a 8 byte output of PBKDF2. Whether that's a Little Endian or Big Endian value doesn't matter so long as you're consistent.

Since PBKDF2 has good spread, a 64-bit capture from it gets a 50% chance of collision around the 5.1 billionth different input, still down at 1% around 600 million. (See the table on Birthday Attack.)

$\endgroup$
  • $\begingroup$ I am already using scrypt, which should serve the same purpose, but using PBKDF2 is no problem. - At this point, I have no way for storing a different salt; is it safe to reuse the salt or use a fixed salt, like say, an array of zeros? $\endgroup$ – Manuel Aug 19 '16 at 15:29
  • 2
    $\begingroup$ @Manuel: If you're already using scrypt, why are you bothering with all the voodoo mumbo-jumbo in your code? Just feed the password into scrypt and use its output as the key material. Do remember to set the work factor parameters appropriately (i.e. as high as possible without undue slowdown) and, if possible, include a random salt. $\endgroup$ – Ilmari Karonen Aug 19 '16 at 15:53
0
$\begingroup$

Password hashes are as pseudo-random as you can get from just the password. You could try to improve quality by mixing in the user name (but you should be using salted password hashes anyway). Also, try to use a RNG with more internal state than just a long. There are good pseudo-random with 256-1024 bits of internal state, so you can use more bits of your password hash.

$\endgroup$

Your Answer

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