4 ms·

If you don't trust the hardware, then you've already lost, no matter what algorithmic construction you are using. How are you going to trust your random number

by patio11 13y ago

If you don't trust the hardware, then you've already lost, no matter what algorithmic construction you are using. How are you going to trust your random number generator if 1 + 1 = 2 except when it equals NSA? (This is one of those times where I regret HN that has twin interests in software security as an engineering science and software security as a political statement.)

H3g3m0n 13y ago
> If you don't trust the hardware, then you've already lost, no matter what algorithmic construction you are using. How are you going to trust your random number generator if 1 + 1 = 2 except when it equals NSA? You can verify the random number generator. If you know the algorithm and the seed values you can run it on multiple different platforms, or with a pen and paper and verify that the output is as expected and repeatable. If you have large amounts of entropy you are feeding into it, you can log it for testing purposes. There are also apparently some EC based algorithms that can be used to fix or at lease reduce the impact of a compromised random number generator. That might not protect against a active attack on your specific system by the NSA (they could send/embedded a magic packet that gives them total control over the CPU for example), might even be possible for it to happen on the NIC controller rather than the CPU if it has access to the system bus. At the least they could flip it into some kind of backdoor random number mode by embedding some extra data in a TLS handshake or whatever. But it should protect against widespread passive surveillance.
- tptacek 13y ago
  Reducing the impact of a CSPRNG state compromise is a basic design goal for CSPRNGs, and you don't need ECC to do it; the "NSA backdoored" RNG you're referring to is one that no system anyone knows about actually uses, for that reason. Again: you're making a point that has nothing to do with my comment. If you don't trust RDRAND, don't use it. But you should still be using the OS's CSPRNG. Just make sure your OS isn't using RDRAND. Done and done.
ig1 13y ago
It's about verifiability, you can verify if a CPU is adding incorrectly, there's no way of verifying if the random source is generating randomness correctly. Integers form a closed group (in the group theory sense) under multiplication and addition, so if you were concerned about specific calculations being compromised you could verify the answer via alternative calculations and testing for consistency. Faking consistency is likely impossible without causing a huge amount other calculations (which the CPU will do as part of day-to-day operations) to fail. Making the CPU alter calculations only under very specific circumstances and in an undetectable way would require a huge amount of complexity. On the other hand we know several fairly trivial ways of faking reversable randomness using standard crypto algos that would be statistically undetectable without taking the hardware apart.
- patio11 13y ago
  Tell you what: You write executable code which tests whether, e.g., Ruby's Fixnum addition is actually adding or not, without using introspection on the implementation. (i.e. You're allowed to test any combination of inputs and outputs, but cannot look within the black box.) Feel free to use number theory, statistics, or a web service which wraps Cthulu in JSON. I will provide a script which monkeypatches Fixnum such that your test script still reports "Yep, it's still adding correctly" and which will predictably cause 1 + 1 to equal the string "LOL I AM THE NSA" under attacker-chosen conditions. There are many, many ways I could do this as the crafty adversary, but I anticipate my implementation would be roughly seven lines long and trivially implementable in hardware. (At complexity somewhere between a half-adder and the circuits which we had to hand-draw for our finals in hardware design, which -- obviously -- are a drop in the ocean of complexity on a modern CPU.)
  - ig1 13y ago
    Say you wanted your backdoor to kick-in when I was calculating the fibonacci sequence, will you also detect when I was calculating it via the golden ratio, or via continued fractions, etc. If I can write a test that can show that there's a backdoor because it's not behaving consistently then your attack is significantly weaker then a RNG attack. You can't just break one calculation under specific circumstances, you have to break any way of verifying it which means compromising pretty much every calculation. (not to mention you'd have to figure out that it's the fibonacci sequence being calculated and not some other calculation that happens to start with 1+1) Remember you don't have an interactive attack, you have one chance to build something and ship it out in hardware, and it then has to compromise software that's going to be written in the future. The beauty of the RNG attack is that it's undetectable, introduces a backdoor into a huge number of systems and it only makes the system vulnerable to the attacker and not to anyone else.

by patio11 13y ago

H3g3m0n 13y ago

> If you don't trust the hardware, then you've already lost, no matter what algorithmic construction you are using. How are you going to trust your random number generator if 1 + 1 = 2 except when it equals NSA? You can verify the random number generator. If you know the algorithm and the seed values you can run it on multiple different platforms, or with a pen and paper and verify that the output is as expected and repeatable. If you have large amounts of entropy you are feeding into it, you can log it for testing purposes. There are also apparently some EC based algorithms that can be used to fix or at lease reduce the impact of a compromised random number generator. That might not protect against a active attack on your specific system by the NSA (they could send/embedded a magic packet that gives them total control over the CPU for example), might even be possible for it to happen on the NIC controller rather than the CPU if it has access to the system bus. At the least they could flip it into some kind of backdoor random number mode by embedding some extra data in a TLS handshake or whatever. But it should protect against widespread passive surveillance.

tptacek 13y ago
Reducing the impact of a CSPRNG state compromise is a basic design goal for CSPRNGs, and you don't need ECC to do it; the "NSA backdoored" RNG you're referring to is one that no system anyone knows about actually uses, for that reason. Again: you're making a point that has nothing to do with my comment. If you don't trust RDRAND, don't use it. But you should still be using the OS's CSPRNG. Just make sure your OS isn't using RDRAND. Done and done.

ig1 13y ago

It's about verifiability, you can verify if a CPU is adding incorrectly, there's no way of verifying if the random source is generating randomness correctly. Integers form a closed group (in the group theory sense) under multiplication and addition, so if you were concerned about specific calculations being compromised you could verify the answer via alternative calculations and testing for consistency. Faking consistency is likely impossible without causing a huge amount other calculations (which the CPU will do as part of day-to-day operations) to fail. Making the CPU alter calculations only under very specific circumstances and in an undetectable way would require a huge amount of complexity. On the other hand we know several fairly trivial ways of faking reversable randomness using standard crypto algos that would be statistically undetectable without taking the hardware apart.

patio11 13y ago
Tell you what: You write executable code which tests whether, e.g., Ruby's Fixnum addition is actually adding or not, without using introspection on the implementation. (i.e. You're allowed to test any combination of inputs and outputs, but cannot look within the black box.) Feel free to use number theory, statistics, or a web service which wraps Cthulu in JSON. I will provide a script which monkeypatches Fixnum such that your test script still reports "Yep, it's still adding correctly" and which will predictably cause 1 + 1 to equal the string "LOL I AM THE NSA" under attacker-chosen conditions. There are many, many ways I could do this as the crafty adversary, but I anticipate my implementation would be roughly seven lines long and trivially implementable in hardware. (At complexity somewhere between a half-adder and the circuits which we had to hand-draw for our finals in hardware design, which -- obviously -- are a drop in the ocean of complexity on a modern CPU.)
- ig1 13y ago
  Say you wanted your backdoor to kick-in when I was calculating the fibonacci sequence, will you also detect when I was calculating it via the golden ratio, or via continued fractions, etc. If I can write a test that can show that there's a backdoor because it's not behaving consistently then your attack is significantly weaker then a RNG attack. You can't just break one calculation under specific circumstances, you have to break any way of verifying it which means compromising pretty much every calculation. (not to mention you'd have to figure out that it's the fibonacci sequence being calculated and not some other calculation that happens to start with 1+1) Remember you don't have an interactive attack, you have one chance to build something and ship it out in hardware, and it then has to compromise software that's going to be written in the future. The beauty of the RNG attack is that it's undetectable, introduces a backdoor into a huge number of systems and it only makes the system vulnerable to the attacker and not to anyone else.