8 ms·

I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collap

I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...

somat 4y ago
One of the neater bits of world building/subplots in the book "A fire upon the deep" is their ship is a freighter with a cargo full of one time pad keys. that is, the encryption you would revert to in a world where factorization is easy.
omoikane 4y ago
"Summer Wars"[1] features breaking keys as a plot element, with a passing mention of Shor's Algorithm. The rest of the movie is mostly unrelated to math. Good movie though. [1] https://en.wikipedia.org/wiki/Summer_Wars https://en.wikipedia.org/wiki/Summer_Wars
jsmith99 4y ago
Symmetric encryption should still be unbreakable even against quantum computers or any advances in prime numbers. Given we currently trust CAs they could switch to something like Kerberos.
gambiting 4y ago
In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetched.
- tptacek 4y ago
  There's any number of less subtle and more important problems with this idea, but another problem you have here is that one-time pads only provide confidentiality, not integrity.
- codethief 4y ago
  > we just switch to the one time pad encryption "just". So how do you do the key exchange?
  - grogenaut 4y ago
    Email it obviously
  - gambiting 4y ago
    Depends on the security of the service you want to use - I'd expect my bank or my email provider to send me my encryption keys by a recorded letter. Hacker news can probably email me their key instead. Again, we're talking about some "world ending" scenario that OP mentioned - where all "normal" forms of encryption are already broken. If OTP is the only unbreakable encryption around, them I'm sure we'd find a way to distribute keys.
- gleenn 4y ago
  Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
  - nelgaard 4y ago
    The distribution part have gotten a lot easier. I would be very possible for banks to give all their customers USB devices with a few GByte of one time pads and keep a copy of those same GBytes in their own systems. And most banks still have brick-and-mortar stores where customers could come and identify themselves and collect their one time pad. And a GByte of keypads would cover your banking need for a long time. The problem is more that it works for some one-to-many relationsships such as banks, but not many-to-many relationships, such as emails, websites, etc. There have to be second or third parties. On the hand, a lot of people seems to log in everywhere with Google Sign In or similar anyway. And we could instead all have Google or Amazon devices with GBytes of one time pads. And that could be used to set up symmetric encryption, which should be more resistant to quantum computer attacks. The only drawback is that we would have to trust the third party and everyone who could compromise the third party and every government that could put pressure on the third party :-)
alberth 4y ago
Agreed. But how would the movie end?
- orthecreedence 4y ago
  Cloudflare and Meta team up to invent a proprietary crypto algorithm that fixes everything but routes all traffic through their servers, centralizing the internet completely. All speech is controlled and monitored by this new entity, which receives a national security letter thereby merging it with the US government for all intents and purposes, but, like, you know, for our safety. Nobody notices or cares what has happened, and critics are met with "well it dOesN'T mATteR because they aren't using the information for anything bad."
  - quickthrower2 4y ago
    How did Google not get a look in? But makes me think how would that work? Physical key swaps?
idiotsecant 4y ago
This is now my new favorite apocalypse.
BillSaysThis 4y ago
They have, usually this is called a skeleton key. NCIS has done at least two separate episodes with it as the MacGuffin.
claytongulick 4y ago
All that would need to happen for this exact scenario to occur would be for anyone, anywhere to find a case where P == NP. [1] P !== NP is a theory that has never been proven, so it very well could happen in reality. This is one of those things that keeps me awake, like Carrington events [2]. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem [2] https://en.wikipedia.org/wiki/Carrington_Event https://en.wikipedia.org/wiki/Carrington_Event
- janalsncm 4y ago
  The Carrington event page was fascinating to read. Telegraph operators held an entire conversation without power! It is fairly unsettling though. I wonder if there are contingency plans that include thoroughly shielded or non-electronic communications equipment.
- gjsman-1000 4y ago
  Some have speculated though that P doesn't necessarily have to be a short period of time. If P == NP, but P takes hundreds of years to compute, we may survive.
