6 ms·

You can be sure that our numerate friends at the NSA have spent some quality time trying to find an efficient factoring algorithm over the past few decades. As

You can be sure that our numerate friends at the NSA have spent some quality time trying to find an efficient factoring algorithm over the past few decades. As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. And given the stakes it's really not likely to be the possibly untested problem that this author speculates about.

leereeves 10y ago
Decades of research don't prove that there's no solution. It took mathematicians 357 years to prove Fermat's Last Theorem.
- _asummers 10y ago
  And that required about 357 years of mathematics to be able to prove it, as well. With the recentish GI announcement, I'm hopeful factoring and discrete log will fall within the next decade or two, but it's likely going to involve a bunch of subtle perspective shifts on several different fronts combined with new machinery in math to show.
  - kazinator 10y ago
    3 x 7 x 17 = 357 years, by the way.
    - Retra 10y ago
      I see you're not a physicist...
feral 10y ago
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. "assume with good confidence" - this is very naive. They're not going to advertise their super secret breakthrough by acting like they no longer care about encryption. Such a secret is going to be compartmentalized in the organization etc.
- thesimpsons1022 10y ago
  from all the Snowden leaks it seems pretty apparent they couldn't break encryption... but it's been a while since then so who knows now
- nickpsecurity 10y ago
  Fortunately, those slides leaked. The lower levels talked about cryptanalysis and supercomputers. The TS/SCI/ECI stuff said they were backdooring crypto at the company level using FBI locally and CIA/ISA foreign. Also note their own Type 1 systems allow these ciphers with most sensitive stuff and EKMS using a variation of Photorus called Firefly. Safe bet that good implementations of the stuff still work.
  - feral 10y ago
    That's a lot of detail, which I'm not familiar with as a causal observer, but its irrelevant. The slides show the capabilities of one layer of the onion, but its surely naive to assume that's everything? A total mathematical factoring break is a holy grail. I mean, they made a hollywood movie about this! In the 90s! Sneakers: "There isn't a government on this planet that wouldn't kill us all for that thing." Obviously, that's a movie, not real life, but the sentiment is valid.
    - nickpsecurity 10y ago
      It's possible. Yet, someone has to be able to use that stuff. The Sentry Eagle leaks showed that, as I predicted, they developed most of this stuff in Special Access Programs that compartmentalize things away from even TS clearance. Then, as capabilities are developed, people with TS/SCI clearances are briefed on one or more based on their need to know. Some are so high up they get briefed on all of them. That was Sentry Eagle: https://leaksource.info/2014/10/17/sentry-eagle-nsa-core-secrets-re-covert-activities-inside-companies-access-sensitive-data-compromise-networks-subvert-encryption/ https://leaksource.info/2014/10/17/sentry-eagle-nsa-core-sec... As you can see, the descriptions represent their most guarded secrets that can do the gravest damage. There could be an extra layer that basically has that one fact in it. I doubt it given how many different angles of attack & severity these docs cover. We also saw that predicted damage adding up after the releases of such leaks. It's more believable given it's the exact kinds of things I'd expect a post-9/11 agency to be doing if they couldn't break RSA, etc. They'd do it anyway for deniability but these are so secret they'd rather let targets go to preserve them. The secrecy level was already tight enough to cover preserving RSA so long as insiders on highest levels kept quiet. Last part they didn't play so well. ;)
fizx 10y ago
> As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed It would be quite the bluff though.
munificent 10y ago
> As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. After the Enigma was cracked, the government was terrified that the Axis would find out. If they knew they were cracked, they could change the cipher and set back the Allies significantly. So they spent a ton of effort obscuring their own intelligence. Whenever a decoded Enigma message told them where a U-boat would be, they sent a "spotter" boat whose job is was to be seen seeing the U-boat before it was attacked. That way there was a plausible source of information for the U-boat's location. (These spotters were so "effective", the Germans suspected there must be many more of them in the area then there actually were.) One time they weren't able to get a spotter there in time and Churchill himself made the call to attack anyway. To cover for that and avoid arousing suspicion, they sent a radio dispatch to a fake spy thanking him for the intel, so that the message could be intercepted by the Germans. I wouldn't be so confident if I were you.
- monkmartinez 10y ago
  That is just so fascinating... do you know where I could read more about this sort of thing. I don't care about time frames. Vietnam, I suspect, may have some interesting crypto treasures... edit: spelling
  - harry8 10y ago
    cryptonomicon by Neal Stehpens is a fiction but has a lot of this kind of thing in it. Not sure how accurate. Code book by Simon Singh. "The Man Who Never Was" is a boot I have never read but should because it's great ww2 espionage story. I'm sure others will kick in some suggestions.
  - Terribledactyl 10y ago
    If you want fiction, https://en.m.wikipedia.org/wiki/Cryptonomicon https://en.m.wikipedia.org/wiki/Cryptonomicon is a lot of fun.
  - ecesena 10y ago
    I like Simon Singh a lot. I've used his The Code Book to teach basic crypto at high school.
