[liberationtech] Google confirms critical Android crypto flaw

[Maxim Kammerer]

On Thu, Aug 15, 2013 at 3:38 PM, Maxim Kammerer <mk at dee.su> wrote:
> On Thu, Aug 15, 2013 at 2:34 PM, Nathan of Guardian
> <nathan at guardianproject.info> wrote:
>> The best description is here:
>> http://armoredbarista.blogspot.ch/2013/03/randomly-failed-weaknesses-in-java.html
>
> Unbelievable… It seems that PRNG implementers suffer from NIH
> syndrome. If you are going to use /dev/urandom, then use it all the
> time, and rely on code that's reviewed and maintained by thousands of
> kernel people, not just your favorite buggy seeded PRNG du-jour. And
> even sans the bugs, consider something like the following in Apache
> Harmony (precursor of Dalvik's class library) [1, p. 131]:
>
>   iv = sha1(iv,concat(state, cnt));
>   cnt = cnt + 1;
>   return iv;
>
> So they're essentially constructing a state-based bit stream that
> varies in each block, and hash it with SHA-1 — exposing each
> intermediate hash value in the middle. Who the hell told them it's
> safe from cryptanalysis POV? E.g., SP800-90A's Hash_DRBG [2, p. 40]
> resembles nothing of the sort.
>
> [1] http://dx.doi.org/10.1007/978-3-642-36095-4_9
> [2] http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf

I have looked at (what I believe is) the code, finally:
git clone https://android.googlesource.com/platform/libcore
git blame luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java

Long story short — unbelievable POS monstrosity (of course), and
Google shares the blame. The paper authors are completely right —
seed[BYTES_OFFSET] is not assigned anywhere where it matters, and the
initial seed gets continuously partly overwritten with the counter at
the same offset 0. The funny part is that even if Apache Harmony
people were to get that part right, the PRNG would still possibly have
entropy issues due to this gem (slightly simplified below):

     lastWord = seed[BYTES_OFFSET] == 0 ? 0
             : (seed[BYTES_OFFSET] + 7) >> 3 - 1;

They didn't notice that subtraction takes precedence over bitshift, so
this last "word" (8 bytes — just to confuse with 4-byte words in
SHA-1, I presume) is taken from the wrong place in the array. How did
I notice the precedence blunder? Why, there is a commit:

    Author: Nick Kralevich <nnk at google.com>
    Date:   Wed Oct 20 13:53:55 2010 -0700

    fix operator precedence bug when calculating bits.

-            bits = seedLength << 3 + 64; // transforming # of bytes
into # of bits
+            bits = (seedLength << 3) + 64; // transforming # of bytes
into # of bits

So this Google guy noticed a precedence bug in one place, but left the
one a few lines above it (dating to Apache Harmony) intact. Not his
problem, probably — corporate programming at its finest. Had he fixed
the bug above as well, he might have noticed (or not) that the output
stream for a given seed remained completely unchanged.

In short, don't use Google's security-related code for anything important.

-- 
Maxim Kammerer
Liberté Linux: http://dee.su/liberte