[Esapi-user] ESAPI Random Number Generation Broken

Jim Manico jim.manico at owasp.org
Wed Jun 25 16:31:37 UTC 2014


One more note, yes lack of reseeding is the root cause.

But if we just force a new instance each time or reseed every few minutes,
that can be disaster on servers that are needing frequent secure random
(where seeding entropy is low) - the requests have the potential block and
kill the app.

I'm actively researching this (and will loop you into a few more
conversations). This is a •lot• tougher than I expected.

--
Jim Manico
@Manicode
(808) 652-3805

On Jun 25, 2014, at 3:32 PM, Jeff Williams <jeff.williams at aspectsecurity.com>
wrote:

  I know all that, but I’m trying to focus on the specific issue
identified.  Are you suggesting that not reseeding is responsible for
failing the Burp tests?



--Jeff





*From:* Jim Manico [mailto:jim.manico at owasp.org <jim.manico at owasp.org>]
*Sent:* Wednesday, June 25, 2014 10:00 AM
*To:* Jeff Williams; Bruno Girin
*Cc:* Kevin W. Wall; esapi-dev at lists.owasp.org; esapi-user at lists.owasp.org
*Subject:* Re: [Esapi-user] ESAPI Random Number Generation Broken



Let me correct one thing:

"You are using a single instance of SecureRandom without reseeding."

...should be...

"We are using a single instance of SecureRandom without reseeding."

There is no blame meant to be spread here, I just want to help make the
random number generation super strong since it's so important to so many
aspects of a security library.

I just CC'ed you into a conversation with a research professor that has
done extensive research in this area. I think he can explain the problem
better than I.

Seeking a solution,
Aloha,
Jim

 On 6/25/14, 2:57 PM, Jim Manico wrote:

Jeff,

You are using a single instance of SecureRandom without reseeding. This is
definitely a problem and is in general a poor practice (and without doubt
leads to poor random numbers).

However, this is way more complex of an issue. The problem with regular
reseeding depends on how you instantiate SecureRandom (what algorithm),
what OS are you using, how much entropy you have available on your OS, are
you using blocking or non-blocking OS level random calls, etc. It's a tough
problem.

I just ran into Steven Murdock from the Tor foundation and he has been
working on this  (so has DJ Bernstein, a internally well know
cryptographer) and I'll send you a copy of their research as soon as I can.

Normally, I would not harp on this kind of usage of SecureRandom, but
because ESAPI is a security library, we really need to get this right.
It's not as it stands, no question about it.

PS: Java 8 improves upon this and provides a new API:
http://docs.oracle.com/javase/8/docs/api/java/security/SecureRandom.html#getInstanceStrong--
which is what we should be using for " high-value/long-lived secrets like
RSA public/private keys". But even then, using the same instance without
reseeding with lead to a PRNG, not a CRNG sequence.

- Jim

On 6/25/14, 2:11 PM, Jeff Williams wrote:

The problem (if there is one) almost has to be in the test suite or Java’s
SecureRandom.  The ESAPI code does very little here. I strongly suspect
that it is the test.  Remember that these tests are looking for a purely
random set of bits, and that is not what the API provides.  The ESAPI
provides random characters from a defined character set.



Does anyone see a problem with this part?



    public String getRandomString(int length, char[] characterSet) {

        StringBuilder sb = new StringBuilder();

        for (int loop = 0; loop < length; loop++) {

            int index = secureRandom.nextInt(characterSet.length);

            sb.append(characterSet[index]);

        }

        String nonce = sb.toString();

        return nonce;

    }



--Jeff





*From:* Bruno Girin [mailto:bruno at energydeck.com <bruno at energydeck.com>]
*Sent:* Tuesday, June 24, 2014 4:16 PM
*To:* Jim Manico
*Cc:* Jeff Williams; Kevin W. Wall; esapi-dev at lists.owasp.org;
esapi-user at lists.owasp.org
*Subject:* Re: [Esapi-user] ESAPI Random Number Generation Broken



Hi all,

Apologies for going completely silent after having promised to look into
this. Real life caught up with me. That said I will be in Cambridge
tomorrow and Thursday and would be keen to talk about the future (or lack
thereof) of ESAPI if anybody is interested.

Cheers,

Bruno


  *Bruno Girin*, CTO, EnergyDeck Ltd
Email: bruno at energydeck.com, Mobile: +44 7990 545 927, Direct: +44 20 3021
0557
Web: www.energydeck.com, Twitter: @EnergyDeck
<http://twitter.com/#%21/energydeck>
Address: Level 4, 17-19 Cockspur Street, London SW1Y 5BL, UK



On 11 April 2014 02:58, Jim Manico <jim.manico at owasp.org> wrote:

I think this is a code error, not a documentation error. Our random string
generator, which effects CSRF tokens, has poor randomness now reported by
two folks, in addition to several that noted it off list.

But I think Jeff's concearn about Burb is totally fair, I hope we are wrong
and that it's only Burp that is in error, but I doubt it. A bunch of bits
are bytes.

More on the Burp's random sequencer tester here
http://portswigger.net/burp/sequencer.html and here
http://www.securityninja.co.uk/application-security/burp-suite-tutorial-sequencer-tool/
- These are at least FIPS compliant tests (and more), and FIPS demands
20,000 samples to test, which was in line with Mr. Rooks tests.

Kevin, can you toss us your test code when you have a chance?

Aloha,
Jim




On 4/10/14, 12:33 AM, Jeff Williams wrote:

Since most calls like this in Java are exclusive, we should just change the
documentation.

On the bigger issue, the Burp tool is based on the NIST test suite right? I
grabbed a copy from NIST and ran a bunch of tests.  The first thing is that
you have to be very careful generating the file to make sure you don't
accidentally write two byte characters.  So I'd like to see the real code
you are using to generate tests.

Second, my understanding is that the Burp tests work on bitstreams, not
bytes.  If you just looked at bits, you would see a very obvious pattern in
ESAPI random strings using APLHANUMERIC.  The top and bottom few bits of
each byte would always be zero.  From Burp's point of view the bits don't
appear random at all causing the test to fail.

Could that explain the results?  I tried a test with ESAPI's
getRandomString and a charset of all characters (0-255) and got passing
results, although I want to confirm further.

--Jeff



 On Apr 9, 2014, at 8:58 PM, "Kevin W. Wall" <kevin.w.wall at gmail.com> wrote:

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.
_______________________________________________
Esapi-user mailing list
Esapi-user at lists.owasp.org
https://lists.owasp.org/mailman/listinfo/esapi-user
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.owasp.org/pipermail/esapi-user/attachments/20140625/d0ae14d0/attachment-0001.html>


More information about the Esapi-user mailing list