27 ms·

Quantum Resistance and the Signal Protocol

292 points by dm 3y ago

awestroke 3y ago
Super cool. If current quantum computers were scaled up to more qubits, could they break modern crypto? Or would we need both more qubits and a new quantum computer architecture?
- rjmunro 3y ago
  15 was factorised on a 7 qbit computer by IBM, so yes, they could break RSA if scaled up. I'm not sure about elliptic curve. That was over 20 years ago: https://research.ibm.com/blog/factor-15-shors-algorithm https://research.ibm.com/blog/factor-15-shors-algorithm I wonder how possible it is that IBM could have already gone further and are already cracking modern crypto in secret, e.g. funded by the NSA. Is that a crazy conspiracy idea, or actually a possibility?
  - bob1029 3y ago
    > Is that a crazy conspiracy idea, or actually a possibility? I am investing in IBM under the assumption that this is an actual possibility. Their public QC roadmap actually looks like a realistic journey now. I strongly believe that the NSA, et. al. currently have access to a very powerful quantum computer - likely constructed by IBM under contract. The game theory around this is such that it is impossible for me to accept that there are zero secret quantum computers in existence by now. There is too much to lose by not playing that game as hard as you can.
    - eigenket 3y ago
      Speaking as a researcher in quantum computing (albiet completely on the theory side, with no practical knowledge of experiments). It seems that actually making a quantum computer which is useful (i.e. has error rate below the threshold you need for error correction to work) is incredibly difficult. I wouldn't be surprised if various secret agencies (specifically in the USA and China) have tried, but I would be quite surprised if they had succeded. (I deleted my previous edit because I had misread part of what you wrote.)
    - abdullahkhalids 3y ago
      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 orders of magnitude more difficult than say the Manhattan project. The latter put together the best of the best on the project. You are suggesting a scenario where a tiny fraction of the best of the best are secreted away, with many of their past collaborators unaware of their doings, and have successfully built a QC. While the many brilliant best of the best who are working publicly, with many billions of dollars of research funding are currently only making very slow progress. It simply does not square.
      - contact9879 3y ago
        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.
        paradox460 3y ago
        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
  - 0xDEF 3y ago
    It would be interesting to guesstimate what the NSA might be doing by analyzing the skills they're looking for in their job postings and the kind of open source projects they have released. For example their Accumulo OSS suggests they're capturing and storing a lot of data to analyze later. The Ghidra OSS being a best in class reverse engineering tool also suggests that alot of their work revolves around finding zero day vulnerabilities.
  - zie 3y ago
    I bet at the very least, the US govt and other large govts have some way of knowing whatever is actually possible TODAY and have plans in place to make sure whenever it is practical, they get the very first useful ones built. I would guess they probably don't have any actually useful and in production right now, but they probably have a few secreted away in development, so they will be ready to put them to use if/when they do become useful.
  - kevvok 3y ago
    Algorithms using elliptic curves can also be broken using Shor’s algorithm
- archgoon 3y ago
  > If current quantum computers were scaled up to more qubits That depends on what you mean by "scaled up". There is a concept of "Quantum Volume" that exists, which basically means the depth of the longest qubit circuit you can pull off. https://en.wikipedia.org/wiki/Quantum_volume https://en.wikipedia.org/wiki/Quantum_volume 'Simply' (it's never simple ;) ) adding qubits to a machine does not necessarily increase its Quantum Volume. Decreasing the noise typically will. However, there is a threshold at which point you can scale up mostly indefinitely. This is what the whole Quantum Error Correction is all about. https://en.wikipedia.org/wiki/Quantum_error_correction https://en.wikipedia.org/wiki/Quantum_error_correction There is a paper https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 That goes into a clear discussion of how to build a quantum computer and the associated thresholds that would allow you to do so. There is a minimum number of qubits needed (that work perfectly), but the paper analyzes how many qubits you'd need under realistic assumptions about how many noisy qubits you'd need to get error correcting qubits at the needed reliability.
  - eigenket 3y ago
    For anyone looking for a "headline figure" from the linked arxiv manuscript, their estimate for breaking 2048 bit RSA is around the order of magnitude of a billion qubits.
    - archgoon 3y ago
      [dead]
