[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