Last week, I wrote a blog post succinctly titled, Don’t Use Session. Two interesting things have happened since I published that blog: A few people expressed uncertainty about what I wrote about using Pollard’s rho to attack Session’s design (for which, I offered to write a proof of concept and report back with results), and Session wrote a blog claiming to rebut the claims made in that blog post.

Rather than make a messy edit of my previous blog post, I thought a follow-up would be warranted.

This is a little more tedious than my usual fare, so I’m going to start with the important parts (mainly concerning the proof-of-concept) and then get into the weeds of responding to Session’s statements.

Breaking Short Seeds for Ed25519

In my previous blog, I alluded to using Pollard’s rho to attack Session’s software.

Several people were kind enough to question this claim, suggesting that even a very weak seed wouldn’t matter for using Pollard’s rho algorithm, since the SHA512 hash diffuses the bits and doesn’t preserve enough algebraic structure for the algorithm to work.

Their objection is entirely correct, but that’s not actually relevant to the attack I had in mind when I wrote that. The trouble is, I was getting my wires crossed on the nomenclature.

If you’re deeply interested in this topic, please pay very close attention to the next part, or else you may end up confused as well.

There are different attacks that are known as “Pollard’s Rho Method”.

When I wrote this section of my previous blog post, I was remembering this 1995 paper: Parallel Collision Search with Cryptanalytic Applications, by Paul C. van Oorschot and Michael J. Wiener, which discusses using one of the Pollard’s Rho methods to find collisions in cryptographic primitives that behave like a random function.

The confusion here was my mistake.

But I don’t think it’s difficult to see why such a mistake occurred. In fact, the acknowledgements section of this paper includes the following statement:

“We would like to thank John Pollard for correcting a note about [4] and for clarifying a fundamental difference between his two rho-methods.”

I feel like this validates “naming things” as one of the hard problems in computer science.

Acknowledgements, Page 24

The idea behind the linked paper is you can use the Rho Method to perform a collision attack against any random function in roughly time without requiring memory. The authors discuss attacking a block cipher (DES) this way, as well as the MD5 hash function. The algebraic structure that other cryptography experts were getting hung up on isn’t actually required for this technique.

This is why I made mention of batch attacks right before mentioning Pollard’s rho.

An astute reader might wonder, “So what? We have birthday collision attacks against random functions too, at the same bounds.”