Boogie_Man 3y ago
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?
- candiddevmike 3y ago
  Maybe we need a statue of limitations for encrypted data to help with future proofing/make the collection useless in a court of law? If you go to lengths to encrypt your data, there should be some current and future expectation of privacy around it, even if someone can decrypt it.
  - Boogie_Man 3y ago
    To my understanding, despite variance from state to state, a general "rule of thumb" for the statute of limitations outside of "the big R" and "the big M" is ten years. This squares with the generic declassification timetable. I can't think of anything I'm genuinely upset about from more than a decade ago. I feel that I am an almost completely different person than I was a decade ago. If I found out someone robbed a bank ten years ago I'd be more inclined to think "That's wild, how did that go?" than I am "Oh no this guy is going to rob me".
- lxgr 3y ago
  > 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.
s17n 3y ago
Given that Signal's main innovation (compared to traditional end to end encryption) was to safeguard its users against future compromises via the ratchet protocol, this actually seems like a logical move for them to make.
miles_matthias 3y ago
Appreciate how well-written and approachable this post was!
swamp40 3y ago
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.
- sneak 3y ago
  It's worth way more than $20B USD to have a working quantum computer that nobody knows about. You don't burn a weapon like that by inducing everyone to update immediately.
- rosywoozlechan 3y ago
  This is a myopic take, the attacker could not spend the bitcoins because of the public ledger and the value of bitcoin would drop to nothing once it is realized that wallets are not secure. They'd burn bitcoin for no gain, for a loss even, because they would reveal their capabilities and maybe even who they are.
- xur17 3y ago
  My understanding is that bitcoin addresses are quantum safe as long as you do not reuse an address after spending funds sent to it [0]. Per the linked article, this is standard practice, so I would assume the majority of addresses are actually quantum safe. And for more context: with p2pkh addresses, you are sending to the hash of the address, and hashes are quantum safe. [0] https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/qu...
- keurrr 3y ago
  I don't think these incentives make sense at all. Government organizations suspected to be developing quantum computers probably have larger annual budgets than 20 billion. The ability to undermine virtually all cryptographic systems is unquantifiably large. Once the cat is out of the bag, everyone will rush to post-quantum cryptography and all that value will be lost in a relatively short period. Indeed, we already witnessed this in the 2010s following the Snowden revelations when big tech, in a concerted effort, adopted HTTPS. Now that is the standard. For example, "The Fiscal Year 2022 budget appropriation included $65.7 billion for the National Intelligence Program, and $24.1 billion for the Military Intelligence Program." Source: https://irp.fas.org/budget/index.html https://irp.fas.org/budget/index.html
JanisErdmanis 3y ago
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's similar to how FM radio works: there's a main frequency and several sidebands. When you adjust the tuner to pick up a station, you're essentially "interacting" with the corresponding station. But if there are too many stations, you may no longer be able to hear the music, and as a result, there would be only a static noise present. This leads me to a somewhat cynical conspiracy. Imagine the moment when a curios government agency realises that building a quantum computer for this purpose is a futile endeavor. Instead of admitting this, they could perpetuate the idea that its construction is just around the corner. Then, act as a wolf in sheep’s skin and introduce everyone to quantum-resistant solutions, which are unfortunate to have secret hidden backdoors by having done more advanced research on them. Has anyone thought about this?
- woodruffw 3y ago
  To a first approximation, the US government uses the same cryptography that US consumers do -- AES, SHA-2, the NIST P curves, ECDSA, etc. are all categorized for various levels of data integrity and confidentiality within the government. The same will be true of PQ signing schemes, meaning that a backdoor would be predicated on the USG believing that they have some truly remarkable NOBUS breakthrough in PQC. That feels unlikely to me; NSA interventions in cryptographic design have historically gone in the opposite direction[1]. (This is separate from the actual design question. I don't know as much about stateless PQ signing schemes, but the stateful ones are mostly "boring" hash-based cryptography that's well understood to be strong in both settings.) [1]: https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's_involvement_in_the_design https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's...
  - simcop2387 3y ago
    > NSA interventions in cryptographic design have historically gone in the opposite direction[1]. I'm not sure I'd say that given that there are some other designs and things that have gone on[1][2]. Particularly the Dual EC debacle. They have a history of helping make suspect or down right compromised crypto if they think they can get away with it. That said it does look like they avoid doing it to anything that gets USA GOV approval for use internally but it's difficult to say to what level they would actually go to for getting a backdoor out into the world that would let them look at other secrets. [1] https://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States#PC_era https://en.wikipedia.org/wiki/Export_of_cryptography_from_th... [2] https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG
