News for hackers. Stuff that matters.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by patio11 on Thursday August 15, 2013 @01:59AM (#6216375)
Since this is as good a time as any: I snidely implied that this was likely to have been due to a bug on the part of the Bitcoin community rather than a design error in the Android platform. That seemed like a reasonable guess at the time, but it was wrong, so: sorry, Bitcoin et al devs.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by glurgh on Thursday August 15, 2013 @04:18AM (#6216689)
It was not a reasonable guess even at the time because it should have taken you all of 2 minutes to verify it is, in fact, not a reasonable guess. I don't think there is some great tragedy or mistake in being wrong about this but if you're going to gracefully admit wrongness, admit to the right kind.

You were wrong then and you could have easily known you were wrong then. This new disclosure doesn't make you righter or wronger in retrospect.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @05:40AM (#6216883)
How would you verify this in 2 minutes?
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by glurgh on Thursday August 15, 2013 @06:43AM (#6217051)
The programs in question were not manually seeding the RNG, as was patio11's suggestion. The app implementors in this case don't seem to have actually done anything wrong at all.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @08:07AM (#6217285)
But it took us days to arrive at this conclusion.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by j_s on Thursday August 15, 2013 @10:24AM (#6217919)
I believe this is the point in the discussion where people willing to do some digging indicated that the problem was most likely not in the apps:

https://news.ycombinator.com/item?id=6195707

It wasn't days, but I can't say for sure that it was minutes... my vote would be for hours! :)

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by glurgh on Thursday August 15, 2013 @05:04PM (#6220598)
Once it was clear what library was in use (on the day of the original announcement) it literally took minutes to eliminate that particular one. You're right that it's taken days to learn what the precise problem is - but that's exactly why I'm saying prematurely assigning blame is a mistake!
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by tptacek on Thursday August 15, 2013 @07:40PM (#6221308)
It really did take minutes to see that the bug was almost definitely not bitcoinj or the SpongyCastle code explicitly seeding the CSPRNG with crap.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by tptacek on Thursday August 15, 2013 @07:39PM (#6221303)
Yeah, Patrick. Apologize harder! Harder, dammit!
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by vbuterin on Thursday August 15, 2013 @03:44AM (#6216605)
I would still say it's a bug from the Bitcoin community to rely on one generator rather than XORing a few just in case.

And I'm saying that as a prominent Bitcoin user and not-so-prominent developer. We undervalue redundancy.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by patio11 on Thursday August 15, 2013 @03:53AM (#6216620)
That would be a very, very bad decision. As one possible implementation flaw, consider what happens where Generator A is /dev/urandom and Generator B is SecureRandom whose platform implementor has decided to implement their own pseudorandom number generation algorithm in cases where they're sure they have enough entropy but, if they aren't, they fallback to /dev/urandom.

That will pass all tests and work fine for all purposes right until hilarity ensues in whatever real world circumstances deplete the entropy pool. Note that after attackers realize that depleting the entropy pool is a victory condition, they can actively work to cause that.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @04:40AM (#6216750)
Generator A returns 32 bytes from /dev/urandom. Generator B returns 32 bytes from /dev/urandom. The application XORs them.

What's the problem?

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by ig1 on Thursday August 15, 2013 @04:49AM (#6216771)
If you're XOR multiple generators then if an attacker can zero out the other generators (i.e. draining the pool) they can reduce your security to the weakest generators you're using.

If both generators have the same underlying source then they're also likely to share any security vulnerability so XORing them is unlikely to improve the randomness and can introduce potential weaknesses.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @05:27AM (#6216856)
I see. OK. Well if you let an attacker zero out your random number generators, you're screwed. You'd better not let that happen.

This 'decrement pool entropy estimate and stop returning numbers' idea is the longest running mistake in crypto.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by tptacek on Thursday August 15, 2013 @07:41PM (#6221312)
YES.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by ars on Thursday August 15, 2013 @06:40AM (#6217043)
> they can reduce your security to the weakest generators you're using.

> and can introduce potential weaknesses.

This isn't true. XORing numbers can never decrease entropy. It can only increase it. So your security would stay at the strongest generator, plus some extra entropy from the weaker ones.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by patio11 on Thursday August 15, 2013 @07:20AM (#6217129)
XORing numbers can never decrease entropy. It can only increase it.

Let Generator A(x) equal "For any x, a perfect random number picked by the hand of God Almighty." Let Generator B equal "For any x, A(x+1) unless 'ars is asking in which case A(x)".

If ars chooses Generator A, ars is fine.

If ars chooses Generator B, ars is fine.

If ars chooses Generator C = A(x) ^ B(x), ars will very quickly see that ars' intuitions about math are in some circumstances incorrect. Ars might then think "Phew, good thing they weren't subtly correlated, or it would have looked great right until it didn't."

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by ars on Thursday August 15, 2013 @08:21AM (#6217332)
If your second generator has an output that is a function of the first then it's not a cryptographic RNG in the first place and then Generator B is NOT fine.

(Alternatively it could mean that you can only generator a single cryptographic random number, since all the rest are just functions of the previous one, and then again you are not fine. Either way Generator B is not fine.)

And in any case neither A nor B is a generator - only x is. Neither A nor B are adding any entropy whatsoever.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by nitrogen on Friday August 16, 2013 @01:47AM (#6222375)
If your second generator has an output that is a function of the first then it's not a cryptographic RNG in the first place and then Generator B is NOT fine.

A CSPRNG is a function that takes as input a small set of random bits and generates as output a large set of unpredictable bits. So "Generator B" can be a "cryptographic RNG" and be a function of, or at least correlated with, "Generator A".

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @08:12AM (#6217301)
Reading from /dev/urandom twice does not yield the same result, or even results subtly correlated under XOR.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @06:02PM (#6220887)
XORing numbers does decrease entropy to the extent that there is correlation between the numbers. But you're correct that you can accumulate entropy by taking poorly-random streams and XORing them, as long as they are independently poorly-random.

In cases where they might be non-independent, a simple hash function like even the otherwise broken MD5 would be better at combining them than XOR. But of course, we're now three steps down the path of constructing our own replacement for what the kernel and/or OpenSSL should be doing for us already.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by StavrosK on Thursday August 15, 2013 @07:16AM (#6217117)
A XOR A = 0
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @08:09AM (#6217291)
If your /dev/urandom returns the same sequence of 32 bytes twice in a row, you have something truly pathological going on.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by StavrosK on Thursday August 15, 2013 @08:13AM (#6217304)
In the above example, you're XORing urandom with itself.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @08:37AM (#6217386)
Run this a bunch of times:

     dd if=/dev/urandom bs=32 count=1 | xxd
Substitute 'base64' if you don't have 'xxd'.

If you get the same output twice, see a doctor.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by DanBC on Thursday August 15, 2013 @08:46AM (#6217414)
Why XOR urandom with itself?

You don't gain anything, and if your random numbers are correlated with something you're making it worse.

I guess it makes testing easier. Correlations will be easier to see.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @04:23PM (#6220329)
People were saying 'urandom XOR urandom' was a pathological failure mode. My point is that it's not going to return the same results twice.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by DanBC on Thursday August 15, 2013 @04:54PM (#6220536)
...but you understand that it doesn't matter that it's not returning the same results twice, and that it's still a fail, right?
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by tptacek on Thursday August 15, 2013 @07:43PM (#6221322)
Marsh probably does understand the implications here. What kind of "fail" were you thinking of? That it was pointless? I agree. That it's going to blow up? I less agree.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Thursday August 15, 2013 @08:32PM (#6221499)
Thanks 'tptacek.

The point is

     `dd if=/dev/urandom bs=32 count=1` XOR `dd if=/dev/urandom bs=32 count=1`
is not going to cancel out to be zero as some here are implying. No one is claiming that it's a net gain either though.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by DanBC on Thursday August 15, 2013 @08:42PM (#6221531)
As I understand it: You're taking a non-blocking source of randomness, and depleting its entropy pool quicker, which forces it to drop back into 'not very good random mode' quicker.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by tptacek on Thursday August 15, 2013 @08:43PM (#6221532)
Argh. No, that's not what happens. Think about this for a second. It's not like the "entropic" bytes have a color, and the pool gets low on the bytes with that color.
Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by marshray on Friday August 16, 2013 @02:00AM (#6222417)
It would be like that if you were looking at it decades ago when key sizes were small and cryptographers didn't have much faith in the one-way-ness of hash functions, or from the perspective of that branch of information theory which seems to permit the existence of arbitrarily powerful computers. A lot of guidance coughman pagescough is still written that way.

In the real world, our computers are limited by physics. It seems that in crypto, the least controversial assumption we can make is that given enough secret bits (i.e., entropy) we can be safe from brute force attacks.

Re:Google confirms Java and OpenSSL crypto PRNG on Android a... by x1024 on Thursday August 15, 2013 @03:48AM (#6216616)
XORing random streams doesn't have as much value as you think.