[Esapi-user] ESAPI Random Number Generation Broken

Kevin W. Wall kevin.w.wall at gmail.com
Thu Apr 10 00:57:48 UTC 2014


A more thorough reply, now that I'm at a REAL keyboard. :)

On Wed, Apr 9, 2014 at 6:45 PM, Bruno Girin <bruno at energydeck.com> wrote:
> I had a look at the code and I am slightly confused with regards to the root
> problem so Jim if you could send me the original email from David Rook, it
> would be very useful as it would give me a bit of context.
>
> Now for the things I found out by trying to break down the problem in
> individual pieces.
>
> #1 Bug 217 - getRandomInteger(1, 2) always returns 1
>
> This is because the [Secure]Random.nextInt(n) method returns a number from 0
> (inclusive) to n (exclusive) and the DefaultRandomizer implementation
> doesn't take that into account. So as suggested in the bug report, there are
> two ways to do this: either fix the code or fix the documentation. I can do
> either.

Hmmm... my gut tells me that people who have actually used this
are more likely using it as  getRandomInteger(1, N) where N is
larger than 2; e.g., N = 1000, and that they have never noticed it.

So I guess my own preference would be to fix it to match the existing
documentation, which is most people's expectations. (Hopefully,
there are not that many people using it who have begin to adjust
for its bugs. But that's something that we should note in the release notes.


> This is unrelated to the 2 points below as getRandomString doesn't use
> getRandomInteger.

Good thing, eh? ;)

> #2 getRandomString(int length, char[] characterSet) potentially skewed
>
> At the moment, this method creates the string one character at a time by
> selecting a character at random in the characterSet array. So in the case of
> the current implementation of CSRF tokens, it calls secureRandom.nextInt(62)
> 8 times.
>
> Kevin, your suggested implementation does this instead:
>
>
>     byte[] nonce = new byte[ n ];
>     secureRandom.nextBytes(nonce);
>     StringBuilder result = new StringBuilder(length);
>     for( int i = 0; i < nonce.length; i++ ) {
>         char c = characterSet[ Math.abs( (nonce[i] % characterSet.length) )
> ];
>         result.append( c );
>     }
>     return result.toString();
>
> So instead of calling secureRandom.nextInt(characterSet.length) to avoid a
> potential bias, we call secureRandom.nextBytes(). So far so good. However,
> this code introduces a bias in the loop through the modulo operator:
>
> nonce[i] % characterSet.length
>
> Assuming secureRandom.nextBytes() is not biased, the bytes in the nonce will
> be evenly distributed between -128 and 127. Taking a modulo of those bytes
> will therefore introduce bias if characterSet.length is not a power of 2.

Right; this is where I earlier wrote
   Regarding your #2... another reason I bumped it to 64 chars in the
char set. 64 == 2**6

I couldn't figure out how to (easily) map it to a uniform distribution
w/out some
complicated smoothing, so I figured 64 would work. Unfortunately, it
breaks backward
compatibility by adding to additional characters so if someone has a
regex matcher
against (say) CSRF tokens that looks something like this:

        [A-Za-z0-9]{8}

it would fail to match all possibilities because of the '_' and '.'
characters that
I added.

However, unlike base64 encoding, this encoding gives you the exact #
of characters
you request. That coupled with the fact that the '/', '+', and '='
that are used in
base64 encoding are not safe for URLs, that might be an advantage.

> So all this to say that I'm really not sure we can make getRandomString
> un-biased in the general case.

I agree. I suppose in theory we could do it, since it is should be statistically
possible (although some bias may remain; see the Javadoc for
Random.nextInt() for instance), but practically speaking, I think it
would way over complicate things. And if we had it wrong when it
was relatively simple, my confidence in getting it correct when it
was unduly complicated plummets close to zero. (Bruno: No intent
to disparage your coding abilities it is what it is and we all know
that complexity is an enemy of security.)

> #3 CSRF tokens
>
> Those have a number of problems as identified by Kevin: irrespective of
> bias, an 8 character string with each character taken out of a set of 62 has
> limited entropy. The only way to fix that is in DefaultUser rather than
> DefaultRandomizer so shall I create a new User implementation that returns
> longer CSRF tokens using a variation on base 64 encoding using '_' and '.'?

Dang. No, don't do that. Just change the DefaultUser to use a (new) property
from ESAPI.properties file. (It never really should have been hard coded as '8'
to start with.)  I think of CSRF tokens as being more associated with
authenticators--maybe just because they are a secondary cryptographic
token--but maybe something like

    # Set this to 8 to make it backward compatible with the insecure
setting in ESAPI 2.1.0 and earlier
    Authenticator.CSRF.tokenlength=20

You will have to also tweak SecurityConfigurator and
DefaultSecurityConfigurator classes
to add something to retrieve that property, and then call it from
DefaultUser.resetCSRFToken.

But I'd prefer that over forking DefaultUser. Doing that means that we
have to have a
way to define the user class of choice in ESAPI.properties (not
present today). Seems
like a lot of work for little return IMHO.

I really appreciate your helping out with this. Thanks so much!

-kevin
-- 
Blog: http://off-the-wall-security.blogspot.com/
NSA: All your crypto bit are belong to us.


More information about the Esapi-user mailing list