2
$\begingroup$

This might be too broad to apply for all CSPRNG, but it might apply for the general case, I'm not sure. I need this specifically for python os.urandom() and SystemRandom() which get a seed from /dev/urandom, and on Windows CryptGenRandom(),

Is it possible to truncate or even modify the random number but still retains its randomness. The reason I need to do this is because the OS has nanosleep and the overflowing digits I will need to cut off.

$\endgroup$
5
  • $\begingroup$ you want all the numbers to appear with equal probability after truncate? $\endgroup$ – crypt Jun 17 '17 at 18:42
  • $\begingroup$ @Raza i can understand that, but there exist truncated probability distribution such as truncated exponential dist. to produce random numbers and rejection sampling. While, im no statistician/cryptographer I was wondering if there was anything on similar lines $\endgroup$ – Anderson Jun 17 '17 at 18:47
  • 2
    $\begingroup$ to keep the distribution probability satisfied, you take mod of the number with nearest power(n) to 2 such that desired range of random numbers is less than 2^n. after that if your number is in desired range, you use it, if not, you repeat the process. this way you will get sufficient level of randomness. if you just truncate the result to your desired range, it may loose randomness $\endgroup$ – crypt Jun 17 '17 at 18:57
  • $\begingroup$ define your new upper range as a 2^n to avoid validating a simple rnd % upper operation. if you end on a non-power-of-2, it's a lot more complicated to assure uniform distro, especially on the "end caps" $\endgroup$ – dandavis Jun 17 '17 at 19:06
  • $\begingroup$ @dandavis Not that hard, Raza just showed a not very efficient but valid way of doing so for any kind of number. $\endgroup$ – Maarten Bodewes Jun 17 '17 at 19:43
5
$\begingroup$

The idea for the security notion of Cryptographically Secure Random Number Generators (CSPRNGs) is that at the very least they are as good as Pseudo-Random Generators (PRG) which is why I'm applying their security notion of Indistinguishability.

This says that the probability that somebody can distinguish a PRG from a truly random sequence is better than guessing is negligible.

Now what you want to is to truncate the output of a CSPRNG (that is, you straight-up discard certain bits from the output). Now assume the result was insecure. As this truncated part would also be output by the actual CSPRNG, you could then "just" use this sub-part of the output and use the weakness we assumed to distinguish the CSPRNG's output from random. Now we assumed this to be impossible, so it can't be that such a weakness as assumed above exists and thus it must be secure.

A similar argument applies if you apply a public bijection on the output or a part of it.

$\endgroup$
3
  • 1
    $\begingroup$ Don't you need to caveat this? Forming a distinguisher will only work on truncated binary output. The OP is specifically just truncating. You can't just truncate ASCII representation by dropping the last overflowing digits as it'll introduce strong bias. $\endgroup$ – Paul Uszak Jun 17 '17 at 21:16
  • $\begingroup$ @PaulUszak I added a corresponding remark, thank you. $\endgroup$ – SEJPM Jun 17 '17 at 21:18
  • 1
    $\begingroup$ "A similar argument applies if you apply a public bijection on the output or a part of it." There will be part of the population of the earth - probably way over 99% - that doesn't understand this sentence. $\endgroup$ – Maarten Bodewes Jun 17 '17 at 22:15

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.