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

Quantum Resistance and the Signal Protocol

signal.org

Post reply on HN
Print view View original

61–70 of 135 posts

Re: Quantum Resistance and the Signal Protocol

#61

Post by wolverine876 »

sebzim4500 wrote: post #55
wolverine876 wrote: post #50

That is very well-written, as someone else pointed out, though this common explanation for laypeople needs work (I'm not blaming Signal's blogger, who wrote it more carefully than most): "Instead of bits as in a classical computer, quantum computers operate on qubits. Rather than 0 or 1, qubits can exist in a superposition of states, in some sense allowing them to be both values at once." 'Instead of beads as in a cl…

I don't really understand your objection, that description seems like about as well as you can do when trying to summarize quantum mechanics in one sentence.

It summarizes quantum mechanics, but not how it helps to store numbers and perform certain kinds of calculations.

Re: Quantum Resistance and the Signal Protocol

#62

Post by api »

comboy wrote: post #42
JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

> I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. Seems weird to be assuming what's possible based on current technical obstruction. If you trace CPUs development, or many other technologies, many people with deep technical knowledge were c…

I tend to take "it's impossible" statements from scientists seriously only when the reasoning can be firmly tied to an extremely well established physical law with no "wiggle room."

For example I accept that faster than light travel and inertialess propulsion are both impossible. If either of these things were shown to be possible, it would mean that there are huge errors or oversights in the most well established areas of physics.

I also accept the conditional impossibility of things that are just provably beyond our current ability for fundamental reasons, like a Dyson sphere. I don't know of any physics that says you could not build one, but for us it'd be like dust mites building the international space station.

For everything else I leave the door open. People have historically underestimated creativity.

For the first types of things, taking preparatory steps would be irrational. We don't need to plan for the arrival of FTL travel because we have no reason to think it will ever arrive.

For the latter types of things, preparing does make some sense as long as it's not unreasonably expensive. We do have reason to believe that a large quantum computer might be possible, so mucking around with a bit of code to defend our security against a surprise seems rational.

Re: Quantum Resistance and the Signal Protocol

#63

Post by nullc »

hannob wrote: post #24
JanisErdmanis wrote: post #18

It is good that they kept the classical crypto along. However, the general tendency towards quantum-resistant cryptography leaves me puzzled. From my perspective as a physics PhD graduate, I firmly believe that a quantum computer capable of breaking public key crypto will never be built. This is because as you add more qubits, there's increased interference between them due to the additional connections required. It'…

I've heard physicists raise opinions like yours (i.e. QC will never be built for practical reasons), but I also hear ones that say the opposite. I'd err on the side of caution. As for your conspiracy: The conclusion of that would be to continue using hybrid constructions. Though, and I know crypto more than physics, I'd consider it as highly unlikely. Creating backdoors that others won't find is next to impossible. W…

It's perhaps telling that NSA has been rather aggressively against the use of hybrid systems, even though they have almost no marginal cost (an extra 56 bytes on top of 1.2kb of PQ exchange) and are the obvious move esp while the PQ systems are very new.

Re: Quantum Resistance and the Signal Protocol

#64

Post by nullc »

nabla9 wrote: post #31
swamp40 wrote: post #14

There are 20 bitcoin wallets worth more than a billion dollars each. I think it will be pretty obvious when someone gets a quantum computer working.

Bitcoin is already quantum attack resistant, unless you use un-hashed public keys or reuse Bitcoin addresses (as some do). If Bitcoin would become vulnerable, its value would collapse to zero overnight once it's known. There is limited amount of money anyone could extract before the value collapses.

> Bitcoin is already quantum attack resistant

That is a misleading claim. First: Any quantum key cracker would need to be fast since the operations would all have to be performed within the coherence time, so an attacker could race coins as they were spent or perform small reorgs to steal coins even if they lost the initial race. Secondly: The majority of all circulating coins are stored in addresses which have been reused. Thirdly: the common hashing scheme you mention is 160 bits, so in the presence of quantum computers would only have 80 bits of security against second preimages just by using grover's algorithim and perhaps worse with more specialization (and, in fact, somewhat less considering multi target attacks) which wouldn't and shouldn't be regarded as secure.

> If Bitcoin would become vulnerable, its value would collapse to zero overnight once it's known. There is limited amount of money anyone could extract before the value collapses.

Once its known. There have been insecure altcoins where hackers skimmed them for many months without being noticed. It is indeed technically finite, sure, but large.

Re: Quantum Resistance and the Signal Protocol

#65

Post by lxgr »

blurbleblurble wrote: post #48

Why not use something like backchannel? That way we wouldn't need phone numbers either... The initial shared private key exchange could be done with more expensive, quantum resistant cryptography but the actual communication could be done through symmetric encryption. https://www.inkandswitch.com/backchannel/ For the key exchange itself ("PAKE") maybe something like this: https://journal-home.s3.ap-northeast-2.amazon…

> The initial shared private key exchange could be done with more expensive, quantum resistant cryptography but the actual communication could be done through symmetric encryption.

