4 ms·

I wonder why they didn't go for an easy technique to defend against backdoors: use two independent sources for random numbers that don't know of each other and

by madez 9y ago

I wonder why they didn't go for an easy technique to defend against backdoors: use two independent sources for random numbers that don't know of each other and xor their output together. The increase in cost is small and the win for integrity and security is huge.

PhantomGremlin 9y ago
Yes, XOR. But what's also needed is simplicity. As another poster here said, "simply use getrandom()". Whether or not you agree with that exact function, the idea behind "simply" is exactly that, simplicity. It's a lot easier to audit code that does: getrandom() read hardware RNG XOR those two together done! btw ... keep a permanent log of these random numbers But, as the article said, things were much more complicated. Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays?
- tekacs 9y ago
  > Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays? From the analysis in the article it sounds like the function that you're describing was added to the dylib binary after compilation, so it was 'slipped' rather than 'allowed' into production. That said, auditing the binary and bindiff as suggested could perhaps mitigate the problem, modulo 'Reflections on trusting trust' and its mitigations.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- gizmo686 9y ago
  >getrandom() >read hardware RNG Not secure against a mallicious hardware RNG. In principle, the hardware RNG could access the memory and corralate its output with that of getrandom. For that matter, getrandom might be able to do something to muck with the hardware RNG, or with the code following. Or any code not part of your RNG scheme could try and muck with the results. >Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays? The code was audited and passed because there was no such check. The machine code that made it onto the machine did not match the source code submitted, but instead had an extra function tacked onto the end. How do you defend against this [0]. What if someone sneaks the backdoor in the firmware of the harddrive, that only provides the backdoored code to the CPU occasionally. At some point, you need to trust the people making the lottery machines. [0] Hint, reproducible builds and signed code; but this still devolves into a trusting trust situation.
  - madez 9y ago
    The trusting trust issue is solveable. Also, the deeper you go the more powerful you assume your adversary. If you limit the power of your adversary, you can stop before going fully back to a root of trust you can verify without a computer.
    - dfc 9y ago
      Trusting trust is solveable?
      - madez 9y ago
        Maybe let's first specify what we are talking about. With trusting trust I mean a chicken and egg problem: To verify a computer you need another computer you trust. But then, how would you verify the other computer? How would this be possible to solve? Exactly how you bootstrap building complex CPU's from scratch or a big factory in Factorio. You start from first principles and build a very simple computer you can verify without another computer. This guy is the root of the bootstrapping process. Then you build another computer that is too fast to check manually and make the first one check this one. Now, you already have a verified computer that you can only check with other computers. The basic idea is clear to me, but the specific steps are not. I guess one would need a simple language for the root of the bootstrap process and write a compiler or interpreter for another more complex language in it. Then, use the second compiler/interpreter to build a compiler/interpreter for a yet more powerful language (maybe that's already C), which we run on the next node. Using this process you can end up with a verified computer that can compile stuff, or what not. Since we would probably not be able to build a machine sufficiently fast for our needs, we need to use commercial and maybe backdoored computers. How do we protect against these? You get at least two different machines (at least different ISA) from different manufactures from different countries. Note, that it would not be a problem if they are backdoored. You must only ensure that they don't have identical backdoors. Now you create a verified program for each of the possibly backdoored computers and make sure that they know of each other, they must be unconnected. Their output goes into a simple verifieable machine that does only bit for bit checking. If a backdoor is trigged, then the output of the two machines won't be identical anymore. In this setuo one would need to generate random numbers on some trusted device and feed the same stream into both machines. Also, the operating system must be completely deterministic in it's behaviour. That is surely possible, but no one I know of is. Then, you have a verified setup that does exactly what is written in the source and any backdoor in the system itself will be detected. I'm convinced that the process above is doable for individual developers. But creating and engineering all the steps is a lot of work. I hope some day the community or maybe even governments will have created a manual "Creating trustable trust" where all the steps are worked out.
nene-LOvo 9y ago
bbb
MR4D 9y ago
And trying to explain that to a general population will be impossible. Secure? Yes. Workable? No.
tromp 9y ago
Instead of xor-ing multiple sources of randomness together, it's preferable to feed them all into a cryptographically secure hash function, like Keccak or Blake2. One of the sources to be added could be the header of a recently published bitcoin block.
- brians 9y ago
  Not quite. That gets you better mixing, but maybe Blake2 has bias in some bits, or bias in some output bits given bias in some input bits. Xor is nice in that xor of a biased bit and an unbiased bit is an unbiased bit.
- matt_wulfeck 9y ago
  it would be a terrible oversight to put that thing on the internet, either public or private.
teitelman 9y ago
You still need a program to perform the mixing. The intended source of entropy isn't really the issue. The integrity of the program which produces and displays these numbers is.

by madez 9y ago

PhantomGremlin 9y ago

Yes, XOR. But what's also needed is simplicity. As another poster here said, "simply use getrandom()". Whether or not you agree with that exact function, the idea behind "simply" is exactly that, simplicity. It's a lot easier to audit code that does: getrandom() read hardware RNG XOR those two together done! btw ... keep a permanent log of these random numbers But, as the article said, things were much more complicated. Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays?

tekacs 9y ago
> Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays? From the analysis in the article it sounds like the function that you're describing was added to the dylib binary after compilation, so it was 'slipped' rather than 'allowed' into production. That said, auditing the binary and bindiff as suggested could perhaps mitigate the problem, modulo 'Reflections on trusting trust' and its mitigations.
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
gizmo686 9y ago
>getrandom() >read hardware RNG Not secure against a mallicious hardware RNG. In principle, the hardware RNG could access the memory and corralate its output with that of getrandom. For that matter, getrandom might be able to do something to muck with the hardware RNG, or with the code following. Or any code not part of your RNG scheme could try and muck with the results. >Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays? The code was audited and passed because there was no such check. The machine code that made it onto the machine did not match the source code submitted, but instead had an extra function tacked onto the end. How do you defend against this [0]. What if someone sneaks the backdoor in the firmware of the harddrive, that only provides the backdoored code to the CPU occasionally. At some point, you need to trust the people making the lottery machines. [0] Hint, reproducible builds and signed code; but this still devolves into a trusting trust situation.
- madez 9y ago
  The trusting trust issue is solveable. Also, the deeper you go the more powerful you assume your adversary. If you limit the power of your adversary, you can stop before going fully back to a root of trust you can verify without a computer.
  - dfc 9y ago
    Trusting trust is solveable?
    - madez 9y ago
      Maybe let's first specify what we are talking about. With trusting trust I mean a chicken and egg problem: To verify a computer you need another computer you trust. But then, how would you verify the other computer? How would this be possible to solve? Exactly how you bootstrap building complex CPU's from scratch or a big factory in Factorio. You start from first principles and build a very simple computer you can verify without another computer. This guy is the root of the bootstrapping process. Then you build another computer that is too fast to check manually and make the first one check this one. Now, you already have a verified computer that you can only check with other computers. The basic idea is clear to me, but the specific steps are not. I guess one would need a simple language for the root of the bootstrap process and write a compiler or interpreter for another more complex language in it. Then, use the second compiler/interpreter to build a compiler/interpreter for a yet more powerful language (maybe that's already C), which we run on the next node. Using this process you can end up with a verified computer that can compile stuff, or what not. Since we would probably not be able to build a machine sufficiently fast for our needs, we need to use commercial and maybe backdoored computers. How do we protect against these? You get at least two different machines (at least different ISA) from different manufactures from different countries. Note, that it would not be a problem if they are backdoored. You must only ensure that they don't have identical backdoors. Now you create a verified program for each of the possibly backdoored computers and make sure that they know of each other, they must be unconnected. Their output goes into a simple verifieable machine that does only bit for bit checking. If a backdoor is trigged, then the output of the two machines won't be identical anymore. In this setuo one would need to generate random numbers on some trusted device and feed the same stream into both machines. Also, the operating system must be completely deterministic in it's behaviour. That is surely possible, but no one I know of is. Then, you have a verified setup that does exactly what is written in the source and any backdoor in the system itself will be detected. I'm convinced that the process above is doable for individual developers. But creating and engineering all the steps is a lot of work. I hope some day the community or maybe even governments will have created a manual "Creating trustable trust" where all the steps are worked out.

nene-LOvo 9y ago

bbb

MR4D 9y ago

And trying to explain that to a general population will be impossible. Secure? Yes. Workable? No.

tromp 9y ago

Instead of xor-ing multiple sources of randomness together, it's preferable to feed them all into a cryptographically secure hash function, like Keccak or Blake2. One of the sources to be added could be the header of a recently published bitcoin block.

brians 9y ago
Not quite. That gets you better mixing, but maybe Blake2 has bias in some bits, or bias in some output bits given bias in some input bits. Xor is nice in that xor of a biased bit and an unbiased bit is an unbiased bit.
matt_wulfeck 9y ago
it would be a terrible oversight to put that thing on the internet, either public or private.

teitelman 9y ago

You still need a program to perform the mixing. The intended source of entropy isn't really the issue. The integrity of the program which produces and displays these numbers is.