I’ve read and understood it to some extent (as I’m no expert) and it looks like a good answer. I assume @soatok you’ll write a blog as a response to them, until then I’ll wait for your blog.
1 Like
They still gloss over the removal of PFS which is Soatok’s main reason for already recommending against Session. I’m also not at all qualified to comment of Sessions response but given the lack of PFS I still think Session should be delisted. SimpleX Chat also seems superior in just about every way making Session effectively redundant.
Soatok added an edit for the first claim in their article:
EDIT (2025-01-16): In the interest of transparency, you should be aware that the following claim is being questioned by a few cryptography experts.
To resolve this discussion, I intend to write a proof of concept soon for the kind of attack I think is possible here, but on a much, much smaller scale (since I don’t have the resources of a nation state). I will update this post later with the results of my experiment.
I’m leaving the rest of the text unchanged so you can see the assertion intact.
Even if it turns out I’m mistaken about what follows this blue-boxed text, there is no question that Session’s security against batch attacks is severely downgraded from what you’d expect from Ed25519.
5 Likes
I’m curious @soatok what resources specifically do you think would be required to perform this?
Absolutely.
Their response isn’t 100% incorrect or misleading, but it warrants a correction. But first, a proof-of-concept script needs to be written. I will include it with the blog post I’m writing next.
2 Likes
I sorta gave you the answer in the blog post already: The ability to perform 2^64 queries in a reasonable amount of time.
Each query consists of, at minimum, a SHA512 hash and a scalar multiplication over an elliptic curve. That scalar multiplication is going to be the expensive part.
I can write quick and dirty scripts that perform ~10,000 to ~100,000 scalar multiplications per second on my computer (really, keypair generation).
2^64 is 18,446,744,073,709,551,616.
If I tried to do this all on my personal computer, it would take approximately 585,000 calendar years.
You can parallelize this pretty well, and write more optimal code than I did locally. WIth the NSA’s resources, you can probably parallelize this effort to 100,000,000 devices in a cluster (this is a Fermi estimate). If each device in the cluster is able to perform 100,000 queries per second, you can perform the attack in ~180,000 seconds (or about 3 days of dedicated compute).
That’s performing a batch attack against a 128-bit seed (what Session uses), using Pollard’s Rho to find collisions without requiring storage for 2^64 candidate keypairs on top of all this.
My proof-of-concept is going to be much more economical.
7 Likes
Most of these things have been previously dicussed and there were also papers written on the security of session messenger earlier.
I would agree there is an issue with the lacking PFS. The arguements for them not needing it are wrong in my opinion.
I’ve published my response (and proof-of-concept code) for Session’s blog post:
6 Likes
Thanks for response.
Signal is simply the only private messaging app I’ve looked at to date and haven’t been able to brutally criticize. I try several times a year to see if a new attack strategy I learned will work on their software, because it galls me to not have a notch in my belt for their software. (One of these days, goddammit!)
Have you read: SimpleX blog: SimpleX Chat v5.6 (beta): adding quantum resistance to Signal double ratchet algorithm ? (this now the default in v6 for 1-1 chats btw)
Double ratchet algorithm is used in Signal, Cwtch and SimpleX Chat. But Signal app by allowing to use the same profile on multiple devices compromises the break-in recovery function of Signal algorithm, as explained in this paper. Because of break-in recovery you cannot use SimpleX Chat profile on more than one device at the same time - the encryption scheme rotates the long term keys, randomly, and keys on another device become useless, as they would become useless for the attacker who stole them. Security always has some costs to the convenience.
- unlike Signal design that only added quantum resistance to the initial key exchange by replacing X3DH key agreement scheme with post-quantum PQXDH, but did not improve Signal algorithm itself, our design added quantum-resistant key agreements inside double algorithm, making its break-in recovery property also quantum resistant.
For the record, their messengers comparison chart in this blog is not very accurate. For example: https://xcancel.com/SamuelScheit/status/1880734632624406820#m
No, I haven’t read that yet. Thanks for sharing.
1 Like
There’s also Hi Meta, WhatsApp with Integrity? | by Tal Be'ery | Medium (no bloat frontend: scribe), Usenix paper and
presentation: WhatsApp with privacy? Privacy issues with IM E2EE in the Multi-device setting | USENIX, lastly: https://eprint.iacr.org/2022/1710.pdf
Another thread where I collected known vulnerabilities:
1 Like
Hmm… so Signal is safe or not and the problems raised in the links are still relevant since 2020?
Why is Signal so highly recommended, with so many security problems and disastrous communication?
Because is the golden standard in secure messaging at this moment.
I’ll preface this by saying these might be stupidly obvious questions to you, but they are not to me, a non-cryptographer/mathematician.
I have to say I think it would’ve been nice if you had published the times it took you to run your proofs of concept, how they relate to each other, and an explanation of how to interpret those results to justify the statement that an attack on 128-bit seeds is plausible to someone with far more resources.
My understanding is that what you are doing is proving you can find a 32-bit key in sqrt(2^32) steps, and therefore you are saying you could theoretically find a 128-bit key in sqrt(2^128) (or, 2^64) steps, is that right?
If so I guess my main question is the time it takes to run one of these queries compared to the time it takes to generate an SHA-1 hash, which we have plenty of benchmarks for on various GPU hardware. Is it expected to be very similar? Because if it takes much longer to run one of these queries in comparison then I am not sure how well the SHA-1 comparison holds up.
edit: I now see your runtimes are published in the readmes for each demo, so nvm. Still have the other questions though.
- Instead of Ed25519, I’m using the Ristretto255 group so I don’t have to deal with cofactors in my logic.
- Instead of half a SHA512, I’m using BLAKE2b (via libsodium).
I also don’t have the background knowledge in cryptography to know whether this makes a practical difference here, so I will just have to take your word that it does not, but I sort of expect Session to bring this up in their response.
Idk much about Ristretto255 tbh (this is actually the first time I hear about it)
But you can read about why they recommended BLAKE2b and the libsodium library here GitHub - samuel-lucas6/Cryptography-Guidelines: Guidance on implementing cryptography as a developer.
Disclaimer: this is my summary based on what I discussed with my friend. I’m not a cryptographer.
This is a theoretical attack, not a practical one.
The researcher is effectively saying that if:
-
An attacker has possession of a substantial number of Session keys. If Session is like Signal in this way, then each message is a key. A realistic number is about 4 billion or 2^32. Why? Because it’s effectively impossible to break 1 in 2^128, but it’s within possibility to break 2^(128-32) = 2^96. To get down to 2^64, they would need 2^64 keys, or 18 quintillion.
-
An attacker expends significant resources attempting to decrypt the key. Think (very) roughly the current hashing power of the entire Bitcoin network. Basically, some global-scale compute resources.
After that effort, an attacker would succeed within a reasonable time (e.g. within an average human lifetime, I don’t know the exact time) at decrypting one random key (probably one random message).
Is it reasonable to have approximately 4 billion Session keys? Session is a small network and uses (at least partially) decentralized message routing. Even if Session was this widely used, the attacker would need to infect enough Session nodes or run enough of their own nodes to get keys of this magnitude.
Then, is it really that practical to expend all this effort to decrypt one random message?
Clearly Session’s approach is not as good as Signal’s, and to the researcher’s point, you should use Signal if this is a concern for you. However, the issues described in these two blog posts are not practical concerns for the vast majority of threat models.
Hey guys
Just looking at this now, as i wasn’t previously aware that there was a thread here. We have responded to all the claims made by Soatok in a blog post here: A Response to Recent Claims About Session's Security Architecture - Session Private Messenger . We have updated the blog post to include a response to their PoC Code and updated claims about the security of Session keys.
In short,
- “Security issue” 1 achieves no reduction in the operations required to crack a single targeted Session account/key, this still requires 2^127 operations on average. A worst case multi-target / batch attack implemented using a linear search achieves an improvement on the ability to break a random key out of a extremely large group of keys, but even with the improvement would still take ~22,000 times the amount of power consumed globally each year to compromise a single random key out of 4 billion + keys, representing no practical impact to Session users.
- “Security issue” 2 is not a security issue because of checks which occur on the message and sender before the “In band” signature is validated
- “Security issue” 3 is not a security issue because it was based on a misreading of Session code, as confirmed by Soatak
- “Gripe” 1 has no impact
- “Gripe” 2 has no impact
Just to provide some clarity to the points raised by SGP.
Session has more than 1 million Monthly active users, each of these users typically has only one Ed25519 key, so the the actual number of Session keys which could be used in a multi-target / batch attack is probably closer to a couple of million keys rather than 4 Billion. But in our worse case scenario we assumed that Session had 4 Billion active users to show that Session remains safe even with extensive growth. Further to this, since there is no central location where these public keys are stored its unclear how an attacker could even gather such a large amount of keys.
Regarding the rough calculation that you could leverage a network with the number of operations (hashes) per second that Bitcoin achieves. This was my initial thought too, but the operations used in a multi-target / batch attack are actually EC Base point multiplications rather than hashes, which are many times more computationally expensive than hashes. So the number of operations per second which can be achieved is actually many many times less than the entire Bitcoin network achieves.
Privacy guides already places a note on Session regarding the lack of PFS, and considering that none of the issues raised by the security researcher have practical impact, i don’t think there has been any change to the security profile of Session which would justify removal from Privacy Guides.
Session offers a unique set of properties not achieved by other messaging applications. No phone number sign up, Onion routing by default, and a use of a decentralized network, while having highly usable cross platform clients which maintain synchronization.
Happy to provide any more context if needed.
6 Likes
@KeeJef thank you for the detailed update to the blog post, especially the review of the PoC code. I tried to write a paragraph about how the PoC didn’t document failures, but I didn’t know how to word it very well. Your post helps clear things up there.
Regarding forward secrecy, was the main reason for not including it complexity, efficiency, or something else?
1 Like
I feel that addendum there is the only response Session deserves, given their present conduct.