tptacek 10y ago
No! It does not at all follow from NSA/USG's policy interests that NSA doesn't have secret factoring improvements. As the last few years of crypto research have shown, there's a big difference between having a break and being able to operationalize the break. It's plausible that NSA could have something that is tractable against an individual target, but not against massed targets. In fact: if they have a secret factoring improvement, this is the most likely shape of the problem for them.
Utanith 10y ago
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. I think the real issue with relating their position on legislation to their ability to break any given algorithm (Or the problem on which it is based) is this: Legislation will survive a new, more secure algorithm. Breaking one algorithm is subject to being patched out or the algorithm being entirely replaced. A broken system is a short-term investment, legislation is long-term (With the assumption that the government enforcing the legislation sticks around).
mindslight 10y ago
You're conflating the NSA with the rest of the government, namely the FBI. I believe some spokesperson from the NSA has even gone on record lately against the FBI's desires to criminalize [applied math]. The NSA is an organization that tackles the world as it is. Compromised standards, TAOed equipment, global passive adversary, exploiting OPSEC fails. Even if the highest compartments of the NSA were able to instantly factor any RSA key, these alternative methods would still be useful for plausible deniability as well as general use by less-privileged compartments. The FBI is lucky to receive any of the NSA's scraps (and if they did, it would be some vague tip to start looking in the right place), hence being left to push for criminalization to facilitate their actual investigations.
davidwihl 10y ago
In 1996 I asked Robert Morris Sr if he was worried that so much crypto was dependent upon factorization. "Worried? I'm not worried, but I can tell you that if US Military lives are at stake, we don't use algorithms that depend on factorization." From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago.
- DashRattlesnake 10y ago
  > From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago. Or they judge that a pragmatic solution is within the realm of possibility, and they don't want take the chance of being caught with their pants down. They probably have the resources to take on many extra operational costs to avoid theoretical risks. One of the quotes on his Wikipedia pages is: "Never underestimate the attention, risk, money and time that an opponent will put into reading traffic."
- mkagenius 10y ago
  Because Robert Morris Sr said something hypothetical doesn't mean one should speculate.
- oconnor0 10y ago
  What are the other options?
  - dnautics 10y ago
    Elliptic curve
  - daxfohl 10y ago
    Couriers, duh: http://www.dailykos.com/story/2016/7/29/1554321/-Trump-thinks-US-military-should-communicate-via-courier-no-seriously http://www.dailykos.com/story/2016/7/29/1554321/-Trump-think...
  - gnarbarian 10y ago
    One time pad.
coldtea 10y ago
>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. If they have succeeded wouldn't the very best thing for them to do is to appear "keen on controlling encryption"?

leereeves 10y ago

Decades of research don't prove that there's no solution. It took mathematicians 357 years to prove Fermat's Last Theorem.

_asummers 10y ago
And that required about 357 years of mathematics to be able to prove it, as well. With the recentish GI announcement, I'm hopeful factoring and discrete log will fall within the next decade or two, but it's likely going to involve a bunch of subtle perspective shifts on several different fronts combined with new machinery in math to show.
- kazinator 10y ago
  3 x 7 x 17 = 357 years, by the way.
  - Retra 10y ago
    I see you're not a physicist...

feral 10y ago

>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. "assume with good confidence" - this is very naive. They're not going to advertise their super secret breakthrough by acting like they no longer care about encryption. Such a secret is going to be compartmentalized in the organization etc.

thesimpsons1022 10y ago
from all the Snowden leaks it seems pretty apparent they couldn't break encryption... but it's been a while since then so who knows now
nickpsecurity 10y ago
Fortunately, those slides leaked. The lower levels talked about cryptanalysis and supercomputers. The TS/SCI/ECI stuff said they were backdooring crypto at the company level using FBI locally and CIA/ISA foreign. Also note their own Type 1 systems allow these ciphers with most sensitive stuff and EKMS using a variation of Photorus called Firefly. Safe bet that good implementations of the stuff still work.
- feral 10y ago
  That's a lot of detail, which I'm not familiar with as a causal observer, but its irrelevant. The slides show the capabilities of one layer of the onion, but its surely naive to assume that's everything? A total mathematical factoring break is a holy grail. I mean, they made a hollywood movie about this! In the 90s! Sneakers: "There isn't a government on this planet that wouldn't kill us all for that thing." Obviously, that's a movie, not real life, but the sentiment is valid.
  - nickpsecurity 10y ago
    It's possible. Yet, someone has to be able to use that stuff. The Sentry Eagle leaks showed that, as I predicted, they developed most of this stuff in Special Access Programs that compartmentalize things away from even TS clearance. Then, as capabilities are developed, people with TS/SCI clearances are briefed on one or more based on their need to know. Some are so high up they get briefed on all of them. That was Sentry Eagle: https://leaksource.info/2014/10/17/sentry-eagle-nsa-core-secrets-re-covert-activities-inside-companies-access-sensitive-data-compromise-networks-subvert-encryption/ https://leaksource.info/2014/10/17/sentry-eagle-nsa-core-sec... As you can see, the descriptions represent their most guarded secrets that can do the gravest damage. There could be an extra layer that basically has that one fact in it. I doubt it given how many different angles of attack & severity these docs cover. We also saw that predicted damage adding up after the releases of such leaks. It's more believable given it's the exact kinds of things I'd expect a post-9/11 agency to be doing if they couldn't break RSA, etc. They'd do it anyway for deniability but these are so secret they'd rather let targets go to preserve them. The secrecy level was already tight enough to cover preserving RSA so long as insiders on highest levels kept quiet. Last part they didn't play so well. ;)

