4 ms·

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

by isolli 6y ago

hannob 6y ago
Yes and kinda yes. There's a standardization process going on for post quantum cryptography at the US NIST. Results expected before the almighty RSA-breaking quantum computer arrives. There's still a concern about store-and-encrypt-later (i.e. someone can store encrypted communication today and decrypt it once a QC is available), and how relevant that is depends on some unknowns (how many years to you expect your comms to be secret? how many years till a usable QC is available?).
- KMag 6y ago
  Note, for instance, that Google ran an experiment where Chrome connecting to Google hosts used both conventional elliptic curve Diffie-Hellman over Curve25519 and post-quantum "New Hope" RLWE. A hash of the results of the two key agreements was used for ChaCha20 encryption of the keystream. A store-and-decrypt attack in this case should be required to break both conventional Curve25519 and experimental New Hope. Note that the best known quantum attacks on ChaCha20 cut the key size in half, so 256-bit ChaCha20 should still be fine, as long as your key agreement protocol is quantum-resistant.
BelenusMordred 6y ago
> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real threat, there's no theoretical issues with symmetric crypto, hashing or MAC's. A quantum break already has a multi-billion dollar bounty on it in the form of cryptocurrency wallets which would be hard to fight against in the form of wages or violent coercion. This is probably the best evidence on Earth that no one actually has this capability.
- isolli 6y ago
  Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)
  - lallysingh 6y ago
    I think they're saying that we know nobody's using quantum computing to break crypto yet, because nobody's been draining bitcoin wallets.
    - BelenusMordred 6y ago
      Pretty much, it's not just bitcoin either, basically every cryptocurrency wallet is based on elliptical curve cryptography and any that have been used publicly are vulnerable to anyone on Earth having enough coherent qubits at their disposal to crunch the numbers in order to steal it.
    - Gene_Parmesan 6y ago
      Maybe, but if a state actor has achieved this ability, I doubt they would make its existence public knowledge by stealing a few billion US$ in btc. That's chump change compared to the value of being able to surreptitiously crack the cryptographically secure messages of everybody in the world. Note I'm not saying that I actually think someone has achieved this, I just don't think "no one is stealing btc" is a good non-existence test.
  - gfody 6y ago
    blockchain ledgers are open and public and you could think of the contents of any wallet as a bounty for cracking that wallet's private key. some of the wallets involved in early bitcoin transactions would make perfect targets - they havent moved in years and are presumed lost. the btc in them is worth billions.
  - benlivengood 6y ago
    The bitcoin ledger is a bit of a special case. Coins in a transaction are sent to output addresses identified by a signature which is usually a combination of SHA-256 and RIPEMD-160 hashes of a public key signature. Using coins as an input to a transaction (spending them) requires exposing the public ECDSA key used to originally create the signature. If a particular address has never sent coins then an attacker has to perform a pre-image attack against SHA-256 and RIPEMD-160 which even for quantum computers would be 2^128 operations (generally believed to be intractable) and wouldn't even require breaking ECDSA. Since most original coins have never been sent anywhere there isn't a way to directly attack their ECDSA keypairs. There are, however, plenty of addresses holding (a lot of) coins whose public keys are in the blockchain, making them targets for quantum computing attacks. An attacker could solve the discrete logarithm problem for a key and forge a signature in a transaction sending all the coins owned by the matching signature to a new address owned by the attacker and the transaction would be accepted by everyone.

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

by isolli 6y ago

Side question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?

hannob 6y ago

Yes and kinda yes. There's a standardization process going on for post quantum cryptography at the US NIST. Results expected before the almighty RSA-breaking quantum computer arrives. There's still a concern about store-and-encrypt-later (i.e. someone can store encrypted communication today and decrypt it once a QC is available), and how relevant that is depends on some unknowns (how many years to you expect your comms to be secret? how many years till a usable QC is available?).

KMag 6y ago
Note, for instance, that Google ran an experiment where Chrome connecting to Google hosts used both conventional elliptic curve Diffie-Hellman over Curve25519 and post-quantum "New Hope" RLWE. A hash of the results of the two key agreements was used for ChaCha20 encryption of the keystream. A store-and-decrypt attack in this case should be required to break both conventional Curve25519 and experimental New Hope. Note that the best known quantum attacks on ChaCha20 cut the key size in half, so 256-bit ChaCha20 should still be fine, as long as your key agreement protocol is quantum-resistant.

BelenusMordred 6y ago

> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real threat, there's no theoretical issues with symmetric crypto, hashing or MAC's. A quantum break already has a multi-billion dollar bounty on it in the form of cryptocurrency wallets which would be hard to fight against in the form of wages or violent coercion. This is probably the best evidence on Earth that no one actually has this capability.

isolli 6y ago
Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)
- lallysingh 6y ago
  I think they're saying that we know nobody's using quantum computing to break crypto yet, because nobody's been draining bitcoin wallets.
  - BelenusMordred 6y ago
    Pretty much, it's not just bitcoin either, basically every cryptocurrency wallet is based on elliptical curve cryptography and any that have been used publicly are vulnerable to anyone on Earth having enough coherent qubits at their disposal to crunch the numbers in order to steal it.
  - Gene_Parmesan 6y ago
    Maybe, but if a state actor has achieved this ability, I doubt they would make its existence public knowledge by stealing a few billion US$ in btc. That's chump change compared to the value of being able to surreptitiously crack the cryptographically secure messages of everybody in the world. Note I'm not saying that I actually think someone has achieved this, I just don't think "no one is stealing btc" is a good non-existence test.
- gfody 6y ago
  blockchain ledgers are open and public and you could think of the contents of any wallet as a bounty for cracking that wallet's private key. some of the wallets involved in early bitcoin transactions would make perfect targets - they havent moved in years and are presumed lost. the btc in them is worth billions.
- benlivengood 6y ago
  The bitcoin ledger is a bit of a special case. Coins in a transaction are sent to output addresses identified by a signature which is usually a combination of SHA-256 and RIPEMD-160 hashes of a public key signature. Using coins as an input to a transaction (spending them) requires exposing the public ECDSA key used to originally create the signature. If a particular address has never sent coins then an attacker has to perform a pre-image attack against SHA-256 and RIPEMD-160 which even for quantum computers would be 2^128 operations (generally believed to be intractable) and wouldn't even require breaking ECDSA. Since most original coins have never been sent anywhere there isn't a way to directly attack their ECDSA keypairs. There are, however, plenty of addresses holding (a lot of) coins whose public keys are in the blockchain, making them targets for quantum computing attacks. An attacker could solve the discrete logarithm problem for a key and forge a signature in a transaction sending all the coins owned by the matching signature to a new address owned by the attacker and the transaction would be accepted by everyone.