[Esapi-user] ESAPI Random Number Generation Broken

Jeff Williams jeff.williams at aspectsecurity.com
Wed Jun 25 16:33:44 UTC 2014


I don’t understand how this could be.  The reason for reseeding periodically is to make it more difficult for an attacker to work out what the seed is, not because the output gets less random.

What am I missing here?

--Jeff


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

Yes, that's exactly why the Burp tests are failing.
--
Jim Manico
@Manicode
(808) 652-3805

On Jun 25, 2014, at 3:32 PM, Jeff Williams <jeff.williams at aspectsecurity.com<mailto: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]
Sent: Wednesday, June 25, 2014 10:00 AM
To: Jeff Williams; Bruno Girin
Cc: Kevin W. Wall; esapi-dev at lists.owasp.org<mailto:esapi-dev at lists.owasp.org>; esapi-user at lists.owasp.org<mailto: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]
Sent: Tuesday, June 24, 2014 4:16 PM
To: Jim Manico
Cc: Jeff Williams; Kevin W. Wall; esapi-dev at lists.owasp.org<mailto:esapi-dev at lists.owasp.org>; esapi-user at lists.owasp.org<mailto: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<mailto:bruno at energydeck.com>, Mobile: +44 7990 545 927, Direct: +44 20 3021 0557
Web: www.energydeck.com<http://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<mailto: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<mailto: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<mailto: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<mailto: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/2027d057/attachment.html>


More information about the Esapi-user mailing list