fizx 10y ago

> As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed It would be quite the bluff though.

munificent 10y ago

> As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. After the Enigma was cracked, the government was terrified that the Axis would find out. If they knew they were cracked, they could change the cipher and set back the Allies significantly. So they spent a ton of effort obscuring their own intelligence. Whenever a decoded Enigma message told them where a U-boat would be, they sent a "spotter" boat whose job is was to be seen seeing the U-boat before it was attacked. That way there was a plausible source of information for the U-boat's location. (These spotters were so "effective", the Germans suspected there must be many more of them in the area then there actually were.) One time they weren't able to get a spotter there in time and Churchill himself made the call to attack anyway. To cover for that and avoid arousing suspicion, they sent a radio dispatch to a fake spy thanking him for the intel, so that the message could be intercepted by the Germans. I wouldn't be so confident if I were you.

monkmartinez 10y ago
That is just so fascinating... do you know where I could read more about this sort of thing. I don't care about time frames. Vietnam, I suspect, may have some interesting crypto treasures... edit: spelling
- harry8 10y ago
  cryptonomicon by Neal Stehpens is a fiction but has a lot of this kind of thing in it. Not sure how accurate. Code book by Simon Singh. "The Man Who Never Was" is a boot I have never read but should because it's great ww2 espionage story. I'm sure others will kick in some suggestions.
- Terribledactyl 10y ago
  If you want fiction, https://en.m.wikipedia.org/wiki/Cryptonomicon https://en.m.wikipedia.org/wiki/Cryptonomicon is a lot of fun.
- ecesena 10y ago
  I like Simon Singh a lot. I've used his The Code Book to teach basic crypto at high school.

tptacek 10y ago

No! It does not at all follow from NSA/USG's policy interests that NSA doesn't have secret factoring improvements. As the last few years of crypto research have shown, there's a big difference between having a break and being able to operationalize the break. It's plausible that NSA could have something that is tractable against an individual target, but not against massed targets. In fact: if they have a secret factoring improvement, this is the most likely shape of the problem for them.

Utanith 10y ago

>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. I think the real issue with relating their position on legislation to their ability to break any given algorithm (Or the problem on which it is based) is this: Legislation will survive a new, more secure algorithm. Breaking one algorithm is subject to being patched out or the algorithm being entirely replaced. A broken system is a short-term investment, legislation is long-term (With the assumption that the government enforcing the legislation sticks around).

mindslight 10y ago

You're conflating the NSA with the rest of the government, namely the FBI. I believe some spokesperson from the NSA has even gone on record lately against the FBI's desires to criminalize [applied math]. The NSA is an organization that tackles the world as it is. Compromised standards, TAOed equipment, global passive adversary, exploiting OPSEC fails. Even if the highest compartments of the NSA were able to instantly factor any RSA key, these alternative methods would still be useful for plausible deniability as well as general use by less-privileged compartments. The FBI is lucky to receive any of the NSA's scraps (and if they did, it would be some vague tip to start looking in the right place), hence being left to push for criminalization to facilitate their actual investigations.

davidwihl 10y ago

In 1996 I asked Robert Morris Sr if he was worried that so much crypto was dependent upon factorization. "Worried? I'm not worried, but I can tell you that if US Military lives are at stake, we don't use algorithms that depend on factorization." From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago.

DashRattlesnake 10y ago
> From that I would infer and speculate that the NSA found a pragmatic solution to factorization long ago. Or they judge that a pragmatic solution is within the realm of possibility, and they don't want take the chance of being caught with their pants down. They probably have the resources to take on many extra operational costs to avoid theoretical risks. One of the quotes on his Wikipedia pages is: "Never underestimate the attention, risk, money and time that an opponent will put into reading traffic."
mkagenius 10y ago
Because Robert Morris Sr said something hypothetical doesn't mean one should speculate.
oconnor0 10y ago
What are the other options?
- dnautics 10y ago
  Elliptic curve
- daxfohl 10y ago
  Couriers, duh: http://www.dailykos.com/story/2016/7/29/1554321/-Trump-thinks-US-military-should-communicate-via-courier-no-seriously http://www.dailykos.com/story/2016/7/29/1554321/-Trump-think...
- gnarbarian 10y ago
  One time pad.

coldtea 10y ago

>As they are still so keen on controlling encryption we can assume with good confidence that so far they have failed. If they have succeeded wouldn't the very best thing for them to do is to appear "keen on controlling encryption"?