[OWASP_PHPSEC] Concatenating random numbers

Sven Rautenberg sven at rtbg.de
Sat Sep 28 20:34:11 UTC 2013


> Hello All,
> 
> I have this doubt that if I concatenate two smaller random numbers to
> generate a larger random number, then will that affect security ?
> 
> Suppose I have two 32 length random numbers and I concatenated them and
> created a 64 length random number.
> str1 (length 64) = generated by concatenating two 32 length strings
> str2 (length 64) = generated directly from the function
> 
> Now which of those two strings are more secure ?
> 

Hello, Rahul!

When discussing random strings, you should not discuss security, because
that is an aspect that does not apply directly to them. You should
discuss randomness itself.

What is randomness? Wikipedia has a lot of info, with this introductory
sentence summing it up nicely in my opinion:

    Commonly, it means lack of pattern or predictability in events.

Obviously the key factor is unpredictability, and in statistics that is
reflected in "any event has equal probability to occur". When rolling
dice, you expect that any number from 1 to 6 is equally likely to come,
and when rolling many times, counting the numbers should show that.

Now there is a second concept with these events: Either they are
independent or they are dependent. Rolling dice is producing lots of
independent events, because one single roll is not affected by how many
rolls were before, or which numbers were rolled. A dependent event would
be drawing lots in a lottery or drawing numbers in a BINGO game. Every
lot or number that has been drawn is removed and cannot be drawn again.

For your random number generation, the key question is: Does the
generation of the first string affect the second string, or not? If it
does not affect it, then you can concatenate as many strings as you
like, because the effect is just like rolling dice with a huge amount of
sides.

If however the first generated random number affects the second random
number, then you are in trouble. And because a computer usually is a
deterministic machine which cannot generate "real" randomness, but has
to calculate it, and adding some detected events that could not be
predicted, like mouse movement, you'd really have to analyze the random
number generator you are about to use for your concatenation.

> if I concatenate two random strings of length 32, then the attacker
> will have to guess both the strings. so that would take him 2^32 +
> 2^32 attempts. And to guess the 64 length string, his total attempts
> would be 2^64. Obviously 2^64 is greater than 2* (2^32)...so my guess
> is that it would be bad to concatenate. Am I correct ?

You are wrong. The attacker does not guess two shorter strings, he
guesses the combination of both.

If you explicitly let him detect the strings in isolation, and give
feedback on whether his guess for the first or second string was correct
or not, then you are right: He's only guessing two 2^32 strings.

But you are not telling him whether each single string is correct, you
combine them. So now the attacker has to guess the first string, and for
every guess he makes there, he has to test EVERY possibly second string,
because they only work in combination.

In fact, if you have two 2^32 strings combined, it is 2^32 * 2^32
combinations, or 2^(32+32) = 2^64.

But this only applies if your random number generator is good enough.

The basic random functions in PHP are NOT good enough if the result is
going to be used in a security context (i.e. it does not really matter
if they are used to randomly select a background image, but it does
matter for PHPSEC)!

http://stackoverflow.com/questions/17362402/why-is-phps-mt-rand-not-cryptographically-secure
http://security.stackexchange.com/questions/18033/how-insecure-are-phps-rand-functions

Regards,
Sven


More information about the OWASP_PHP_Security_Project mailing list