tjrgergw 3y ago
Now explain why you had to add bitcoin to signal.
- contact9879 3y ago
  There is no Bitcoin in Signal. Much has been written about MobileCoin that you can find on other threads.
sigmar 3y ago
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), but I'm curious why they couldn't fit the crystals-kyber method for mutual auth in this hybridized implementation? performance concerns?
- lxgr 3y ago
  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-What-is-a-safety-number-and-why-do-I-see-that-it-changed- https://support.signal.org/hc/en-us/articles/360007060632-Wh... [2] https://signal.org/docs/specifications/pqxdh/#active-quantum-adversaries https://signal.org/docs/specifications/pqxdh/#active-quantum... [3] https://signal.org/docs/specifications/x3dh/ https://signal.org/docs/specifications/x3dh/ [4] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf
blurbleblurble 3y ago
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/ https://www.inkandswitch.com/backchannel/ For the key exchange itself ("PAKE") maybe something like this: https://journal-home.s3.ap-northeast-2.amazonaws.com/site/icisc2021/presentation/paper_42.pdf https://journal-home.s3.ap-northeast-2.amazonaws.com/site/ic... And for the symmetric encryption: https://github.com/Steppenwolfe65/eAES https://github.com/Steppenwolfe65/eAES
- lxgr 3y ago
  > 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?
  - deleted 3y ago
    [deleted]
  - blurbleblurble 3y ago
    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 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.
sdeframond 3y ago
I am a bit puzzled: governments and big corp are pouring indecent amounts of money in developing quantum computers, which main application, afaict, is to break cryptography. ...and this is defeated by changing our algorithms ? Whats the use in developing quantum computers then?
- contact9879 3y ago
  The use is all the other applications of quantum computers that aren't breaking cryptosystems
- jmprspret 3y ago
  three letter agencies have been collecting and harvesting encrypted communications for decades in the event that they can break the algorithms later (in this case that would mean quantum computers)
wolverine876 3y ago
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 classical abacus, our Quabacus operates on Quabeads! Rather than positions 0 or 1, quabeads can be in both positions at once!' Beads that are simultaneously in both positions sounds like a f$@!#g annoying glitch and not a feature - how does that help anyone record or calculate numbers? ('Would someone take a look a this broken Quabacus-abacus and resolve these g#$%!m glitching quabeads?!!!') It mocks the non-technical reader, who assumes they must have been given enough information to understand why it's faster and possibly how it works, but can't figure it out. They have not been given enough. Does anyone who perhaps understands it better than I do want to take a stab at a new commonplace explanation, one that connects the dots between quantum superposition and performance (for certain calculations)?
- varjag 3y ago
  There isn't really a great way of explaining quantum behavior using everyday (classical) terms. Any analogy you come up with will be deeply flawed yet unsatisfactory opaque to the reader. The only way is to gear up on math to the level where you can if not reason within the theory then to at least make sense of its presented conclusions.
- sebzim4500 3y ago
  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.
  - wolverine876 3y ago
    It summarizes quantum mechanics, but not how it helps to store numbers and perform certain kinds of calculations.
