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

81–90 of 161 posts

Re: Breaking RSA with a quantum computer?

#81

Post by g_p »

dekhn wrote: post #60
b112 wrote: post #45

Earlier quoted context omitted.

I remeber in the very early 2000s, a guy had a stopwatch sized whos-it, and it kept flashing numbers on it. Updated every 5 minutes. Apparently, some cesium based list of numbers, again, was 20 years ago. Point is, it was a one time pad...

You mean this? https://en.wikipedia.org/wiki/RSA_SecurID I'm not sure but I don't think this is OTP?

Indeed, they're not one-time pads - they are symmetric authenticators where both sides hold the same seed, and iterate a PRNG or similarly iterable function every N units of time (say, 30 seconds), to give you the same new output, based on the same starting seed. Think stream cipher output, with an initialisation vector.

They are often called OTPs though (i.e. one-time passcodes), just to cause confusion.

Re: Breaking RSA with a quantum computer?

#82

Post by Strilanc »

advisedwang wrote: post #8

Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.

Another use case where you should be seriously considering using post-quantum techniques is update verification. If a piece of hardware needs to work 10 years from now, and it uses RSA or ECC public key crypto to verify proposed software updates, it may live long enough to see quantum computers break that.

Re: Breaking RSA with a quantum computer?

#83

Post by gleenn »

gambiting wrote: post #66
itcrowd wrote: post #65

Earlier quoted context omitted.

(not sure if replying to troll..) The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?

Well no, that's not true - a bank could issue you with a one-time-pad long enough to encrypt the next 10000 messages with you, and use that over the years - they just need to tell you which line of the key is needed to decrypt your message. In that scenario you only need to guarantee security for the first time the key is distributed(for example a file sent to you when the account is opened).

So now people have to keep a piece of paper around or somehow put it into some software and not lose access. You're right, it would work. In reality, people can't even be bothered to use a password manager or understand even the most simple of new security software, let alone even remember their password. That makes it completely intractable as a solution.

Re: Breaking RSA with a quantum computer?

#84

Post by goodgoblin »

rrjjww wrote: post #25
claytongulick wrote: post #17

Earlier quoted context omitted.

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 [2] https://en.wikipedia.org/wiki/Carrington_Event

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?

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.

Re: Breaking RSA with a quantum computer?

#85

Post by g_p »

gjsman-1000 wrote: post #12
advisedwang wrote: post #8

Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.

Post-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers. If you want to be safe, you might almost consider standard cryptography on one of…

My understanding is that Bitcoin, used correctly, is effectively quantum safe.

Since the "recipient" address of a UTXO is expressed as a hash, a user does not broadcast their public key until after they spend the funds. If you follow good practice, you make a single transaction, sending funds to the recipient, and the "change" to yourself, in a new wallet address (addressed by the hash of its public key). This means the public key is never visible to an attacker until its balance is zero.

Therefore, to attack this and steal funds through false transactions, you effectively need both a pre-image attack on SHA256 (so you have a valid public key to match the UTXO address), and a way to solve the discrete logarithm problem, breaking ECDSA (on the Secp256k1 curve), so you can sign using the private key corresponding to that public key.

SHA256 would come under Grover's algorithm, I believe, which would give you 128 bits of security under a quantum attack. That is still pretty good going.

Re: Breaking RSA with a quantum computer?

#86

Post by TacticalCoder »

jokoon wrote: post #51

so just increase to 4096 or 8192 bits or beyond?

Why is this downvoted? Ain't it exponentially harder to break RSA using qubits each time you double the key length?

Until we switch to quantum resistant algorithms, we can keep doubling the key length for some time no?

8192 bits should still be acceptable speed wise (if we consider that 2048 bits is broken, then I'll take slower operations over broken keys any day of the week).

Re: Breaking RSA with a quantum computer?

#87

Post by miga »

Strilanc wrote: post #61

I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work.…

It is fair to say, that in security assessment you estimate lower bound on complexity of hacking.

Schor proved upper bound.

Re: Breaking RSA with a quantum computer?

#88

Post by g_p »

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.

And as long as you don't re-use wallet addresses, your public key is effectively not revealed until the balance is zero.

Since your wallet address is a sha256 hash of the public key, you would need to meaningfully break sha256 to be able to go after a public key or generate a false signature.

Once the public key is broadcast to spend the funds, that wallet shouldn't be reused, and a new wallet address should receive the change.

Re: Breaking RSA with a quantum computer?

#90

Post by gambiting »

gleenn wrote: post #83
gambiting wrote: post #66

Earlier quoted context omitted.

Well no, that's not true - a bank could issue you with a one-time-pad long enough to encrypt the next 10000 messages with you, and use that over the years - they just need to tell you which line of the key is needed to decrypt your message. In that scenario you only need to guarantee security for the first time the key is distributed(for example a file sent to you when the account is opened).

So now people have to keep a piece of paper around or somehow put it into some software and not lose access. You're right, it would work. In reality, people can't even be bothered to use a password manager or understand even the most simple of new security software, let alone even remember their password. That makes it completely intractable as a solution.

I mean, the scenario being discussed here is some kind of "world ending" situation where all known encryption is broken. So you either do it the way I described it, or you don't have any encryption whatsoever. I think under those conditions people would adjust. It isn't an alternative to our current arrangements.

Also: my bank access is done entirely through an app that obscures its internal implementation. It could already be using OTP and it wouldn't make any difference to me, nor would I be able to tell(my point is that the user wouldn't need to keep a piece of paper that they would need to type in anywhere - the internal implementation of tools we use every day would change, but most users wouldn't even notice)

Post reply on HN