4 ms·

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

by patio11 13y ago

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.

vbuterin 13y ago
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.
- x1024 13y ago
  XORing random streams doesn't have as much value as you think.
  - deleted 13y ago
    [deleted]
- patio11 13y ago
  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.
  - marshray 13y ago
    Generator A returns 32 bytes from /dev/urandom. Generator B returns 32 bytes from /dev/urandom. The application XORs them. What's the problem?
    - ig1 13y ago
      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.
      - marshray 13y ago
        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.
        tptacek 13y ago
        YES.
      - ars 13y ago
        > 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.
        patio11 13y ago
        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."
glurgh 13y ago
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.
- marshray 13y ago
  How would you verify this in 2 minutes?
  - glurgh 13y ago
    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.
    - marshray 13y ago
      But it took us days to arrive at this conclusion.
      - j_s 13y ago
        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 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! :)
      - glurgh 13y ago
        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!

by patio11 13y ago

vbuterin 13y ago

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.

x1024 13y ago
XORing random streams doesn't have as much value as you think.
- deleted 13y ago
  [deleted]
patio11 13y ago
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.
- marshray 13y ago
  Generator A returns 32 bytes from /dev/urandom. Generator B returns 32 bytes from /dev/urandom. The application XORs them. What's the problem?
  - ig1 13y ago
    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.
    - marshray 13y ago
      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.
      - tptacek 13y ago
        YES.
    - ars 13y ago
      > 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.
      - patio11 13y ago
        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."

glurgh 13y ago

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.

marshray 13y ago
How would you verify this in 2 minutes?
- glurgh 13y ago
  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.
  - marshray 13y ago
    But it took us days to arrive at this conclusion.
    - j_s 13y ago
      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 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! :)
    - glurgh 13y ago
      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!