- ericjmorey 3y ago
jmprspret 3y ago
Very well written and digestable. I have much respect for the Signal people. However I'd like to mention using usernames instead of phone numbers has been met with the classic "soon™" response for years now. When will they actually do it? This the the only thing I really really dislike about Signal - their lack of communication on oddly specific things. Like them holding back the codebase for months on GitHub so as to not spoil the.. Surprise! MobileCoin!
- palata 3y ago
  As much as I hate cryptocurrencies and the MobileCoin effort (that should never have been part of Signal IMO), I think that "playing with MobileCoin" was low-risk as a side project (that never took off as far as I know?). However, moving from phone numbers to username seems very tricky to me. - They have built their system around the idea that they can use the address book that already exists in users phones and not learn about it. It works (at least in theory), it's just that some people don't trust them for that. Or some people have a threat model that is incompatible with that, I suppose. Changing their whole system for a very small minority of very vocal users is a risk. Also if going for usernames makes them collect more metadata, then other users will complain (or maybe even the same that currently complain about the phone numbers). - Most people use WhatsApp, of which Signal is an improvement in terms of privacy. Those people don't give a damn about sharing the phone number, so the reason why they don't move to Signal is surely not this (because Signal certainly doesn't do worse with the phone number). So changing that would be a risk. Moving to usernames is a cost, and a risk. All for a few very vocal users who probably have a threat model that requires it. I would understand if they never moved to username, and I would be fine with it.
Aachen 3y ago
About time! People picked this up soon after it was committed to the repository back in May, and the beta version of Signal has had dual keys aka "safety numbers" for a while now (maybe 1.5 months?). Happy to see they decided releasing a blog post about it after all :) Pick your platform: https://mobile.twitter.com/Th3Zer0/status/1661078047196364815 https://mobile.twitter.com/Th3Zer0/status/166107804719636481... https://ch.linkedin.com/posts/dr-angie-qarry-397538127_add-kyber-kem-and-implement-pqxdh-protocol-activity-7067943827482771456-5Qf7 https://ch.linkedin.com/posts/dr-angie-qarry-397538127_add-k... https://chaos.social/@luc/111048883207848400 https://chaos.social/@luc/111048883207848400 (disclosure: the latter is myself; there was another Mastodon post I'm pretty sure, but when I search for PQXDH there it only shows my own post) The blog doesn't mention it, but based on a code comment, it seems that ~two months from now the new key fingerprints will become mandatory for peers to remain trusted after you update your client From the blog post: > We want to extend our sincerest thanks and appreciation to all the people who contributed to the development of this protocol upgrade. This includes the cryptographic research community, the Kyber team, and the following people who directly contributed to our whitepaper All that behind closed doors, apparently. There was scarcely a mention of PQXDH to be found on the web besides the Signal source code and the handful of people that picked up on it on social media. A github ticket about adding post-quantum support was responded to with "we have no announcements to make" and then closed due to inactivity. I suppose one only needs so many cooks, but why not have this whitepaper, the ideas going into the protocol design, the timeline, whatever goes into this security decision for an open source app visible, even if only read-only? Feels more like source-available than open source spirited, but I guess that's in line with "the ecosystem is moving" (Moxie's talk where he says that they can do better without a community developing more clients, integrations, federation, etc.)
m3kw9 3y ago
Doing quantum resistant algorithm right now is straight up posturing and signaling
- ccooffee 3y ago
  If your threat model includes someone breaking your encrypted communications X years from now, quantum resistance can be important. Signal markets itself as for reporters and whistleblowers who may have state-level adversaries.
  - anigbrowl 3y ago
    If you're seriously worried about that you're already using disappearing messages, and the maximum retention period is 4 weeks. It's good that they're doing this but it also feels a little bit like hype, while very basic UI problems remain unfixed. For example, you can do backups or media exports from signal, but the user isn't given any control over where they are stored. If you want to dump them to an SD card in your phone, for example, you'll have to find them in your primary storage and then copy them manually to the SD card. Bizarrely, voice messages are dumped into a 'music' folder even though they're labeled as 'audio' within the Signal UI.
- kobalsky 3y ago
  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
Tutanota 3y ago
Congrats to Signal, this is a great step! At Tutanota we also use the Signal protocol to build post-quantum secure encryption for email and drive: https://tutanota.com/blog/pqdrive-project https://tutanota.com/blog/pqdrive-project Post-quantum secure encryption can't be developed early enough. In the end all our data today will be at risk of being decrypted in the future - unless we secure it now!
- fieldbob 3y ago
  ^^
- bawolff 3y ago
  That's not exactly the most compelling blog post. Way too many buzz words. Why would end-end cloud storage even be using public-key cryptography? You're sending the encrypted data to yourself forward in time.
  - Tutanota 3y ago
    Not for storing the data, no, but public-key cryptography is needed for sharing encrypted files.