- rrjjww 4y ago
  As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem? To rephrase if this is not the case - what value does solving P = NP provide?
  - goodgoblin 4y ago
    It's been a little while - but I think it's because NP problems can be converted into each other, so if you can solve one of them in P you can solve all of them in P.
  - bodhiandphysics 4y ago
    Think about cryptography for a second…. In cryptography you need a problem that if you know the key is fast to decode but if you don’t is really slow… like you would have to search all the possibilities one by one. Such problems are (basically…) called NP. P are all the algorithms that are fast on computers. If P = NP than any problem you could use for cryptography could be decoded fast
flippy_flops 4y ago
Can a quantum computer fit in an answering machine? :) https://www.youtube.com/watch?v=F5bAa6gFvLs https://www.youtube.com/watch?v=F5bAa6gFvLs
barathr 4y ago
It's called Impagliazzo's Worlds Paper: https://scholar.google.com/scholar?cluster=14678868687868063791&hl=en&as_sdt=0,5 https://scholar.google.com/scholar?cluster=14678868687868063... A classic paper that explores what happens if various scenarios come to pass. Would be worth exploring some of the updated versions and fictionalizing them.
b112 4y ago
And people wonder why I don't upgrade my 1996-1998 webpages to https. In the end, as the world burns, I will helpfully explain how I was right.
bfung 4y ago
I’d be interested to speculate how cryptocoins would fair also, not that it isn’t already a sh1t show XD
filleokus 4y ago
Not exactly that but: https://suricrasia.online/unfiction/basilisk/ https://suricrasia.online/unfiction/basilisk/
- timerol 4y ago
  It took me a surprisingly long time to realize that I was reading fiction. The example SHA sums even do work, it's just that they only start with 40 bits set to 0 (expect to require 10^12 operations to generate each randomly - about a second on an ANTMiner) instead of 88 0 bits (multiple weeks of the full Bitcoin network to generate each randomly)
myself248 4y ago
Isn't that basically implied by the ending of Sneakers (1992)? It would be fun fodder for a sequel, but I feel like it'd come across as histrionic disaster-porn.
aburan28 4y ago
Sneakers is the thriller movie you’re looking for
- riffraff 4y ago
  And it's a great movie!
- pyuser583 4y ago
  Or The Net.
- jwilk 4y ago
  This one? https://www.imdb.com/title/tt0105435/ https://www.imdb.com/title/tt0105435/

somat 4y ago

One of the neater bits of world building/subplots in the book "A fire upon the deep" is their ship is a freighter with a cargo full of one time pad keys. that is, the encryption you would revert to in a world where factorization is easy.

omoikane 4y ago

"Summer Wars"[1] features breaking keys as a plot element, with a passing mention of Shor's Algorithm. The rest of the movie is mostly unrelated to math. Good movie though. [1] https://en.wikipedia.org/wiki/Summer_Wars https://en.wikipedia.org/wiki/Summer_Wars

jsmith99 4y ago

Symmetric encryption should still be unbreakable even against quantum computers or any advances in prime numbers. Given we currently trust CAs they could switch to something like Kerberos.

gambiting 4y ago

In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetched.

tptacek 4y ago
There's any number of less subtle and more important problems with this idea, but another problem you have here is that one-time pads only provide confidentiality, not integrity.
codethief 4y ago
> we just switch to the one time pad encryption "just". So how do you do the key exchange?
- grogenaut 4y ago
  Email it obviously
- gambiting 4y ago
  Depends on the security of the service you want to use - I'd expect my bank or my email provider to send me my encryption keys by a recorded letter. Hacker news can probably email me their key instead. Again, we're talking about some "world ending" scenario that OP mentioned - where all "normal" forms of encryption are already broken. If OTP is the only unbreakable encryption around, them I'm sure we'd find a way to distribute keys.
gleenn 4y ago
Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
- nelgaard 4y ago
  The distribution part have gotten a lot easier. I would be very possible for banks to give all their customers USB devices with a few GByte of one time pads and keep a copy of those same GBytes in their own systems. And most banks still have brick-and-mortar stores where customers could come and identify themselves and collect their one time pad. And a GByte of keypads would cover your banking need for a long time. The problem is more that it works for some one-to-many relationsships such as banks, but not many-to-many relationships, such as emails, websites, etc. There have to be second or third parties. On the hand, a lot of people seems to log in everywhere with Google Sign In or similar anyway. And we could instead all have Google or Amazon devices with GBytes of one time pads. And that could be used to set up symmetric encryption, which should be more resistant to quantum computer attacks. The only drawback is that we would have to trust the third party and everyone who could compromise the third party and every government that could put pressure on the third party :-)

