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

121–130 of 135 posts

Re: Quantum Resistance and the Signal Protocol

#121

Post by tptacek »

pyinstallwoes wrote: post #114
tptacek wrote: post #22

Earlier quoted context omitted.

CRYSTALS-Kyber was designed by an academic team, not a government (though a government standards body refereed the competition that selected it; that competition, in turn, was driven by technical feedback that came predominantly from academic cryptography teams around the world). In general, with some exceptions (like curve isogenies), the "math" behind PQ crypto is pretty well established; it was just less attractiv…

Yet if you followed the money those programs are funded by government adjacent entities that usually have 3 letters.

None of those researchers have been subverted by academic grants.

Re: Quantum Resistance and the Signal Protocol

#122

Post by MobiusHorizons »

krastanov wrote: post #44
blueplanet200 wrote: post #36

Earlier quoted context omitted.

It does not apply to classical bits in the same way. Quantum computers derive their computational power from the qubits being in a single quantum state across the qubits (an entangled one, to use physics jargon.) This is distinct from classical computers, where you can describe a bit without needing to describe the other bits in the computer. You cannot describe a qubit (in a way that's computationally useful, at lea…

But the exponential cost (the need to describe the "whole") is there in the classical case too. To describe a set of classical bits completely, you need a probability distribution over the whole system (including possible classical correlations induced by the crosstalk that OP spoke about). That probability distribution is a stochastic vector that has 2^n real positive components if we have n bits. To describe a set…

I may be misunderstanding your argument, but it seems like you are saying that modeling faults in a classical computer also needs to take into account the states of all bits in relation to one another, and that this somehow proves that the problem of crosstalk is similar to interference in quantum computers.

If I have understood your argument correctly I don’t think the conclusion follows from the premise because crosstalk is not fundamental to classical computing. By that I mean that for a given logical cpu design, crosstalk can be (and is) minimized through physical design characteristics (eg grounding, wire spacing etc) without reducing the size of computation. The same cannot afaik be said of quantum computers, where the interaction between qbits is essential to computation

Re: Quantum Resistance and the Signal Protocol

#123

Post by abdullahkhalids »

wolverine876 wrote: post #90
abdullahkhalids wrote: post #83

Earlier quoted context omitted.

You are correct. That is a horrible explanation. And incomplete. * The state of a qubit has two basis states. Arbitrary states are linear combinations (=superposition) of these basis states. Importantly, the coefficients in the linear combination can be positive or negative. * The state of N qubits has 2^N basis states. poly(N) gate can put the state of the N qubits in which each of the 2^N basis states has a non-zer…

Thanks. > In quantum algorithms, we play with the coefficients. Is it accurate to say, more simply (simplicity being a high priority here), that 'we play with the probabilities' of collapse to one basis state or to the other - thus skipping the need to explain linear combinations or coefficients?

Well, all the playing happens with the positive/negative coefficients. Without explaining that you can cancel them out with each other, it will not be clear how all-positive probabilities collapse to some basis states.

In fact, classical stochastic computational models have exactly this deficiency. You can't pump up probabilities of some unknown states. They can only tend towards a uniform mixture.

Everything is in the minus sign.

Re: Quantum Resistance and the Signal Protocol

#124

Post by krastanov »

MobiusHorizons wrote: post #122
krastanov wrote: post #44

Earlier quoted context omitted.

But the exponential cost (the need to describe the "whole") is there in the classical case too. To describe a set of classical bits completely, you need a probability distribution over the whole system (including possible classical correlations induced by the crosstalk that OP spoke about). That probability distribution is a stochastic vector that has 2^n real positive components if we have n bits. To describe a set…

I may be misunderstanding your argument, but it seems like you are saying that modeling faults in a classical computer also needs to take into account the states of all bits in relation to one another, and that this somehow proves that the problem of crosstalk is similar to interference in quantum computers. If I have understood your argument correctly I don’t think the conclusion follows from the premise because cro…

I do not think I follow your last two sentences. Both for bits and for qubits, two-bit gates are required (e.g. NAND for classical and CNOT for quantum). The bits/qubits need to interact for such a gate to happen and should be isolated from one another before/after the gate. And same as with bits and grounding and wire spacing, we use various decoupling techniques for qubits.

Of course, qubits are drastically more difficult, but the principle is the same.

Re: Quantum Resistance and the Signal Protocol

#125

Post by blurbleblurble »

lxgr wrote: post #65
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 ("P…

Interesting! Thanks for explaining this.

> Why that over regular AES?

Well, I don't understand the exact details but it seems mostly to do with possible vulnerability to brute forcing if certain pseudo-random number generators are used:

https://eprint.iacr.org/2019/1208

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

I'm not too familiar with the details of how Signal's initial key exchange works, other than that from a user experience point of view it relies on people having shared phone numbers in at least one direction. So in practice this is kind of similar to the sharing of a one time password. Basically the users already need some kind of a "trusted outside channel" to exchange phone numbers.

From that vantage requiring people to "pair" in a secure context, most likely in person, wouldn't be that much different in practice from the way people usually exchange global public identifiers now (social media handles, phone numbers, etc.) over existing trusted channels. And having a shared private key that you store in a kind of pet-name address book is already so conceptually similar to an address book, which I find kind of amazing.

The big difference being that you'd obviously want to keep this address book secret, whereas phones have made it incredibly easy and have normalized leaking your contacts to any app that requests it. In practice, preventing private key leaks would be a challenging part of building out something like backchannel. The shared secret petname address books would probably need to be application specific, used in a sandbox and encrypted at rest.

Maybe there could be some standard tools for securely using one application's channels to bootstrap connections on another, but ideally it should be very, very hard for the shared secrets to leak, but easy enough for users to manage and be aware of them.

Re: Quantum Resistance and the Signal Protocol

#126

Post by MobiusHorizons »

krastanov wrote: post #124
MobiusHorizons wrote: post #122

Earlier quoted context omitted.

I may be misunderstanding your argument, but it seems like you are saying that modeling faults in a classical computer also needs to take into account the states of all bits in relation to one another, and that this somehow proves that the problem of crosstalk is similar to interference in quantum computers. If I have understood your argument correctly I don’t think the conclusion follows from the premise because cro…

I do not think I follow your last two sentences. Both for bits and for qubits, two-bit gates are required (e.g. NAND for classical and CNOT for quantum). The bits/qubits need to interact for such a gate to happen and should be isolated from one another before/after the gate. And same as with bits and grounding and wire spacing, we use various decoupling techniques for qubits. Of course, qubits are drastically more di…

Good point, I said computation, but I was thinking more of the storage and routing pieces of that rather than the gates, likely because I don’t understand quantum gates very well. Most of the quantum ecc I have read about was in the storage lifetime and retrieval process.

Basically what I mean is that classical computing can split things up during storage or routing to reduce coupling, but quantum can’t do this because the qbits must stay entangled to be useful

Re: Quantum Resistance and the Signal Protocol

#127

Post by lxgr »

blurbleblurble wrote: post #125
lxgr wrote: post #65

Earlier quoted context omitted.

> 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 ("P…

Interesting! Thanks for explaining this. > Why that over regular AES? Well, I don't understand the exact details but it seems mostly to do with possible vulnerability to brute forcing if certain pseudo-random number generators are used: https://eprint.iacr.org/2019/1208 > A PAKE requires a short shared secret. That does not usually exist in Signal's scenario. I'm not too familiar with the details of how Signal's init…

> https://eprint.iacr.org/2019/1208

Ah, it's apparently a quantum-hardened variant of AES! But AES-256 is inherently quantum-hard and much better understood at this point. In other words, AES is really not the security bottleneck against quantum adversaries.

> I'm not too familiar with the details of how Signal's initial key exchange works, other than that from a user experience point of view it relies on people having shared phone numbers in at least one direction. So in practice this is kind of similar to the sharing of a one time password.

A user's phone number is public information; you can't use that as the password in a PAKE.

Signal has basically two ways of exchanging keys: Unauthenticated (in which case you trust Signal's service to really provide you your contact's keys, and not their own, which would allow them to MITM your chats), and "safety number comparison", for which you have to manually compare a short numerical string with each contact over a trusted channel (ideally in person). It's less convenient, but removes Signal's servers from the set of entities you need to trust.

Theoretically Signal could also offer a PAKE option to interactively authenticate a new contact remotely (if you do indeed have a shared password), but that's probably not easy to do in a way that's not prone to social engineering attacks, since you don't have a channel to communicate about what your password should be. (Remember that you don't trust the contact yet; an attacker could pick a password hint that they know the answer to as well!)

Re: Quantum Resistance and the Signal Protocol

#128

Post by krastanov »

MobiusHorizons wrote: post #126
krastanov wrote: post #124

Earlier quoted context omitted.

I do not think I follow your last two sentences. Both for bits and for qubits, two-bit gates are required (e.g. NAND for classical and CNOT for quantum). The bits/qubits need to interact for such a gate to happen and should be isolated from one another before/after the gate. And same as with bits and grounding and wire spacing, we use various decoupling techniques for qubits. Of course, qubits are drastically more di…

Good point, I said computation, but I was thinking more of the storage and routing pieces of that rather than the gates, likely because I don’t understand quantum gates very well. Most of the quantum ecc I have read about was in the storage lifetime and retrieval process. Basically what I mean is that classical computing can split things up during storage or routing to reduce coupling, but quantum can’t do this becau…

WiFi, 5G, PCIe, Ethernet, QR codes, and pretty much any other classical communication protocol uses error correcting codes where classical bits need to be sent in blocks, e.g. for PCIe6, blocks of 256 physical bytes are sent, but only 242 of information is transmitted because the rest is used to enforce some classical correlation for the purposes of error correction. We can not send smaller packets of data (unless we pad). There are probably many technical details I am oblivious to here on the classical side of things, but this "can not split things up" constraint does not seem unique to quantum correlations (entanglement).

And the way we mathematically express and model classical correlations in classical error correcting codes is virtually the same as the way to model quantum correlations (entanglement) in quantum error correcting codes.

All of this with the usual disclaimer: the quantum case is much more difficult, engineeringly speaking.

Re: Quantum Resistance and the Signal Protocol

#129

Post by kobalsky »

m3kw9 wrote: post #79

Doing quantum resistant algorithm right now is straight up posturing and signaling

if there are no important drawbacks, why not?

the tinfoil hatters have been proven again and again.

why not take the precautions we can to protect today’s data from being fed into some AI in a few years decades or whatever

Re: Quantum Resistance and the Signal Protocol

#130

Post by blurbleblurble »

lxgr wrote: post #127
blurbleblurble wrote: post #125

Earlier quoted context omitted.

Interesting! Thanks for explaining this. > Why that over regular AES? Well, I don't understand the exact details but it seems mostly to do with possible vulnerability to brute forcing if certain pseudo-random number generators are used: https://eprint.iacr.org/2019/1208 > A PAKE requires a short shared secret. That does not usually exist in Signal's scenario. I'm not too familiar with the details of how Signal's init…

> https://eprint.iacr.org/2019/1208 Ah, it's apparently a quantum-hardened variant of AES! But AES-256 is inherently quantum-hard and much better understood at this point. In other words, AES is really not the security bottleneck against quantum adversaries. > I'm not too familiar with the details of how Signal's initial key exchange works, other than that from a user experience point of view it relies on people havi…

> A user's phone number is public information; you can't use that as the password in a PAKE.

For sure, I just mean that people are already used to exchanging numbers, in person, to establish phone contact. So from a user experience point of view, exchanging a PAKE password for a shared secret isn't that much different from exchanging phone numbers. The resulting shared secret could be treated very much like a phone number, except it's like a secret phone number between you and that person.

> Theoretically Signal could also offer a PAKE option to interactively authenticate a new contact remotely (if you do indeed have a shared password), but that's probably not easy to do in a way that's not prone to social engineering attacks, since you don't have a channel to communicate about what your password should be. (Remember that you don't trust the contact yet; an attacker could pick a password hint that they know the answer to as well!)

This kind of thing makes the most sense to establish a secure connection with someone you already trust over an existing trusted channel. Much in the same way that you'd commonly get someone's phone number for the first time at a party, in person. (The physical environment of the party being the trusted channel.)

Assuming these generative fake voice/video models get to the point (over the next five years) where people cannot easily differentiate between a real and fake conversation over an arbitrary/untrusted digital channel, I'd assume that the most trusted channels for these kinds of exchanges will be IRL in person or established secure channels.

> A user's phone number is public information

One of the big arguments in the backchannel proposal is that global public identifiers are vulnerable to spam, fraud, impersonation, etc... and that maybe we don't actually need them as much as we assume? Maybe we can instead share per-contact shared secrets as a form of identity?

If you haven't watched it already, I highly recommend this talk about backchannel: https://www.youtube.com/watch?v=5ClLkuaoE-o

Post reply on HN