fieldbob 3y ago
[flagged]
- rollulus 3y ago
  That’s something else than discussed here.
  - fieldbob 3y ago
    I tried to remove it but you comment blocked deletion I'm sorry I am still human please forgive me God bless you I love you

292 points by dm 3y ago

Super cool. If current quantum computers were scaled up to more qubits, could they break modern crypto? Or would we need both more qubits and a new quantum computer architecture?

rjmunro 3y ago
15 was factorised on a 7 qbit computer by IBM, so yes, they could break RSA if scaled up. I'm not sure about elliptic curve. That was over 20 years ago: https://research.ibm.com/blog/factor-15-shors-algorithm https://research.ibm.com/blog/factor-15-shors-algorithm I wonder how possible it is that IBM could have already gone further and are already cracking modern crypto in secret, e.g. funded by the NSA. Is that a crazy conspiracy idea, or actually a possibility?
- bob1029 3y ago
  > Is that a crazy conspiracy idea, or actually a possibility? I am investing in IBM under the assumption that this is an actual possibility. Their public QC roadmap actually looks like a realistic journey now. I strongly believe that the NSA, et. al. currently have access to a very powerful quantum computer - likely constructed by IBM under contract. The game theory around this is such that it is impossible for me to accept that there are zero secret quantum computers in existence by now. There is too much to lose by not playing that game as hard as you can.
  - eigenket 3y ago
    Speaking as a researcher in quantum computing (albiet completely on the theory side, with no practical knowledge of experiments). It seems that actually making a quantum computer which is useful (i.e. has error rate below the threshold you need for error correction to work) is incredibly difficult. I wouldn't be surprised if various secret agencies (specifically in the USA and China) have tried, but I would be quite surprised if they had succeded. (I deleted my previous edit because I had misread part of what you wrote.)
  - abdullahkhalids 3y ago
    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 orders of magnitude more difficult than say the Manhattan project. The latter put together the best of the best on the project. You are suggesting a scenario where a tiny fraction of the best of the best are secreted away, with many of their past collaborators unaware of their doings, and have successfully built a QC. While the many brilliant best of the best who are working publicly, with many billions of dollars of research funding are currently only making very slow progress. It simply does not square.
    - contact9879 3y ago
      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.
      - paradox460 3y ago
        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
- 0xDEF 3y ago
  It would be interesting to guesstimate what the NSA might be doing by analyzing the skills they're looking for in their job postings and the kind of open source projects they have released. For example their Accumulo OSS suggests they're capturing and storing a lot of data to analyze later. The Ghidra OSS being a best in class reverse engineering tool also suggests that alot of their work revolves around finding zero day vulnerabilities.
- zie 3y ago
  I bet at the very least, the US govt and other large govts have some way of knowing whatever is actually possible TODAY and have plans in place to make sure whenever it is practical, they get the very first useful ones built. I would guess they probably don't have any actually useful and in production right now, but they probably have a few secreted away in development, so they will be ready to put them to use if/when they do become useful.
- kevvok 3y ago
  Algorithms using elliptic curves can also be broken using Shor’s algorithm
archgoon 3y ago
> If current quantum computers were scaled up to more qubits That depends on what you mean by "scaled up". There is a concept of "Quantum Volume" that exists, which basically means the depth of the longest qubit circuit you can pull off. https://en.wikipedia.org/wiki/Quantum_volume https://en.wikipedia.org/wiki/Quantum_volume 'Simply' (it's never simple ;) ) adding qubits to a machine does not necessarily increase its Quantum Volume. Decreasing the noise typically will. However, there is a threshold at which point you can scale up mostly indefinitely. This is what the whole Quantum Error Correction is all about. https://en.wikipedia.org/wiki/Quantum_error_correction https://en.wikipedia.org/wiki/Quantum_error_correction There is a paper https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 That goes into a clear discussion of how to build a quantum computer and the associated thresholds that would allow you to do so. There is a minimum number of qubits needed (that work perfectly), but the paper analyzes how many qubits you'd need under realistic assumptions about how many noisy qubits you'd need to get error correcting qubits at the needed reliability.
- eigenket 3y ago
  For anyone looking for a "headline figure" from the linked arxiv manuscript, their estimate for breaking 2048 bit RSA is around the order of magnitude of a billion qubits.
  - archgoon 3y ago
    [dead]

