6 ms·

Except if /dev/urandom is using a hardware based random number generator, then you have to trust that the hardware hasn't received some NSA alterations at some

by H3g3m0n 13y ago

Except if /dev/urandom is using a hardware based random number generator, then you have to trust that the hardware hasn't received some NSA alterations at some point during the design. The NSA did design a random number generator that likely had a backdoor in it: https://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy https://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy). Here's Bruce Schneier talking about it: https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_ad.html https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_... Also it's in Windows (although it's not used by default but userspace programs could rely on it). https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_ad.html https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_... It would be possible for the NSA to go to Intel and get them to put in something in their random number generator that would let them to basically break the encryption by massively reducing the keyspace if they have the secret key.

gizmo686 13y ago
No you don't. The only time you need to worry about the NSA having a back door into your random number generator is if you are worried either about the NSA attacking you (in which case you probably don't have a chance anyway), or are worried that some learned of the NSA's back door and is exploiting that.
- derefr 13y ago
  That reminds me of a question I've been pondering on-and-off for a while: is it possible even in theory to use Sufficiently Advanced Mathematics (e.g. homomorphic encryption) to build a trusted computation environment on top of an untrustworthy foundation? For example, I want to run a VM on EC2, knowing the NSA's after something I have. Is there some way I could, even theoretically, build my VM, that would protect it from the NSA compelling Amazon's cooperation in ripping the data right from my VM's memory at the hypervisor level?
  - tptacek 13y ago
    Possibly. For instance, look up some papers on White Box Cryptography; these are implementations of things like AES designed to run AES computations on untrusted platforms without revealing their key (the key gets "baked in" to the code that runs the algorithm in such a way that it's theorized to be cryptographically hard to extract the key from the algorithm). You are getting into the flip side of the DRM coin here; put differently: if there's a way to do what you want, there's also a way for the MPAA to do what it wants on PCs. Personally, I think there is, at least in the dollar-cost model of security.
    - ballard 13y ago
      It's a good insight. There is distinction between I/O (rendering the video and audio to the host) and computations of a seemingly blackbox. Would also be an interesting avenue for malware to grow into if possible. The problem is there's always been decryption code that has to live somewhere that effectively unlocks the whole thing. Edit: PyPy but zk computing for malware.
    - deleted 13y ago
      [deleted]
    - homeomorphic 13y ago
      Wouldn't this make nice foundations for hardware cryptographic tokens such as CryptoStick?
    - bch 13y ago
      I'm out of my depth here, but since this conversation seems precise, and is discussing theoretical and practical implementations, does this paper[1] factor in? If so, is it fair to say that at some level, without auditing every aspect of hardware, and every aspect of all software used at build time and runtime, you can't know? [1] http://cm.bell-labs.com/who/ken/trust.html http://cm.bell-labs.com/who/ken/trust.html
  - ballard 13y ago
    Funny you should mention this. I was asked to "suggest solutions" to this in 2008 as a client-facing AWS enterprise consultant in the mobile industry. The naïve way relies on: "If there isn't a Rootkit or capture mechanism, it's secure if it's obscure." That will buy an iota of time. The other way is to simply not trust the host and end-to-end encrypt everything important. This is a PITA, but there is no current viable alternative without a significantly rigorous and extensive project (would be in the form of a VM for servers &| something that runs on js like asm.js) Mostly you need zero knowledge computation. Storage and network are easier probs. The intractable problem is eventually an answer needs to be presented somewhere. For now, you should minimize exposure as much as possible through all means available.
  - sweis 13y ago
    We're working on a similar problem at PrivateCore: Protecting VM data in-use on outsourced infrastructure. We're running a high-assurance, remotely attestable hypervisor inside the CPU cache and encrypting all access to main memory. This protects against threats from the physical layer, like cold boot, DMA attacks, NVDIMMs, bus analyzers, etc. It's not quite what you're talking about in your Amazon and NSA scenario. Amazon doesn't let you bring your own hypervisor to run on bare metal and the NSA can compromise the CPU itself. However, our approach does give you assurance that someone with physical access can't easily snapshot your VM memory.
    - derefr 13y ago
      > remotely attestable hypervisor How does this bit work, by the way? What's stopping an altered hypervisor from lying to say it's unaltered? (This is the classic "how do you verify a player on your FPS isn't running a bot instead of a game-client" problem in a nutshell.)
      - sweis 13y ago
        Today we rely on the TPM to measure the state of the system using Intel TXT. These measurements are stored in platform configuration registers (PCRs) on the TPM device. There are known TPM and LPC bus vulnerabilities. That is why long-term we will move away from that dependency by utilizing upcoming CPU features.
    - e12e 13y ago
      > our approach does give you assurance that someone with physical access can't easily snapshot your VM memory. But how do you know the VM (or rather the hypervisor for the vm) is running on physical hardware, and not in a hypervisor? I can't think of a way you could be certain of this remotely? Perhaps you could be on-site for the boot-up, and then rely on the fact that snapshotting is very hard -- but it sounds rather fragile... Still very interesting project! I've been thinking a bit on "running inside the L/1/2/3 chache"-lately - but I hadn't thought about the particular idea that you could treat RAM as "external" -- assuming you could guarantee that you're always in cache.
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.
tptacek 13y ago
None of this comment has anything to do with my comment. If you don't want to use RDRAND, compile a kernel that doesn't.
ballard 13y ago
To avoid hobgoblins wearing Faraday cages without denying the reality of the privacy debate, open source hw can make them quieter. I think it's going to happen because of PC market forces (IBM/Lenovo, Dell) and prior examples (OpenSparc). The startup costs (eda, test equipment) are doable because there are enough people with specialized expertise that could contribute. If you don't trust the hw or vhost, you're stuffed. Political upwards and technical downwards are the ways to make sure this doesn't happen.
cpeterso 13y ago
Linux's /dev/urandom does not trust hardware RNGs any more than other entropy sources. All entropy sources are stirred into the same entropy pool.
- ballard 13y ago
  Does it use multiple pools a-la Fortuna?
  - __alexs 13y ago
    There's an input pool and 2 output pools but it's not like Fortuna. This is the most up to date analysis of the Linux entropy system I'm aware of http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf
DanBC 13y ago
> Except if /dev/urandom is using a hardware based random number generator, then you have to trust that the hardware hasn't received some NSA alterations at some point during the design. That is a valid concern that needs to be part of your risk assessment. "Do I want to protect my secrets from a well funded government agency?"[1] But there are other risks that need to be thought about too. Some people seem to think that hardware RNGs are better than software. Often they're not, they're lousy. HWrngs can have subtle failure rates which are hard to detect. Once you've done all the de-skewing and other checks they can be quite low bandwidth. I have a bunch of links to reading about HWRNGs here - (https://news.ycombinator.com/item?id=6060636 https://news.ycombinator.com/item?id=6060636) And here's a really nice thread (https://news.ycombinator.com/item?id=1453299 https://news.ycombinator.com/item?id=1453299) [1] Although if you want to defend yourself against a well funded secret government agency you need to worry about more than a weak RNG.

by H3g3m0n 13y ago

gizmo686 13y ago

No you don't. The only time you need to worry about the NSA having a back door into your random number generator is if you are worried either about the NSA attacking you (in which case you probably don't have a chance anyway), or are worried that some learned of the NSA's back door and is exploiting that.

derefr 13y ago
That reminds me of a question I've been pondering on-and-off for a while: is it possible even in theory to use Sufficiently Advanced Mathematics (e.g. homomorphic encryption) to build a trusted computation environment on top of an untrustworthy foundation? For example, I want to run a VM on EC2, knowing the NSA's after something I have. Is there some way I could, even theoretically, build my VM, that would protect it from the NSA compelling Amazon's cooperation in ripping the data right from my VM's memory at the hypervisor level?
- tptacek 13y ago
  Possibly. For instance, look up some papers on White Box Cryptography; these are implementations of things like AES designed to run AES computations on untrusted platforms without revealing their key (the key gets "baked in" to the code that runs the algorithm in such a way that it's theorized to be cryptographically hard to extract the key from the algorithm). You are getting into the flip side of the DRM coin here; put differently: if there's a way to do what you want, there's also a way for the MPAA to do what it wants on PCs. Personally, I think there is, at least in the dollar-cost model of security.
  - ballard 13y ago
    It's a good insight. There is distinction between I/O (rendering the video and audio to the host) and computations of a seemingly blackbox. Would also be an interesting avenue for malware to grow into if possible. The problem is there's always been decryption code that has to live somewhere that effectively unlocks the whole thing. Edit: PyPy but zk computing for malware.
  - deleted 13y ago
    [deleted]
  - homeomorphic 13y ago
    Wouldn't this make nice foundations for hardware cryptographic tokens such as CryptoStick?
  - bch 13y ago
    I'm out of my depth here, but since this conversation seems precise, and is discussing theoretical and practical implementations, does this paper[1] factor in? If so, is it fair to say that at some level, without auditing every aspect of hardware, and every aspect of all software used at build time and runtime, you can't know? [1] http://cm.bell-labs.com/who/ken/trust.html http://cm.bell-labs.com/who/ken/trust.html
- ballard 13y ago
  Funny you should mention this. I was asked to "suggest solutions" to this in 2008 as a client-facing AWS enterprise consultant in the mobile industry. The naïve way relies on: "If there isn't a Rootkit or capture mechanism, it's secure if it's obscure." That will buy an iota of time. The other way is to simply not trust the host and end-to-end encrypt everything important. This is a PITA, but there is no current viable alternative without a significantly rigorous and extensive project (would be in the form of a VM for servers &| something that runs on js like asm.js) Mostly you need zero knowledge computation. Storage and network are easier probs. The intractable problem is eventually an answer needs to be presented somewhere. For now, you should minimize exposure as much as possible through all means available.
- sweis 13y ago
  We're working on a similar problem at PrivateCore: Protecting VM data in-use on outsourced infrastructure. We're running a high-assurance, remotely attestable hypervisor inside the CPU cache and encrypting all access to main memory. This protects against threats from the physical layer, like cold boot, DMA attacks, NVDIMMs, bus analyzers, etc. It's not quite what you're talking about in your Amazon and NSA scenario. Amazon doesn't let you bring your own hypervisor to run on bare metal and the NSA can compromise the CPU itself. However, our approach does give you assurance that someone with physical access can't easily snapshot your VM memory.
  - derefr 13y ago
    > remotely attestable hypervisor How does this bit work, by the way? What's stopping an altered hypervisor from lying to say it's unaltered? (This is the classic "how do you verify a player on your FPS isn't running a bot instead of a game-client" problem in a nutshell.)
    - sweis 13y ago
      Today we rely on the TPM to measure the state of the system using Intel TXT. These measurements are stored in platform configuration registers (PCRs) on the TPM device. There are known TPM and LPC bus vulnerabilities. That is why long-term we will move away from that dependency by utilizing upcoming CPU features.
  - e12e 13y ago
    > our approach does give you assurance that someone with physical access can't easily snapshot your VM memory. But how do you know the VM (or rather the hypervisor for the vm) is running on physical hardware, and not in a hypervisor? I can't think of a way you could be certain of this remotely? Perhaps you could be on-site for the boot-up, and then rely on the fact that snapshotting is very hard -- but it sounds rather fragile... Still very interesting project! I've been thinking a bit on "running inside the L/1/2/3 chache"-lately - but I hadn't thought about the particular idea that you could treat RAM as "external" -- assuming you could guarantee that you're always in cache.

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.

tptacek 13y ago

None of this comment has anything to do with my comment. If you don't want to use RDRAND, compile a kernel that doesn't.

ballard 13y ago

To avoid hobgoblins wearing Faraday cages without denying the reality of the privacy debate, open source hw can make them quieter. I think it's going to happen because of PC market forces (IBM/Lenovo, Dell) and prior examples (OpenSparc). The startup costs (eda, test equipment) are doable because there are enough people with specialized expertise that could contribute. If you don't trust the hw or vhost, you're stuffed. Political upwards and technical downwards are the ways to make sure this doesn't happen.

cpeterso 13y ago

Linux's /dev/urandom does not trust hardware RNGs any more than other entropy sources. All entropy sources are stirred into the same entropy pool.

ballard 13y ago
Does it use multiple pools a-la Fortuna?
- __alexs 13y ago
  There's an input pool and 2 output pools but it's not like Fortuna. This is the most up to date analysis of the Linux entropy system I'm aware of http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf

DanBC 13y ago

> Except if /dev/urandom is using a hardware based random number generator, then you have to trust that the hardware hasn't received some NSA alterations at some point during the design. That is a valid concern that needs to be part of your risk assessment. "Do I want to protect my secrets from a well funded government agency?"[1] But there are other risks that need to be thought about too. Some people seem to think that hardware RNGs are better than software. Often they're not, they're lousy. HWrngs can have subtle failure rates which are hard to detect. Once you've done all the de-skewing and other checks they can be quite low bandwidth. I have a bunch of links to reading about HWRNGs here - (https://news.ycombinator.com/item?id=6060636 https://news.ycombinator.com/item?id=6060636) And here's a really nice thread (https://news.ycombinator.com/item?id=1453299 https://news.ycombinator.com/item?id=1453299) [1] Although if you want to defend yourself against a well funded secret government agency you need to worry about more than a weak RNG.