But Birthday attacks have storage costs (you need to not only measure samples, but also store all of the prior samples taken, in order to find a colliding pair.

Using Pollard’s Rho method saves you from having to figure out how to store things in workable memory. This also lets you parallelize your searches.

The Rho Less Travelled

Given the existence of this technique for parallel collision searching, and the fact that the more straightforward application of one of Pollard’s rho methods is used for breaking the ECDLP in queries, it seemed plausible to me to turn this into a practical attack against 128-bit seeds.

However, the wording I used when speculating about this possibility was confusing, even to me when I read it the next morning. I definitely had a wire crossed somewhere.

I have since removed the confusing parts (after capturing a snapshot with the Internet Archive for full transparency).

Speculation About Government Capabilities

I had previously mixed speculation in with my criticism of Session’s protocols, which magnified the confusion of the previous blog post in its original form. That was a mistake, but I do want to (in a dedicated session) state my point clearly.

If there exists any variant of this attack that successfully solves the ECDLP in the setup Session uses, I sure as hell don’t know it–as I admitted very plainly in my previous blog post.

If anyone does happen to know of such a mathematical technique along these lines, it’s probably a classified government secret (given how many American mathematicians and cryptanalysts work for the NSA). It would make for a tantalizing target to develop into an intelligence capability, as it’d be effectively “NOBUS” to anyone without the same computational resources.

Additionally, such an exploit also wouldn’t weaken the ECDLP security of any other system that didn’t use truncated seeds, as Session does.

But enough about that.

I promised a proof-of-concept for the attack I was envisioning, so let’s get to it.

PoC || GTFO

As I mentioned previously, I do not have the computing resources available to me to perform the actual attack. While is certainly attainable for nation states, it’s far beyond the budget of furry bloggers.

I’ve constructed and published a few demo scripts to test this attack, with a few changes (mostly economical and for convenience):

1. Instead of a 128-bit seed, I start with a 16-bit seed and then graduate to a 32-bit seed.
2. Because clamping and cofactors are annoying to deal with, I work over the Ristretto group (which libsodium provides a great implementation of).

You can find the proof of concept scripts here on GitHub.

The demo scripts are as follows:

1. Demo Script 1 attacks 256 public keys generated from 16-bit seeds. This should be extremely quick (unless you don’t have libsodium installed).
2. Demo Script 2 attacks 65,536 public keys generated from 32-bit seeds. This is a straightforward scaling of script 1.
3. Demo Script 3 attacks 32,768 public keys generated from 32-bit seeds. This should take more steps, but each step should be slightly faster (and keygen should be faster too), so it sometimes outperforms Demo 2.
4. Demo Script 4 attacks 16,384 public keys across 128 different processes, using GNU parallel.

These proof-of-concept scripts use a modification of Pollard’s Rho to find collisions. Given that we know the input at each step of the way, this reveals the secret key.

At each step, what we’re actually doing is this:

1. Take the first k bits of the public key, then pad with zeroes, to get the seed for the next iteration.
2. Hash the result with BLAKE2b.
3. Perform a scalar multiplication of the base point for the Ristretto group. This is your public key.
4. Repeat (in parallel) until a result is found.

These scripts are not optimized. Hell, I wrote them in PHP of all languages.

But you can play with them and see how this sort of attack strategy scales up to different degrees of parallelism, different batch sizes, and different seed sizes.

What’s The Takeaway?

Batch key-recovery attacks do work against short seeds. The practicality of attacking 128-bit seeds is definitely in the reaches of a powerful adversary that exists today.

Re: Session’s Response Blog

The first thing I want to note about Session’s blog responding to my previous one is that they tried to debunk parts of my blog post that didn’t need debunking.

Session mnemonic decoding isn’t done in constant-time

Although this finding is correct, it doesn’t have any practical impact. […]

I have to wonder: Why did they think it was listed as a gripe, not a security issue?

Of course there’s no practical impact!

I never claimed it had practical impact. I even said, quite explicitly, “This isn’t a real security problem.”

Ability to force Android clients to run an Argon2 KDF

This code is only run when looking up ONS usernames. It is not possible to force other Session clients to perform this Argon2 KDF at will, since ONS lookups are only ever triggered by explicit user action. This KDF is done to maintain backwards compatibility with old format ONS records; new ONS records do not use Argon2.

This one wasn’t even listed as a gripe, just a remark in the closing section about something I found funny in the code.

But let’s really chew on this for a moment, because I think it’s a great starting point for understanding the blind spots of Session’s development team.

Specifically, this part:

This KDF is done to maintain backwards compatibility with old format ONS records; new ONS records do not use Argon2.

Let’s take a moment talk about protocol design.

Interlude: Protocol Design

Any time you design a communications protocol, you will inevitably have at least one state machine–whether implicit or explicit. When you’re working with cryptography, you want to minimize the number of variant conditions in your state machines.

If an attacker can modify a ciphertext and subsequently alter which cryptographic protocol is being run, that’s often problematic (the devil’s in the details).

The worst offender here is JSON Web Tokens, which offers an alg header for a token… for which none be a valid option. This frequently bites users. This is why I argue for cryptographic alacrity and versioned protocols instead of in-band signaling and cryptographic agility. My approach minimizes the number of variants (and the ways to trigger them) in your state machines.

Attackers generally don’t care about your “only for backwards compatibility” policies. In fact, that’s very often a beacon that says, “Try to exploit me.”

Back to Session’s Blog Post

That’s why I found this code funny. If you can find a way to delete the nonce from a payload, you can trigger a much more expensive operation before the contents are rejected. This sort of resource asymmetry is often exploited in denial-of-service attacks, but I didn’t claim to have found one.

That the presence or absence of a nonce in a payload is the only condition that triggers an variant in their system’s behavior (and a much more resource intensive one, to boot) was, and still is, fucking hilarious!

You don’t need to try to rebut my sense of humor. Not everyone gets tickled by the same things I do. That’s fine! It’s not even listed as a finding or a gripe, just an amusing observation in the code.

And yet, Session still tried to debunk it.

They were so quick to try to save face that they didn’t stop for a moment and ponder, “Maybe we misunderstood something.”

Fascinating.

Anyway, let’s dig into their responses to the security issues.

On Session’s Rebuttal for Claim 1

Claim 1: Session Ed25519 keys are generated with insufficient entropy and provide only 64 bits of security

At a high level, we believe this claim is incorrect, but let us walk through the key generation process in Session and explain why.

[…]

If the described attack is possible, it should be fairly easy to validate this claim by publishing a PoC showing that this attack is feasible using a smaller amount of entropy to limit computation time. Session developers have been unable to reproduce the author’s claimed reduction in security.

See above: Breaking Short Seeds for Ed25519.

Libsodium goes out of its way to encourage developers to use full 256-bit seeds in their Ed25519 API. Session went out of their way to reduce this to 128 bits.

The attack strategy demonstrated by the Proof of Concept does not work with 256-bit random seeds. Full stop.

On their FAQs page, Session’s response to “are you rolling your own cryptography?” can be abbreviated to, “No, we use libsodium!”

But that statement is extremely misleading.

Session, you’ve absolutely rolled your own cryptography, even if it is atop libsodium! You’ve gone out of your way to bypass one of libsodium’s guard-rails to use shorter Ed25519 seeds. There’s more custom cryptography to be found, as I’ll dig into in the other claims. It’s not particularly damning custom cryptography, but it does make a liar out of whoever wrote that FAQ entry.

On Session’s Rebuttal for Claim 2

Claim 2: The validation process for Ed25519 signatures is “in band”

The author has misinterpreted Session code, and has missed various validation steps which are performed on the senders message and identity in other code blocks. Taken as a whole, the message and sender validation process in Session provides no way to spoof the origin or contents of a message.

The most interesting thing about their attempted rebuttal here is its emphasis on trying to debunk a claim I never made in my original blog post.

Specifically: I never claimed any impact for this finding, only that it’s a badly designed step in a cryptographic protocol.

And, sure, if you have other code blocks to validate the sender’s message and identity, you can mitigate the risk of a full exploit.

But that’s not the problem. The problem is that Session’s code grabs a public key from a payload, and then uses it to validate the signature on the same payload.

As I wrote in the section leading up to the rebuttals, this failure to understand cryptography protocol design is blatant. It’s alarming to find something like this in a messaging app that people broadly compare against Signal, which doesn’t have any astonishing aspects to their messaging protocol.

Interlude: Connecting Claims 1 and 2

With the proof of concept above, I’ve demonstrated that the batch attacks to find a collision against the 128-bit seeds is nontrivial, but likely well within the resources available to a powerful adversary.

To be abundantly clear, a collision attack isn’t a preimage attack. It makes batch attacks (where your goal is to compromise any user, rather than a targeted user) achievable.

This Ed25519 keypair is where the public key for issue 2 is supposed to come from. The identity binding in Session is based on a birationally equivalent X25519 public key, which is part of a person’s identity.

Here’s something to think about:

• A successful collision against the seed recovers the same Ed25519 keypair.
• A given Ed25519 keypair is birationally equivalent to one X25519 keypair, via libsodium’s APIs.
• This X25519 public key is a long-term key used to encrypt messages throughout Session’s protocol.

That last bullet point is where forward secrecy should save the god damn day.

In Signal, if you compromise a user’s long-term identity key, you don’t immediately get to decrypt every ciphertext sent to the user you’ve intercepted in the past. That’s the whole fucking point of forward secrecy.

With Session, you just don’t get this protection. They deliberately removed in in 2020. Without forward secrecy, a successful batch attack lets you compromise all historical ciphertexts you’ve intercepted for the recipient.

If you try to handwave “but they can’t intercept the ciphertext”, you’re missing the point of secure protocol design: You assume an adversary has some powerful capabilities, and then design your systems to still adequately protect users from that adversary. Ideally, you also document the hell out of these capabilities in your threat model.

If your threat model for an app that tries to compete with Signal is “infrastructure is never compromised” and “active attacks never happen”?
I think I have a bridge to sell you.

What’s The Fix?

Use 256-bit seeds, not 128-bit, like libsodium’s API has always encouraged you to.

The remark in the 2021 Quarkslab audit about “13 words vs 25 words” for recovery phrases is ridiculous:

This reduction was deliberately chosen to provide Session users with more usable 13-word recovery phrases as opposed to the 25 words which would be required if using a 256-bit key.

Quarkslab 2021 audit of session, page 5.

If your typical user’s routine experience with recovery phrases is significantly more involved than “copy and paste from password manager” or “transcribe from handwritten note stored in a fireproof safe,” then there’s something fundamentally wrong with your app.

Session’s Rebuttal for Claim 3 is Correct

The third heading in my blog post under the Security Issues category discussed a place in their code where they appeared to pass an X25519 public key to AES-GCM as the symmetric key.

I will reproduce the relevant section of their rebuttal in its entirety:

Claim 3: Session reuses public keys as private keys for symmetric onion requests

This claim is plainly incorrect, because the author has misinterpreted the code. 

The author mentions the encrypt function and links to the wrong overload of that function.  Instead the one being called is the later overload, of the same name, which takes the public key but then also uses an ephemeral locally generated private key to compute a shared secret. This shared secret, computable only by the request creator and the Service Node, is then passed into the function that the author is linking to.

The code for both encrypt functions, which are side-by-side in the code, can be viewed here

They are correct on this point: I did misinterpret the code. That is my mistake, and I apologize for any confusion on that.

But let’s also take a closer look at the code in question.

1. The file is named AESGCM.kt, and the class is named AESGCM so you would expect it to implement AES-GCM. Anything outside of AES-GCM would be astonishing.
2. There are two encrypt() functions, because Java and Kotlin support method overloading as long as the type signatures differ.
3. For flavor, there is only one decrypt() function.
4. The second encrypt() function (the one that accepts a string rather than a byte array) implements X25519 wrapping, then calls the first one.
5. There is yet another algorithm (HMAC-SHA256, with a secret key set to “LOKI”) for hashing the X25519 scalar multiplication result. Hashing is important to prevent Cheon’s attack (as discussed here), but this ain’t AES-GCM.

Why the hell would anyone write cryptography code this way?

Cryptography code should be boring: Obviously secure, at a security level that is obviously at least 100-bit, with no cleverness or magic to it.

“Boring” is important to make it easy to independently verify claims made by the software vendor’s marketing department.

The most alarming thing isn’t that I misinterpreted the code and took it for something patently absurd, but rather that someone could look at Session’s source code and misinterpret it to be safer than it is.

Other Astonishing Cryptographic Software

There is so much about Session’s ecosystem that is goddamn YOLO that I omitted from my previous blog post.

For example, they ship a TypeScript implementation of Curve25519 without any unit tests. This appears to be used by their Desktop app.

Despite being TypeScript, it’s full of type declarations that look like this:

function gf(init?: any) {}
function ts64(x: any, i: any, h: any, l: any) {}
function vn(x: any, xi: any, y: any, yi: any, n: any) {}
function crypto_verify_32(x: any, xi: any, y: any, yi: any) {}
function set25519(r: any, a: any) {}
function car25519(o: any) {}
function sel25519(p: any, q: any, b: any) {}
function pack25519(o: any, n: any) {}
function neq25519(a: any, b: any) {}
function par25519(a: any) {}

/* ... etc. but these are internal functions. What about the public API? */

export function sharedKey(secretKey: any, publicKey: any) {}
export function signMessage(secretKey: any, msg: any, opt_random: any) {}
export function openMessage(publicKey: any, signedMsg: any) {}
export function sign(secretKey: any, msg: any, opt_random: any) {}
export function verify(publicKey: any, msg: any, signature: any) {}
export function generateKeyPair(seed: any) {}

That doesn’t inspire much confidence, does it?

The reason I omitted mentioning this library in my previous post is that I wrote a simple testing harness for Wycheproof and it didn’t find anything (presumably because it was ported from TweetNaCl.js), so it didn’t feel worth mentioning.

But I don’t want to focus only on the negative, so here’s something nice: My favorite part of this Curve25519 code is where it enforces a seed length of 256 bits instead of padding it with zeroes.

if (seed.length !== 32) throw new Error('wrong seed length');

What’s The Score?

My previous blog post stated my position on Session as an alternative to Signal, which is answerable by that blog post’s title.

To add weight to my reasons to not recommend Session, I included observations about their cryptographic security design–some which have security implications, and others which do not.

Session responded to my blog post–while failing to actually link to it (or an archived snapshot of it).

Here’s a recap of how their response blog holds up:

1. Session claimed that the 128-bit seeds are not an issue.
   Incorrect. See: Proof-of-Concepts.
2. Session insisted that their “trust attacker-provided public key to validate attacker-provided signature” design flaw doesn’t lead to a practical impact.
   Misleading. Such an outcome wasn’t claimed to begin with.
3. Session claims I misinterpreted their AES-GCM code.
   Correct, but they may want to make their software less astonishing to reviewers.
4. Session went out of their way to insist that the timing leak on mnemonic decoding I griped about has no practical impact.
   Unnecessary.
5. Session pledged to fix their usage of SecureRandom to follow best practices on Android.
   Great! This is probably the only part of their blog post that wasn’t screaming ego.
6. Session doubled down on their removal of forward secrecy.
   Stupid. As I mentioned above, forward secrecy would limit the blast radius of a successful batch attack (which is only vaguely possible because of their short keys).
7. Session tried to debunk an argument I did not make about their usage of Argon2.
   Unnecessary.

That’s 2 good responses out of 7 (or about 28%). Not a passing score in my book.

Bonus: Forward Secrecy with Onion Routing

It’s actually really easy to include PFS with Session’s design, should they actually care about post-compromise security for their users.

This isn’t even the hardest concept in the world, either.

Are you with me?

Tunnel SignedPreKeys over the same fucking channel you use to send encrypted messages, then keep Signal’s excellent ratcheting protocol in place.

If you need a higher layer that doesn’t utilize it because of some onerous technical requirements, then just wrap your forward-insecure protocol around a forward-secure protocol.

Conclusion

I stand by what I said previously: Don’t Use Session.

The fact that they forked Signal and deliberately moved forward secrecy from the protocol was already sufficient reason to never trust it.

What they replaced forward secrecy with does not pass muster for secure cryptographic software.

Session’s use of 128-bit seeds is only secure against poorly-resourced adversaries (as my proof of concept demonstrates).

Their protocol design decision to trust the attacker-provided Ed25519 public key to verify an attacker-provided signature is simply bone-headed, even if it isn’t exploitable.

Do you know what software provides end-to-end encryption and doesn’t do weird shit? I’ll give you a hint: It’s not a very long list.

What To Use Instead?

Signal, for all its other faults, provides excellent cryptographic security.

I can’t recommend Signal without some jackass insisting I’m being paid to promote Signal.

I’m not. This blog is not monetized in any way. I actually pay a modest amount to keep it online, ad-free, because I want a place I can express myself without being pressured to sell something.

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!)