Boogie_Man 3y ago

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?

candiddevmike 3y ago
Maybe we need a statue of limitations for encrypted data to help with future proofing/make the collection useless in a court of law? If you go to lengths to encrypt your data, there should be some current and future expectation of privacy around it, even if someone can decrypt it.
- Boogie_Man 3y ago
  To my understanding, despite variance from state to state, a general "rule of thumb" for the statute of limitations outside of "the big R" and "the big M" is ten years. This squares with the generic declassification timetable. I can't think of anything I'm genuinely upset about from more than a decade ago. I feel that I am an almost completely different person than I was a decade ago. If I found out someone robbed a bank ten years ago I'd be more inclined to think "That's wild, how did that go?" than I am "Oh no this guy is going to rob me".
lxgr 3y ago
> 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.

s17n 3y ago

Given that Signal's main innovation (compared to traditional end to end encryption) was to safeguard its users against future compromises via the ratchet protocol, this actually seems like a logical move for them to make.

miles_matthias 3y ago

Appreciate how well-written and approachable this post was!

swamp40 3y ago

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.

sneak 3y ago
It's worth way more than $20B USD to have a working quantum computer that nobody knows about. You don't burn a weapon like that by inducing everyone to update immediately.
rosywoozlechan 3y ago
This is a myopic take, the attacker could not spend the bitcoins because of the public ledger and the value of bitcoin would drop to nothing once it is realized that wallets are not secure. They'd burn bitcoin for no gain, for a loss even, because they would reveal their capabilities and maybe even who they are.
xur17 3y ago
My understanding is that bitcoin addresses are quantum safe as long as you do not reuse an address after spending funds sent to it [0]. Per the linked article, this is standard practice, so I would assume the majority of addresses are actually quantum safe. And for more context: with p2pkh addresses, you are sending to the hash of the address, and hashes are quantum safe. [0] https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/qu...
keurrr 3y ago
I don't think these incentives make sense at all. Government organizations suspected to be developing quantum computers probably have larger annual budgets than 20 billion. The ability to undermine virtually all cryptographic systems is unquantifiably large. Once the cat is out of the bag, everyone will rush to post-quantum cryptography and all that value will be lost in a relatively short period. Indeed, we already witnessed this in the 2010s following the Snowden revelations when big tech, in a concerted effort, adopted HTTPS. Now that is the standard. For example, "The Fiscal Year 2022 budget appropriation included $65.7 billion for the National Intelligence Program, and $24.1 billion for the Military Intelligence Program." Source: https://irp.fas.org/budget/index.html https://irp.fas.org/budget/index.html

JanisErdmanis 3y ago

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's similar to how FM radio works: there's a main frequency and several sidebands. When you adjust the tuner to pick up a station, you're essentially "interacting" with the corresponding station. But if there are too many stations, you may no longer be able to hear the music, and as a result, there would be only a static noise present. This leads me to a somewhat cynical conspiracy. Imagine the moment when a curios government agency realises that building a quantum computer for this purpose is a futile endeavor. Instead of admitting this, they could perpetuate the idea that its construction is just around the corner. Then, act as a wolf in sheep’s skin and introduce everyone to quantum-resistant solutions, which are unfortunate to have secret hidden backdoors by having done more advanced research on them. Has anyone thought about this?

woodruffw 3y ago
To a first approximation, the US government uses the same cryptography that US consumers do -- AES, SHA-2, the NIST P curves, ECDSA, etc. are all categorized for various levels of data integrity and confidentiality within the government. The same will be true of PQ signing schemes, meaning that a backdoor would be predicated on the USG believing that they have some truly remarkable NOBUS breakthrough in PQC. That feels unlikely to me; NSA interventions in cryptographic design have historically gone in the opposite direction[1]. (This is separate from the actual design question. I don't know as much about stateless PQ signing schemes, but the stateful ones are mostly "boring" hash-based cryptography that's well understood to be strong in both settings.) [1]: https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's_involvement_in_the_design https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's...
- simcop2387 3y ago
  > NSA interventions in cryptographic design have historically gone in the opposite direction[1]. I'm not sure I'd say that given that there are some other designs and things that have gone on[1][2]. Particularly the Dual EC debacle. They have a history of helping make suspect or down right compromised crypto if they think they can get away with it. That said it does look like they avoid doing it to anything that gets USA GOV approval for use internally but it's difficult to say to what level they would actually go to for getting a backdoor out into the world that would let them look at other secrets. [1] https://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States#PC_era https://en.wikipedia.org/wiki/Export_of_cryptography_from_th... [2] https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG

