The Mathematics Community and the NSA [pdf](ams.org)
ams.org
The Mathematics Community and the NSA [pdf]
http://www.ams.org/notices/201502/rnoti-p165.pdf
13 comments
"The international war on terrrorism" (by the end). Sorry: despite whatever he says, this is totally out of place. As long as you use the (buzz)word war, you open the door to exceptional "security" measures
To be fair, these are the operating directives of his employers. I imagine it's hard to be a completely objective mathematician when your work is actually used to affect substantial political change IRL.
And likewise, after you utter the words “National Security”®, the U.S. all of a sudden don't have a constitution any more. I'm quite sure, however, that this isn't any mathematician's fault.
He also mentions 'piracy' (the data sharing kind, I presume) - it seems he will stoop to using any convenient buzzword/bogeyman.
Well, in absence of tangible success, what else can you do but admit failure, or otherwise produce massive amounts of hot air?
It's probably easier to catch a “pirate” than a “terrorist”, so if the NSA has you believe “piracy” is a threat to National Security, then maybe they can claim some success stories after all.
It's probably easier to catch a “pirate” than a “terrorist”, so if the NSA has you believe “piracy” is a threat to National Security, then maybe they can claim some success stories after all.
Why would you assume 'piracy' doesn't refer to actual piracy? It's a fairly big deal in several parts of the world.
Sure, many things are a 'big deal' in some parts of the world - malaria, corrupt governments, famine, domestic violence, ebola, contaminated drinking water, etc etc.
Why did I presume he meant data sharing 'piracy'? Well he didn't choose to mention organised crime, of which naval piracy is a small part. It would probably be a more relevant target for sigint than e.g. Somalis in speedboats, and also more relevant to US security.
The author is, imo, casting around for buzzwords/bogeymen, and he thought data sharing 'piracy' hit the right buttons.
Why did I presume he meant data sharing 'piracy'? Well he didn't choose to mention organised crime, of which naval piracy is a small part. It would probably be a more relevant target for sigint than e.g. Somalis in speedboats, and also more relevant to US security.
The author is, imo, casting around for buzzwords/bogeymen, and he thought data sharing 'piracy' hit the right buttons.
Because you don't need a strong cipher to send text messages like "Yo-ho-ho, and a bottle of rum."
Presumably pirates favor arrrr-C4 or arrrr-SA (both of them invented by Ronald Rivest.)
I especially liked the name-dropping of 9/11 toward the end, and the emotional appeals to the heroism of fighting Germany and Japan.
> Filtering algorithms decide what material is
defeated, i.e., neither collected nor stored for
analysis.
This is one of the NSA's definitions I disagree with. Filtering is collection and analysis, the only difference is the government agent performing the search is an algorithm.
This is one of the NSA's definitions I disagree with. Filtering is collection and analysis, the only difference is the government agent performing the search is an algorithm.
I'm sorry, but to me this reads like an apology[* ] letter targeted to future (and current) employees, because of all the bad publicity they have received. They're probably having a hard time recruiting, hence this smoke.
[* ] for some very weak definition of 'apology'
[* ] for some very weak definition of 'apology'
The author sounds like a nice guy/gal but they seem to have selectively forgot several facts. First the NSA's Dual_EC_DRBG was used as the default in some RSA products. Is it debatable that the RSA was not paid for this (the $10m claim)? But this is not the only episode quoted as reason to consider NSA malice. The Bullrun program? And his/her employers constant lies?
If your employer is using your work for malice without telling you, and lying to many of their clients (the public)... stop kidding yourself just because they were nice to you and paid for your PhD.
If your employer is using your work for malice without telling you, and lying to many of their clients (the public)... stop kidding yourself just because they were nice to you and paid for your PhD.
[deleted]
Whatever justifications the NSA comes up with, the crux with Dual_EC_DRBG remains: Either they are as malicious as is now publicly believed and those points were indeed generated with an included backdoor. Or they are stupid enough to endorse an RNG that is slow, not provably secure and may even contain a backdoor.
Extending on the provably secure part: There actually are constructions that allow you to reduce the discrete logarithm problem to the one-way property and to the pseudo randomness property of the RNG. And without such a proof, what is the benefit of a slow elliptic curve RNG anyway?
Regarding the backdoor part: Even for the NSA the potential of a backdoor is a problem, because every division has to trust the person that has actually generated the points. And as the Dual_EC_DRBG was used by the DoD, this person potentially has the keys to some very sensitive parts of the kingdom.
Extending on the provably secure part: There actually are constructions that allow you to reduce the discrete logarithm problem to the one-way property and to the pseudo randomness property of the RNG. And without such a proof, what is the benefit of a slow elliptic curve RNG anyway?
Regarding the backdoor part: Even for the NSA the potential of a backdoor is a problem, because every division has to trust the person that has actually generated the points. And as the Dual_EC_DRBG was used by the DoD, this person potentially has the keys to some very sensitive parts of the kingdom.
"In truth, I can think of no better way to describe our failure to drop support for the Dual_EC_DRBG algorithm as anything other than regrettable."
'malicious', perhaps?
'malicious', perhaps?
For some reason, this feigned almost-apology seems a lot more dickish than if they were just silent on the matter completely.
It's pretty well-accepted at this point that they intended the algorithm to allow for "key escrow" (a government backdoor) from the very beginning. And instead of just admitting that's what they did, they're trying to come up with a story about how it was all a big mistake and no they didn't backdoor it, they just supported a broken and insecure algorithm.
It's like someone coming up to you, punching you in the face, and then saying "oh, sorry, didn't mean to do that, my hand slipped". The words just add insult to injury.
It's pretty well-accepted at this point that they intended the algorithm to allow for "key escrow" (a government backdoor) from the very beginning. And instead of just admitting that's what they did, they're trying to come up with a story about how it was all a big mistake and no they didn't backdoor it, they just supported a broken and insecure algorithm.
It's like someone coming up to you, punching you in the face, and then saying "oh, sorry, didn't mean to do that, my hand slipped". The words just add insult to injury.
> Even for the NSA the potential of a backdoor is a problem, because every division has to trust the person that has actually generated the points. And as the Dual_EC_DRBG was used by the DoD, this person potentially has the keys to some very sensitive parts of the kingdom.
While this is generally true, it is possible for a person or organization to remove the backdoor by generating their own point and/or by reducing the number of bits generated from curve points at each RNG step (which NIST had pushed for an insecure number of).
I can't claim to know for sure, but it would be my guess that the implementations used at the Federal Reserve, the DoD and other highly sensitive areas of government that use public algorithms highly vetted to remove known implementation problems and weak parameterizations.
While this is generally true, it is possible for a person or organization to remove the backdoor by generating their own point and/or by reducing the number of bits generated from curve points at each RNG step (which NIST had pushed for an insecure number of).
I can't claim to know for sure, but it would be my guess that the implementations used at the Federal Reserve, the DoD and other highly sensitive areas of government that use public algorithms highly vetted to remove known implementation problems and weak parameterizations.
In the case of the NSA:
Never attribute to stupidity what can be attributed to malice.
And that is the only compliment they will get from me.
And that is the only compliment they will get from me.
Pardon me if I'm misinterpreting you, but isn't the existence of one-way functions equivalent to P != NP? So far we definitely haven't proved/disproved that one-way functions exist, so any primitive that relies on them is not provably secure.
More generally, I don't think there are any CSPRNGs that are actually provably secure; please correct me if I'm wrong. The proofs all rely in some way on problems that are conjectured to be hard, which depends on P != NP. This isn't necessarily the case, if we could devise an algorithm that depends on a decidable problem harder than NP-complete, but I don't think we have proved if any such problems exist.
Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.
More generally, I don't think there are any CSPRNGs that are actually provably secure; please correct me if I'm wrong. The proofs all rely in some way on problems that are conjectured to be hard, which depends on P != NP. This isn't necessarily the case, if we could devise an algorithm that depends on a decidable problem harder than NP-complete, but I don't think we have proved if any such problems exist.
Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.
To say that something is reducible to a conjectured hard problem is what 'provably secure' means in cryptography. Also, cryptographic hardness is not trivially relatable to P vs. NP, especially for hardness assumptions used to build public-key systems. For example, a poly-time factoring algorithm would not prove P == NP, but it would break RSA.
Good point, thanks. It looks like a few of them, including factorization and the discrete log problem, are conjectured to be NP-intermediate; that is, NP but neither P nor NP complete. However, this class may actually be empty, and is only non-empty if P != NP.
If P = NP, NP-intermediate is necessarily empty, so problems like factorization would be P = NP = NP-complete. You're right, though: the existence of a (classical) polynomial-time factorization algorithm doesn't solve P = NP.
If P = NP, NP-intermediate is necessarily empty, so problems like factorization would be P = NP = NP-complete. You're right, though: the existence of a (classical) polynomial-time factorization algorithm doesn't solve P = NP.
> Edit: On reflection, I think the parent is saying that there was never a proof published that Dual_EC_DRBG is reducible to a hard problem, and without that we cannot even say whether Dual_EC_DRBG is as secure as other PRNGs that can be shown to be related to hard problems.
Yes, that was what I meant to say. There are elliptic curve PRNGs for which it is proven that breaking their security properties allows you to calculate the discrete logarithm on the elliptic curve. IIRC, no such proof is publicly known for Dual_EC_DRBG, even under the assumption that both points P and Q were chosen at random.
If you have specifically crafted the points (you know the logarithm of Q to base P), then breaking Dual_EC_DRBG is trivial. And by "breaking" I mean recovering the internal state of the PRNG out of its output.
Yes, that was what I meant to say. There are elliptic curve PRNGs for which it is proven that breaking their security properties allows you to calculate the discrete logarithm on the elliptic curve. IIRC, no such proof is publicly known for Dual_EC_DRBG, even under the assumption that both points P and Q were chosen at random.
If you have specifically crafted the points (you know the logarithm of Q to base P), then breaking Dual_EC_DRBG is trivial. And by "breaking" I mean recovering the internal state of the PRNG out of its output.
>Using aggregate numbers, of the exceedingly small proportion of the world’s foreign communications we access, NSA algorithms filter out approximately 99.998 percent of the data it sees.
Keeping 0.002% seems like just little bit of data, but is it?
79% of the Internet traffic is video. If you filter out almost all video content and other uninteresting transfer to everyone (50 companies deliver more than half of all Internet traffic), I think you can retain all metadata and all or most unique text based communications. Speech to text filter can keep metadata and at least huge number of keywords from all phone conversations.
Keeping 0.002% seems like just little bit of data, but is it?
79% of the Internet traffic is video. If you filter out almost all video content and other uninteresting transfer to everyone (50 companies deliver more than half of all Internet traffic), I think you can retain all metadata and all or most unique text based communications. Speech to text filter can keep metadata and at least huge number of keywords from all phone conversations.
"Don't worry. Sure, the thief left with all your cash, jewelry, IDs, tax information, and private documents... But 99.998% of the mass contained by your house is still there! Honestly, if it's less than 100kg it's not even worth getting upset about."
Yeah, it's a stupid statistic designed to mislead, since the metric bears no real relationship to the impact or severity of the act.
I wonder how the NSA would react if a spy browsed all their top-secret documents, but made copies of "only 0.002%" of them?
Yeah, it's a stupid statistic designed to mislead, since the metric bears no real relationship to the impact or severity of the act.
I wonder how the NSA would react if a spy browsed all their top-secret documents, but made copies of "only 0.002%" of them?
"The remaining 25 percent" [of reported 'illegal' interceptions] ", about 700 in total, were human error (e.g., typing mistakes). Put into perspective, the average analyst at NSA makes a compliance mistake once every ten years."
This does not reassure me.
First, those are only the 'mistakes' that were detected and reported - which independent body is doing the oversight?
Secondly, he says that their staff are just about perfect (an error rate of 1 per 10 years) whilst at the same time saying that the errors were typing mistakes.
It is sad to see a Mathematician reduced to such deceit.
This does not reassure me.
First, those are only the 'mistakes' that were detected and reported - which independent body is doing the oversight?
Secondly, he says that their staff are just about perfect (an error rate of 1 per 10 years) whilst at the same time saying that the errors were typing mistakes.
It is sad to see a Mathematician reduced to such deceit.
First, note how the only numbers addressed are the '2,776 instances publicly known'. So from the start we're working with unreasonable numbers. But let's run with it.
Hmm. If the average number of mistakes an analyst makes is 0.1 per year and there were 700 mistakes only, this means 7000 analysts (or do we need to model this as a poisson distribution?). Is 7,000 analysts reasonable? Anyone have more details on this?
The NSA has said that it performs about 20 million queries a month, or 240 million queries a year. If these are done by analysts that's 16 manual queries an hour or 130 a day assuming a standard work week. That seems reasonable. Or at least reasonable"ish". [240,000,000 / 7,000 / (5/7 * 8 * 365)]
But it would also imply an error rate of 700/24,000,000 = 0.000002917 (which is absurd, if the error are presumably due to 'typos').
Hmm. If the average number of mistakes an analyst makes is 0.1 per year and there were 700 mistakes only, this means 7000 analysts (or do we need to model this as a poisson distribution?). Is 7,000 analysts reasonable? Anyone have more details on this?
The NSA has said that it performs about 20 million queries a month, or 240 million queries a year. If these are done by analysts that's 16 manual queries an hour or 130 a day assuming a standard work week. That seems reasonable. Or at least reasonable"ish". [240,000,000 / 7,000 / (5/7 * 8 * 365)]
But it would also imply an error rate of 700/24,000,000 = 0.000002917 (which is absurd, if the error are presumably due to 'typos').
The author repeatedly refers to the NSA operating within the bounds of the law and set policy. Do not be fooled by that decoy. Yes, they may be operating legally;but there in lies the fundamental problem: the law and policy is lax, to put it gently.
Absolutely agree. People often fall into the false mindset that legal = morally or ethically right. Law is neither. Law is the result of politically motivated negotiations which managed to reach majority consensus. It could be argued that law is amoral.
> majority consensus.
A majority consensus of those who have been bribed enough to make a mockery of the idea.
A majority consensus of those who have been bribed enough to make a mockery of the idea.
They're also relying on legal opinions provided by interested and involved parties, so the claim of "legality" is dubious at best.
And thus, we are to blame. When was the last time anyone voted for a candidate based on their privacy stance? Can anyone name a presumptive presidential candidate who has spoken out against NSA abuses? I can name one but I'd get downvotes just for mentioning his name.
The simple tragedy is that most Americans don't have the time or inclination to understand the nuances of the issue -- at least not to a degree that they'd vote on that issue.
Most people seem to think "higher taxes bad; tax the rich; end welfare; increase welfare; no free school lunches; more free lunches.." People seem to be almost binary in their understanding of the issues of the day.
Let's hope that changes. The fact is that most people can at least understand the idea of online privacy, but when issues like illegal file sharing or similar things that aren't in the mainstream of your average person, then the passion for the issue is muted.
If, for example, there were high profile cases that made the national news about Grandma getting violated in a detrimental way by the NSA, then maybe the issue would gain traction. However, privacy violations typically happen to either a "criminal" or "someone else." So the issue is ignored.
It's everyone's issue, but the issue hasn't been well framed. It's the same logic used to get traffic camera installed: "If you ain't doing anything wrong, then it shouldn't matter."
Frustrating.
The simple tragedy is that most Americans don't have the time or inclination to understand the nuances of the issue -- at least not to a degree that they'd vote on that issue.
Most people seem to think "higher taxes bad; tax the rich; end welfare; increase welfare; no free school lunches; more free lunches.." People seem to be almost binary in their understanding of the issues of the day.
Let's hope that changes. The fact is that most people can at least understand the idea of online privacy, but when issues like illegal file sharing or similar things that aren't in the mainstream of your average person, then the passion for the issue is muted.
If, for example, there were high profile cases that made the national news about Grandma getting violated in a detrimental way by the NSA, then maybe the issue would gain traction. However, privacy violations typically happen to either a "criminal" or "someone else." So the issue is ignored.
It's everyone's issue, but the issue hasn't been well framed. It's the same logic used to get traffic camera installed: "If you ain't doing anything wrong, then it shouldn't matter."
Frustrating.
I did vote for Obama in 2008 because he promised no more warrantless wiretaps and in general seemed the least-bad 'realistic' (as in Schelling-point) choice for civil liberty. (I did not in 2012.) I agree that not nearly enough people give creeping totalitarianism its proper priority in voting; for the foreseeable future some other sort of action is needed.
I voted for Mark Udall for Colorado Senator last November, mostly for his work on the Senate Intelligence Committee. Does that count?
The NSA doesn't consider itself bound by law and hasn't since its inception. During the Church Committee hearings in the 70s, the NSA's general counsel admitted as much:
“No existing statutes control, limit, or define the signals intelligence activities of the NSA.”
-Roy Banner
“No existing statutes control, limit, or define the signals intelligence activities of the NSA.”
-Roy Banner
The fourth amendment was written in the simplest possible terms because it was meant to be interpreted by us. The moment we stop interpreting this constitution right for ourselves, and let politicians and lawyers interpret it for us, is the moment we surrender our freedom. As part of the constitution, no other law or ruling can supersede it, no matter how much some bureaucrats and fear-mongers may say otherwise.
No matter what policy the NSA comes up with, it cannot trump our fourth amendment right, nor our right to interpret it.
No matter what policy the NSA comes up with, it cannot trump our fourth amendment right, nor our right to interpret it.
See also Matthew Green's response:
http://blog.cryptographyengineering.com/2015/01/hopefully-la...
http://blog.cryptographyengineering.com/2015/01/hopefully-la...
and yesterday's discussion at https://news.ycombinator.com/item?id=8888635
It's good that the NSA are seeking to be more open and transparent.
A few things I'm curious about, though...
> The NSA-generated elliptic curve points were necessary for accreditation of the Dual_EC_DRBG but only had to be implemented for actual use in certain DoD applications.
Why were the NSA-generated elliptic curve points have to be included in the standard for it to be accredited?
Why did those points have to be used for certain DoD applications? Why not use random points?
And why was it necessary for those points to be included in the standard? Why not leave it up to the implementer to decide what points to use?
A few things I'm curious about, though...
> The NSA-generated elliptic curve points were necessary for accreditation of the Dual_EC_DRBG but only had to be implemented for actual use in certain DoD applications.
Why were the NSA-generated elliptic curve points have to be included in the standard for it to be accredited?
Why did those points have to be used for certain DoD applications? Why not use random points?
And why was it necessary for those points to be included in the standard? Why not leave it up to the implementer to decide what points to use?
In 2007--8, I was trying to leave my academic position and join the NSA as a mathematician. It didn't end up working out. That was an enormous blow at the time: with the cycle of academic contracts, I had to choose whether to not sign or to defer the NSA job until the end of the next academic year. I chose the former, and the provisional job offer fell through.
In the end, though, it was probably for the best. When Snowden first hit the news, all I could think of was "there but for the grace of the gods go I."
In the end, though, it was probably for the best. When Snowden first hit the news, all I could think of was "there but for the grace of the gods go I."