2
$\begingroup$

Is it practical to make a PRNG cryptographically secure if I shuffle the randomly generated numbers (say 256-bit) several times before hashing it, even if a hacker knows when I generate the numbers?

Note: They say PRNG is not cryptographically secure because the generation depends on the state of the generator, that it is somewhat deterministic and not random enough. Can the simple act of shuffling a 256-bit PRNG (length is around 77-78 numbers, i.e. probability of generating all 9s is close to zero) be good enough to make it cryptographically secure?

More specifically, if I use Python's random.getrandbits() to randomly generate a length of 256-bit numbers and then use random.shuffle() on it several times, can this help make the numbers cryptographically secure? Can this even resist quantum hacking?

$\endgroup$
  • $\begingroup$ That's a very interesting question once restated in general terms. What degree of state convolution is required for a generator's output to cross the cryptographically secure threshold? I would suggest that's an open question somewhat equivalent to calculating Kolmogorov complexity. $\endgroup$ – Paul Uszak Oct 25 '18 at 3:10
  • $\begingroup$ @PaulUszak It's not an open question. It just has to provide confusion and diffusion. $\endgroup$ – forest Nov 7 '18 at 2:03
  • 1
    $\begingroup$ @PaulUszak A single toggled bit in the input should toggle each output bit with a 50% probability (diffusion). There must be no mathematical correlations between the input and the output (confusion). The requirements are very similar to that of a cryptographic hash function. $\endgroup$ – forest Nov 7 '18 at 4:43
2
$\begingroup$

I assume what you are asking is if I take a non-cryptographic random generation, is it enough to shuffle and then hash to get something cryptographically secure. In general, the answer is most certainly no. To start with, a non-cryptographic random call typically has very low entropy. I assume that random.shuffle() is also a non-cryptographic function, and so you are adding low-entropy randomness to low-entropy randomness; the result still has very low entropy and can be brute forced. At the end, you hash the result. I am assuming here you want to use a cryptographic hash function. In such a case, under reasonable modeling, if the input to the hash function has high enough entropy then you are fine; otherwise you are not. I assume here you are not.

In any case, as with all cryptography, it is very very very hard to get this right and you should not try to invent it yourself until you are an expert.

$\endgroup$
  • $\begingroup$ It's also possible that the RNG used for generating pre-shuffle inputs is the same RNG used to shuffle a list. Then no entropy is added. Adding low entropy to low entropy would be a best case scenario. $\endgroup$ – Future Security Oct 25 '18 at 23:50

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.