tjrgergw 3y ago

Now explain why you had to add bitcoin to signal.

contact9879 3y ago
There is no Bitcoin in Signal. Much has been written about MobileCoin that you can find on other threads.

sigmar 3y ago

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), but I'm curious why they couldn't fit the crystals-kyber method for mutual auth in this hybridized implementation? performance concerns?

lxgr 3y ago
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-What-is-a-safety-number-and-why-do-I-see-that-it-changed- https://support.signal.org/hc/en-us/articles/360007060632-Wh... [2] https://signal.org/docs/specifications/pqxdh/#active-quantum-adversaries https://signal.org/docs/specifications/pqxdh/#active-quantum... [3] https://signal.org/docs/specifications/x3dh/ https://signal.org/docs/specifications/x3dh/ [4] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf

blurbleblurble 3y ago

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/ https://www.inkandswitch.com/backchannel/ For the key exchange itself ("PAKE") maybe something like this: https://journal-home.s3.ap-northeast-2.amazonaws.com/site/icisc2021/presentation/paper_42.pdf https://journal-home.s3.ap-northeast-2.amazonaws.com/site/ic... And for the symmetric encryption: https://github.com/Steppenwolfe65/eAES https://github.com/Steppenwolfe65/eAES

lxgr 3y ago
> 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?
- deleted 3y ago
  [deleted]
- blurbleblurble 3y ago
  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 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.

sdeframond 3y ago

I am a bit puzzled: governments and big corp are pouring indecent amounts of money in developing quantum computers, which main application, afaict, is to break cryptography. ...and this is defeated by changing our algorithms ? Whats the use in developing quantum computers then?

contact9879 3y ago
The use is all the other applications of quantum computers that aren't breaking cryptosystems
jmprspret 3y ago
three letter agencies have been collecting and harvesting encrypted communications for decades in the event that they can break the algorithms later (in this case that would mean quantum computers)

wolverine876 3y ago

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 classical abacus, our Quabacus operates on Quabeads! Rather than positions 0 or 1, quabeads can be in both positions at once!' Beads that are simultaneously in both positions sounds like a f$@!#g annoying glitch and not a feature - how does that help anyone record or calculate numbers? ('Would someone take a look a this broken Quabacus-abacus and resolve these g#$%!m glitching quabeads?!!!') It mocks the non-technical reader, who assumes they must have been given enough information to understand why it's faster and possibly how it works, but can't figure it out. They have not been given enough. Does anyone who perhaps understands it better than I do want to take a stab at a new commonplace explanation, one that connects the dots between quantum superposition and performance (for certain calculations)?

varjag 3y ago
There isn't really a great way of explaining quantum behavior using everyday (classical) terms. Any analogy you come up with will be deeply flawed yet unsatisfactory opaque to the reader. The only way is to gear up on math to the level where you can if not reason within the theory then to at least make sense of its presented conclusions.
sebzim4500 3y ago
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.
- wolverine876 3y ago
  It summarizes quantum mechanics, but not how it helps to store numbers and perform certain kinds of calculations.
ericjmorey 3y ago

jmprspret 3y ago

Very well written and digestable. I have much respect for the Signal people. However I'd like to mention using usernames instead of phone numbers has been met with the classic "soon™" response for years now. When will they actually do it? This the the only thing I really really dislike about Signal - their lack of communication on oddly specific things. Like them holding back the codebase for months on GitHub so as to not spoil the.. Surprise! MobileCoin!