alberth 4y ago

Agreed. But how would the movie end?

orthecreedence 4y ago
Cloudflare and Meta team up to invent a proprietary crypto algorithm that fixes everything but routes all traffic through their servers, centralizing the internet completely. All speech is controlled and monitored by this new entity, which receives a national security letter thereby merging it with the US government for all intents and purposes, but, like, you know, for our safety. Nobody notices or cares what has happened, and critics are met with "well it dOesN'T mATteR because they aren't using the information for anything bad."
- quickthrower2 4y ago
  How did Google not get a look in? But makes me think how would that work? Physical key swaps?

idiotsecant 4y ago

This is now my new favorite apocalypse.

BillSaysThis 4y ago

They have, usually this is called a skeleton key. NCIS has done at least two separate episodes with it as the MacGuffin.

claytongulick 4y ago

All that would need to happen for this exact scenario to occur would be for anyone, anywhere to find a case where P == NP. [1] P !== NP is a theory that has never been proven, so it very well could happen in reality. This is one of those things that keeps me awake, like Carrington events [2]. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem [2] https://en.wikipedia.org/wiki/Carrington_Event https://en.wikipedia.org/wiki/Carrington_Event

janalsncm 4y ago
The Carrington event page was fascinating to read. Telegraph operators held an entire conversation without power! It is fairly unsettling though. I wonder if there are contingency plans that include thoroughly shielded or non-electronic communications equipment.
gjsman-1000 4y ago
Some have speculated though that P doesn't necessarily have to be a short period of time. If P == NP, but P takes hundreds of years to compute, we may survive.
rrjjww 4y ago
As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem? To rephrase if this is not the case - what value does solving P = NP provide?
- goodgoblin 4y ago
  It's been a little while - but I think it's because NP problems can be converted into each other, so if you can solve one of them in P you can solve all of them in P.
- bodhiandphysics 4y ago
  Think about cryptography for a second…. In cryptography you need a problem that if you know the key is fast to decode but if you don’t is really slow… like you would have to search all the possibilities one by one. Such problems are (basically…) called NP. P are all the algorithms that are fast on computers. If P = NP than any problem you could use for cryptography could be decoded fast

flippy_flops 4y ago

Can a quantum computer fit in an answering machine? :) https://www.youtube.com/watch?v=F5bAa6gFvLs https://www.youtube.com/watch?v=F5bAa6gFvLs

barathr 4y ago

It's called Impagliazzo's Worlds Paper: https://scholar.google.com/scholar?cluster=14678868687868063791&hl=en&as_sdt=0,5 https://scholar.google.com/scholar?cluster=14678868687868063... A classic paper that explores what happens if various scenarios come to pass. Would be worth exploring some of the updated versions and fictionalizing them.

b112 4y ago

And people wonder why I don't upgrade my 1996-1998 webpages to https. In the end, as the world burns, I will helpfully explain how I was right.

bfung 4y ago

I’d be interested to speculate how cryptocoins would fair also, not that it isn’t already a sh1t show XD

filleokus 4y ago

Not exactly that but: https://suricrasia.online/unfiction/basilisk/ https://suricrasia.online/unfiction/basilisk/

timerol 4y ago
It took me a surprisingly long time to realize that I was reading fiction. The example SHA sums even do work, it's just that they only start with 40 bits set to 0 (expect to require 10^12 operations to generate each randomly - about a second on an ANTMiner) instead of 88 0 bits (multiple weeks of the full Bitcoin network to generate each randomly)

myself248 4y ago

Isn't that basically implied by the ending of Sneakers (1992)? It would be fun fodder for a sequel, but I feel like it'd come across as histrionic disaster-porn.

aburan28 4y ago

Sneakers is the thriller movie you’re looking for

riffraff 4y ago
And it's a great movie!
pyuser583 4y ago
Or The Net.
jwilk 4y ago
This one? https://www.imdb.com/title/tt0105435/ https://www.imdb.com/title/tt0105435/