I can't believe that they named their protocol SPQR. It's the Latin abbreviation for Senatus Populusque Romanus. https://en.wikipedia.org/wiki/SPQR
Love it :)
Lol. You would only see this comment on Hacker News. Reminds me of an old comic I read on how mathematicians memorize their locker numbers. "1975? Oh that's easy. It's just the square root of 3,900,625!"
Ever since I've heard of the meme that "modern men can't spend 24 hours without thinking of the Roman Empire", I haven't been able to escape it, even on days where my only contact with the outside world is HN.
I guess it's like a curse, once you've heard about it you're doomed.
And for anyone finding out about it just now, alea jacta est
For this particular one, you could easily see that comment on any community with a sufficient number of Asterix fans. Banners and standards with "SPQR" written somewhere were common enough that they should produce a Pavlovian reaction.
I am struggling to believe that the Roman Empire reference for this acronym is "so obvious". I do know about the meme: in fact, what struck me so hard about this is how, for a protocol where you'd almost expect it to be hard for them to avoid the acronym "SPQR" (as, even if it were not Sparse, it is made by Signal; I could even see them having started with Signal and decided to remove their brand from the acronym), there are not one but two top-level posts on Hacker News where "speaker" seems to have wooshed over their head and somehow this extremely niche acronym from the Roman Empire is clearly the reason why this is called SPQR. Is the tech community on Hacker News really this stereotypical?
I dunno, SPQR is fairly obvious for anyone who covered Rome in elementary or middle school history.
Beyond that, if you’re from the part of the world where asterix comics were popular (mostly thr francosphere, but also europe more broadly), it really stands out.
That’s all to say nothing of people who’ve got formal higher education in history or even the classics.
I struggle to see how this could be a conspiracy in any form, but maybe you can make it more clear for me? As I see it, it would make perfect sense for a democracy driving app to focus on “Senate and People”, the fact that is sound like "speaker" simply makes it more brilliant.
So far the biggest weakness of Signal is identification via a phone number. It's not only hackers who can spoof the numbers, but an authoritarian governments too may take ownership of a number at any moment.
Addressing future threats is good, but priorities should be different.
This is different though. PP is saying that you require a phone number to sign up, and phone numbers are being used to match your account to your user name.
"Signal does not send your phone number to anyone unless you have enabled that others can see it and then you send them a message or make a call to them."
Yup, in Poland, a mobile phone number (pre-paid or not, it doesn't matter) is tied to a PESEL number [1] at the time of purchase. The official justification, as usual, was combating crime, but the end result is a tighter grip on citizens' privacy by the government while spammers and others continue their business as usual.
If no one knows your user ID besides you and the people you share it with, why would spam be a big issue? If it's a random string, I don't know how anyone could get it, unless you share it publicly or with someone untrustworthy who shares it publicly. And even if it's a username users choose, as long as there's no directory it still shouldn't be a big problem.
That is - even if someone makes 1000 bot Signal accounts, what can they really do with that if they don't have a good way of enumerating other Signal users?
> if they don't have a good way of enumerating other Signal users?
You can always brute force.
Btw, if you don't accept message requests from spammers they have no indication of if you have an account or not. Try sending a message to a friend who you haven't added on signal. You can just see you sent the message but not if it was received or rejected or anything. Not until they click accept
If it's a sufficiently long random string, that shouldn't be possible, right? Admittedly not an amazing user experience to have to share a random string to your friends, but many Signal-like apps do this.
Great point that requiring a friend request beforehand kind of eliminates the issue too. I assume the Signal developers do have a good reason for thinking requiring phone numbers reduces abuse, but I'm having trouble understanding it.
> Admittedly not an amazing user experience to have to share a random string to your friends
And struggle to get adoption. If it's too long, it's hard to share but difficult to brute force even with massive parallelism. But you can always brute force, it is just about how effective brute force is. Entropy is a double edged sword.
It's also harder to then do contact discovery to find who's already in the network. Which is the basic principle of any social network (yes, I'm calling old school landline phones a social network too). It's a tradeoff, right?
And it's worth noting that usernames exist now and this is serving as a bridge. You can provide links and QR codes too. I think this is a fair system and allows my grandma to use signal while still providing a path forward to another paradigm.
This brings me to one of my critiques of signal. I wish they would recognize we all have multiple identities. My real name obviously isn't godelski. But I might want to link my contact here on HN but not reveal to those people that my actual name is "Joe Schmoe". We don't need unlimited identities but having 2 or 3 could really do a lot for privacy. Let me have a little more granularity over my privacy settings. Let me have some people contact me via godelski.## and some by joeschmoe.##. The former sees my name as "godelski" and the latter as "joe".
And to be clear, the phone number issue is privacy related, not security.
You can't brute force it if the ID is large enough. E.g. if it's a 256 bit ID, sending 10^18 brute force messages per second it would still take 10^41 years until you hit a real user (assuming 6 billion users).
"Can I contact you on signal? Just wait for a few minutes while I type this 64 character long hex string".
I know you can work around this with QRs, but that's poor UX, has many failure scenarios and takes a long time. In comparison, you can just tell someone your phone number, even without neither of you having a phone nearby - you just need a piece of paper and a pen.
Signal brought security and privacy for the masses, because it - correctly - prioritized ease of use over tech-nerd paranoia.
> but that's poor UX, has many failure scenarios and takes a long time.
And requires you to build your social graph from scratch. That alone is killer to the average person.
Is signal the right tool for those hyper concerned with both security and privacy? No. But is it the right tool for the average person to securely communicate and get some good privacy? Absolutely.
People forget the GPG days. GPG had a huge flaw back then: you can't send GPG encrypted emails if no one was going to read them. It didn't become viable until that part was hidden in the background.
Good luck brute force guessing an Ed25519 keys (32 bytes).
Honestly there are so many better options than phone numbers available. If you're already using QR-codes to transmit user ids, you might as well use something that is transferable and user generated.
You're reading the problem wrong. Yeah, even considering the birthday problem you're going to have a hard time finding a valid key.
But now we have a discovery problem. How do I find my current contacts? Do I need you rebuild my social graph from scratch? Good luck getting my friends with PhDs in computer science doing this, let alone my grandma.
Entropy is a double edged sword. IMO signal is doing a good job here. We can go drop phone numbers completely when enough people are using signal. But while the userbase is low it's probably worth the 3 spam messages I get a year. I get more than that in a week on my iPhone and more than that a month when I used Android. So I'll take the trade.
And I must stress, the phone number issue is about privacy, not security. At least with regards to signal
One can still use simpler contact information like a phone number, email or QR code to transfer a user id.
While I love what Signal has done, the compromises are significant. I use Secure Scuttlebutt, Cabal, Spritely Goblins, Tor, email and a variety of other P2P software on whatever device I like, but Signal requires a phone with Android or Apple, and requires that I lock my id to my phone number.
Sort of. There are now immense warehouses filled with racks of used cell phones to generate spam. Limiting by phone number helps, but it's FAR from being an adequate cure.
You don't need phonenumbers to deal with spam, just set the "allow messages only from contacts/friends" and a way to add new contacts when needed (via username, email, or even a phone number). It used to work without issues with protocols like MSN messenger, aim, icq etc.
Identification of what? That you have a signal account?[0] I'll admit that that's not ideal but I'm unconvinced this is a big issue.
> an authoritarian governments too may take ownership of a number at any moment.
Suppose they did hijack the account. This would not give them the message history. You know that, right? It also kicks out the original owner, warning them they've been pwned.
Don't get me wrong, Signal has issues and we should be critical and hold them to high standards. BUT *they are only E2EE and low metadata Messenger that my grandma can use.* That's a big fucking deal. If we want secure communication to be common place we need to make sure it's usable. Sure, there's more secure and more private services, but none that my grandma could use.
I very much think signal should shift focus to privacy as they've got the security side pretty well handled (as this blog illustrates). But also these comments at the top of any signal thread feel a bit out of touch. Maybe I'm reading too much into it but there's a lot of people who confidently act like this compromises security or places harm on a user. The existence of a registered signal account means very little, especially as you note numbers can be spoofed. You need more than a number to hijack an account and hijacking only reveals messages moving forward while telling the compromised user they're compromised.
So can we focus on bigger issues? Can we critique while still recommending? I have no problem saying I have issues with signal and wish they did more while acknowledging that it is strongly my preferred means of contact and I try to convince others to talk to me that way. These things are not at odds. I've gone so far as donating to them several times because I use the service so much
Having run some family through the Signal onboarding process lately I'm actually kind of disappointed though: the CAPTCHA requirements are a big turn off, and it was relatively difficult to get them to see "look I'm on Signal!" In their existing contacts.
To wit: phone numbers have to stay. That's how I even get people to use it with me, and that's enormously valuable.
But also: there really needs to be a way I can use my own account to vouch for a new user and skip that CAPTCHA (maybe there is? What happens if I do an in app invite?)
Most people take no notice of this stuff IMO. I see it regularly in WhatsApp groups when someone gets a new phone (presumably, or they are being impersonated!).
Can anyone comment on where this puts Signal now in relation to iMessage with PQ3[1]? As an aside, can anyone comment on earlier (fast/rushed/sound?) attempts at quantum-resistant encrypted messaging in Cyph[2] and Simplex[3] in comparison?
My read is that Signal now ratchets with ML-KEM in a similar way to iMessages's PQ3, with key delivery being one of the main differentiating features.
Everyone is worried about the fact that ML-KEM keys are so chonky, so PQ3 sends them out only occasionally while Signal chunks them up and sends them in pieces along with all normal messages. Signal's argument is that a huge re-keying message could be detected and blocked, and chunking them is both safer and smoother on bandwidth. Erasure coding will likely wind up costing a bit more overall bandwidth, but each message will be more consistently sized. Given the wide range of Signal's deployment posture, that is probably a wise tradeoff to make. I would expect that Apple has a bit more control over their networks and are in a better position to deal with adversaries attempting to actively block their re-key updates.
Im feeling pretty dumb even after reading the tldr. Can anyone who is well versed in this explain how this is better or safer? I read about the time, will it now be slower to send messages?
In the standard practical analysis of quantum threats to cryptography, your adversary is "harvesting and then decrypting". Everybody agrees that no adversary can perform quantum cryptography today, but we agree (to agree) that they'll plausibly be able to at some point in the future. If you assume Signal is carrying messages that have to be kept secret many years into the future, you have to assume your adversary is just stockpiling Signal ciphertexts in a warehouse somewhere waiting so that 15 or 20 years from now they can decrypt them.
That's why you want PQ key agreement today: to protect against a future capability targeting a record of the past. (It's also why you don't care as much about PQ signatures, because we agree no adversary can time travel back and MITM, say, a TLS signature verification).
To understand the importance of a PQ ratchet, add one more capability to the adversary. In addition to holding on to ciphertexts for 15-20 years, assume they will eventually compromise a device, or find an implementation-specific flaw in cryptography code that they can exploit to extract key material. This is a very realistic threat model; in fact, it's of much more practical importance than the collapse of an entire cryptographic primitive.
You defend against that threat model with "forward secrecy" and "post-compromise security". You continually update your key, so the compromise of any one key doesn't allow an attacker to retrospectively decrypt, or to encrypt future messages.
For those defenses to hold against a "harvest and decrypt" attacker, the "ratchet" mechanism you use to keep re-keying your session also needs to be PQ secure. If it isn't, attackers will target the ratchet instead of the messages, and your system will lose its forward and post-compromise secrecy.
>> Forward secrecy is somewhat overrated in end to end encrypted messaging. Most people do not want a truly off the record experience but instead keep their old messages around indefinitely. As long as those old messages exist and are accessible to the user they will be just as accessible to any attacker that gets access to the secret key material.
On a more serious note, if a quantum computer can break a key, a task requiring exponential complexity with key length on a classical computer, then breaking N keys is only a negligible additional cost in comparison.
So it kind of feels like it’s overrated in this case to be honest :)
I think this used to be true. Now one problem is that a Signal message goes through this whole forward secrecy protocol, but the receiving device has some probability of uploading it to the cloud with a static key that never changes.
You don't have to enable the Signal backups feature, but you have no way of knowing whether the recipient of your messages has. One person in a group chat with that enabled will undo all of the forward secrecy you're describing.
The static symmetric key is fundamentally different from an ephemeral asymmetric key. We've no indication that symmetric encryption is vulnerable to "store now, decrypt later" attacks when used with a sufficiently long key, which Signal has. Non-post-quantum asymmertic cryptography is vulnerable to "store now, decrypt later" attacks, which is why forward secrecy is needed.
The backups feature doesn't open up any new vulnerability that didn't inherently exist in sending messages to someone else you might not fully trust. One person in a group chat can also take pictures of their phone's screen & upload your messages to the public.
Images can be modified, won't these essentially be signed as verifiably coming from the sender, or is cryptographic proof of that thrown away in what they store?
This is no different than if recipient of the secure message shares the message in plaintext. The problem is a discipline problem not a technology one, and the solution is the same in both cases.
There's a difference between what Signal does in the app and a manual action a user performs outside of the app. It is not realistic to expect that people will see a feature Signal has built for them in the app and understand the underlying implications to "post compromise security" and "forward secrecy" that it may have.
The expectation is that what happens inside Signal is secure, and the features Signal provides are secure. If the idea is that nobody is going to enable this feature, then why build it? If the idea is that many people are going to enable this feature, then this entire cryptographic protocol is meaningless.
Those are the breaks though when catering to a large audience with wildly differing threat models. Do you throw away users that are looking for a vague sense of security so they run off somewhere else less secure because you lack some feature?
If you are just looking for "secure(TM)[X]", you are making a mistake somewhere anyway.
If your life or livelihood depends on it, you learn what the impact of every choice is and you painstakingly keep to your opsec.
Somewhere between the two user action becomes a necessity. You need to judge where that point is for you and take responsibility for it because nobody else can guarantee it.
The history of Signal has been to provide the security properties we're talking about without users having to think about it or understand. To suddenly remove forward secrecy is a very big change, and it isn't one that they seem to have acknowledged or documented. Like this blog post: they are making an announcement that they have a "post-quantum ratchet," when they have effectively removed the ratchet. It's theater.
I think you missed the point entirely. You can't have security without thinking about it. You can have vague sense of security, which is the theater you are talking about.
Show me a company anywhere that can provide security without user thought and deliberate action. It's a fantasy to believe anything you don't have to think about isn't theater.
These things can still be used as evidence. The process used by the police of a rogue country (or any other adversary) isn't a cryptographer's highly technical wet dream or nightmare. They simply look at the screen of your phone saying you sent or received a message, and as far as the adversary is concerned, that proves you sent or received it. Even if you didn't. (Actually, they use Cellebrite and just trust whatever the Cellebrite analyzer outputs, which is basically what your screen would have said)
I've yet to see a protocol that lets you convincingly insert fake messages into both sides of your own chat history, especially in a way that isn't detectable by say, sqlite rowid order, but that would be an interesting idea for where to take this sort of thing.
But practically, it probably has more risk as people bypassing employer or legal controls think it’s “secure”. So they have conversations that they wouldn’t have.
The security problem that a messaging app like Signal solves is NOT: Allow a person to secure their communication against eavesdroppers.
It solves the problem: How can a group of people (two or more people) securely communicate with each other.
The group has to mutually decide their risk profile, and then decide which features of the application to use. And each person in the group has to decide whether they can trust others in the group to follow the agreed upon opsec. Signal cannot solve these social problems.
Historically as long as everything remained "in the app," it was secure. It's an easy assumption to make and communicate to others. Now it's more complicated: there are things that people can unwittingly do "in the app" that make it less secure.
AFAIK, it has the same security as before. Perfect forward secrecy means that if someone starts recording encrypted messages in transit and two years later obtains an encryption key, they cannot use that key to decrypt the messages they recorded earlier (because of re-keying).
On the other hand, if an adversary captures one of the group participants' phone and breaks device security, and the chat was recorded on that device, then they can access all recorded chats. By the same token, no cryptography can protect against a malicious group participant who records messages.
In the same scenario, cloud backups seem to merely imply that the same adversary can obtain the cloud backup key and therefore decipher the cloud backups if they get their hands on it. They won't need that, however, since the group chat history is already stored on the device. If no chats were recorded on the device at all the situation would be different.
You also have no way of knowing when someone you're chatting with screenshots your messages and uploads them to Imgur.
I jest, and Signal's support for backups do really increase exposure to this risk, but just trying to say its a matter of degree not a fundamentally new change. People that have been using sigtop[0] to backup their Signal messages to plaintext also create the same exposure risk.
I don't think that's quite right. PQ attacks focus on the "trapdoor" functions in asymmetric cryptography, _not_ the symmetric encryption that happens after key negotiation. The current concern is that a future attacker could unwrap the symmetric key, not directly attack the symmetric encryption that is used for something like backups.
(Note: I didn't actually dig into the backup implementation, but my guess is that it's more of a KDF -> symmetric design, rather than the sorts of asymmetric negotiation you'd find in multi-party messaging.)
If the app takes your disappearing message, encrypts it with a static key that never changes and is never deleted, and uploads it to the cloud, then the message is never truly "disappearing." A "post compromise" event will allow the attacker to decrypt that ciphertext at any point in the future. All of this ratcheting is undone by backups.
Disappearing messages were never a real thing in the first place. You can have a gentleman's agreement that the person you send your message to will delete it after reading it, there's no way to guarantee anything beyond that.
(Fair point though that probably "disappearing" messages shouldn't be included in backups since that obviously prevents them from being deleted. Idk if Signal implements that or not.)
What type of static key? If it's just a big symmetric key that isn't derived from an asymmetric handshake of some type then no, that's not our current understanding of the PQ threat model.
Part of the premise of FS/PCS is that "shit happens" to compromise keys even if the underlying cryptography is strong, so if you want a coherent end-to-end FS/PCS story, the claim would be that you need to be ratcheting everywhere.
Definitely, but when we're running around sprinkling PQ algorithms all over the place, it's on top of the asymmetric bits, not replacing the "boring" stuff like your symmetrically encrypted backups. Shit certainly does happen, especially where key management is involved, but I'm not sure I agree that offering an encrypted backup feature is necessarily undoing the FS/PCS story.
edit: Well, let me argue with myself for a moment. I don't think offering an encrypted backup feature undoes the PQ story. But FS/PCS is weakened, sure, since we're talking about all types of shit happening, not just currently known (or strongly theorized) attacks.
Yes, if Signal has effectively removed ratcheting and forward secrecy from the logical "encryption protocol" by encrypting all messages (even disappearing messages) with a single static key that never changes for your lifetime and sending them to the cloud, then all this talk about "post-quantum ratchets" is theater. There are no ratchets.
I'm slightly confused about the PCS part. If I've understood correctly the new key is derived from the old key + some kind or message header. If the attacker has access to a key and messages encrypted with it, can't they read the shared secret used for key exchange and use their existing key to generate the new one? Or is this only possible with ECDH and not KEM?
The new one is randomly chosen (with the randomness coming from both parties, and then combined using ECDH and/or KEM). So you cannot predict it from previous key material, pretty much by definition.
What is the state of PQ symmetric crypto? My layman's understanding is that 128 bit AES is known to be broken by a quantum computer and that 256 AES may be OK but that isn't certain? Is this an additional vector for the "harvest and wait" strategy in the future?
> My layman's understanding is that 128 bit AES is known to be broken by a quantum computer
Weakened, not broken. Quantum computers turns 128 bit AES into 64 bit equivalent. Which will still be extremely difficult for quantum computers due to the large computer size/number of steps required.
And it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
Well, you get sqrt(n / N) as a result. It works like any other parallel computation.
E.g. if you have 256 quantum computers, then each one of them needs to search only 60 bits of the key space to crack a 128-bit key (each one of them will only need to search 2^120 keys).
It's not really going to make much difference with near-future quantum computers. Especially since Grover's algorithm _has_ to complete all the 2^60 steps to produce a reliable result, you can't just run a quantum computer for a while, stop it, and then restart it.
Their existing post quantum encryption didn't do post compromise security (PCS) against quantum attackers. This new one does.
I am excited to finally know what they mean by PCS after reading this article. It means that the session keys from their key agreement scheme (n ratchet) are generated new so an attacker doesn't get them again after a fairly specific sort of compromise. So from that I get that the off the record (OTR) protocol also has PCS. Which is a bit disappointing, I thought that they had come up with some new concept.
This key agreement doesn't happen that often. So a user isn't going to notice any slowness even if it was significantly slower.
> "What does this mean for you as a Signal user? First, when it comes to your experience using the app, nothing changes. Second, because of how we’re rolling this out and mixing it in with our existing encryption, eventually all of your conversations will move to this new protocol without you needing to take any action. Third, and most importantly, this protects your communications both now and in the event that cryptographically relevant quantum computers eventually become a reality, and it allows us to maintain our existing security guarantees of forward secrecy and post-compromise security as we proactively prepare for that new world."
The (very weak) Caesar cipher was used in ancient Rome though and cryptography in general way before. It could be a silent nod to how far our achievements have gone and that encryption is a basic human desire since millennia.
I would really like to see some modern comparisons of the Signal protocol to Matrix, MLS, etc. since it's hard to keep up with everything but it seems like things are still moving.
Wow, this is one of the most well written cryptography articles I've ever seen.
I consider myself a fairly experienced software engineer with a moderate amount of professional experience in private sector encryption, so I'm not completely out of my element, but many articles along this vein have my eyes glazing over halfway through the breakdown.
This one was actually easy for me to follow the entire time for once, despite explaining something I'm not familiar with.
Strange that they are posting about the "signal ratchet" when they just removed it by launching cloud backups that use a static key? Since those cloud backups include disappearing messages, that feature completely undoes all of the forward secrecy in this protocol.
Yes, but you don't need a complicated ratcheting protocol if you've eliminated forward secrecy in other ways. This post is about "post compromise security," but there is already no post-compromise security after the cloud backups feature
Do you also think it's "strange" that they're introducing that (optional!) feature while also storing all the messages on your device? The cloud backup is strictly more secure than that on-device database. Their blog post on the subject also explicitly says it won't include disappearing messages that disappear within 24 hours.
It's not optional because you don't know whether the people you are communicating with have it enabled. One person in a group chat with the feature enabled undoes the forward secrecy for everyone in the group chat.
A cloud backup eliminates any forward secrecy. It used to be that in Signal, when you have a message on your device and it is deleted (or a disappearing message disappears), then it is truly gone and can never be recovered. Now with backups, since the key that was used to encrypt it to the cloud remains on your device, it can be recovered even after the message is deleted or disappears.
The only way to "truly" opt-out is to, as you say, set a disappearing message timer for <24 hours.
Yeah, and all of that's already true right now because messages are stored on those users' devices already. You'll be heartbroken to hear that those users can also take a screenshot of your disappearing messages and send it to anyone. There are fundamental limitations to what a messaging app can protect you from.
While the analog hole will always exist, and you can't make it actually impossible, Snapchat's quite good at that screenshot thing. Both platforms have APIs to prevent, or at least notify on the use of screenshot. It's weird that signal doesn't use any of them.
i know of ~3 currently working methods to take screenshots on snapchat
it isn't "weird that signal doesn't use any of them" because it does [1] use both, just not for giving a false sense of security to your correspondents
Signal can't protect you against the other party you are communicating with. They can backup the conversation, or screenshot it, or take a photo of the screen with another camera. They could also retell in their words what you sent.
You know (with pretty high certainty) that your conversational partner is using Signal. The security level of Signal affects your estimation of the security level of your partner.
Signal is lacking a crucial safety feature. To cover some background, it is necessary to set "Who can see my number" and "Who can find me by number" both to "Nobody", as this lowers the chances of spam messages and attempted hacks. Once these are set, the only way for someone to start a conversation with you is if they know your Signal username or QR link, both of which you can set in your Profile. The issue is that your link can be saved unsafely by your Contacts, and can be used multiple times, also by others, leaking it to hackers who can then send you unsolicited messages to compromise your device. The safety feature that would be good to have is to allow someone to contact me only via a one-time use link that cannot be reused by anyone.
This sounds like an excellent feature request that would shore up their anti-abuse endeavors more than them "lacking a very basic crucial safety feature".
Which of the so-called Signal competitors have implemented something like this already today?
Maybe my reading comprehension is failing me, but what does this mean for existing messages? I guess nothing of the have already been 'siphoned' to a 3rd party. As it couldn't retroactively apply to data not under Signals control of course..but what about existing messages already within their control?
Its interesting to imagine that somebody [1] is already now capturing encrypted internet traffic and storing it all long-term, to then hypothetically in 40-50 years or something decrypt it and draw value from that information. I suppose to blackmail future politicians, learn military secrets, whatever.
> Its interesting to imagine that somebody [1] is already now capturing encrypted internet traffic and storing it all long-term, to then hypothetically in 40-50 years or something decrypt it and draw value from that information. I suppose to blackmail future politicians, learn military secrets, whatever.
You don't have to imagine, there's literally a NSA datacenter in Utah for doing just that.
As someone not in the field it's hard to distinguish the "quantum startup raised x billions, claims quantum computing x years away" from "fusion startup raised x billions, claims fusion power x years away" headlines every few months for the past 10+ years.
Thanks for the link. I skimmed through the report that the article is based on. It tracks rising activity in quantum computing R&D in several areas. But at least in the executive summary, I didn't see anything about commercial applications one way or the other. It doesn't seem to make any predictions?
So, it's odd that the article summarized it that way.
> Overall, quantum processing units (QPUs) are making impressive progress in performance, but they remain far from meeting the requirements for running large-scale commercial applications such as chemical simulations or cryptanalysis.
This is actually disturbing, as the article suggests that all previous messages sent using Signal are decryptable with quantum computers. If there are people with, for example, selfhosted mailservers sending PGP encrypted emails to each other, then, while they have to worry about them not leaking out from the server either by someone hacking to it or someone sniffing the traffic with the encrypted messages beforehand, they know for sure that their messages are safe.
Meanwhile Signal users have been sending messages onto signal servers for years now, as far as I know they aren't sent directly through some p2p protocol. I don't know what their policy is about storing messages, and I believe that they have a lot of other countermeasures, but it still points to the problem with Signals centralized nature.
As far as they say, messages are deleted once delivered, or retained up to 45 days if not:
Devices are always retrieving messages from their mailbox when they are
online, and as soon as the device confirms they’ve gotten a message, it is
deleted from the Signal servers.
If a device has been offline for a while, it may have a lot of messages
waiting in its mailbox when it returns. Today, Signal will hold a message in
a device’s mailbox for up to 45 days, giving an idle device a chance to wake
up and fetch it.
It is possible for them to say that they deleted the messages without actually deleting them though. One has to trust a pretty big company in order to not worry about the messages actually not being stored anywhere.
I'm not aware of all techniques that Signal uses to somehow make the message anonymous even when if the encryption would have been broken, but sealed sender seems to be one of them:
So at least there's that. Unless the encrypted sealed sender messages aren't somehow being fingerprinted by the IP address of client and the timestamps of connections. Signal probably also says that they don't log these, but with self hosted mailserver I wouldn't have to trust them on that too.
I can't believe that they named their protocol SPQR. It's the Latin abbreviation for Senatus Populusque Romanus. https://en.wikipedia.org/wiki/SPQR Love it :)
Yes, very clever. I am familiar with SPQR as a common tattoo on Roman legionnaires from the (excellent) BBC miniseries "Rome". https://en.wikipedia.org/wiki/Rome_(TV_series)
Is that what Maximus tried to carve off in Gladiator?
Lol. You would only see this comment on Hacker News. Reminds me of an old comic I read on how mathematicians memorize their locker numbers. "1975? Oh that's easy. It's just the square root of 3,900,625!"
Ever since I've heard of the meme that "modern men can't spend 24 hours without thinking of the Roman Empire", I haven't been able to escape it, even on days where my only contact with the outside world is HN.
I guess it's like a curse, once you've heard about it you're doomed.
And for anyone finding out about it just now, alea jacta est
I need an faq or something then, to figure out what's wrong with me for never thinking of the Roman Empire. Except now then.
Thank you for reminding me, this is so fun to have bobbing around in the back of your mind! :D
For this particular one, you could easily see that comment on any community with a sufficient number of Asterix fans. Banners and standards with "SPQR" written somewhere were common enough that they should produce a Pavlovian reaction.
Or any community large enough to have people who have, y’know, visited Rome IRL?
It's something collectively known as INRI or CCCP.
spqr is a well-known phrase
Or, maybe, it just sounds like "speaker", because they are a chat app? ;P... not everything has to be framed as a Roman conspiracy.
It’s not a conspiracy, it’s a pop culture reference. Very unlikely it’s unintentional, given that Thinking About Roman Empire was a fairly notable meme of ‘23/‘24 (https://knowyourmeme.com/memes/how-often-do-you-think-about-...).
Could be not a primary cause for the naming - only authors can tell - but I doubt they missed the reference entirely. It’s just way too obvious.
I am struggling to believe that the Roman Empire reference for this acronym is "so obvious". I do know about the meme: in fact, what struck me so hard about this is how, for a protocol where you'd almost expect it to be hard for them to avoid the acronym "SPQR" (as, even if it were not Sparse, it is made by Signal; I could even see them having started with Signal and decided to remove their brand from the acronym), there are not one but two top-level posts on Hacker News where "speaker" seems to have wooshed over their head and somehow this extremely niche acronym from the Roman Empire is clearly the reason why this is called SPQR. Is the tech community on Hacker News really this stereotypical?
Just piling on to say it's super obvious to me, and I didn't even know of this meme before.
I dunno, SPQR is fairly obvious for anyone who covered Rome in elementary or middle school history.
Beyond that, if you’re from the part of the world where asterix comics were popular (mostly thr francosphere, but also europe more broadly), it really stands out.
That’s all to say nothing of people who’ve got formal higher education in history or even the classics.
Caesar cipher anyone? Romans knew (bad) cryptography.
I struggle to see how this could be a conspiracy in any form, but maybe you can make it more clear for me? As I see it, it would make perfect sense for a democracy driving app to focus on “Senate and People”, the fact that is sound like "speaker" simply makes it more brilliant.
Strength and Honor
Scotch and soda
So far the biggest weakness of Signal is identification via a phone number. It's not only hackers who can spoof the numbers, but an authoritarian governments too may take ownership of a number at any moment.
Addressing future threats is good, but priorities should be different.
In case anyone is not aware:
https://news.ycombinator.com/item?id=39444500 Keep your phone number private with Signal usernames (2024-02-20, 1422 points, 890 comments)
This is different though. PP is saying that you require a phone number to sign up, and phone numbers are being used to match your account to your user name.
"As a new default, your phone number will no longer be visible to everyone in Signal."
https://support.signal.org/hc/en-us/articles/6712070553754-P...
"Signal does not send your phone number to anyone unless you have enabled that others can see it and then you send them a message or make a call to them."
https://support.signal.org/hc/en-us/articles/360007061452-Do...
Agreed. For a long time though user names were not even support between Signal users.
Many other secure IM software managed to work without phone numbers and they are also metadata resistant. Signal should start doing things that way.
In many countries your SIM card is tied to you, which is a huge deal-breaker.
Yup, in Poland, a mobile phone number (pre-paid or not, it doesn't matter) is tied to a PESEL number [1] at the time of purchase. The official justification, as usual, was combating crime, but the end result is a tighter grip on citizens' privacy by the government while spammers and others continue their business as usual.
[1] https://en.wikipedia.org/wiki/PESEL
Its a difficult problem because you, ideally, want to curb spam. Requiring phone numbers is a somewhat easy and somewhat reliable way to do that.
If no one knows your user ID besides you and the people you share it with, why would spam be a big issue? If it's a random string, I don't know how anyone could get it, unless you share it publicly or with someone untrustworthy who shares it publicly. And even if it's a username users choose, as long as there's no directory it still shouldn't be a big problem.
That is - even if someone makes 1000 bot Signal accounts, what can they really do with that if they don't have a good way of enumerating other Signal users?
Btw, if you don't accept message requests from spammers they have no indication of if you have an account or not. Try sending a message to a friend who you haven't added on signal. You can just see you sent the message but not if it was received or rejected or anything. Not until they click accept
If it's a sufficiently long random string, that shouldn't be possible, right? Admittedly not an amazing user experience to have to share a random string to your friends, but many Signal-like apps do this.
Great point that requiring a friend request beforehand kind of eliminates the issue too. I assume the Signal developers do have a good reason for thinking requiring phone numbers reduces abuse, but I'm having trouble understanding it.
It's also harder to then do contact discovery to find who's already in the network. Which is the basic principle of any social network (yes, I'm calling old school landline phones a social network too). It's a tradeoff, right?
And it's worth noting that usernames exist now and this is serving as a bridge. You can provide links and QR codes too. I think this is a fair system and allows my grandma to use signal while still providing a path forward to another paradigm.
This brings me to one of my critiques of signal. I wish they would recognize we all have multiple identities. My real name obviously isn't godelski. But I might want to link my contact here on HN but not reveal to those people that my actual name is "Joe Schmoe". We don't need unlimited identities but having 2 or 3 could really do a lot for privacy. Let me have a little more granularity over my privacy settings. Let me have some people contact me via godelski.## and some by joeschmoe.##. The former sees my name as "godelski" and the latter as "joe".
And to be clear, the phone number issue is privacy related, not security.
You can't brute force it if the ID is large enough. E.g. if it's a 256 bit ID, sending 10^18 brute force messages per second it would still take 10^41 years until you hit a real user (assuming 6 billion users).
"Can I contact you on signal? Just wait for a few minutes while I type this 64 character long hex string".
I know you can work around this with QRs, but that's poor UX, has many failure scenarios and takes a long time. In comparison, you can just tell someone your phone number, even without neither of you having a phone nearby - you just need a piece of paper and a pen.
Signal brought security and privacy for the masses, because it - correctly - prioritized ease of use over tech-nerd paranoia.
Is signal the right tool for those hyper concerned with both security and privacy? No. But is it the right tool for the average person to securely communicate and get some good privacy? Absolutely.
People forget the GPG days. GPG had a huge flaw back then: you can't send GPG encrypted emails if no one was going to read them. It didn't become viable until that part was hidden in the background.
Good luck brute force guessing an Ed25519 keys (32 bytes).
Honestly there are so many better options than phone numbers available. If you're already using QR-codes to transmit user ids, you might as well use something that is transferable and user generated.
You're reading the problem wrong. Yeah, even considering the birthday problem you're going to have a hard time finding a valid key.
But now we have a discovery problem. How do I find my current contacts? Do I need you rebuild my social graph from scratch? Good luck getting my friends with PhDs in computer science doing this, let alone my grandma.
Entropy is a double edged sword. IMO signal is doing a good job here. We can go drop phone numbers completely when enough people are using signal. But while the userbase is low it's probably worth the 3 spam messages I get a year. I get more than that in a week on my iPhone and more than that a month when I used Android. So I'll take the trade.
And I must stress, the phone number issue is about privacy, not security. At least with regards to signal
One can still use simpler contact information like a phone number, email or QR code to transfer a user id.
While I love what Signal has done, the compromises are significant. I use Secure Scuttlebutt, Cabal, Spritely Goblins, Tor, email and a variety of other P2P software on whatever device I like, but Signal requires a phone with Android or Apple, and requires that I lock my id to my phone number.
In signal you can change your username any time.
Sort of. There are now immense warehouses filled with racks of used cell phones to generate spam. Limiting by phone number helps, but it's FAR from being an adequate cure.
Yeah, if the telegram and whatsapp spam I get is any reading, limiting by phone number is not sufficient.
Whitelisting solves spam. Phone numbers should be obsolete by now.
You don't need phonenumbers to deal with spam, just set the "allow messages only from contacts/friends" and a way to add new contacts when needed (via username, email, or even a phone number). It used to work without issues with protocols like MSN messenger, aim, icq etc.
Don't get me wrong, Signal has issues and we should be critical and hold them to high standards. BUT *they are only E2EE and low metadata Messenger that my grandma can use.* That's a big fucking deal. If we want secure communication to be common place we need to make sure it's usable. Sure, there's more secure and more private services, but none that my grandma could use.
I very much think signal should shift focus to privacy as they've got the security side pretty well handled (as this blog illustrates). But also these comments at the top of any signal thread feel a bit out of touch. Maybe I'm reading too much into it but there's a lot of people who confidently act like this compromises security or places harm on a user. The existence of a registered signal account means very little, especially as you note numbers can be spoofed. You need more than a number to hijack an account and hijacking only reveals messages moving forward while telling the compromised user they're compromised.
So can we focus on bigger issues? Can we critique while still recommending? I have no problem saying I have issues with signal and wish they did more while acknowledging that it is strongly my preferred means of contact and I try to convince others to talk to me that way. These things are not at odds. I've gone so far as donating to them several times because I use the service so much
[0] https://signal.org/bigbrother/
Imagine being someone who would downvote this without a comment.
Is it:
"I disagree but am not literate enough to state why"
Or is it:
"This person is right, but I don't want people to know it (insert motive here), so I will try to make their comment invisible"
Either way they're cowards, and you are correct. Signal is the best intersection of genuine security and ease-of-use I've seen.
Having run some family through the Signal onboarding process lately I'm actually kind of disappointed though: the CAPTCHA requirements are a big turn off, and it was relatively difficult to get them to see "look I'm on Signal!" In their existing contacts.
To wit: phone numbers have to stay. That's how I even get people to use it with me, and that's enormously valuable.
But also: there really needs to be a way I can use my own account to vouch for a new user and skip that CAPTCHA (maybe there is? What happens if I do an in app invite?)
They can take ownership of the number but not the keys on the device, which would show up as safety codes changing.
This problem is honestly minor compared to teaching users to have opsec practices suitable against such a threat.
Most people take no notice of this stuff IMO. I see it regularly in WhatsApp groups when someone gets a new phone (presumably, or they are being impersonated!).
You can set a password in Signal, preventing movement of your account in case of SIM hijacking. Feature is called "Registration lock".
Can anyone comment on where this puts Signal now in relation to iMessage with PQ3[1]? As an aside, can anyone comment on earlier (fast/rushed/sound?) attempts at quantum-resistant encrypted messaging in Cyph[2] and Simplex[3] in comparison?
[1] https://security.apple.com/blog/imessage-pq3/ [2] https://www.cyph.com/castle [3] https://simplex.chat/blog/20240314-simplex-chat-v5-6-quantum...
My read is that Signal now ratchets with ML-KEM in a similar way to iMessages's PQ3, with key delivery being one of the main differentiating features.
Everyone is worried about the fact that ML-KEM keys are so chonky, so PQ3 sends them out only occasionally while Signal chunks them up and sends them in pieces along with all normal messages. Signal's argument is that a huge re-keying message could be detected and blocked, and chunking them is both safer and smoother on bandwidth. Erasure coding will likely wind up costing a bit more overall bandwidth, but each message will be more consistently sized. Given the wide range of Signal's deployment posture, that is probably a wise tradeoff to make. I would expect that Apple has a bit more control over their networks and are in a better position to deal with adversaries attempting to actively block their re-key updates.
Im feeling pretty dumb even after reading the tldr. Can anyone who is well versed in this explain how this is better or safer? I read about the time, will it now be slower to send messages?
Sure.
In the standard practical analysis of quantum threats to cryptography, your adversary is "harvesting and then decrypting". Everybody agrees that no adversary can perform quantum cryptography today, but we agree (to agree) that they'll plausibly be able to at some point in the future. If you assume Signal is carrying messages that have to be kept secret many years into the future, you have to assume your adversary is just stockpiling Signal ciphertexts in a warehouse somewhere waiting so that 15 or 20 years from now they can decrypt them.
That's why you want PQ key agreement today: to protect against a future capability targeting a record of the past. (It's also why you don't care as much about PQ signatures, because we agree no adversary can time travel back and MITM, say, a TLS signature verification).
To understand the importance of a PQ ratchet, add one more capability to the adversary. In addition to holding on to ciphertexts for 15-20 years, assume they will eventually compromise a device, or find an implementation-specific flaw in cryptography code that they can exploit to extract key material. This is a very realistic threat model; in fact, it's of much more practical importance than the collapse of an entire cryptographic primitive.
You defend against that threat model with "forward secrecy" and "post-compromise security". You continually update your key, so the compromise of any one key doesn't allow an attacker to retrospectively decrypt, or to encrypt future messages.
For those defenses to hold against a "harvest and decrypt" attacker, the "ratchet" mechanism you use to keep re-keying your session also needs to be PQ secure. If it isn't, attackers will target the ratchet instead of the messages, and your system will lose its forward and post-compromise secrecy.
>> Forward secrecy is somewhat overrated in end to end encrypted messaging. Most people do not want a truly off the record experience but instead keep their old messages around indefinitely. As long as those old messages exist and are accessible to the user they will be just as accessible to any attacker that gets access to the secret key material.
On a more serious note, if a quantum computer can break a key, a task requiring exponential complexity with key length on a classical computer, then breaking N keys is only a negligible additional cost in comparison.
So it kind of feels like it’s overrated in this case to be honest :)
I think this used to be true. Now one problem is that a Signal message goes through this whole forward secrecy protocol, but the receiving device has some probability of uploading it to the cloud with a static key that never changes.
You don't have to enable the Signal backups feature, but you have no way of knowing whether the recipient of your messages has. One person in a group chat with that enabled will undo all of the forward secrecy you're describing.
The static symmetric key is fundamentally different from an ephemeral asymmetric key. We've no indication that symmetric encryption is vulnerable to "store now, decrypt later" attacks when used with a sufficiently long key, which Signal has. Non-post-quantum asymmertic cryptography is vulnerable to "store now, decrypt later" attacks, which is why forward secrecy is needed.
The backups feature doesn't open up any new vulnerability that didn't inherently exist in sending messages to someone else you might not fully trust. One person in a group chat can also take pictures of their phone's screen & upload your messages to the public.
I think they're making a point that is broader than PQ and a more general complaint about Signal's direction.
Images can be modified, won't these essentially be signed as verifiably coming from the sender, or is cryptographic proof of that thrown away in what they store?
This is no different than if recipient of the secure message shares the message in plaintext. The problem is a discipline problem not a technology one, and the solution is the same in both cases.
There's a difference between what Signal does in the app and a manual action a user performs outside of the app. It is not realistic to expect that people will see a feature Signal has built for them in the app and understand the underlying implications to "post compromise security" and "forward secrecy" that it may have.
The expectation is that what happens inside Signal is secure, and the features Signal provides are secure. If the idea is that nobody is going to enable this feature, then why build it? If the idea is that many people are going to enable this feature, then this entire cryptographic protocol is meaningless.
Those are the breaks though when catering to a large audience with wildly differing threat models. Do you throw away users that are looking for a vague sense of security so they run off somewhere else less secure because you lack some feature?
If you are just looking for "secure(TM)[X]", you are making a mistake somewhere anyway.
If your life or livelihood depends on it, you learn what the impact of every choice is and you painstakingly keep to your opsec.
Somewhere between the two user action becomes a necessity. You need to judge where that point is for you and take responsibility for it because nobody else can guarantee it.
The history of Signal has been to provide the security properties we're talking about without users having to think about it or understand. To suddenly remove forward secrecy is a very big change, and it isn't one that they seem to have acknowledged or documented. Like this blog post: they are making an announcement that they have a "post-quantum ratchet," when they have effectively removed the ratchet. It's theater.
I think you missed the point entirely. You can't have security without thinking about it. You can have vague sense of security, which is the theater you are talking about.
Show me a company anywhere that can provide security without user thought and deliberate action. It's a fantasy to believe anything you don't have to think about isn't theater.
These things can still be used as evidence. The process used by the police of a rogue country (or any other adversary) isn't a cryptographer's highly technical wet dream or nightmare. They simply look at the screen of your phone saying you sent or received a message, and as far as the adversary is concerned, that proves you sent or received it. Even if you didn't. (Actually, they use Cellebrite and just trust whatever the Cellebrite analyzer outputs, which is basically what your screen would have said)
I've yet to see a protocol that lets you convincingly insert fake messages into both sides of your own chat history, especially in a way that isn't detectable by say, sqlite rowid order, but that would be an interesting idea for where to take this sort of thing.
I think you’re right.
But practically, it probably has more risk as people bypassing employer or legal controls think it’s “secure”. So they have conversations that they wouldn’t have.
It's a technological one when the feature is offered to laymen for their convenience.
The security problem that a messaging app like Signal solves is NOT: Allow a person to secure their communication against eavesdroppers.
It solves the problem: How can a group of people (two or more people) securely communicate with each other.
The group has to mutually decide their risk profile, and then decide which features of the application to use. And each person in the group has to decide whether they can trust others in the group to follow the agreed upon opsec. Signal cannot solve these social problems.
Historically as long as everything remained "in the app," it was secure. It's an easy assumption to make and communicate to others. Now it's more complicated: there are things that people can unwittingly do "in the app" that make it less secure.
AFAIK, it has the same security as before. Perfect forward secrecy means that if someone starts recording encrypted messages in transit and two years later obtains an encryption key, they cannot use that key to decrypt the messages they recorded earlier (because of re-keying).
On the other hand, if an adversary captures one of the group participants' phone and breaks device security, and the chat was recorded on that device, then they can access all recorded chats. By the same token, no cryptography can protect against a malicious group participant who records messages.
In the same scenario, cloud backups seem to merely imply that the same adversary can obtain the cloud backup key and therefore decipher the cloud backups if they get their hands on it. They won't need that, however, since the group chat history is already stored on the device. If no chats were recorded on the device at all the situation would be different.
You also have no way of knowing when someone you're chatting with screenshots your messages and uploads them to Imgur.
I jest, and Signal's support for backups do really increase exposure to this risk, but just trying to say its a matter of degree not a fundamentally new change. People that have been using sigtop[0] to backup their Signal messages to plaintext also create the same exposure risk.
[0] https://github.com/tbvdm/sigtop
I don't think that's quite right. PQ attacks focus on the "trapdoor" functions in asymmetric cryptography, _not_ the symmetric encryption that happens after key negotiation. The current concern is that a future attacker could unwrap the symmetric key, not directly attack the symmetric encryption that is used for something like backups.
(Note: I didn't actually dig into the backup implementation, but my guess is that it's more of a KDF -> symmetric design, rather than the sorts of asymmetric negotiation you'd find in multi-party messaging.)
If the app takes your disappearing message, encrypts it with a static key that never changes and is never deleted, and uploads it to the cloud, then the message is never truly "disappearing." A "post compromise" event will allow the attacker to decrypt that ciphertext at any point in the future. All of this ratcheting is undone by backups.
Disappearing messages were never a real thing in the first place. You can have a gentleman's agreement that the person you send your message to will delete it after reading it, there's no way to guarantee anything beyond that.
(Fair point though that probably "disappearing" messages shouldn't be included in backups since that obviously prevents them from being deleted. Idk if Signal implements that or not.)
Disappearing messages are an opsec feature for trusted counterparties, not a cryptographic feature. They are very much a real thing.
> encrypts it with a static key
What type of static key? If it's just a big symmetric key that isn't derived from an asymmetric handshake of some type then no, that's not our current understanding of the PQ threat model.
Part of the premise of FS/PCS is that "shit happens" to compromise keys even if the underlying cryptography is strong, so if you want a coherent end-to-end FS/PCS story, the claim would be that you need to be ratcheting everywhere.
Definitely, but when we're running around sprinkling PQ algorithms all over the place, it's on top of the asymmetric bits, not replacing the "boring" stuff like your symmetrically encrypted backups. Shit certainly does happen, especially where key management is involved, but I'm not sure I agree that offering an encrypted backup feature is necessarily undoing the FS/PCS story.
edit: Well, let me argue with myself for a moment. I don't think offering an encrypted backup feature undoes the PQ story. But FS/PCS is weakened, sure, since we're talking about all types of shit happening, not just currently known (or strongly theorized) attacks.
I think they point they're making doesn't have much to do with PQ.
Yes, if Signal has effectively removed ratcheting and forward secrecy from the logical "encryption protocol" by encrypting all messages (even disappearing messages) with a single static key that never changes for your lifetime and sending them to the cloud, then all this talk about "post-quantum ratchets" is theater. There are no ratchets.
I think it's a valid point but also that it assumes a lot about the threat model that can be disputed, so your "theater" point is not well taken.
I'm slightly confused about the PCS part. If I've understood correctly the new key is derived from the old key + some kind or message header. If the attacker has access to a key and messages encrypted with it, can't they read the shared secret used for key exchange and use their existing key to generate the new one? Or is this only possible with ECDH and not KEM?
The new one is randomly chosen (with the randomness coming from both parties, and then combined using ECDH and/or KEM). So you cannot predict it from previous key material, pretty much by definition.
They also don't know the random elements used in previous headers, since they're thrown away a few rounds after the message was decrypted.
ah ok, thank you. Starting to make sense now
What is the state of PQ symmetric crypto? My layman's understanding is that 128 bit AES is known to be broken by a quantum computer and that 256 AES may be OK but that isn't certain? Is this an additional vector for the "harvest and wait" strategy in the future?
128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.
> My layman's understanding is that 128 bit AES is known to be broken by a quantum computer
Weakened, not broken. Quantum computers turns 128 bit AES into 64 bit equivalent. Which will still be extremely difficult for quantum computers due to the large computer size/number of steps required.
And it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
Yes, but then you give up the advantage that Grover's gives you in the first place. The advantage is sqrt(n). You are reducing n by parallelizing.
Well, you get sqrt(n / N) as a result. It works like any other parallel computation.
E.g. if you have 256 quantum computers, then each one of them needs to search only 60 bits of the key space to crack a 128-bit key (each one of them will only need to search 2^120 keys).
It's not really going to make much difference with near-future quantum computers. Especially since Grover's algorithm _has_ to complete all the 2^60 steps to produce a reliable result, you can't just run a quantum computer for a while, stop it, and then restart it.
Their existing post quantum encryption didn't do post compromise security (PCS) against quantum attackers. This new one does.
I am excited to finally know what they mean by PCS after reading this article. It means that the session keys from their key agreement scheme (n ratchet) are generated new so an attacker doesn't get them again after a fairly specific sort of compromise. So from that I get that the off the record (OTR) protocol also has PCS. Which is a bit disappointing, I thought that they had come up with some new concept.
This key agreement doesn't happen that often. So a user isn't going to notice any slowness even if it was significantly slower.
thank you for the explanation
From the article:
> "What does this mean for you as a Signal user? First, when it comes to your experience using the app, nothing changes. Second, because of how we’re rolling this out and mixing it in with our existing encryption, eventually all of your conversations will move to this new protocol without you needing to take any action. Third, and most importantly, this protects your communications both now and in the event that cryptographically relevant quantum computers eventually become a reality, and it allows us to maintain our existing security guarantees of forward secrecy and post-compromise security as we proactively prepare for that new world."
Sparse Post-Quantum Ratchet, or SPQR. Someone at Signal is a Roman history enjoyer.
How often do you think about the Roman Empire?
Not very. But the Roman Republic…
Or, just maybe, they are merely an enjoyer of chat apps (SPQR -> "speaker").
The (very weak) Caesar cipher was used in ancient Rome though and cryptography in general way before. It could be a silent nod to how far our achievements have gone and that encryption is a basic human desire since millennia.
Or maybe this SPQR is weak too /s
At first, I thought the article was published on an April Fools day...
Sono pazzi, questi Romani
Die spinnen, die Römer!
I would really like to see some modern comparisons of the Signal protocol to Matrix, MLS, etc. since it's hard to keep up with everything but it seems like things are still moving.
Wow, this is one of the most well written cryptography articles I've ever seen.
I consider myself a fairly experienced software engineer with a moderate amount of professional experience in private sector encryption, so I'm not completely out of my element, but many articles along this vein have my eyes glazing over halfway through the breakdown.
This one was actually easy for me to follow the entire time for once, despite explaining something I'm not familiar with.
This is really impressive, especially the way they've used formal verification. Great work.
Fantastic news! Awesome that the Signal team was able to deliver another first-class security feature.
Strange that they are posting about the "signal ratchet" when they just removed it by launching cloud backups that use a static key? Since those cloud backups include disappearing messages, that feature completely undoes all of the forward secrecy in this protocol.
That backup system presumably uses symmetric encryption, which is not nearly as vulnerable to quantum-accelerated attacks.
Yes, but you don't need a complicated ratcheting protocol if you've eliminated forward secrecy in other ways. This post is about "post compromise security," but there is already no post-compromise security after the cloud backups feature
Do you also think it's "strange" that they're introducing that (optional!) feature while also storing all the messages on your device? The cloud backup is strictly more secure than that on-device database. Their blog post on the subject also explicitly says it won't include disappearing messages that disappear within 24 hours.
It's not optional because you don't know whether the people you are communicating with have it enabled. One person in a group chat with the feature enabled undoes the forward secrecy for everyone in the group chat.
A cloud backup eliminates any forward secrecy. It used to be that in Signal, when you have a message on your device and it is deleted (or a disappearing message disappears), then it is truly gone and can never be recovered. Now with backups, since the key that was used to encrypt it to the cloud remains on your device, it can be recovered even after the message is deleted or disappears.
The only way to "truly" opt-out is to, as you say, set a disappearing message timer for <24 hours.
Yeah, and all of that's already true right now because messages are stored on those users' devices already. You'll be heartbroken to hear that those users can also take a screenshot of your disappearing messages and send it to anyone. There are fundamental limitations to what a messaging app can protect you from.
While the analog hole will always exist, and you can't make it actually impossible, Snapchat's quite good at that screenshot thing. Both platforms have APIs to prevent, or at least notify on the use of screenshot. It's weird that signal doesn't use any of them.
i know of ~3 currently working methods to take screenshots on snapchat
it isn't "weird that signal doesn't use any of them" because it does [1] use both, just not for giving a false sense of security to your correspondents
[1] https://support.signal.org/hc/en-us/articles/360043469312-Sc...
>but there is already no post-compromise security after the cloud backups feature
The feature is opt in, so I really don't see the issue here.
Signal can't protect you against the other party you are communicating with. They can backup the conversation, or screenshot it, or take a photo of the screen with another camera. They could also retell in their words what you sent.
You know (with pretty high certainty) that your conversational partner is using Signal. The security level of Signal affects your estimation of the security level of your partner.
Signal is lacking a crucial safety feature. To cover some background, it is necessary to set "Who can see my number" and "Who can find me by number" both to "Nobody", as this lowers the chances of spam messages and attempted hacks. Once these are set, the only way for someone to start a conversation with you is if they know your Signal username or QR link, both of which you can set in your Profile. The issue is that your link can be saved unsafely by your Contacts, and can be used multiple times, also by others, leaking it to hackers who can then send you unsolicited messages to compromise your device. The safety feature that would be good to have is to allow someone to contact me only via a one-time use link that cannot be reused by anyone.
This sounds like an excellent feature request that would shore up their anti-abuse endeavors more than them "lacking a very basic crucial safety feature".
Which of the so-called Signal competitors have implemented something like this already today?
Is it true that Signal was funded by the CIA or is that disinformation to try to get people to mistrust it?
Well, for some reason they're not worried about metadata. And the agencies mostly collect metadata...
This is not true, though? https://signal.org/blog/sealed-sender/
(Yes, I am aware Sealed Sender is not perfect and still susceptible to statistical attacks.)
Maybe my reading comprehension is failing me, but what does this mean for existing messages? I guess nothing of the have already been 'siphoned' to a 3rd party. As it couldn't retroactively apply to data not under Signals control of course..but what about existing messages already within their control?
Its interesting to imagine that somebody [1] is already now capturing encrypted internet traffic and storing it all long-term, to then hypothetically in 40-50 years or something decrypt it and draw value from that information. I suppose to blackmail future politicians, learn military secrets, whatever.
[1] NSA
> Its interesting to imagine that somebody [1] is already now capturing encrypted internet traffic and storing it all long-term, to then hypothetically in 40-50 years or something decrypt it and draw value from that information. I suppose to blackmail future politicians, learn military secrets, whatever.
You don't have to imagine, there's literally a NSA datacenter in Utah for doing just that.
https://en.wikipedia.org/wiki/Utah_Data_Center
That's exactly what I was thinking about too, but I was to lazy to find the link, thanks ;)
It's hard to tell as someone not in the field, but quantum computing seems to be moving faster than that? I'm not sure I believe two years, but:
Harvard physicists working to develop game-changing tech demonstrate 3,000 quantum-bit system capable of continuous operation
https://news.harvard.edu/gazette/story/2025/09/clearing-sign...
PsiQuantum Raises $1 Billion, Says Its Computer Will Be Ready in Two Years
https://archive.is/AEuan
As someone not in the field it's hard to distinguish the "quantum startup raised x billions, claims quantum computing x years away" from "fusion startup raised x billions, claims fusion power x years away" headlines every few months for the past 10+ years.
Headlines like these are the outliers to the trend that thus appear more credible to me personally: https://news.ycombinator.com/item?id=45238481
Thanks for the link. I skimmed through the report that the article is based on. It tracks rising activity in quantum computing R&D in several areas. But at least in the executive summary, I didn't see anything about commercial applications one way or the other. It doesn't seem to make any predictions?
So, it's odd that the article summarized it that way.
> Overall, quantum processing units (QPUs) are making impressive progress in performance, but they remain far from meeting the requirements for running large-scale commercial applications such as chemical simulations or cryptanalysis.
Page 6 it's a quote
> to blackmail future politicians
This seems to me the most valid reason. Any other secret is useless after 30 years.
Does this mean we're any closer to getting editable messages?
10 edits in 24 hours. Been that way for ages.
Signal already has editable messages
We're about minus five months away.
I remember editing messages a couple of years ago. Am I missing something?
It's been 2 years https://signal.org/blog/new-features-fall-2023/
Oh wow, time flies.
Update your app please
This is actually disturbing, as the article suggests that all previous messages sent using Signal are decryptable with quantum computers. If there are people with, for example, selfhosted mailservers sending PGP encrypted emails to each other, then, while they have to worry about them not leaking out from the server either by someone hacking to it or someone sniffing the traffic with the encrypted messages beforehand, they know for sure that their messages are safe.
Meanwhile Signal users have been sending messages onto signal servers for years now, as far as I know they aren't sent directly through some p2p protocol. I don't know what their policy is about storing messages, and I believe that they have a lot of other countermeasures, but it still points to the problem with Signals centralized nature.
As far as they say, messages are deleted once delivered, or retained up to 45 days if not:
(source: https://signal.org/blog/a-synchronized-start-for-linked-devi..., dated Jan. 2025)It is possible for them to say that they deleted the messages without actually deleting them though. One has to trust a pretty big company in order to not worry about the messages actually not being stored anywhere.
I'm not aware of all techniques that Signal uses to somehow make the message anonymous even when if the encryption would have been broken, but sealed sender seems to be one of them:
https://signal.org/blog/sealed-sender/
So at least there's that. Unless the encrypted sealed sender messages aren't somehow being fingerprinted by the IP address of client and the timestamps of connections. Signal probably also says that they don't log these, but with self hosted mailserver I wouldn't have to trust them on that too.