That's exactly how Signal's symmetric ratcheting works (with the addition of an asymmetric ratcheting step to limit the forward impact of a key compromise on either side, which you can't do symmetrically).

> For the key exchange itself ("PAKE")

A PAKE requires a short shared secret. That does not usually exist in Signal's scenario.

> And for the symmetric encryption: [...]

Why that over regular AES?

Re: Quantum Resistance and the Signal Protocol

#66

Post by lxgr »

nullc wrote: post #64
nabla9 wrote: post #31

Earlier quoted context omitted.

Bitcoin is already quantum attack resistant, unless you use un-hashed public keys or reuse Bitcoin addresses (as some do). If Bitcoin would become vulnerable, its value would collapse to zero overnight once it's known. There is limited amount of money anyone could extract before the value collapses.

> Bitcoin is already quantum attack resistant That is a misleading claim. First: Any quantum key cracker would need to be fast since the operations would all have to be performed within the coherence time, so an attacker could race coins as they were spent or perform small reorgs to steal coins even if they lost the initial race. Secondly: The majority of all circulating coins are stored in addresses which have been…

> The majority of all circulating coins are stored in addresses which have been reused.

Interesting, do you have any statistics on that? But I guess with large exchange wallets, it makes sense.

> only have 80 bits of security against second preimages just by using grover's algorithim

True, but 80 bits are anything but trivial to brute-force using classical computers! I'm not that familiar with quantum complexity, but as I understand it, you'd still need 2^80 quantum operations to brute-force a 160 bit hash.

Re: Quantum Resistance and the Signal Protocol

#67

Post by lxgr »

Boogie_Man wrote: post #5

Actively resisting future attackers and hardware is an incredibly forward-thinking thing to do, bravo. How long into the future is an achievable and desirable duration for encryption (barring any rapid, unforeseen paradigm shift)? If ten years is acceptable for declassification of standard documents in the US, is this a reasonable target for day to day signal chats?

> How long into the future is an achievable and desirable duration for encryption (barring any rapid, unforeseen paradigm shift)?

I don't think "years of expected security" (as used to be popular for e.g. RSA key lengths for some time) is a meaningful metric anymore:

AES-256 and elliptic curve encryption are resistant against classical attackers until beyond the heat death of the universe, so their "time of security" is, for practical purposes, infinite.

I'd expect that, for quantum-safe asymmetric algorithms as well as for AES, there is a similar number corresponding to fundamental pyhsical infeasibility, and then we can also just pick that rather than any low or high number of years.

Re: Quantum Resistance and the Signal Protocol

#68

Post by lxgr »

sigmar wrote: post #37

Whitepaper says: >PQXDH provides post-quantum forward secrecy and a form of cryptographic deniability but still relies on the hardness of the discrete log problem for mutual authentication in this revision of the protocol. So that's why active mitm with a contemporary quantum computer is a concern mentioned in the blog post. Of course it isn't of any concern currently (since no one has the hardware to exploit this),…

That's likely simply because they don't want to switch fingerprint formats again just yet. (They are currently in the process of upgrading the format for a non-cryptographic reason [1].)

Signal fingerprints, which users can manually verify in person or over a trusted channel, are just hashes over the public keys of both users involved – and if these keys change (e.g. due to a quantum upgrade), the format would need to change as well.

Update: Seems like that's actually due to a fundamental restriction of the quantum-safe primitives used and is addressed in the technical specification [2]:

> The post-quantum KEM and signature schemes being standardized by NIST [...] do not provide a mechanism for post-quantum deniable mutual authentication [...]

Seems like Signal's neat trick of using Diffie-Hellman in a three-way manner [3] doesn't work here, since the primitive used (FIPS 203, [4]) is only a key encapsulation method, and FIPS 204 only offers "regular" post-quantum signatures of the non-deniable kind.

Signal highly values deniability, and in this version they seem to have prioritized that in favor of quantum-safe mutual authentication.

[1] https://support.signal.org/hc/en-us/articles/360007060632-Wh...

[2] https://signal.org/docs/specifications/pqxdh/#active-quantum...

[3] https://signal.org/docs/specifications/x3dh/

[4] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf

Re: Quantum Resistance and the Signal Protocol

#69

Post by paradox460 »

contact9879 wrote: post #52
abdullahkhalids wrote: post #12

Earlier quoted context omitted.

You are probably mistaken. The number of people with the right expertise to build QCs is very limited - only a few hundred people with world class PhDs in quantum computing are produced every year across the world. A small fraction are truly innovative - the ones who can act as leaders to build something real. The challenge of building QCs - as evidenced by billions of dollars worth of research in them - is many orde…

Reminds me of how everyone who knew anything about the physics academia scene in the 30s/40s knew what was going on at Los Alamos. Second-order effects are extremely hard to obscure.

The secrecy around Los Alamos was less what they were doing and more how they were getting it done and how far along they were

Re: Quantum Resistance and the Signal Protocol

#70

Post by krastanov »

andyferris wrote: post #59
krastanov wrote: post #23

Earlier quoted context omitted.

Doesn't your argument apply to classical bits too? The more interconnected a classical bit is, the more parasitic coupling it will experience. That used to be an argument used against the feasibility of classical computers in the 40s (until von Neumann published work on fault tolerant classical computing). Both classical and quantum computers (1) can not "scale" without error correction because of analog noise (altho…

To add to the sibling comment, the reason our classical computers work is because the individual transistor errors in your CPU are basically zero. We do use “error correction” on storage (and do see bit errors creep into data stored on disk and in RAM over time) but not “fault tolerance” on the compute. In fact there is no such thing as fault-tolerant classical compute - the CPU only works if it “perfect” or “near pe…

With the benefit of hindsight, it is easy to agree with what you say. But from the point of view of the scientists creating the first classical computers, classical fault-tolerance seemed just as difficult to them as quantum fault-tolerant computation seems to us. See von Neumann's "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" from 1952 https://static.ias.edu/pitp/archive/2012files/Probabilistic_...

Not that it is impossible for OP to be right, but the argument he is using used to be applied to classical computation and ultimately turned out to be wrong in that context.

Post reply on HN