tag:blogger.com,1999:blog-5845671313867906274.post229702680460569760..comments2024-03-03T00:45:39.827-08:00Comments on k3170: More Details on the Android JCA PRNG FlawKeith Makanhttp://www.blogger.com/profile/10220395050030522020noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-5845671313867906274.post-33116535865164484942013-09-16T23:27:45.839-07:002013-09-16T23:27:45.839-07:00For the flaw described in this blogpost, you can c...For the flaw described in this blogpost, you can confirm the entropy is reduced by doing this:<br />Replace the line <br />Streams.readFully(devURandom, result, 0, byteCount);<br />in org.apache.harmony.security.provider.crypto.RandomBitsSupplier.getRandomBits(int)<br />with some hardcoded byte array (like byte[] result = new byte[]{0, 1, 2, 3,..., 19};).<br />If you can produce the same random number after changing some element of the byte array, I think it is a proof that the entropy is reduced to fewer bits (64bits in this case).Klarc Ghunchttps://www.blogger.com/profile/07754911862279763972noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-91778822553636558962013-09-16T10:34:55.776-07:002013-09-16T10:34:55.776-07:00Hi,
Thanks for your reply. Reading against the...Hi,<br /><br /> Thanks for your reply. Reading against the random number generator weakness I found<br /> that there are two different java implementations. "java.util.Random" and<br /> "java.security.SecureRandom".<br /><br /> I did not realize it. I was trying to replicate the problem on the following website:<br /> http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html<br /> but is a different weakness (a previous one). [January, 2013] For this reason I expected<br /> to have the same outputs because in the above website the "r1" value is the same.<br /> But how is possible that the PRNG repeat the output (r1) ?<br /><br /> In the other hand, now I can see that the weakness that you describe here is<br /> different. Firstly because affect to "java.security.SecureRandom". Secondly<br /> because even using the same "seed" (thanks to /dev/urandom) the PRNG give<br /> different outputs, but is not as good as it should be.<br /> I got confused because a new bitconins problem occurs this month.<br /> http://www.extremetech.com/computing/164134-how-bitcoin-thieves-used-an-android-flaw-to-steal-money-and-how-it-affects-everyone-else [August, 2013]<br /> In this case no PRNG outputs were repeated but collecting enough messages <br /> they could obtain the private key. How ? Brute force ? This was because the<br /> seed problem related in this post ?<br /><br /> I would link all the PRNG problems and causes from the beginning.<br /> <br /><br /> Thanks youHéctor Marcohttps://www.blogger.com/profile/13856171752017463635noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-43492540434031579552013-09-15T14:40:34.068-07:002013-09-15T14:40:34.068-07:00Hay Hector,
I actually still have the code I used...Hay Hector,<br /><br />I actually still have the code I used to detail study this vulnerability I'll post it on my github page first thing tomorrow, hopefully this will show you the same things I noticed, I'll post a link to the code in a follow up comment.<br /><br />Though I what I can say about your approach is that you may be looking for the wrong thing, you may also be looking for it in the wrong way. Well not "wrong" but it would require a lot of work to detail the flaw using this kind of approach, namely to inspect and compare the output of the PRNG. <br /><br />The problem stems from how the "true" psuedo-randomness used to seed the PRNG *implicitly* is corrupted--by this I mean when the algorithm asks for X bits of randomness but it actually only operates on X-Y bits of randomness where Y is just too large to be ignored. Psuedo randomness here is an input to the PRNG sampled from /dev/urandom when not seeded implicitly.<br /><br />What this would cause is certain subsets (of the bits) of psuedo random seed would be predictable because of how they are corrupted--namely with counter values, it also violates the requirements for a cryptographically secure PRNG we need .i.e "X amount of psuedo-random output but only X-Y reliable psuedo-random bits are being used".<br /><br />The way I tested the code was to look at how the psuedo-random seed is corrupted, and whether multiple runs of the algorithm would end up using the same seed or would have large portions of the seed in common--the screenshot in the blogpost shows the seed value and how it changes after successive calls--when seeded implicitly. What this would mean?, given that the PRNG uses SHA to compute its output; if you know what the seed is or is going to be for the digest (SHA-1) computation you can then calculate the next seed, or large enough amounts of it to determine what the next digest would be. Simply seeding it and checking the output would not reliably show you the correlation especially if you're not inspecting the individual bits, you may be looking at the characters in the digest to see if they are "verbatim" the same but what you may miss that certain bit patterns appear for instance what does the character "a" and "z" have in common? They aren't *exactly* the same but their bit patterns are terribly similar! I'm not sure how you are checking the seed for similarity but you're simply inspecting the characters and checking whether they are the same you miss a lot of detail. <br /><br />Some advice: Try looking at how "much" of the bits are the same, look at whether you can reliably determine the probability of a certain bit in the PRNG output being a certain value, namely what is the probability (based on previous outputs) that a certain bit will be 0 or 1? it if its significantly greater than 50% probably closed to 60% then you have what's called a biased PRNG, this means its not cryptographically secure at all!<br /><br />I'll push the code tomorrow, and talk about what you should be noticing and why its bad.<br /><br />Cheers<br />k3<br /><br /> Keith Makanhttps://www.blogger.com/profile/10220395050030522020noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-89185241902270603582013-09-15T07:38:19.097-07:002013-09-15T07:38:19.097-07:00Hi,
I am trying to replicate the random number ge...Hi,<br /><br />I am trying to replicate the random number generator problem.<br /><br />Basically I am doing three tests:<br /><br />1) Using diferent random instances:<br /><br />SecureRandom random = new SecureRandom();<br />byte rnd1[] = new byte[8];<br /><br />for(int i=0; i< 10000; i ){<br />random = new SecureRandom();<br />random.nextBytes(rnd1);<br />...<br />isValueRepeated(..);<br />....<br />}<br /><br />2) Using the same random instance:<br /><br />SecureRandom random = new SecureRandom();<br />byte rnd1[] = new byte[8];<br /><br />for(int i=0; i< 10000; i ){<br />random.nextBytes(rnd1);<br />...<br />isValueRepeated(...);<br />....<br /><br />3) Test output with the same seed:<br /><br /><br />byte rndbytes1[] = new byte[4];<br />byte rndbytes2[] = new byte[4];<br />SecureRandom random = new SecureRandom("123456790".getBytes()); <br /><br />random.nextBytes(rndbytes1);<br />random.setSeed("123456790".getBytes());<br />random.nextBytes(rndbytes2);<br /><br />compare(..);<br /><br /><br />Result:<br />Test 1: All output values are different.<br />Test 2: All output values are different.<br />Test 3: rnd1 and rnd2 are different.<br /><br /><br />Can anyone explain what I am doing wrong ?<br /><br />Thanks you.Héctor Marcohttps://www.blogger.com/profile/13856171752017463635noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-71097231610553186732013-09-15T07:29:28.044-07:002013-09-15T07:29:28.044-07:00This comment has been removed by the author.Héctor Marcohttps://www.blogger.com/profile/13856171752017463635noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-1359857514663340862013-09-10T11:13:41.357-07:002013-09-10T11:13:41.357-07:00Gimmie sometime to read through the implementation...Gimmie sometime to read through the implementation a bit more, I would love to agree with you but right now I'm not completely sure. Although based on the way they calculate it in other instances I think you may be on the right track ;)Keith Makanhttps://www.blogger.com/profile/10220395050030522020noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-71586645253338101402013-09-10T03:11:31.362-07:002013-09-10T03:11:31.362-07:00Thanks for your prompt reply.
After studying the ...Thanks for your prompt reply.<br /><br />After studying the lines of filling counter and END_FLAGS (in for(;;){} ), I think lastWord means the position of seed array of first not fully-filled element.<br />For example, if we have filled 3 bytes into seed, I think lastWord should be 0 so that the line<br />seed[lastWord] |= (int) ((counter >>> RIGHT1[n]) & MASK[n]);<br />can make sense.<br />IMHO,<br />seed[BYTES_OFFSET] = 0 => lastWord = 0<br />seed[BYTES_OFFSET] = 1 => lastWord = 0<br />seed[BYTES_OFFSET] = 2 => lastWord = 0<br />seed[BYTES_OFFSET] = 3 => lastWord = 0<br />seed[BYTES_OFFSET] = 4 => lastWord = 1<br />...<br />that is why I think lastWord = seed[BYTES_OFFSET] >> 2 without adding extrabytes before shifting.<br />Please correct me if I'm wrong.<br /><br />Thanks.Klarc Ghunchttps://www.blogger.com/profile/07754911862279763972noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-10737577913496766052013-09-10T01:34:30.221-07:002013-09-10T01:34:30.221-07:00Hay thanks for your comment,
1. yeah uhm that &q...Hay thanks for your comment, <br /><br />1. yeah uhm that "- 1" seems a bit iffy to me its typically something a developer will leave in some code after trying to hack it into a functioning condition--brute-forcing a working solution. So I'm not sure why its calculated this way :/ I would have simply left this as ">> 2", actually if you have a look at the Provider Implementation for the SHA Message Digest you'll see it calculated as you suggested :)<br /><br />"<br /> lastWord = (buffer[BYTES_OFFSET] + 3)>>2 ; // computing of # of full words by shifting<br /> // # of bytes<br />"<br />from https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1_MessageDigestImpl.java [line 86-87]<br /><br /><br />2. I think "extrabytes" are added to compensate for a padding frame, though other instances of this calculation are done quite differently including the example above, in the SHAImpl, it calculates the bytes offset as follows:<br /><br />"<br /><br /> int index = intArray[BYTES_OFFSET];<br /> int i = fromByte;<br /> int maxWord;<br /> int nBytes;<br /><br /> int wordIndex = index >>2;<br /> int byteIndex = index & 0x03;<br />"<br />from https://android.googlesource.com/platform/libcore/+/jb-release/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1Impl.java [lines 174 - 180]<br /><br />I honestly am not sure but I think it has something to do with compensating for a frame that holds other counter data. I read this code to find out how the PRNG corrupts /dev/urandom output, I haven't studied a lot of its other properties. Keith Makanhttps://www.blogger.com/profile/10220395050030522020noreply@blogger.comtag:blogger.com,1999:blog-5845671313867906274.post-40190790657744405522013-09-10T00:59:33.063-07:002013-09-10T00:59:33.063-07:00Hi, thanks to your post. It is clear.
The possible...Hi, thanks to your post. It is clear.<br />The possible solution might be re-calculating the lastWord variable after updateSeed(RandomBitsSupplier.getRandomBits(DIGEST_LENGTH)); since seed[BYTES_OFFSET] is updated.<br />But I have a few questions about calculating the variable lastWord.<br />1. In Java operator precedence, >> is lower than +/-. Therefore (...) >> 3 - 1 is equal to (...) >> 2. I am not sure if this is what it means to do.<br />2. Why extrabytes is used here? At first I assumed that a word is 8-byte (as the comment after declaring extrabytes suggests). Thus, (num_bytes + 7) / 8 - 1 will be the index of last word. Only the previous operator precedence problem here. But it seems that a word here is 4-byte and the lastWord is the index of seed array.<br />I think the correct implementation should be lastWord = seed[BYTES_OFFSET] >> 2. Am I right?<br /><br />Thanks.Klarc Ghunchttps://www.blogger.com/profile/07754911862279763972noreply@blogger.com