palata 3y ago
As much as I hate cryptocurrencies and the MobileCoin effort (that should never have been part of Signal IMO), I think that "playing with MobileCoin" was low-risk as a side project (that never took off as far as I know?). However, moving from phone numbers to username seems very tricky to me. - They have built their system around the idea that they can use the address book that already exists in users phones and not learn about it. It works (at least in theory), it's just that some people don't trust them for that. Or some people have a threat model that is incompatible with that, I suppose. Changing their whole system for a very small minority of very vocal users is a risk. Also if going for usernames makes them collect more metadata, then other users will complain (or maybe even the same that currently complain about the phone numbers). - Most people use WhatsApp, of which Signal is an improvement in terms of privacy. Those people don't give a damn about sharing the phone number, so the reason why they don't move to Signal is surely not this (because Signal certainly doesn't do worse with the phone number). So changing that would be a risk. Moving to usernames is a cost, and a risk. All for a few very vocal users who probably have a threat model that requires it. I would understand if they never moved to username, and I would be fine with it.

Aachen 3y ago

About time! People picked this up soon after it was committed to the repository back in May, and the beta version of Signal has had dual keys aka "safety numbers" for a while now (maybe 1.5 months?). Happy to see they decided releasing a blog post about it after all :) Pick your platform: https://mobile.twitter.com/Th3Zer0/status/1661078047196364815 https://mobile.twitter.com/Th3Zer0/status/166107804719636481... https://ch.linkedin.com/posts/dr-angie-qarry-397538127_add-kyber-kem-and-implement-pqxdh-protocol-activity-7067943827482771456-5Qf7 https://ch.linkedin.com/posts/dr-angie-qarry-397538127_add-k... https://chaos.social/@luc/111048883207848400 https://chaos.social/@luc/111048883207848400 (disclosure: the latter is myself; there was another Mastodon post I'm pretty sure, but when I search for PQXDH there it only shows my own post) The blog doesn't mention it, but based on a code comment, it seems that ~two months from now the new key fingerprints will become mandatory for peers to remain trusted after you update your client From the blog post: > We want to extend our sincerest thanks and appreciation to all the people who contributed to the development of this protocol upgrade. This includes the cryptographic research community, the Kyber team, and the following people who directly contributed to our whitepaper All that behind closed doors, apparently. There was scarcely a mention of PQXDH to be found on the web besides the Signal source code and the handful of people that picked up on it on social media. A github ticket about adding post-quantum support was responded to with "we have no announcements to make" and then closed due to inactivity. I suppose one only needs so many cooks, but why not have this whitepaper, the ideas going into the protocol design, the timeline, whatever goes into this security decision for an open source app visible, even if only read-only? Feels more like source-available than open source spirited, but I guess that's in line with "the ecosystem is moving" (Moxie's talk where he says that they can do better without a community developing more clients, integrations, federation, etc.)

m3kw9 3y ago

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

ccooffee 3y ago
If your threat model includes someone breaking your encrypted communications X years from now, quantum resistance can be important. Signal markets itself as for reporters and whistleblowers who may have state-level adversaries.
- anigbrowl 3y ago
  If you're seriously worried about that you're already using disappearing messages, and the maximum retention period is 4 weeks. It's good that they're doing this but it also feels a little bit like hype, while very basic UI problems remain unfixed. For example, you can do backups or media exports from signal, but the user isn't given any control over where they are stored. If you want to dump them to an SD card in your phone, for example, you'll have to find them in your primary storage and then copy them manually to the SD card. Bizarrely, voice messages are dumped into a 'music' folder even though they're labeled as 'audio' within the Signal UI.
kobalsky 3y ago
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

Tutanota 3y ago

Congrats to Signal, this is a great step! At Tutanota we also use the Signal protocol to build post-quantum secure encryption for email and drive: https://tutanota.com/blog/pqdrive-project https://tutanota.com/blog/pqdrive-project Post-quantum secure encryption can't be developed early enough. In the end all our data today will be at risk of being decrypted in the future - unless we secure it now!

fieldbob 3y ago
^^
bawolff 3y ago
That's not exactly the most compelling blog post. Way too many buzz words. Why would end-end cloud storage even be using public-key cryptography? You're sending the encrypted data to yourself forward in time.
- Tutanota 3y ago
  Not for storing the data, no, but public-key cryptography is needed for sharing encrypted files.

fieldbob 3y ago

[flagged]

rollulus 3y ago
That’s something else than discussed here.
- fieldbob 3y ago
  I tried to remove it but you comment blocked deletion I'm sorry I am still human please forgive me God bless you I love you