[Esapi-user] ESAPI Random Number Generation Broken

Jim Manico jim.manico at owasp.org
Wed Jun 25 13:59:49 UTC 2014


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; 
>> 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
>>     <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/81e76923/attachment-0001.html>


More information about the Esapi-user mailing list