My peers tell me that iMessage and WhatsApp are both good too, but I can’t review their source code, so who knows?

Furthermore, I’m hesitant to ever recommend products or services from Meta, the company that owns WhatsApp.

WhatsApp uses the Signal protocol, so if anyone disregards my advice and uses it, that’s not the worst choice.

To my knowledge, there isn’t currently an anonymous-first, cross-platform messaging app that offers end-to-end encryption and has a great user experience that meets the bar for applied cryptography. Sorry to say.

That isn’t to say that one cannot ever be developed. I’m working on a project to bring end-to-end encryption to the Fediverse, after all. Some of the work I’m doing there may be useful for building a next generation private messenger.

An Appeal To Tranquility

Finally, I would really appreciate it if the folks reading these blogs would do me one quick favor:

DO NOT ASK ME “What about [other app]?”

I’ve been needled by a fuckton of these requests and queries over the past year or so. It’s extremely exhausting, and they never seem to stop.

If it’s not on this list, I don’t have an opinion to share.

If you really want to know what a cryptography expert thinks of their designs or software, ask the app if they have any third-party audit reports first.

(For example: SimpleX was audited in December 2024. Don’t ask me about SimpleX, you have a goddamn report from professionals I respect right there.)

If a vendor don’t have any audits from the past 2 years, but their software has changed a lot since then, don’t fucking trust it–especially if their audit report is from a no-name security vendor and it claims the vendor’s product is perfect.