Technical feasibility of decrypting https by replacing the computer's PRNG(crypto.stackexchange.com)
crypto.stackexchange.com
Technical feasibility of decrypting https by replacing the computer's PRNG
http://crypto.stackexchange.com/questions/9210/technical-feasibility-of-decrypting-https-by-replacing-the-computers-prng/9212
12 comments
I believe the problem here is that you're dividing us into "tinfoil hat people" and normal people. This would be a useful designation if the world would remain static. However, we're clearly seeing that what used to be "tinfoil hat people" are right now just sensible people, so then you have to distinguish the really tinfoil hat people from the previous bunch, and so on. It's a moving target.
The key problem from all of this is the injection of distrust into the entire stack caused by state security. I'm not getting into the BTB and pipelining, this article is just a symptom of the problem. The entire technology stack is up for grabs, and authors are going to get a lot of mileage out of taking it apart.
So, to me, there are two questions here. 1) Can you demonstrate an attack that uses some weaknesses yet undetected by the average nerd? If so, that's news. 2) Can you speculate that with the resource of a nation-state, such an attack might be made? If so, to me that kind of qualifies as nerd gossip. It may turn out to be true, and it may just be a lot of hand-waving. Some people like this stuff. Some people don't. I never liked the hero-worship crap or the latest from famous author X, so if I had to choose from piles of crap I'd prefer this.
For the average person, the only choice right now is to carry on or not. That does not make the situation acceptable or tolerable, that's just how it is.
And I really like the word kerfuffle.
The key problem from all of this is the injection of distrust into the entire stack caused by state security. I'm not getting into the BTB and pipelining, this article is just a symptom of the problem. The entire technology stack is up for grabs, and authors are going to get a lot of mileage out of taking it apart.
So, to me, there are two questions here. 1) Can you demonstrate an attack that uses some weaknesses yet undetected by the average nerd? If so, that's news. 2) Can you speculate that with the resource of a nation-state, such an attack might be made? If so, to me that kind of qualifies as nerd gossip. It may turn out to be true, and it may just be a lot of hand-waving. Some people like this stuff. Some people don't. I never liked the hero-worship crap or the latest from famous author X, so if I had to choose from piles of crap I'd prefer this.
For the average person, the only choice right now is to carry on or not. That does not make the situation acceptable or tolerable, that's just how it is.
And I really like the word kerfuffle.
> However, we're clearly seeing that what used to be "tinfoil hat people" are right now just sensible people, so then you have to distinguish the really tinfoil hat people from the previous bunch, and so on. It's a moving target.
Well, no. There's a difference between the people who said, for many years, that GCHQ / NSA are monitoring all communications and the people who said that GCHQ / NSA are monitoring all their communications. People deny this, but there is a big difference between "collecting the content" and "collecting the content then grepping it for your contributions to that content".
> For the average person, the only choice right now is to carry on or not.
I am genuinely baffled by the responses to the snowdon "revelations". i) They're not new ii) They've been included in routine risk assessment for years.
What do you have that you want to protect, and who are you protecting it from? If you're protecting your teen-angst poetry from your classmates you can carry on as normal. If you're protecting a stash of images of child sexual abuse from law enforcement you need to continually assess your encryption and secrecy methods. If you're protecting plans to destroy America from a well funded government agency you need to worry about everything. But that's always been the case.
There are so many other, easier, attacks than a weakened pool of entropy so it's a shame that people are being distracted by this. Don't get me wrong, I don't like RdRand and I'd prefer it if it was open and transparent, but there's so many other weak steps that people could be fixing before they get to RdRand.
Well, no. There's a difference between the people who said, for many years, that GCHQ / NSA are monitoring all communications and the people who said that GCHQ / NSA are monitoring all their communications. People deny this, but there is a big difference between "collecting the content" and "collecting the content then grepping it for your contributions to that content".
> For the average person, the only choice right now is to carry on or not.
I am genuinely baffled by the responses to the snowdon "revelations". i) They're not new ii) They've been included in routine risk assessment for years.
What do you have that you want to protect, and who are you protecting it from? If you're protecting your teen-angst poetry from your classmates you can carry on as normal. If you're protecting a stash of images of child sexual abuse from law enforcement you need to continually assess your encryption and secrecy methods. If you're protecting plans to destroy America from a well funded government agency you need to worry about everything. But that's always been the case.
There are so many other, easier, attacks than a weakened pool of entropy so it's a shame that people are being distracted by this. Don't get me wrong, I don't like RdRand and I'd prefer it if it was open and transparent, but there's so many other weak steps that people could be fixing before they get to RdRand.
In between those extremes you present, there are the huge number of people who at one point or other does something that might make them blackmail targets if some future administration needs something from them, their family, their friends or their employer, or that have carried out any kind of activism or political or religious activity that might brand them in the future.
We have two recent demonstrations of why people should be concerned about this: McCarthyism and 9/11. Imagine McCarthy with access to years worth of stored electronic communications. But you got rid of that. Instead you got post-9/11 restrictions in the dark like the no-fly list. Imagine the post-9/11 attitudes to muslims escalating one step further. It takes very little before a lot of seemingly uninteresting stuff that nobody cares much about now is suddenly enough to ruin careers or relationships.
It takes very little before the impact of indiscretions online or on the phone can be used as a source to impose even more restrictions on you. Suddenly some people will get fewer job offers for example.
There are much worse possibilities. But these are just simple, straight forward escalations similar to episodes in the recent past.
For my own part, about 20 years ago I was politically active in a left wing political party where just a few years before mere membership was often sufficient that you'd get denied entry to the US. Despite the fact that membership lists were confidential and never released to outside sources.
But then again all officers of the party had known they'd been under extensive surveillance for many years (yet were considered crackpots for claiming so, until it was proven the Norwegian security services had engaged in extensive illegal surveillance, including against a left wing member of parliament on the parliamentary commission investigating their violations while they were investigating them)
The groups that western intelligence organization target have shifted, but I'd be outright shocked if there are not perfectly legal, democratic organisations where membership would cause restrictions on your air travel and trigger additional surveillance without any evidence of even potential threats (some members of the party I was involved with at various points where shadowed on the way to and from work routinely, and "ran into" surveillance people that taunted them about private conversations they'd had in their own home...)
This is the flaw with the idea that you don't have anything to hide. Everyone has lots to hide - as much as it doesn't look that way, we all filter and none of us post everything in our lives on Facebook. We just don't think we have anything to hide because many haven't done anything they consider to be wrong or believes the current government will care about. Guess what? Most of the people targeted by Joseph McCarthy didn't think they had anything to hide either, and most didn't until his witch hunts started, yet many of them lost their jobs and got blacklisted.
This is the really scary thing about these NSA revelations: The surveillance is bad. But the storage of data over time is 10 times worse - it means the threat is not just abuse now, but abuse from the next government too, and we don't yet know whether that government will be better or worse in terms of how it might use or abuse that data, or if they might simply decide to extend storage periods further and put people at further risk of even later governments.
We have two recent demonstrations of why people should be concerned about this: McCarthyism and 9/11. Imagine McCarthy with access to years worth of stored electronic communications. But you got rid of that. Instead you got post-9/11 restrictions in the dark like the no-fly list. Imagine the post-9/11 attitudes to muslims escalating one step further. It takes very little before a lot of seemingly uninteresting stuff that nobody cares much about now is suddenly enough to ruin careers or relationships.
It takes very little before the impact of indiscretions online or on the phone can be used as a source to impose even more restrictions on you. Suddenly some people will get fewer job offers for example.
There are much worse possibilities. But these are just simple, straight forward escalations similar to episodes in the recent past.
For my own part, about 20 years ago I was politically active in a left wing political party where just a few years before mere membership was often sufficient that you'd get denied entry to the US. Despite the fact that membership lists were confidential and never released to outside sources.
But then again all officers of the party had known they'd been under extensive surveillance for many years (yet were considered crackpots for claiming so, until it was proven the Norwegian security services had engaged in extensive illegal surveillance, including against a left wing member of parliament on the parliamentary commission investigating their violations while they were investigating them)
The groups that western intelligence organization target have shifted, but I'd be outright shocked if there are not perfectly legal, democratic organisations where membership would cause restrictions on your air travel and trigger additional surveillance without any evidence of even potential threats (some members of the party I was involved with at various points where shadowed on the way to and from work routinely, and "ran into" surveillance people that taunted them about private conversations they'd had in their own home...)
This is the flaw with the idea that you don't have anything to hide. Everyone has lots to hide - as much as it doesn't look that way, we all filter and none of us post everything in our lives on Facebook. We just don't think we have anything to hide because many haven't done anything they consider to be wrong or believes the current government will care about. Guess what? Most of the people targeted by Joseph McCarthy didn't think they had anything to hide either, and most didn't until his witch hunts started, yet many of them lost their jobs and got blacklisted.
This is the really scary thing about these NSA revelations: The surveillance is bad. But the storage of data over time is 10 times worse - it means the threat is not just abuse now, but abuse from the next government too, and we don't yet know whether that government will be better or worse in terms of how it might use or abuse that data, or if they might simply decide to extend storage periods further and put people at further risk of even later governments.
I get that slurping the content and meta data is bad, and I get that keeping that is bad. And it must stop. And I'm glad people are doing stuff to change government behaviours.
But still, I look at stories like these...
(http://www.courthousenews.com/2011/06/29/37770.htm) " Dayton police "mistook" a mentally handicapped teenager's speech impediment for "disrespect," so they Tasered, pepper-sprayed and beat him and called for backup from "upward of 20 police officers" after the boy rode his bicycle home to ask his mother for help"
(http://www.ajc.com/news/news/local/2-officers-out-of-jobs-in...) Woman calls police for help; is repeatedly tasered and pepper sprayed
(http://www.courthousenews.com/2010/06/24/28330.htm) 86 yr old bed-ridden woman tasered after pulling knife from under pillow
...and I wonder why Americans aren't vigorously campaigning for better law enforcement.
These aren't hypothetical abuses that might happen in future under a worse government. These are all actual examples of abusive law enforcement, that are affecting real people today.
Having your medical needs neglected until your penis rots off and you die of penile cancer (http://www.sandiegoreader.com/news/2008/dec/10/cover/) is barbaric.
Popehat has all of these here: (http://www.popehat.com/2012/05/02/citizen-incredulity-and-la...)
> This is the flaw with the idea that you don't have anything to hide.
I'm not saying that people don't have anything to hide. I'm saying that even the people who do have something to hide have more important things to worry about than NSA slurping 3 days of content. (But not that the NSA slurping that content is acceptable, it isn't.)
But still, I look at stories like these...
(http://www.courthousenews.com/2011/06/29/37770.htm) " Dayton police "mistook" a mentally handicapped teenager's speech impediment for "disrespect," so they Tasered, pepper-sprayed and beat him and called for backup from "upward of 20 police officers" after the boy rode his bicycle home to ask his mother for help"
(http://www.ajc.com/news/news/local/2-officers-out-of-jobs-in...) Woman calls police for help; is repeatedly tasered and pepper sprayed
(http://www.courthousenews.com/2010/06/24/28330.htm) 86 yr old bed-ridden woman tasered after pulling knife from under pillow
...and I wonder why Americans aren't vigorously campaigning for better law enforcement.
These aren't hypothetical abuses that might happen in future under a worse government. These are all actual examples of abusive law enforcement, that are affecting real people today.
Having your medical needs neglected until your penis rots off and you die of penile cancer (http://www.sandiegoreader.com/news/2008/dec/10/cover/) is barbaric.
Popehat has all of these here: (http://www.popehat.com/2012/05/02/citizen-incredulity-and-la...)
> This is the flaw with the idea that you don't have anything to hide.
I'm not saying that people don't have anything to hide. I'm saying that even the people who do have something to hide have more important things to worry about than NSA slurping 3 days of content. (But not that the NSA slurping that content is acceptable, it isn't.)
[deleted]
Agreed, what is the practical risk?
> In between those extremes you present, there are the huge number of people who at one point or other does something that might make them blackmail targets if some future administration needs something from them, their family, their friends or their employer, or that have carried out any kind of activism or political or religious activity that might brand them in the future.
Well, you say this as if actually doing any of these things would be necessary to end up on the hit-list of a future tyranny.
You yourself provide the clues that NSA surveillance is not necessary, however. Do you think everyone caught up in McCarthy's witchhunt was really a Communist? Stuff like storage of Internet data here would be a 'nice-to-have' for a future tyranny, but not at all a requirement.
The stuff that I do have to hide I don't let on the Internet unprotected, but it's because I don't trust the ISP or the web service that would hold the data, not because I'm worried about NSA.
Our modern deep-connected life is already a despot's wet dream, just ask Aaron Hernandez, who was caught completely without need for NSA involvement.
I do think you're 100% right with indefinite data storage being the concern. However if data storage of some form is implemented, it's probably way better (from a future dystopia POV) that they focus on retaining all-of-the-Internet for a short amount of time, rather than interesting-parts-of-the-Internet indefinitely.
Well, you say this as if actually doing any of these things would be necessary to end up on the hit-list of a future tyranny.
You yourself provide the clues that NSA surveillance is not necessary, however. Do you think everyone caught up in McCarthy's witchhunt was really a Communist? Stuff like storage of Internet data here would be a 'nice-to-have' for a future tyranny, but not at all a requirement.
The stuff that I do have to hide I don't let on the Internet unprotected, but it's because I don't trust the ISP or the web service that would hold the data, not because I'm worried about NSA.
Our modern deep-connected life is already a despot's wet dream, just ask Aaron Hernandez, who was caught completely without need for NSA involvement.
I do think you're 100% right with indefinite data storage being the concern. However if data storage of some form is implemented, it's probably way better (from a future dystopia POV) that they focus on retaining all-of-the-Internet for a short amount of time, rather than interesting-parts-of-the-Internet indefinitely.
Daniel, I wasn't making a political point. I was making an engineering point. I'm not interested in this leg of the conversation and think that injecting politics into this discussion will consume the thread with chaff that will make it harder for people to understand how crypto and hardware work, which is a shame.
Thomas, I honestly don't understand what you mean.
I think perhaps you're suggesting separating the idea of information leakage from talking about those willing to exploit it. That's fine, but it's going to be really difficult to have a long technical conversation about things that might or might not happen without having any person/entity/organization to be doing them. It would be like telling a story without having characters in it. If I understand you correctly, you'd like this to be way too abstract to have much traction with anybody. By all means break out Alice and Bob and have a go at it. But I'm not sure I understand you.
I was also not trying to make a political point. I was simply trying to say that if you want to use the term "tinfoil hat people", then acknowledge that the term is a moving target based on a world of contextual information that keeps changing. That's all.
I think perhaps you're suggesting separating the idea of information leakage from talking about those willing to exploit it. That's fine, but it's going to be really difficult to have a long technical conversation about things that might or might not happen without having any person/entity/organization to be doing them. It would be like telling a story without having characters in it. If I understand you correctly, you'd like this to be way too abstract to have much traction with anybody. By all means break out Alice and Bob and have a go at it. But I'm not sure I understand you.
I was also not trying to make a political point. I was simply trying to say that if you want to use the term "tinfoil hat people", then acknowledge that the term is a moving target based on a world of contextual information that keeps changing. That's all.
I inadvertently spawned this discussion by pointing out that many open source security projects like Linux, OpenSSL, GnuTLS, libgcrypt, dm-crypt, etc. all depend on closed-source crypto implementations [1]. This was followed by one of the Linux guys saying he quit the project over RdRand [2].
Everyone seems to be missing the point: RdRand is the least of your worries. If you can't trust the CPU, you can't trust it to multiply correctly, much less perform crypto.
If a CPU maker or OEM wanted to be evil, they wouldn't even need to bother backdooring the hardware. SMM or microcode updates would be much easier to compromise.
[1] https://mailman.stanford.edu/pipermail/liberationtech/2013-J...
[2] https://mailman.stanford.edu/pipermail/liberationtech/2013-J...
Everyone seems to be missing the point: RdRand is the least of your worries. If you can't trust the CPU, you can't trust it to multiply correctly, much less perform crypto.
If a CPU maker or OEM wanted to be evil, they wouldn't even need to bother backdooring the hardware. SMM or microcode updates would be much easier to compromise.
[1] https://mailman.stanford.edu/pipermail/liberationtech/2013-J...
[2] https://mailman.stanford.edu/pipermail/liberationtech/2013-J...
It's about verifiability, you can verify if a CPU is multiplying incorrectly, there's no way of verifying if the random source is generating randomness correctly.
You can verify that your CPU is multiply correctly at one moment in time.
Yes, but active attacks where a third-party can switch on-and-off features on your CPU are obviously vastly different from a passive attack such as a compromised random number source.
The RNG attack suggested can pass verifiability while at the exact same time introduce a backdoor and thus constantly be on.
The RNG attack suggested can pass verifiability while at the exact same time introduce a backdoor and thus constantly be on.
Are you ready to test all the 2^128 possible multiplications your CPU can do?
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.
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.
Not an expert, but in theory the CPU can detect specific contexts and change its behavior. If side-channel attacks can detect AES operations, the CPU can do an even a better job.
> you can't trust it to multiply correctly
That did happen at one point, and cost Intel an estimated $475 Million[1]. Of course, that was (presumably) an unintentional bug.
[1]http://en.wikipedia.org/wiki/Pentium_FDIV_bug
--
I don't consider SMM or microcode updates to be above suspicion; Ken Thompson's's Reflections on Trusting Trust suggests that nothing is above suspicion.
That did happen at one point, and cost Intel an estimated $475 Million[1]. Of course, that was (presumably) an unintentional bug.
[1]http://en.wikipedia.org/wiki/Pentium_FDIV_bug
--
I don't consider SMM or microcode updates to be above suspicion; Ken Thompson's's Reflections on Trusting Trust suggests that nothing is above suspicion.
Don't forget early 386 steppings too. Remember the double sigma?
But what if the government, specifically under the argument of national security, wanted a chip manufacturer to use a specific algorithm? They may want to do this not to create a general weakness or backdoor. That is to say not a backdoor that just anyone could use, but a specific backdoor that only the NSA (not even the chip manufacturer) knew.
Such a back door could be accomplished with tools like Dual_EC_DRBG (http://en.wikipedia.org/wiki/Dual_EC_DRBG).
Such a back door could be accomplished with tools like Dual_EC_DRBG (http://en.wikipedia.org/wiki/Dual_EC_DRBG).
NSA does not need a ludicrously inefficient RNG design to backdoor your crypto.
Really, because they have a better way?
Either they are just dumb and designed Dual_EC_DRBG by accident, or they design systems like that for a purpose. Your assessment of what they need is an assertion, based on what exactly? Security is designed not around what one thinks an attacker needs, or why they would want do do something. It's about preventing an attacker from getting access to things a person wishes to keep secure regardless of why they would want to. In that light weaknesses in random number generators is a relevant field of inquiry. Otherwise simply ignore cryptography altogether, trow up your ands and say why bother.
Either they are just dumb and designed Dual_EC_DRBG by accident, or they design systems like that for a purpose. Your assessment of what they need is an assertion, based on what exactly? Security is designed not around what one thinks an attacker needs, or why they would want do do something. It's about preventing an attacker from getting access to things a person wishes to keep secure regardless of why they would want to. In that light weaknesses in random number generators is a relevant field of inquiry. Otherwise simply ignore cryptography altogether, trow up your ands and say why bother.
[deleted]
Ugh. In light of recent events you can't seriously be using the phrase "tinfoil hat" in good conscience.
As to whether you're right or not, I don't know. But please figure out a less lazy way of getting your point across. The whole "tinfoil hat" argument is a fallacy used to marginalize people and shut them up without actually providing any evidence. And if you have evidence, then you don't need it.
As to whether you're right or not, I don't know. But please figure out a less lazy way of getting your point across. The whole "tinfoil hat" argument is a fallacy used to marginalize people and shut them up without actually providing any evidence. And if you have evidence, then you don't need it.
By recent events I'm assuming you are referring to the NSA. Note: What the NSA has been doing is well known and has been outlined in detail in the press all the way back to 2008. The country just hasn't cared enough to pay attention until the current exciting manhunt underway.
This is the first I'm hearing of it, and I imagine the first a lot of other people are hearing of it. Two things:
1. Just because it's old news, doesn't mean it isn't news for a lot of people.
2. My point still stands: some conspiracy theories do turn out to be true (do a search for "conspiracy theories that were proven true"), so wholesale calling conspiracy theorists nut jobs, or saying they are "tinfoil hat" wearers is unbelievably shortsighted.
1. Just because it's old news, doesn't mean it isn't news for a lot of people.
2. My point still stands: some conspiracy theories do turn out to be true (do a search for "conspiracy theories that were proven true"), so wholesale calling conspiracy theorists nut jobs, or saying they are "tinfoil hat" wearers is unbelievably shortsighted.
I guess the larger point is: the current NSA issue should in no way be considered a conspiracy since it has been well known, and not hidden (if you have been paying attention) from the outset. Also jumping to a conspiracy theory re: what tptacek is saying is shortsighted, unless you have actual relevant evidence to support said conspiracy.
It's not of interest whether or not people should be considered ignorant if the recent NSA information was news to them. willurd was correctly pointing out that the phrase "tinfoil hat" used by tptacek is an empty insult, which avoids the need to say something more intelligent in its place. I agree with him that it's inappropriate in this forum.
Two months ago the mainstream would have called anyone talking about the NSA a nutjob, and anybody not looking closely probably thinks Snowden is a vile traitor. No matter how "known" the issue is, every new piece of evidence helps convince a few more people to care.
No, this isn't true; rather, it's something people on HN and Reddit say to make themselves feel smarter. In cryptography, it has been article of faith for decades that the NSA is actively working to subvert the security of public cryptography.
The problem with the rdrand conspiracy theory isn't that it's unreasonable to believe the NSA is trying to backdoor something; it's that it's a stupid backdoor, and that the logic that delivers you to the conclusion that it's a backdoor also concludes that everything else must be a backdoor.
The problem with the rdrand conspiracy theory isn't that it's unreasonable to believe the NSA is trying to backdoor something; it's that it's a stupid backdoor, and that the logic that delivers you to the conclusion that it's a backdoor also concludes that everything else must be a backdoor.
I was only addressing res0nat0r's comment that the NSA's broad surveillance was well known, not the possibility that Intel's HWRNG is compromised. I agree that if you can't trust your CPU, all bets are off, but there is probably a different way of expressing the futility and improbability of such a situation that doesn't use the word tinfoil.
One would think that burden of evidence would be on the side of the accusers of backdooring. So far all I have seen is inaccurate speculation.
That is how the legal system works, so do you seriously plan to arrest the NSA?
But the topic here is about maintaining a secure system. You must prove beyond a reasonable doubt that every element is either secure or allowed to be owned by your antagonist. Technically no one should have ever trusted something that can not be observed (and it sounds like the people responsible didn't.)
If you chose to trust intel for no good reason, then you must now untrust them given that there is a reason. As a company they would be idiots to introduce such a thing. But if every US company can clearly be threatened with even worse outcomes into going against its own market interests then such an argument does not apply.
As a side note, I do think there was already plenty of evidence that the US was actively forcing companies to do the NSA's bidding. The encryption export laws were largely designed to keep everyone who makes encryption products perpetually afraid of losing all their right to export anything mostly by "governmental discretion" on handling the companies inevitable 'incidents' of support talking to the wrong person about how RSA worked.
But the topic here is about maintaining a secure system. You must prove beyond a reasonable doubt that every element is either secure or allowed to be owned by your antagonist. Technically no one should have ever trusted something that can not be observed (and it sounds like the people responsible didn't.)
If you chose to trust intel for no good reason, then you must now untrust them given that there is a reason. As a company they would be idiots to introduce such a thing. But if every US company can clearly be threatened with even worse outcomes into going against its own market interests then such an argument does not apply.
As a side note, I do think there was already plenty of evidence that the US was actively forcing companies to do the NSA's bidding. The encryption export laws were largely designed to keep everyone who makes encryption products perpetually afraid of losing all their right to export anything mostly by "governmental discretion" on handling the companies inevitable 'incidents' of support talking to the wrong person about how RSA worked.
It is. That doesn't mean we have to marginalize people who have theories, even if they don't have any evidence to back them up. My approach is to entertain all possibilities until they are proven to me to be false. In that way I attempt to avoid tunnel vision.
Care to buy some of my tiger repellent? It's been 100% effective so far!
How many tigers have you repelled? Which species? I'm particularly worried about bengal tigers in my apartment complex. Can it handle those?
That "if you have evidence" cuts both ways. You can't deny that Recent shenangians have pulled the paranoid delusionals out of the woodwork...
Has it? Examples? (I'm not saying it hasn't; I don't know)
I don't deny that some people do actually have paranoid delusions. But there's a big difference between a paranoid delusion and a (conspiracy) theory. The point I'm trying to make is that in light of recent conspiracies, we have to cut the conspiracy theorists some slack.
I don't deny that some people do actually have paranoid delusions. But there's a big difference between a paranoid delusion and a (conspiracy) theory. The point I'm trying to make is that in light of recent conspiracies, we have to cut the conspiracy theorists some slack.
I disagree. They are bound to the same burden of proof everyone else is.
I agree, as I stated above in another comment. When asked whether the burden of proof is on them, I replied: "It is. That doesn't mean we have to marginalize people who have theories, even if they don't have any evidence to back them up. My approach is to entertain all possibilities until they are proven to me to be false. In that way I attempt to avoid tunnel vision."
Once again, if you believe this is a real issue, you're logically enjoined from using practically any hardware cryptography, including the AES instructions or any HSM.
Why is true? Let's assume that a chip has hardware AES support, and the team which designed the AES module is working for Eve (the standard generic attacker). What can Eve do to compromise the AES encryption without getting caught?
She can't have the AES module encrypt the data with a known key, because then it won't decrypt correctly. She can't leak the key data, because we already know what size output we're expecting. Basically, AES is a well-understood function, and as long as we control the inputs, we can verify that the outputs are correct. It's not a 100% guarantee, but the risk to the attacker (and the chip vendor) are enormous.
But a hardware RNG offers some especially nice features for attackers:
1) It's an essential part of many security algorithms. 2) If a weak random sequence is fed through a stream cipher, the output is indistinguishable from a very strong RNG. 3) It's possible to generate weak RNG sequences by "accident", which would allow the chip vendor to deny wrongdoing. It's like writing 'if (uid = 0)' instead of 'if (uid == 0)' in an obscure kernel security check—it looks accidental but leaves an enormous backdoor.
So there are ways to deniably and almost-undetectably sabotage a hardware RNG, and by doing so, you could vastly reduce the keyspace of anything from cryptographic keys to SSL sessions to TCP sequence numbers.
Personally, I use AWS all the time, but that's because I understand the threat model. If I can't accept the threat model of AWS, then I encrypt data on a local machine using keys generated from /dev/random. Different applications demand different threat models.
Besides, the costs of feeding a hardware RNG through an entropy pool are relatively low. So why not do the professional thing, and in the process, protect against backdoored or buggy hardware RNGs?
Now, if your chip vendor is willing to engage in high-risk attacks with no plausible deniability, then you're pretty much hosed.
Why is true? Let's assume that a chip has hardware AES support, and the team which designed the AES module is working for Eve (the standard generic attacker). What can Eve do to compromise the AES encryption without getting caught?
She can't have the AES module encrypt the data with a known key, because then it won't decrypt correctly. She can't leak the key data, because we already know what size output we're expecting. Basically, AES is a well-understood function, and as long as we control the inputs, we can verify that the outputs are correct. It's not a 100% guarantee, but the risk to the attacker (and the chip vendor) are enormous.
But a hardware RNG offers some especially nice features for attackers:
1) It's an essential part of many security algorithms. 2) If a weak random sequence is fed through a stream cipher, the output is indistinguishable from a very strong RNG. 3) It's possible to generate weak RNG sequences by "accident", which would allow the chip vendor to deny wrongdoing. It's like writing 'if (uid = 0)' instead of 'if (uid == 0)' in an obscure kernel security check—it looks accidental but leaves an enormous backdoor.
So there are ways to deniably and almost-undetectably sabotage a hardware RNG, and by doing so, you could vastly reduce the keyspace of anything from cryptographic keys to SSL sessions to TCP sequence numbers.
Personally, I use AWS all the time, but that's because I understand the threat model. If I can't accept the threat model of AWS, then I encrypt data on a local machine using keys generated from /dev/random. Different applications demand different threat models.
Besides, the costs of feeding a hardware RNG through an entropy pool are relatively low. So why not do the professional thing, and in the process, protect against backdoored or buggy hardware RNGs?
Now, if your chip vendor is willing to engage in high-risk attacks with no plausible deniability, then you're pretty much hosed.
You are assuming the nominal output is the only output.
This is a software perspective:
This is a software perspective:
output_block = aes(input block)
output_block, cpu_state = aes(input block, cpu_state)
This doesn't preclude RdRand from being _worse_ however.
If your software— by design— eliminates side channels and isolates out timing. Then your hypothetical evil AES() would have a hard time screwing you over— it still might, somehow, but the window may be very narrow.
The only way to narrow the exposure from a bad rdrand is to never use it directly (e.g. without whitening via a CSPRNG with other truly random inputs).
If your software— by design— eliminates side channels and isolates out timing. Then your hypothetical evil AES() would have a hard time screwing you over— it still might, somehow, but the window may be very narrow.
The only way to narrow the exposure from a bad rdrand is to never use it directly (e.g. without whitening via a CSPRNG with other truly random inputs).
This is a good point, but only if your attacker has access to cpu_state somehow. To do this, they would need to do one of the following:
1) Run code directly on the secure machine. Personally, I normally assume that if an attacker can run code, it's already Game Over. This includes running Java bytecodes and supplying data to media codecs, all of which can potentially be escalated to running code, and then further escalated to root.
2) Gain external access to cpu_state without running code, perhaps via a back-doored network card that colludes with the CPU. This would be pretty impressive, but it would also require some degree of network access. You can protect against this by sticking your whole computer behind a serial line and writing an extremely simple custom protocol in Go. This would make perfect sense for a credit card vault, for example.
3) Run a really exotic attack, such as the ones described in Reflections on Trusting Trust. For example, if the chip is willing to pattern-match on certain instruction sequences in the Linux kernel and replace them with compromised microcode, then we're in trouble. But if Intel ever got caught doing something this blatant, it would be a first-rate PR nightmare.
The nasty thing about a bugged hardware RNG is that it could silently compromise most of your encryption even if you had amazing perimeter security. And even if the attack were revealed, your chip vendor could claim it was just a dumb mistake.
1) Run code directly on the secure machine. Personally, I normally assume that if an attacker can run code, it's already Game Over. This includes running Java bytecodes and supplying data to media codecs, all of which can potentially be escalated to running code, and then further escalated to root.
2) Gain external access to cpu_state without running code, perhaps via a back-doored network card that colludes with the CPU. This would be pretty impressive, but it would also require some degree of network access. You can protect against this by sticking your whole computer behind a serial line and writing an extremely simple custom protocol in Go. This would make perfect sense for a credit card vault, for example.
3) Run a really exotic attack, such as the ones described in Reflections on Trusting Trust. For example, if the chip is willing to pattern-match on certain instruction sequences in the Linux kernel and replace them with compromised microcode, then we're in trouble. But if Intel ever got caught doing something this blatant, it would be a first-rate PR nightmare.
The nasty thing about a bugged hardware RNG is that it could silently compromise most of your encryption even if you had amazing perimeter security. And even if the attack were revealed, your chip vendor could claim it was just a dumb mistake.
No, this 1-3 list is not comprehensive; it ignores the entire literature on side channels and covert channels.
Have you read any of these papers? I respectfully guess that you haven't. You're in luck. Go read Boneh's "Remote Timing Attacks Are Practical", and Osvik & Tromer's local spy process paper.
Have you read any of these papers? I respectfully guess that you haven't. You're in luck. Go read Boneh's "Remote Timing Attacks Are Practical", and Osvik & Tromer's local spy process paper.
My apologies for summarizing things a little too casually, and thank you for the excellent papers. I'm especially impressed by the cross-campus timing attack in Boneh.
My knowledge of convert channel attacks and timing attacks mostly dates to the 90s. Here's what little I know, for whatever it might be worth:
1. If your crypto primitives take variable time and your attacker can see that, you're hosed. Any encryption system with variable time encryption is useless unless you can somehow quantize it safely.
2. Eliminating covert channels is very nearly impossible. The literature on this goes way back, and it's ugly.
Should most users defend against these attacks? The timing attacks, yes. But I would assert that if a hardware encryption module appears to operate in constant time, most users should trust it. But as always, it depends on your threat model.
For something like a serious credit card vault, I still think your best bet is to get it off the network, build and audit a custom protocol that only passes a known set of messages, rate limit those messages, and quantize message timings. At that point, your biggest problems are bribery, insiders and physical security.
But if you do all that, I can't imagine why you would want to generate your encryption keys using somebody else's black-box hardware. Entropy pools are a good idea, even if you decide to trust your hardware AES implementation.
(And yes, I'm still oversimplifying. Hacker News is no substitute for a real threat analysis and security audit, nor for a conversation with whoever regulates or insures your business.)
My knowledge of convert channel attacks and timing attacks mostly dates to the 90s. Here's what little I know, for whatever it might be worth:
1. If your crypto primitives take variable time and your attacker can see that, you're hosed. Any encryption system with variable time encryption is useless unless you can somehow quantize it safely.
2. Eliminating covert channels is very nearly impossible. The literature on this goes way back, and it's ugly.
Should most users defend against these attacks? The timing attacks, yes. But I would assert that if a hardware encryption module appears to operate in constant time, most users should trust it. But as always, it depends on your threat model.
For something like a serious credit card vault, I still think your best bet is to get it off the network, build and audit a custom protocol that only passes a known set of messages, rate limit those messages, and quantize message timings. At that point, your biggest problems are bribery, insiders and physical security.
But if you do all that, I can't imagine why you would want to generate your encryption keys using somebody else's black-box hardware. Entropy pools are a good idea, even if you decide to trust your hardware AES implementation.
(And yes, I'm still oversimplifying. Hacker News is no substitute for a real threat analysis and security audit, nor for a conversation with whoever regulates or insures your business.)
One of the main threats that people have been worried about recently is global-scale passive attacks by the NSA. We know that they are gathering and retaining vast quantities of data; that they don't consider it illegal to simply gather and retain data without a warrant of any sort, and only actually look at it later once they have a warrant or have a 51% confidence that at least one of the parties in the communication is foreign.
For this threat, most active attacks are not particularly useful. They may capture encrypted data at a different point in transit than the one that originated it, making most side channel attacks difficult or impossible.
But a compromised RNG can be almost impossible to detect, and yet render almost any crypto system trivially breakable offline after the fact. The NSA has already once created a DRBG for which there could be a secret key that could determine the internal state of the generator with only 32 bytes of its output http://www.schneier.com/essay-198.html
I agree that being too wary of your hardware can lead you down a rabbit hole of paranoia, and that on the whole, we have much bigger problems to solve than hypothetical backdoored hardware random number generators (I have not seen any evidence that Intel has included a backdoor, merely people saying that because it's a black box we can't tell that they haven't). But since a good RNG is absolutely essential to so much crypto, and a compromised RNG would make it so easy for an adversary who passively monitors all communications and would like to have the option to decrypt them at their leave at a later date, I think that this is more worth worrying about than problems with the AES instructions.
For this threat, most active attacks are not particularly useful. They may capture encrypted data at a different point in transit than the one that originated it, making most side channel attacks difficult or impossible.
But a compromised RNG can be almost impossible to detect, and yet render almost any crypto system trivially breakable offline after the fact. The NSA has already once created a DRBG for which there could be a secret key that could determine the internal state of the generator with only 32 bytes of its output http://www.schneier.com/essay-198.html
I agree that being too wary of your hardware can lead you down a rabbit hole of paranoia, and that on the whole, we have much bigger problems to solve than hypothetical backdoored hardware random number generators (I have not seen any evidence that Intel has included a backdoor, merely people saying that because it's a black box we can't tell that they haven't). But since a good RNG is absolutely essential to so much crypto, and a compromised RNG would make it so easy for an adversary who passively monitors all communications and would like to have the option to decrypt them at their leave at a later date, I think that this is more worth worrying about than problems with the AES instructions.
They could try sneaking in a timing-based covert channel but surely that would be externally observable? The expected latency of those instructions is specified down to the last cycle, and since encryption is often performance-critical code people will be looking at their behaviour in detail.
[deleted]
Your argument is just smart-ass argument for the sake of argumentation.
Having CPU state that somehow leaks information past operating system is not realistic road for take. It would be known for thousands of Intel engineers.
Having tiny feature in chip that contains purposefully but not obviously vulnerable design that needs high level cryptographic knowledge to understand and compromises security is completely different matter.
EDIT comparing potential side channel attack to the possibility of weaken practically all ssl keys that use Intel chips is error in scale. Side channel attacks would work against specific targeted people. Weakening random numbers would work at the mass surveillance level.
Having CPU state that somehow leaks information past operating system is not realistic road for take. It would be known for thousands of Intel engineers.
Having tiny feature in chip that contains purposefully but not obviously vulnerable design that needs high level cryptographic knowledge to understand and compromises security is completely different matter.
EDIT comparing potential side channel attack to the possibility of weaken practically all ssl keys that use Intel chips is error in scale. Side channel attacks would work against specific targeted people. Weakening random numbers would work at the mass surveillance level.
This is a baffling comment given that researchers have alrady found multiple side channels in Intel CPUs that have created viable key leaking attacks. It's possible to have this problem merely by accident.
Such side channels can be avoided in a proper implementation by avoid things like table lookups and conditionals based on secret data.
Comparing potential side channel attack to the possibility to weakening practically all ssl keys that use Intel chips makes massive error in scale.
Side channel attacks would work against specific targeted people. Weakening random numbers would work at the mass surveillance level.
Side channel attacks would work against specific targeted people. Weakening random numbers would work at the mass surveillance level.
[deleted]
I think the bigger concern is the nature of the patch Intel supplied. The kernel developers at Intel are smart people, even if they're not putting in malicious code they know there's a risk that there might be something wrong with their random number generation so the logical thing would be for them to add their random source to the pool to mitigate against that.
The fact that they chose not to do that puts red flags all over the patch. Sure it could have been purely accidental, but any patch that "accidentally" weakens the security of a system deserves thorough analysis regardless of who submitted it.
Assuming you were a malicious party who wanted to backdoor a system in such a way that you could gain access without creating a massive security vulnerability then the random number source would be ideal as we've got a pretty good idea of how you could do it. It'd be harder to do with other parts of the architecture (although presumably not impossible). It would also give you attacks against a much wider range of systems (i.e. ones with which you can't directly interact so can't do timing-based attacks on).
The fact that they chose not to do that puts red flags all over the patch. Sure it could have been purely accidental, but any patch that "accidentally" weakens the security of a system deserves thorough analysis regardless of who submitted it.
Assuming you were a malicious party who wanted to backdoor a system in such a way that you could gain access without creating a massive security vulnerability then the random number source would be ideal as we've got a pretty good idea of how you could do it. It'd be harder to do with other parts of the architecture (although presumably not impossible). It would also give you attacks against a much wider range of systems (i.e. ones with which you can't directly interact so can't do timing-based attacks on).
Does NSA really have to use side channels? They could just send NSL to amazon for full memory dump and hdd clones of the virtual machine in question.
There are much easier ways to obtain data than subverting the crypto. This makes sense only for communications between secure endpoints. Like the Russian embassy sending data back home in Moscow. The security in this case comes from the fact that NSA cannot freely make intrusions without risking triggering a diplomatic incident/war - not that the Russian networks are secure in some absolute sense.
There are much easier ways to obtain data than subverting the crypto. This makes sense only for communications between secure endpoints. Like the Russian embassy sending data back home in Moscow. The security in this case comes from the fact that NSA cannot freely make intrusions without risking triggering a diplomatic incident/war - not that the Russian networks are secure in some absolute sense.
> They could just send NSL to amazon for full memory dump and hdd clones of the virtual machine in question
If everything is encrypted (disk, communications) and keys aren't stored in memory / CPU cache, then that won't work.
If everything is encrypted (disk, communications) and keys aren't stored in memory / CPU cache, then that won't work.
Unless amazon have homomorphic encryption services how exactly will you be able to do something with the vm without having the keys in memory? NSA just have to wait to fire it up.
"If"
>The NSA can pay $50 to get a VM on the same AWS box as runs your VMs, and then use local side channels to siphon out your secrets.
Where can I go to read about these side channel attacks? I tried to find the articles about them but they were covered in a bunch of w3schools style spam.
Where can I go to read about these side channel attacks? I tried to find the articles about them but they were covered in a bunch of w3schools style spam.
Here are a few for a start:
- "Cross-VM Side Channels and Their Use to Extract Private Keys" http://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf
- "Cache-timing attacks on AES" http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
- "Hey, You, Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds" http://www.cs.cornell.edu/courses/cs6460/2011sp/papers/cloud...
- "System-Level Protection Against Cache-Based Side Channel Attacks in the Cloud" http://pdos.csail.mit.edu/~taesoo/pubs/2012/stealthmem/steal...
In my mind, cache-timing attacks are fairly easily solved, but may be platform dependent. However, VM escapes in general are still a concern.
- "Cross-VM Side Channels and Their Use to Extract Private Keys" http://www.cs.unc.edu/~reiter/papers/2012/CCS.pdf
- "Cache-timing attacks on AES" http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
- "Hey, You, Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds" http://www.cs.cornell.edu/courses/cs6460/2011sp/papers/cloud...
- "System-Level Protection Against Cache-Based Side Channel Attacks in the Cloud" http://pdos.csail.mit.edu/~taesoo/pubs/2012/stealthmem/steal...
In my mind, cache-timing attacks are fairly easily solved, but may be platform dependent. However, VM escapes in general are still a concern.
> - "Cache-timing attacks on AES" http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
Sixteen years later....
"....These pages will eventually be open to the public. Right now they are inaccessible pending resolution of my court case."
Re:
MCS 494, Cryptography, Spring 1997
This is an online introduction to cryptography. It is based on the web pages that I wrote for my MCS 494 course at UIC.
http://cr.yp.to/crypto.html
See:
The main repository of information on Bernstein v. United States used to be http://www.eff.org/bernstein, subsequently moved to https://www.eff.org/cases/bernstein-v-us-dept-justice. This page is now much more comprehensive; you should change your bookmark to point to http://export.cr.yp.to.
http://cr.yp.to/export.html
Sixteen years later....
"....These pages will eventually be open to the public. Right now they are inaccessible pending resolution of my court case."
Re:
MCS 494, Cryptography, Spring 1997
This is an online introduction to cryptography. It is based on the web pages that I wrote for my MCS 494 course at UIC.
http://cr.yp.to/crypto.html
See:
The main repository of information on Bernstein v. United States used to be http://www.eff.org/bernstein, subsequently moved to https://www.eff.org/cases/bernstein-v-us-dept-justice. This page is now much more comprehensive; you should change your bookmark to point to http://export.cr.yp.to.
http://cr.yp.to/export.html
Huh? His papers are public. The only thing unpublished on that site is an old crypto class from the '90s.
Exactly. The question is, what possible legal justification argues for censoring the 90's course material regarding his Bernstein v. United States?
There isn't one. He could publish it if he wanted to. He just doesn't want to. That page is ancient. And none of this has anything to do with this story.
>There isn't one. He could publish it if he wanted to. He just doesn't want to.
Incorrect.
"....These pages will eventually be open to the public. Right now they are inaccessible pending resolution of my court case."
>And none of this has anything to do with this story.
Wrong again:
>...will make it harder for people to understand how crypto and hardware work, which is a shame. -tptacek
Advice:
In the future, as you reply to other's comments, read carefully with due consideration or you will continue to shoot yourself in the foot.
Incorrect.
"....These pages will eventually be open to the public. Right now they are inaccessible pending resolution of my court case."
>And none of this has anything to do with this story.
Wrong again:
>...will make it harder for people to understand how crypto and hardware work, which is a shame. -tptacek
Advice:
In the future, as you reply to other's comments, read carefully with due consideration or you will continue to shoot yourself in the foot.
I don't think you know what you're talking about. There are much more comprehensive US academic crypto resources than Bernstein's old page. Researchers routinely publish crypto research. The page you're pointing to is an artifact of '90s crypto policy.
I know enough to know it requires years of study to participate with "...Researchers routinely publish crypto research." For many of us on HN, including myself, what is more valuable is what is canonical textbook and more accessible. I would welcome being facile in '90s crypto policy'.
I'm not smart enough to understand what this comment is trying to say.
It's saying roughly "I know enough to know that it takes years of study before you can read research papers in crypto. I am happy just to read canonical textbook resources, even if they are from the 90s"
I think you could have tried a little bit harder to understand it before posting. Obviously English wasn't the author's first language and there's a risk that the author might perceive an insult to his English language skills. It's really nice that HN is a discussion between people with a wide variety of native languages as I'm certain you'd agree.
I think you could have tried a little bit harder to understand it before posting. Obviously English wasn't the author's first language and there's a risk that the author might perceive an insult to his English language skills. It's really nice that HN is a discussion between people with a wide variety of native languages as I'm certain you'd agree.
Re hardware AES such output can certainly be bit-by-bit compared with a pure software implementation, so we can be much more certain that it does exactly what it says.
But I also think we shouldn't worry much about RdRand, see my other comment here.
But I also think we shouldn't worry much about RdRand, see my other comment here.
So what if you can bit-by-bit compare its outputs? How do you know it isn't leaking key information via a side channel?
The argument that you can "bit-by-bit compare outputs" is an argument that AES cores can't be backdoored in any setting.
The argument that you can "bit-by-bit compare outputs" is an argument that AES cores can't be backdoored in any setting.
Are we talking about attacks on the bits of the message or about the penetration? I'm just pointing to the different level of potential problems. If somebody would blindly trust RdRand and it is actually not random (it's just a thought experiment, I don't believe that myself, and I know that Linux doesn't blindly trust it!) he can produce encrypted bits which could be easier to decode as they are. There's no such chance for AES instructions, which are trivially certain to match software implementations.
See Julian Morrison's comment upthread. If you don't trust Intel, don't kid yourself; you can't use their CPUs for crypto at all.
I believe that is fallacious.
For example, I don't trust Microsoft. We now know that they have some kind of backdoor in Skype. They are able to give the contents of my conversations to law enforcement or intelligence agencies. If I'm targeted, they can just flip a switch and record anything they want. But that doesn't mean it's impossible to have secure conversations if you use a Microsoft OS. It's unlikely that there is an actual remote admin backdoor in Windows itself, and even if it was, you'd have to be targeted, your PC identified, and the backdoor has to be activated before someone can siphon off data. And if you have a decently secure network, and use secure, open source software that doesn't route your traffic over microsoft's servers, it's much much harder to identify, let alone eavesdrop on you.
The existence of one highly specific access vector does not imply that the whole platform is compromised. Conversely, just because there is the theoretical possibility that the platform may be compromized on a low level, one should not forego additional security measures.
Just because the NSA might install a camera above my keyboard, I shouldn't stop encrypting my emails. Just because Intel might subvert my CPU in multiple ways doesn't mean I shouldn't be wary of them introduce specific potential security weaknesses.
*) Let's look at a potental tinfoil-hat attack mode. Intel might have some entity in their processors that detects whether I'm a potential target for surveillance and then weakens the hardware crypto. It would have to be pretty clever to find out from the CPU instructions that I'm doing something suspicious, or that I'm visiting a website containing a secret "enable weak crypto" byte sequence. While we're at it, it might also rewrite instructions to weaken 'software' crypto too, or even inject instructions to phone home. While theoretically possible, I believe this is highly unlikely. It is much, much more likely that they'd introduce a subtle weakness in the RNG that would let them crack keys a bit easier.
Being afraid about the former surely is paranoia, being afraid about the latter is rational distrust in a black box, IMHO.
For example, I don't trust Microsoft. We now know that they have some kind of backdoor in Skype. They are able to give the contents of my conversations to law enforcement or intelligence agencies. If I'm targeted, they can just flip a switch and record anything they want. But that doesn't mean it's impossible to have secure conversations if you use a Microsoft OS. It's unlikely that there is an actual remote admin backdoor in Windows itself, and even if it was, you'd have to be targeted, your PC identified, and the backdoor has to be activated before someone can siphon off data. And if you have a decently secure network, and use secure, open source software that doesn't route your traffic over microsoft's servers, it's much much harder to identify, let alone eavesdrop on you.
The existence of one highly specific access vector does not imply that the whole platform is compromised. Conversely, just because there is the theoretical possibility that the platform may be compromized on a low level, one should not forego additional security measures.
Just because the NSA might install a camera above my keyboard, I shouldn't stop encrypting my emails. Just because Intel might subvert my CPU in multiple ways doesn't mean I shouldn't be wary of them introduce specific potential security weaknesses.
*) Let's look at a potental tinfoil-hat attack mode. Intel might have some entity in their processors that detects whether I'm a potential target for surveillance and then weakens the hardware crypto. It would have to be pretty clever to find out from the CPU instructions that I'm doing something suspicious, or that I'm visiting a website containing a secret "enable weak crypto" byte sequence. While we're at it, it might also rewrite instructions to weaken 'software' crypto too, or even inject instructions to phone home. While theoretically possible, I believe this is highly unlikely. It is much, much more likely that they'd introduce a subtle weakness in the RNG that would let them crack keys a bit easier.
Being afraid about the former surely is paranoia, being afraid about the latter is rational distrust in a black box, IMHO.
Besides, I think the Skype backdoor started before it was acquired by MS:
http://www.slate.com/blogs/future_tense/2013/07/12/skype_sur...
This looks like more of a speculative political comment than a technical one. Your last paragraph is the only one that makes direct observations on crypto implementation, but gets crypto so wrong that I'm not encouraged to answer it; as a starting point, the problems in Intel microarchitecture that have led to actual attacks on cryptosystems have all targeted pure software crypto so far.
[deleted]
Sorry I don't see the relevance of CPU having any hidden global state in the thought experiment I've addressed. If all I give you is a PGP file made on the Intel CPU you simply don't have access to the global state of my CPU and I can be sure that I'd get exactly the same file up to the last bit using non-Intel CPU starting from the same inputs (including same 'seeds'). So I can actually be absolutely sure in AES instructions for any scenario where I only give you the results of encryption.
You're open to a different attack: If someone has access to (part of) your CPU state before and after you make the PGP file, they may be able to decrypt the message if they manage to intercept it.
And who is likely to have that access on an air-gapped machine in a faraday cage, exactly?
Just as a thought experiment: what sort of attack could Intel make if you limited your instruction set to the bare instructions (i.e. no special crypto assembly code)? Wouldn't it be unfeasible to attempt to detect crypto operations using normal assembly functions without even knowing whether crypto is taking place or not?
Practically every hardware side channel paper considers exactly this scenario. Start with Osvik and Tromer.
I think you're missing a key point. Yes, you can test AES at one moment in time. But when you're talking backdoors, they aren't necessarily active all the time.
Backdoors could wait for a specific trigger from outside input. I've been referring to these as "sleeper cell" attacks. For example, you could have a malicious memory module that alters its own contents when it sees a specific value and exploits the system in place.
Backdoors could wait for a specific trigger from outside input. I've been referring to these as "sleeper cell" attacks. For example, you could have a malicious memory module that alters its own contents when it sees a specific value and exploits the system in place.
Your suggestion is irrelevant for passive attacks.
There's also something fairly basic you can use to mitigate this: mix rdrand's output with some amount of entropy from other sources.
Even if it were done just a little to minimize performance impact, this would greatly increase the difficulty of using such a backdoor if it did exist.
And totally good point about cloud. Any cloud host can trivially observe everything you are doing, steal your keys, etc.
Even if it were done just a little to minimize performance impact, this would greatly increase the difficulty of using such a backdoor if it did exist.
And totally good point about cloud. Any cloud host can trivially observe everything you are doing, steal your keys, etc.
If you have other sources of good entropy then there's absolutely no point in using RdRand at all.
It never hurts to mix in more random.
Even if RdRand is a plot by the NSA it seems quite illogical to think that this is the first time they've collaborated with Intel so why are these people still using Intel chips at all?
It kind of sucks that RdRand is hard to verify as a user but it's no smoking gun either so it's not a great sell if you are trying to warn other people about the risks of backdoored hardware too.
It kind of sucks that RdRand is hard to verify as a user but it's no smoking gun either so it's not a great sell if you are trying to warn other people about the risks of backdoored hardware too.
Well, people use Intel chips because they don't really have a choice. I assume if Intel cooperates with the NSA, then so does AMD, and then you don't really have many more options.
Yes, manufacturers could plant all sorts of backdoors in your CPU (and other hardware), and they probably have. Still, I can reasonably assume that if I buy consumer hardware in a regular store, run secure and open source software, and am careful about my network, I'll be reasonably safe. Now, Intel introduces RdRand as a black box RNG. I'm not saying there's anything wrong with it, but if the NSA or whoever wanted to plant an inconspicuous weakness on millions of computers, this would be a nice way. I guess they could also do it with only a handfull of engineers at Intel knowing about it, as opposed to some other attacks that involve the whole processor.
Yes, manufacturers could plant all sorts of backdoors in your CPU (and other hardware), and they probably have. Still, I can reasonably assume that if I buy consumer hardware in a regular store, run secure and open source software, and am careful about my network, I'll be reasonably safe. Now, Intel introduces RdRand as a black box RNG. I'm not saying there's anything wrong with it, but if the NSA or whoever wanted to plant an inconspicuous weakness on millions of computers, this would be a nice way. I guess they could also do it with only a handfull of engineers at Intel knowing about it, as opposed to some other attacks that involve the whole processor.
The difference is that planted weakness in RdRand enables mass surveillance by weakening cryptographic algorithms. Other possible backdoors just make subject that are specially targeted weaker.
I'm guessing you don't work in cryptography research, and so posting on deep security issues seems pretty silly to me. The US government has endorsed demonstrably weak random number generating algorithms, and it is security professionals jobs to be very conservative.
As was discussed in Bruce Schneier's article about Dual_EC_DRBG:
http://www.schneier.com/blog/archives/2007/11/the_strange_st...
(Edit: This article was just discussed on HN only two weeks ago. https://news.ycombinator.com/item?id=5997483)
As was discussed in Bruce Schneier's article about Dual_EC_DRBG:
http://www.schneier.com/blog/archives/2007/11/the_strange_st...
(Edit: This article was just discussed on HN only two weeks ago. https://news.ycombinator.com/item?id=5997483)
It's not just about AWS, though. What about hard disk encryption, PGP, Bitcoin, or any other process that doesn't immediately leak its timing information over the network?
I imagine it would be difficult to covertly leak LUKS keys on a massive scale via a compromised AES-NI implementation. It's not like you can just modify the ciphertext output, and anything that uses a lot of silicon would attract attention.
On the other hand, a compromised RNG can do this pretty easily. Hell, NIST already published an algorithm that can do this.
I imagine it would be difficult to covertly leak LUKS keys on a massive scale via a compromised AES-NI implementation. It's not like you can just modify the ciphertext output, and anything that uses a lot of silicon would attract attention.
On the other hand, a compromised RNG can do this pretty easily. Hell, NIST already published an algorithm that can do this.
What can you trust then? License an ARM or MIPS IP core (in HDL form so it can be audited) and run it in an FPGA (or if you're rich, an ASIC)?
> and run it in an FPGA (or if you're rich, an ASIC)?
An FPGA contains way more junk than just the gate array these days.
And I don't know why you would trust Xilinx or Altera (who are way more dependent on government orders than Intel) over Intel. Or any fab, for that matter.
I think it's reasonable to be paranoid, but at some point one should do a cost-benefit analysis of the measures one is willing to indulge in. Because ultimately you will have to trust someone blindly, and that is true for both people and machines.
An FPGA contains way more junk than just the gate array these days.
And I don't know why you would trust Xilinx or Altera (who are way more dependent on government orders than Intel) over Intel. Or any fab, for that matter.
I think it's reasonable to be paranoid, but at some point one should do a cost-benefit analysis of the measures one is willing to indulge in. Because ultimately you will have to trust someone blindly, and that is true for both people and machines.
The back door would have to do some complicated pattern matching against the bitstream to identify potential "hook" or extraction points. Of course, built in crypto modules could not be trusted. I wouldn't trust much more than the LUTs! I could even see how a multiply block may be backdoored.
Of course, I am ignoring the proprietary tool chains in all of this. But again that depends on being able to find interesting stuff in your IP to backdoor. I would recommend using vendor IP as little as possible.
Don't use a vendor Ethernet module! I could see that as a great place to attach a scan-chain backdoor.
Don't use a vendor Ethernet module! I could see that as a great place to attach a scan-chain backdoor.
Speaking of ARM, the 64 bit ARMv8 architecture is supposed to come with AES, SHA1 and SHA-256 hardware encryption.
>(Actually, so can the Slovak Mafia, which is a reason to be leery of doing any crypto on AWS.)
Hi there! Any specific reason you have chosen Slovak Mafia (any reference)? They do not seem to me to be that kind of sophisticated at all. If any I would bet on Russian mafia..
Best regards from Slovakia.
Hi there! Any specific reason you have chosen Slovak Mafia (any reference)? They do not seem to me to be that kind of sophisticated at all. If any I would bet on Russian mafia..
Best regards from Slovakia.
I've long assumed that there is enough competition in the CPU space that if somebody was doing something particularly naughty, they would be found out by one of their competitors soon after when the competitors put chip under an electron microscope.
Is this a bad assumption?
Is this a bad assumption?
The 'answer' is light on technical details, however.
Given a 'random' number generator which always outputs the number 4, how can you attack ARIA, DES, 3DES, ARCFOUR, AES, Camellia, RC2, IDEA, SEED. That should be easy enough to show.
Now take a random number generator that seems random when N values are graphed, when N is small.
How do you exploit that?
How about when N is large? How about when N is huge and you've got researchers writing programs looking for predictability?
Given a 'random' number generator which always outputs the number 4, how can you attack ARIA, DES, 3DES, ARCFOUR, AES, Camellia, RC2, IDEA, SEED. That should be easy enough to show.
Now take a random number generator that seems random when N values are graphed, when N is small.
How do you exploit that?
How about when N is large? How about when N is huge and you've got researchers writing programs looking for predictability?
[deleted]
Reminds me of this friend working at the DST (french counter-intelligence service) explaining how all the crypto hardware coming from Bull, Thales and other French companies need to be backdoored to get its proper government qualification. Furthermore, the French government happily provides this hardware for a very attractive price to "their friends", like Romanian, Lebanese, etc. security services.
No, you shouldn't be worried about RdRand particularly, not more than about any other function, as long as you use it properly. If you don't use it yourself, others already did the right thing for you, so you don't have to worry: The present discussion here on HN showed that it is used properly on Linux. It's not the only source and there's a seed used separately:
https://news.ycombinator.com/item?id=6040912
https://news.ycombinator.com/item?id=6040912
It's still used directly in Linux: https://mailman.stanford.edu/pipermail/liberationtech/2013-J... Furthermore, if RdRand is insecure but not recognized as such it's a potential risk due to people building supposedly secure software using the instruction.
Address space randomization is not something you should worry about unless the attacker is already on your machine, that is, it's irrelevant for passive attacks.
The Advanced Encryption Standard (AES)
"...is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.[3] It is based on the Rijndael cipher[4] developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, who submitted a proposal which was evaluated by the NIST during the AES selection process.[5]
AES has been adopted by the U.S. government and is now used worldwide. It supersedes the Data Encryption Standard (DES),[6] which was published in 1977. The algorithm described by AES is a symmetric-key algorithm, meaning the same key is used for both encrypting and decrypting the data.
AES is available in many different encryption packages, and is the first publicly accessible and open cipher approved by the National Security Agency (NSA) for top secret information when used in an NSA approved cryptographic module (see Security of AES, below)..."
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
RdRand (also RDRAND)
"...is an instruction for returning random numbers from an on-chip random number generator.[1] RdRand is available in Ivy Bridge processors[note 1] and is part of the Intel 64 and IA-32 instruction set architectures.
Intel Secure Key, formerly known as Bull Mountain, is Intel's code name for both the RdRand instruction and the underlying random number generator (RNG) hardware implementation.[1] Intel calls their RNG a "digital random number generator". The generator uses an on-processor entropy source, which passes the randomly generated bits to an AES (in CBC-MAC mode) conditioner to distill the entropy into non-deterministic random numbers. A deterministic random-bit generator is seeded by the output from the conditioner, providing cryptographically secure random numbers to applications requesting them via the RdRand instruction..."
http://en.wikipedia.org/wiki/RDRAND
"...is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.[3] It is based on the Rijndael cipher[4] developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, who submitted a proposal which was evaluated by the NIST during the AES selection process.[5]
AES has been adopted by the U.S. government and is now used worldwide. It supersedes the Data Encryption Standard (DES),[6] which was published in 1977. The algorithm described by AES is a symmetric-key algorithm, meaning the same key is used for both encrypting and decrypting the data.
AES is available in many different encryption packages, and is the first publicly accessible and open cipher approved by the National Security Agency (NSA) for top secret information when used in an NSA approved cryptographic module (see Security of AES, below)..."
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
RdRand (also RDRAND)
"...is an instruction for returning random numbers from an on-chip random number generator.[1] RdRand is available in Ivy Bridge processors[note 1] and is part of the Intel 64 and IA-32 instruction set architectures.
Intel Secure Key, formerly known as Bull Mountain, is Intel's code name for both the RdRand instruction and the underlying random number generator (RNG) hardware implementation.[1] Intel calls their RNG a "digital random number generator". The generator uses an on-processor entropy source, which passes the randomly generated bits to an AES (in CBC-MAC mode) conditioner to distill the entropy into non-deterministic random numbers. A deterministic random-bit generator is seeded by the output from the conditioner, providing cryptographically secure random numbers to applications requesting them via the RdRand instruction..."
http://en.wikipedia.org/wiki/RDRAND
For many years, I've been considering purchasing one of these:
http://www.entropykey.co.uk/
I honestly don't know why we're using anything other than provable randomness using discrete entropy sources in this day and age.
IIRC, even the Raspberry Pi has an entropy generator on-board. I haven't verified this though.
http://www.entropykey.co.uk/
I honestly don't know why we're using anything other than provable randomness using discrete entropy sources in this day and age.
IIRC, even the Raspberry Pi has an entropy generator on-board. I haven't verified this though.
Lots of things I've seen show hardware random number generators to be flawed. That particular device looks much better than those older devices.
(http://www.robertnz.net/hwrng.htm)
(http://www.robertnz.net/true_rng.html)
EDIT: here are some more devices, but I have no idea if these are any good.
(http://www.westphal-electronic.com/)
(http://www.trng98.se/shop/index.php)
(http://www.comscire.com/)
(http://www.idquantique.com/random-number-generators/products...)
(http://www.letech.jpn.com/)
(http://www.robertnz.net/hwrng.htm)
(http://www.robertnz.net/true_rng.html)
EDIT: here are some more devices, but I have no idea if these are any good.
(http://www.westphal-electronic.com/)
(http://www.trng98.se/shop/index.php)
(http://www.comscire.com/)
(http://www.idquantique.com/random-number-generators/products...)
(http://www.letech.jpn.com/)
From the website
Please note that there is a very long waiting period for
Entropy Keys at the moment.
Not exactly:
On Tue, Jul 02, 2013 at 08:11:13AM -0500, Robert Lee wrote: > This is unfortunate. I do hope they are not going out of business.
We've gone through a major crisis, but are still here... just. To say any more in public at this stage might be unwise from a legal standpoint.
We currently have no manufacturing capability for ekeys but are working towards getting things up and running again. There's no timescale on that yet, I'm afraid.
-- Paul Martin <pm at simtec.co.uk> Simtec Electronics http://www.simtec.co.uk/
On Tue, Jul 02, 2013 at 08:11:13AM -0500, Robert Lee wrote: > This is unfortunate. I do hope they are not going out of business.
We've gone through a major crisis, but are still here... just. To say any more in public at this stage might be unwise from a legal standpoint.
We currently have no manufacturing capability for ekeys but are working towards getting things up and running again. There's no timescale on that yet, I'm afraid.
-- Paul Martin <pm at simtec.co.uk> Simtec Electronics http://www.simtec.co.uk/
I am just curious, why can't there be an online service which does Random Number Generation, that should free up this dependency right? I understand there would be trust issues etc, but I am sure well defined contracts and code transparency coupled with open hardware can solve that?
1) It would be slow.
2) The trust issue would be even greater and it would introduce a single point of failure.
3) Online RNGs do actually exist. http://Random.org for example.
2) The trust issue would be even greater and it would introduce a single point of failure.
3) Online RNGs do actually exist. http://Random.org for example.
{snipped}
EDIT: Thanks to lub1be for pointing out my error!!
EDIT: Thanks to lub1be for pointing out my error!!
You mean Thomas[1]? That's not Thomas Pornin[2].
[1] http://crypto.stackexchange.com/questions/9210/technical-fea...
[2] http://crypto.stackexchange.com/users/28/thomas-pornin
Edit: Guys there is no need to downvote him for making a simple mistake. I actually also assumed that at first before remembering that Thomas Pornin uses his full name as display name.
[1] http://crypto.stackexchange.com/questions/9210/technical-fea...
[2] http://crypto.stackexchange.com/users/28/thomas-pornin
Edit: Guys there is no need to downvote him for making a simple mistake. I actually also assumed that at first before remembering that Thomas Pornin uses his full name as display name.
Wouldn't a easier path for decrypting SSL be to go directly to Cert providers and hit them with a NSL?
Cert provider does not have the secret key, so the only thing you can do is get a new cert and and then do man-in-the-middle. It's doable for an individual target, but not doable for a massive dragnet.
If a compromised RNG can be used to decrypt data, it might be useful for wholesale decryption of all encrypted traffic on the web.
If a compromised RNG can be used to decrypt data, it might be useful for wholesale decryption of all encrypted traffic on the web.
If this actually yields anything, could it mean the wider proliferation of HW random number generators?
Guess what: none of this matters, because RdRand is only one source of entropy among many. For example, another source is the timing of TCP packets coming into the machine. The NSA can't predict that; nobody can. It's the butterfly effect in action.
RdRand is kind of the "crocodiles in the sewer" of HN. A tall tale that somehow keeps getting passed around. Guys, they're just generating random bits from thermal noise, that's it! There's a million other more effective backdoors they could insert into the motherboard, CPU, or firmware.
RdRand is kind of the "crocodiles in the sewer" of HN. A tall tale that somehow keeps getting passed around. Guys, they're just generating random bits from thermal noise, that's it! There's a million other more effective backdoors they could insert into the motherboard, CPU, or firmware.
Moreover, if you're serious about having a problem with rdrand, you really can't be doing crypto on the x86 platform (putting you between a rock and a hard place, owing to that HSM injunction) --- that's because you don't actually know what the microarchitecture of the x86 platform is. It's far more complicated than the instruction set, or even what's documented in the PRM.
Aciicmez was able to recover keys from an Intel branch target buffer (the branch prediction cache). Did you know what the BTB was before I wrote this? Well, the BTB is public knowledge. How many microarchitectural features are there on the platform that aren't public knowledge? Probably lots. Not being a tinfoil hat type, I tend not to believe that any of these are malicious. But if you think rdrand is a plot by the NSA, you are a tinfoil hat type, and so let me help you be consistent: you need to stop using AWS right now, and stop using x86 platforms to run your encryption code. The NSA can pay $50 to get a VM on the same AWS box as runs your VMs, and then use local side channels to siphon out your secrets.
(Actually, so can the Slovak Mafia, which is a reason to be leery of doing any crypto on AWS.)
If you can't tell, I think this whole kerfluffle about Linux using rdrand is pretty silly.