Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Breaking RSA with a quantum computer?

schneier.com

Post reply on HN
Print view View original

151–160 of 161 posts

Re: Breaking RSA with a quantum computer?

#151

Post by jsmith99 »

gjsman-1000 wrote: post #5

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...

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.

Re: Breaking RSA with a quantum computer?

#152

Post by simne »

pelasaco wrote: post #146

I remember that some small countries, running DPI in their up-link were just storing their whole encrypted traffic to - when this day comes - be able to decrypt the traffic and see who was conspiring against the government back in the days and then start the witch hunt. Maybe this day is coming. Maybe its already there for some degree.

In Russia few decades lobbied initiative, to store all country traffic for some amount of time, for law enforcement agencies. As I know, now this reborn-ed to store just connection initiation data (tcp syn from tcpdump, gsm call originate/receiver numbers, datetime stamp and duration).

In Ukraine, I hear inside, one law enforcement agency asked big provider ~ in 2000 to gather all emails. Co-owner said, "ok, you will got it". Than he few weeks gather old hdds from everywhere, and once sent to this agency small truck with few hundreds hdds, filled with data.

After that, at least 10 years, nothing similar asked.

Re: Breaking RSA with a quantum computer?

#153

Post by pelasaco »

simne wrote: post #152
pelasaco wrote: post #146

I remember that some small countries, running DPI in their up-link were just storing their whole encrypted traffic to - when this day comes - be able to decrypt the traffic and see who was conspiring against the government back in the days and then start the witch hunt. Maybe this day is coming. Maybe its already there for some degree.

In Russia few decades lobbied initiative, to store all country traffic for some amount of time, for law enforcement agencies. As I know, now this reborn-ed to store just connection initiation data (tcp syn from tcpdump, gsm call originate/receiver numbers, datetime stamp and duration). In Ukraine, I hear inside, one law enforcement agency asked big provider ~ in 2000 to gather all emails. Co-owner said, "ok, you will…

there were/are countries in africa with small uplink, pretty easy to store everything in flows, pcaps and then extract encrypted attachments offline, run different tools and techniques to identify adversaries (that in that region, are mostly seem as deadly enemies)

Re: Breaking RSA with a quantum computer?

#154

Post by idiotsecant »

jksmith wrote: post #32
idiotsecant wrote: post #19

Earlier quoted context omitted.

It's worth noting that BTC could be quantum-resistant if enough of the network decided they wanted it to be. Unfortunately the BTC community is famously resistant to change so it wouldn't happen until it's too late, but in a rational world the problem could be fixed.

Tangentially to secant, BTC community resistance is in the spirit of maintaining a solid base layer that is not perpetually in startup mode given stakeholder motives. Use other coins for that purpose. Regarding changes that still maintain or even enhance this goal of long-lived store of value, I bet they'd be fine with that, even if the work effort of BTC transactions increased.

> Tangentially to secant

I see what you did there. And I approve.

Re: Breaking RSA with a quantum computer?

#155

Post by greggarious »

retrocryptid wrote: post #113
quotemstr wrote: post #104

Earlier quoted context omitted.

Decrypt decades of pre-PFS archived encrypted internet traffic.

If only someone archived it in a data center in the desert.

>> Decrypt decades of pre-PFS archived encrypted internet traffic.

> If only someone archived it in a data center in the desert.

Uh oh

https://en.wikipedia.org/wiki/Utah_Data_Center

Good think I declared moral bankruptcy this year, all that is the old me :-)

Re: Breaking RSA with a quantum computer?

#157

Post by simne »

pelasaco wrote: post #153
simne wrote: post #152

Earlier quoted context omitted.

In Russia few decades lobbied initiative, to store all country traffic for some amount of time, for law enforcement agencies. As I know, now this reborn-ed to store just connection initiation data (tcp syn from tcpdump, gsm call originate/receiver numbers, datetime stamp and duration). In Ukraine, I hear inside, one law enforcement agency asked big provider ~ in 2000 to gather all emails. Co-owner said, "ok, you will…

there were/are countries in africa with small uplink, pretty easy to store everything in flows, pcaps and then extract encrypted attachments offline, run different tools and techniques to identify adversaries (that in that region, are mostly seem as deadly enemies)

Yes, and Africa is not alone.

Colleague said, he considered to build internet in Uzbekistan, even visited country. What he see, they have all very unfriendly or extremely conservative (Afghanistan) countries around, so he cannot just buy external internet channel.

Internet there extremely slow, most time near impossible to use, only email working (but could delay for few hours).

To send tweet or whatsapp, start app, push "send" and lay phone/tablet alone turned on, and in few hours will see "message delivered".

Re: Breaking RSA with a quantum computer?

#158

Post by kmeisthax »

Grimburger wrote: post #74
kmeisthax wrote: post #20

Earlier quoted context omitted.

Alright. Who gets to confiscate the pre-quantum keyed Bitcoin? Miners or codebreakers?

SHA2 is not under threat from post-quantum computing. Only the signatures used.

Yes, but the signatures are what's keeping your funds secure, not the hash.

To explain why, we need to talk about a type of nonstandard transaction people used to do as a sort of puzzle: hash-only outputs. This is a Bitcoin transaction whose outputs can only be spent by someone who knows the input that gives a particular SHA-256 output. Cute, right?

Problem is, this is a proof of knowledge, not a proof of identity. Anyone else can replicate it once the problem is solved and the solution does not restrict itself to whoever is identified as the first solver. Which means that the only thing that keeps people from claiming THEY were the first to solve it is the Sybil-resistance that keeps the blockchain from being reorg'd.

In Ethereum we call this the "dark forest" problem[0] - anything in the mempool that is not cryptographically locked down can and will be manipulated to the benefit of others. Smart contracts make it way more lucrative to scan the mempool for manipulable transactions, because instead of looking for the one guy solving old SHA-256 puzzles you now have potentially millions of arbitrage opportunities to find. But this isn't limited to Ethereum. It's whoever mines[1] the block wins.

So if quantum computing breaks RSA, that turns all existing coins into SHA-256 puzzles on a blockchain whose users haven't internalized the maximal extent of transaction malleability. The only way to avoid having your coins stolen would be to coordinate with trustworthy miners to include your signature transition transaction into a block - almost certainly with a very large fee, effectively a cooperative confiscation[2]. Those who rely on the kindness of strangers (read: the mempool) will find quantum computer owners and miners fighting to see who can steal their coins first. And the only protocol-level change to fix this would be to just invalidate all RSA signatures and treat all old wallets as burned.

[0] https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest

[1] The Ethereum term for this is Miner Extractable Value, which reportedly has even incentivized miners to reorg blocks (i.e. a short-term 51% attack) if and when they can get away with it.

[2] This is, again, another thing Ethereum's ecosystem already thought of; they call it Flashbots.

Re: Breaking RSA with a quantum computer?

#160

Post by quickthrower2 »

orthecreedence wrote: post #48
alberth wrote: post #7

Earlier quoted context omitted.

Agreed. But how would the movie end?

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 ha…

How did Google not get a look in? But makes me think how would that work? Physical key swaps?
Post reply on HN