Categories

Threema: Three Strikes, You’re Out

Threema boldly claims to be more secure than Signal. Does this hold up to scrutiny?

(If you aren’t interested in the background information, feel free to skip to the meat of this post. If you’re in a hurry, there’s a summary of results at the end.)

Around this time last year, I was writing Going Bark: A Furry’s Guide to End-to-End Encryption and the accompanying TypeScript implementation of the Extended 3-Way Diffie-Hellman authenticated key exchange (Rawr X3DH). In that blog post, I had said:

The goal of [writing] this is to increase the amount of end-to-end encryption deployed on the Internet that the service operator cannot decrypt (even if compelled by court order) and make E2EE normalized. The goal is NOT to compete with highly specialized and peer-reviewed privacy technology.

This effort had come on the heels of my analysis of bizarre choices in Zoom’s end-to-end encryption, and a brief foray into the discussion into the concept of cryptographic deniability.

I’m stating all this up-front because I want to re-emphasize that end-to-end encryption is important, and I don’t want to discourage the development of E2EE. Don’t let a critical post about someone else’s product discourage you from encrypting your users’ data.

Until recently, but especially at the time I wrote all of that, Threema had not been on my radar at all, for one simple reason: Until December 2020, Threema was not open source software.

In spite of this, Threema boasts over 1 million installs on the Google Play Store.

Partly as a result of being closed source for so long, but mostly the Threema team’s history of over-emphasizing the legal jurisdiction they operate from (Switzerland) in their claims about privacy and security, most of the cryptography experts I know had quietly put Threema in the “clown-shoes cryptography” bucket and moved on with their lives. After all, if your end-to-end encryption is well implemented and your engineers prioritized privacy with metadata collection, jurisdiction shouldn’t matter.

What changed for me was, recently, a well-meaning Twitter user mentioned Threema in response to a discussion about Signal.

In response, I had casually glanced through their source code and pointed out a few obvious WTFs in the Twitter thread. I had planned on following up by conducting a thorough analysis of their code and reporting my findings to them privately (which is called coordinated disclosure, not “responsible disclosure”).

But then I read this bit of FUD on their Messenger Comparison page.

Signal requires users to disclose personally identifiable information. Threema, on the other hand, can be used anonymously: Users don’t have to provide their phone number or email address. The fact that Signal, being a US-based IT service provider, is subject to the CLOUD Act only makes this privacy deficit worse.

Threema – Messenger Comparison

Thus, because of their deliberate misinformation (something I’ve opposed for years), Threema has been disqualified from any such courtesy. They will see this blog post, and its contents, once it’s public and not a moment sooner.

How Are Threema’s Claims FUD?

The quoted paragraph is deceptive, and was apparently designed to make their prospective customers distrustful of Signal.

The CLOUD Act isn’t black magic; it can only force Signal to turn over the data they actually possess. Which is, as demonstrated by a consistent paper trail of court records, almost nothing.

That’s it.

The Signal blog

Additionally, their claim that “Threema […] can be used anonymously” is, at best, a significant stretch. At worst, they’re lying by omission.

Sure, it’s possible to purchase Threema with cryptocurrency rather than using the Google Play Store. And if you assume cryptocurrency is private (n.b., the blockchain is more like tweeting all your financial transactions, unless you use something like Zcash), that probably sounds like a sweet deal.

However, even if you skip the Google Play Store, you’re constantly beaconing a device identifier to their server (which is stored on your device) whenever a license key check is initiated.

Bear in mind, over 1 million of their installed base is through the Google Play Store. This means that, in practice, almost nobody actually takes advantage of this “possibility” of anonymity.

Additionally, their own whitepaper discusses the collection of users’ phone number and email addresses. Specifically, they store hashes (really HMAC with a static, publicly known key for domain separation, but they treat it as a hash) of identifiers (mobile numbers, email addresses) on their server.

Circling back to the possibility of anonymity issue: When it comes to security (and especially cryptography), the defaults matter a lot. That’s why well-written cryptographic tools prioritize both correctness and misuse resistance over shipping new features. The default configuration is the only configuration for all but your most savvy users, because it’s the path of least resistance. Trying to take credit for the mere existence of an alternate route (bypassing the Google Play Store, paying with cryptocurrency) that few people take is dishonest, and anyone in the cryptography space should know better. It’s fine to offer that option, but not fine to emphasize it in marketing.

The only correct criticism of Signal contained within their “comparison” is that, as of this writing, they still require a phone number to bootstrap an account. The phone number requirement makes it difficult for people to have multiple independent, compartmentalized identities; i.e. preventing your professional identity from intersecting with your personal identity–which is especially not great for LGBTQIA+ folks that aren’t out to their families (usually for valid safety reasons).

This obviously sucks, but fails to justify the other claims Threema made.

With all that out of the way, let’s look at Threema’s cryptography protocol and some of their software implementations.

Threema Issues and Design Flaws

To be up front: Some of the issues and design flaws discussed below are not security vulnerabilities. Some of them are.

Where possible, I’ve included a severity rating atop each section if I believe it’s a real vulnerability, and omitted this severity rating where I believe it is not. Ultimately, a lot of what’s written here is my opinion, and you’re free to disagree with it.

Issues With Threema’s Cryptography Protocols

This first discussion is about weaknesses in Threema’s cryptography protocol, irrespective of the underlying implementation.

At its core, Threema uses similar cryptography to Tox. This means that they’re using some version of NaCl (the library that libsodium is based on) in every implementation.

This would normally be a boring (n.b. obviously secure) choice, but the security bar for private messaging apps is very high–especially for a Signal competitor.

It isn’t sufficient for a secure messenger competing with Signal to just use NaCl. You also have to build well-designed protocols atop the APIs that NaCl gives you.

No Forward Secrecy

The goal of end-to-end encryption is to protect users from the service provider. Any security property guaranteed by transport-layer cryptography (i.e. HTTPS) are therefore irrelevant, since the cryptography is terminated on the server rather than your peer’s device.

The Threema team claims to provide forward secrecy, but only on the network connection.

Forward secrecy: Threema provides forward secrecy on the network connection (not on the end-to-end layer).

What makes Threema secure?

This is how Threema admits a weakness in their construction. “We offer it at a different [but irrelevant] layer.”

Their whitepaper acknowledges this deficit.

As I’ve demonstrated previously, it’s not difficult to implement Signal’s X3DH AKE (which offers forward secrecy) using libsodium. Most of what I’ve done there can be done with NaCl (basically use SHA512 instead of BLAKE2b and you’re golden).

The X3DH handshake is essentially multiple Curve25519 ECDH handshakes (one long-term, one short-term e.g. biweekly, one totally ephemeral), which are mixed together using a secure key derivation function (i.e. HKDF).

To the state of the art for secure messaging that Threema claims, Forward Secrecy is table stakes. Threema’s end-to-end encryption completely lacks this property (and transport-layer doesn’t count). No amount of hand-waving on their part can make this not a weakness in Threema.

The specification for X3DH has been public for 5 years. My proof-of-concept TypeScript implementation that builds atop libsodium is nearly a year old.

If the Threema team wanted to fix this, it would not be hard for them to do so. Building a usable messaging app is much harder than building X3DH on top of a well-studied Curve25519 implementation.

Threema IDs Aren’t Scalable

Severity: Low
Impact: Denial of Service

Threema IDs are 8-digit alphanumeric unique identifiers, chosen randomly, that serve as a pseudonymous mapping to an asymmetric keypair.

This means there are $36^{8}$ possible Threema IDs (2.8 trillion). This is approximately $2^{41.3594}$, so we can say there’s about a 41-bit keyspace.

That may seem like a large number (more than 100,000 the human population), but they’re chosen randomly. Which means: The birthday problem rears its ugly head.

Threema will begin to experience collisions (with 50% probability) after $2^{20.6797}$ (roughly 1.7 million) Threema IDs have been reserved.

At first, this won’t be a problem: If you collide with someone else’s Threema ID, you just have to generate another one. That’s just an extra round-trip for the Threema server to say “LOL NO try again”. In fact, given the Google Play Store estimates for the number of Threema installs, they’re probably in excess of the birthday bound today.

Quick aside: One known problem with Threema IDs is that users don’t know they’re supposed to back them up, so when they switch phones, they lose access to their old IDs and secret keys. Aside from the obvious social engineering risk that emerges from habitually tolerating new Threema IDs for all contacts (“I lost my old Threema ID, again, so blindly trust that it’s me and not a scammer”), there’s a bigger problem.

Since Threema IDs are used by each app to identify peers, it’s not possible for Threema to recycle expired IDs. In order to do so, Threema would need to be able to inspect the social graph to determine which Threema IDs can be freed, which would be a huge privacy violation and go against their marketing.

So what happens if someone maliciously reserve-then-discards billions of Threema IDs?

Due to the pigeonhole principle, this will eventually lead to an address space exhaustion and prevent more Threema users from being onboarded. However, trouble will begin before it gets this far: At a certain point, legitimate users’ attempts to register a new Threema ID will result in an unreasonable number of contentions with reserved IDs.

Neither the Threema website nor their whitepaper discusses how Threema can cope with this sort of network strain.

This problem could have been prevented if the Threema designers were more cognizant of the birthday bound.

Additionally, the fact that Threema IDs are generated server-side is not sufficient to mitigate this risk. As long as IDs are never recycled unless explicitly deleted by their owner, they will inevitably run head-first into this problem.

Peer Fingerprints Aren’t Collision-Resistant

Severity: Informational
Impact: None

From the Threema whitepaper:

Truncating a SHA-256 hash to 128 bits doesn’t give you 128 bits of security against collision attacks. It gives you 64 bits of security, which is about the same security that SHA-1 gives you against collision attacks.

This is, once again, attributable to the birthday bound problem that affects Threema IDs.

Related: I also find it interesting that they only hash the Curve25519 public key and not the combination of public key and Threema ID. The latter construction would frustrate batch attacks by committing both the public key (which is random and somewhat opaque to users) and the Threema ID (which users see and interact with) to a given fingerprint:

• Finding a collision against a 128-bit probability space, where the input is a public key, can be leveraged against any user.
• Finding a collision against a 128-bit probability space, where the input is a public key and a given Threema ID, can only be leveraged against a targeted user (i.e. that Threema ID).

Both situations still suck because of the 128-bit truncation, but Threema managed to choose the worse of two options, and opened the door to a multi-user attack.

Impact of the Peer Fingerprint Bypass

To begin with, let’s assume the attacker has compromised all of the Threema servers and is interested in attacking the security of the end-to-end encryption. (Assuming the server is evil is table stakes for the minimum threat model for any end-to-end encrypted messaging app.)

Imagine a situation with Alice, Bob, and Dave.

Alice pushes her Threema ID and public key to the server (`A_id, A_pk`), then chats with Bob legitimately (`B_id, B_pk`). Bob suggests that Alice talks to his drug dealer, Dave (`D_id, D_pk`).

The attacker can obtain knowledge of everyone’s public keys, and begin precomputing fingerprint collisions for any participants in the network. Their first collision will occur after $2^{64}$ keypairs are generated (with 50% probability), and then collisions will only become more frequent.

What happens when an attacker finds fingerprint collisions for people that are close on the social graph?

When Alice goes to talk with Dave, the attacker replaces her public key with one that collides with her fingerprint, but whose secret key is known to the attacker (`M_pk1`). The attacker does the same thing in the opposite direction (`D_id, M_pk2`).

When Alice, Bob, and Dave compare their fingerprints, they will think nothing is amiss. In reality, an attacker can silently intercept Alice’s private conversation with Dave.

The full range of key exchanges looks like this:

```  Alice -> Bob:  (A_id, A_pk)
Alice -> Dave: (A_id, M_pk1)
Bob -> Alice:  (B_id, B_pk)
Bob -> Dave:   (B_id, D_pk)
Dave -> Bob:   (D_id, D_pk)
Dave -> Alice: (D_id, M_pk2)

SHA256-128(A_pk) == SHA256-128(M_pk1), A_pk != M_pk1
SHA256-128(D_pk) == SHA256-128(M_pk2), D_pk != M_pk2
```

Alice will encrypt messages against `M_pk2`, rather than `D_pk`. But the fingerprints will match for both. Dave will respond by encrypting messages against `M_pk1`, instead of `A_pk`. The attacker can sit in the middle and re-encrypt messages on behalf of the recipient. Even if both Alice and Dave compare the fingerprints they see with what Bob sees, nobody will detect anything.

This is why you only need a collision attack to violate the security of the peer fingerprint, and not a preimage attack.

To be clear, a targeted attack is much more expensive (roughly several trillion times the cost of a general attack; $2^{107}$ versus $2^{64}$).

This is a certificational weakness, and I’m only including it as further evidence of poor cryptographic engineering by Threema’s team rather than an overt vulnerability.

Update (2021-11-08): Remember, this is a list of issues I discovered, not specifically a list of vulnerabilities. People trying to argue in the comments, or my inbox, about whether this is “really” a vulnerability is getting a little tiring; hence, this reminder.

How to Fix Threema’s Fingerprints

First, you need to include both the Threema ID and curve25519 public key in the calculation. This will frustrate batch attacks. If they were to switch to something like X3DH, using the long-term identity key for fingerprints would also be reasonable.

Next, calculate a winder margin of truncation. here’s a handy formula to use: $128 + \log_2(P)$ where $P$ is the expected population of users. If you set equal to $2^{40}$, you end up with a fingerprint that truncates to 168 bits, rather than 128 bits.

This formula yields a probability space with a birthday bound of $2^{84}$ for collisions, and a preimage cost of $2^{128}$ (even with a trillion Threema IDs reserved), which plainly isn’t going to ever happen.

Severity: Informational
Impact: Frustration of Engineering Efforts

There is no concept of versioning anywhere in Threema’s protocols or designs, which means that one day migrating to better cryptography, without introducing the risk of downgrade attacks, simply isn’t possible.

The lack of any cryptography migration breadcrumb also prevents Threema from effectively mitigating security weaknesses inherent to their protocols and designs. You’ll see why this is a problem when we start looking at the implementations.

Cryptography migrations are difficult in general, because:

1. Secure cryptography is not backwards compatible with insecure cryptography.
2. In any distributed system, if you upgrade writers to a new cryptography protocol before your readers are upgraded too, you’ll cause availability issues.

The asynchronous nature of mobile messaging apps makes this even more challenging.

Inconsistency with Cryptographic Randomness

Severity: None
Impact: Annoyed Cryptography Auditors

Threema commits the same sin as most PGP implementations in misunderstanding the difference between `/dev/random` and `/dev/urandom` on Linux.

Doesn’t the man page say to use /dev/random?

You should ignore the man page. Don’t use /dev/random. The distinction between /dev/random and /dev/urandom is a Unix design wart. The man page doesn’t want to admit that, so it invents a security concern that doesn’t really exist. Consider the cryptographic advice in random(4) an urban legend and get on with your life.

Emphasis mine.

If you use /dev/random instead of urandom, your program will unpredictably (or, if you’re an attacker, very predictably) hang when Linux gets confused about how its own RNG works. Using /dev/random will make your programs less stable, but it won’t make them any more cryptographically safe.

Emphasis not mine.

This is an easy fix (`/dev/random` -> `/dev/urandom`), but it signals that the whitepaper’s author lacks awareness of cryptographic best practices.

And it turns out, they actually use `/dev/urandom` in their code. So this is just an inconsistency and an annoyance rather than a flaw.

Update (2021-11-08): Yes, I’m aware that the Linux RNG changed in 5.6 to make `/dev/random` behave the way it always should have.

However, Linux 5.6 is extremely unlikely to help anyone affected by the old Android `SecureRandom` bug that Threema has implied as part of their threat model when they called it out in their Cryptography Whitepaper, so I didn’t originally deem it fit to mention.

Invisible Salamanders with Group Messaging

Severity: Medium
Impact: Covert channel through media messages due to multi-key attacks

Note: This was discovered after the initial blog post was published and added later the same day.

Threema doesn’t do anything special (e.g. TreeKEM) for Group Messaging. Instead, groups are handled by the client and messages are encrypted directly to all parties.

This provides no group messaging authentication whatsoever. A user with a malicious Threema client can trivially join a group then send different messages to different recipients.

Imagine a group of five stock traders (A, B, C, D, E). User A posts a message to the group such that B, C, and D see “HOLD” but user E sees “SELL”.

An attacker can have some real fun with that, and it’s probably the easiest attack to pull off that I’ll discuss in this post.

User E won’t have much recourse, either: Users B, C, and D will all see a different message than User E, and will think E is dishonest. Even if User E provides a screenshot, the rest of the users will trust their own experiences with their “private messaging app” and assume User E is spinning yarns to discredit User A. It would then be very easy for A to gaslight E. This is the sort of attack that us LGBTQIA+ folks and furries are often, sadly, all too familiar with (usually from our families).

Additionally, there’s an invisible salamanders attack with media files.

Invisible Salamanders is an attack technique in systems where traditional, fast AEAD modes are employed, but more than one key can be selected. The security modes of most AEAD modes assumed one fixed symmetric encryption key held by both parties in their security designs.

To exploit the Invisible Salamanders attack:

1. Generate two (or more) Xsalsa20-Poly1305 keys that will encrypt different media files to a given ciphertext + tag.
2. Send a different key to a different subset of group participants.

Both parties will download the same encrypted file, but will see a different plaintext. Threema cannot detect this attack server-side to mitigate impact, either.

Encrypting multiple plaintexts, each under a different key, that produce an identical ciphertext and authentication tag is possible with AES-GCM, AES-GCM-SIV, and even Xsalsa20-Poly1305 (NaCl secretbox, which is what Threema uses).

Preventing this kind of misuse was never a security goal of these modes, and is generally not recognized as a vulnerability in the algorithms. (It would only qualify as a vulnerability if the algorithm designers stated an assumption that this violated.) However, Invisible Salamanders absolutely is a vulnerability in the protocols that build atop the algorithms. Thus, it qualifies as a vulnerability in Threema.

Here’s a Black Hat talk by Paul Grubbs explaining how the Invisible Salamanders technique works in general:

This isn’t a problem for i.e. Signal, because the Double Ratchet algorithm keeps the key synchronized for all group members. Each ciphertext is signed by the sender, but encrypted with a Double Ratchet key. There’s no opportunity to convince one partition of the Group to use a different key to decrypt a message. See also: Sesame for multi-device.

The reason the vulnerability exists is that Poly1305, GMAC, etc. are fast symmetric-key message authentication algorithms, but they are not collision-resistant hash functions (e.g. SHA-256).

When you use a collision-resistant hash function, instead of a polynomial evaluation MAC, you’re getting a property called message commitment. If you use a hash function over the encryption key (and, hopefully, some domain-separation constant)–or a key the encryption key is deterministically derived from–you obtain a property called key commitment.

In either case, you can claim your AEAD mode is also random-key robust. This turns out to be true of AES-CBC + HMAC-SHA2 (what Signal uses), due to HMAC-SHA2.

Invisible Salamanders Mitigation with NaCl

First, you’ll need to split the random per-media-file key into two keys:

1. A derived encryption key, which will take the place of what is currently the only key.
2. A derived authentication key, which will be used with `crypto_auth` and `crypto_auth_verify` to commit the ciphertext + tag.

It’s important that both keys are derived from the same input key, and that the key derivation relies on a strong pseudorandom function.

Pseudocode:

```function encryptMediaV2(data: Buffer, fileKey: Buffer) {
const encKey  = HmacSha256('File Encryption Key', fileKey);
const authKey = HmacSha256('Media Integrity Key', fileKey);

const encrypted = NaCl.crypto_secretbox(data, nonce, encKey);
const commitment = NaCl.crypto_auth(encrypted, authKey);
return Buffer.concat([commitment, encrypted]);
}

const authKey = HmacSha256('Media Integrity Key', fileKey);

if (!NaCl.crypto_auth_verify(tag, ciphertext, authKey)) {
}

const encKey  = HmacSha256('File Encryption Key', fileKey);
return NaCl.crypto_secretbox_open(ciphertext, nonce, encKey);
}
```

This code does two things:

1. It derives two keys instead of only using the one. You could also just use a SHA512 hash, and then dedicate the left half to encryption and the right half to authentication. Both are fine.
2. It uses the second key (not for encryption) to commit the ciphertext (encrypted file). This provides both message- and key-encryption.

If you didn’t care about message-commitment, and only cared about key-commitment, you could just skip the `crypto_auth` entirely and just publish the `authKey` as a public commitment hash of the key.

This corresponds to Type I in the Key Committing AEADs paper (section 3.1), if you’re trying to build a security proof.

Of course, the migration story for encrypted media in Threema is going to be challenging even if they implement my suggestion.

Issues With Threema Android

Weak Encryption with Master Key (LocalCrypto)

Severity: Low/High
Impact: Weak KDF with Crib (default) / Loss of Confidentiality (no passphrase)

The on-device protection of your Master Key (which also protects your Curve25519 secret key) consists of the following:

1. A hard-coded obfuscation key (`950d267a88ea77109c50e73f47e06972dac4397c99ea7e67affddd32da35f70c`), which is XORed with the file’s contents.
2. (Optional) If the user sets a passphrase, calculate the PBKDF2-SHA1 of their passphrase (with only 10,000 iterations) and XOR the master key with this output.

If the user opts to not use a passphrase, if their phone is ever seized from a government agency, it might as well be stored as plaintext.

To be charitable, maybe that kind of attack is outside of their (unpublished) threat model.

Even if a user elects to store a passphrase, the low iteration count of PBKDF2 will allow for sophisticated adversaries to be able to launch offline attacks against the encrypted key file.

The 4-byte SHA1 verification checksum of the plaintext master key gives cracking code a crib for likely successful attempts (which, for weak passphrases, will almost certainly mean “you found the right key”). This is somehow worse than a typical textbook MAC-and-Encrypt design.

The checksum-as-crib is even more powerful if you’ve sent the target a photo before attempting a device seizure: Just keep trying to crack the Master Key then, after each time the checksum passes, decrypt the photo until you’ve successfully decrypted the known plaintext.

The verification checksum saves you from wasted decryption attempts; if the KDF output doesn’t produce a SHA1 hash that begins with the verification checksum, you can keep iterating until it does.

Once you’ve reproduced the file you sent in the first place, you also have their Curve25519 secret key, which means you can decrypt every message they’ve ever sent or received (especially if the Threema server operator colludes with their government).

Also, `Array.equals()` isn’t constant-time. Threema should know this by now thanks to their Cure53 audit finding other examples of it a year ago. It’s 2021, you can use `MessageDigest.isEqual()` for this.

Update: An Even Faster Attack Strategy

SHA1 can be expensive in a loop. A much faster technique is to do the XOR dance with the deobfuscated master key file, then see if you can decrypt the `private_key` file.

Because this file is AES-CBC encrypted using the Master Key, you can just verify that the decryption result ends in a valid padding block. Because Curve25519 secret keys are 32 bytes long, there should be a full 16-byte block of PKCS#7 padding bytes when you’ve guessed the correct key.

You can then use the 4-byte SHA-1 checksum and a scalarmult vs. the target’s public key to confirm you’ve guessed the correct password.

Thanks to @Sc00bzT for pointing this attack strategy out.

File Encryption Uses Unauthenticated CBC Mode

Severity: Low
Impact: Unauthenticated encryption (but local)

Threema’s `MasterKey` class has an API used elsewhere throughout the application that encrypts and decrypts files using `AES/CBC/PKCS5Padding`. This mode is widely known to be vulnerable to padding oracle attacks, and has a worse wear-out story than other AES modes.

Unlike the care taken with nonces for message encryption, Threema doesn’t bother trying to keep track of which IVs it has seen before, even though a CBC collision will happen much sooner than an Xsalsa20 collision. It also just uses `SecureRandom` despite the whitepaper claiming to avoid it due to weaknesses with that class on Android.

Additionally, there’s no domain separation or protection against type confusion in the methods that build atop this feature. They’re just AES-CBC-encrypted blobs that are decrypted and trusted to be the correct file format. So you can freely swap ciphertexts around and they’ll just get accepted in incorrect places.

Tangent: The Pure-Java NaCl implementation they use when JNI isn’t available also uses `SecureRandom`. If you’re going to include a narrative in your Cryptography Whitepaper, maybe check that you’re consistently adhering to it?

Cache-Timing Leaks with Hex-Encoding (JNaCl)

Severity: Low
Impact: Information disclosure through algorithm time

This isn’t a meaningfully practical risk, but it’s still disappointing to see in their pure-Java NaCl implementation. Briefly:

1. JNaCl definition for hex-encoding and decoding
2. OpenJDK definition for `Character.digit()`
3. OpenJDK definition for `CharacterDataLatin1.digit()`

Because this implementation uses table lookups, whenever a secret (plaintext or key) goes through one of the JNaCl hexadecimal functions, it will leak the contents of the secret through cache-timing.

For reference, here’s how libsodium implements hex-encoding and decoding.

Issues With Threema Web

I’m not going to spend a lot of time on the Threema Web project, since it’s been in maintenance-only mode since at least January.

Severity: High
Impact: Insecure cryptographic storage

While SHA512 is a good cryptographic hash function, it’s not a password hash function. Those aren’t the same thing.

Threema’s Web client derives the keystore encryption key from a password by using the leftmost 32 bytes of a SHA512 hash of the password.

```/**
* Convert a password string to a NaCl key. This is done by getting a
* SHA512 hash and returning the first 32 bytes.
*/
const hash = nacl.hash(bytes);
return hash.slice(0, nacl.secretbox.keyLength);
}
```

Once again, just because you’re using NaCl, doesn’t mean you’re using it well.

This code opens the door to dictionary attacks, rainbow tables, accelerated offline attacks, and all sorts of other nasty scenarios that would have been avoided if a password hashing algorithm was used instead of SHA512.

Also, this is another cache-timing leak in most JavaScript engines and the entire method that contains it could have been replaced by `Uint8Array.from(password, 'utf-8')`.

Threema can’t claim they were avoiding the `UInt8Array.from()` method there because of compatibility concerns (e.g. with IE11) because they use it here.

Summary of Results

In the cryptography employed by Threema, I was able to quickly identify 5 6 issues, of which 2 3 directly negatively impact the security of their product (Threema IDs Aren’t Scalable can lead to address exhaustion and Denial-of-Service; Peer Fingerprints Aren’t Collision-Resistant allows moderately-funded adversaries to bypass fingerprint detection for a discount).

Both security issues in the Threema cryptography protocol were caused by a poor understanding of the birthday bound of a pseudorandom function–something that’s adequately covered by Dan Boneh’s Cryptography I course.

Additionally, the total lack of forward secrecy invalidates the Threema marketing claims of being more private or secure than Signal.

Update (3:45 PM): After initially publishing this, I realized there was a third security issue in the cryptography protocol, concerning Group Messaging: Invisible Salamanders.

In the Android app, I was able to identify 3 issues, of which 2 directly negatively impact the security of their product (Weak Encryption With Master Key (LocalCrypto) provides a very weak obfuscation or somewhat weak KDF (with a checksum) that, either way, makes leaking the key easier than it should be; File Encryption Uses Unauthenticated CBC Mode introduces all of the problems of CBC mode and unauthenticated encryption).

Finally, I only identified 1 security issue in the web client (Insecure Password-Based Key Derivation) before I saw the maintenance notice in the README on GitHub and decided it’s not worth my time to dive any deeper.

I did not study the iOS app at all. Who knows what dragons there be?

There were a few other issues that I thought existed, and later realized was false. For example: At first glance, it looked like they weren’t making sure received messages didn’t collide with an existing nonce (n.b. only on messages being sent)–which, since the same key is used in both directions, would be catastrophic. It turns out, they do store the nonces on received messages, so a very obvious attack isn’t possible.

The fact that Threema’s developers built atop NaCl probably prevented them from implementing higher-severity issues in their product. Given that Threema Web finding, I can’t help but ponder if they would have been better served by libsodium instead of NaCl.

Threema has been publicly audited (twice!) by vendors that they hired to perform code audits, and yet so many amateur cryptography mistakes persist in their designs and implementations years later. From their most recent audit:

Cure53’s conclusion doesn’t jive with my observations. I don’t know if that says something about them, or something about me, or even something much more meta and existential about the nature of cryptographic work.

Is Threema Vulnerable to Attack?

Unfortunately, yes. In only a few hours of review, I was able to identify 3 vulnerabilities in Threema’s cryptography, as well as 3 others affecting their Android and web apps.

How Severe Are These Issues?

While there are several fundamental flaws in Threema’s overall cryptography, they mostly put the service operators at risk and signal a lack of understanding of the basics of cryptography. (Namely: discrete probability and pseudorandom functions.)

The biggest and most immediate concern for Threema users is that a malicious user can send different media messages to different members of the same group, and no one can detect the deception. This is a much easier attack to pull off than anything else discussed above, and can directly be used to sew confusion and enable gaslighting.

For Threema Enterprise users, imagine someone posting a boring document in a group chat for work purposes, while also covertly leaking confidential and proprietary documents to someone that’s not supposed to have access to said documents. Even though you all see the same encrypted file, the version you decrypt is very different from what’s being fed to the leaker. Thus, Threema’s vulnerability offers a good way for insider threats to hide their espionage in plain sight.

The remaining issues discussed do not put anyone at risk, and are just uncomfortable design warts in Threema.

Recommendations for Threema Users

Basically, I don’t recommend Threema.

Most of what I shared here isn’t a game over vulnerability, provided you aren’t using Threema for group messaging, but my findings certainly debunk the claims made by Threema’s marketing copy.

If you are using Threema for group messaging–and especially for sharing files–you should be aware of the Invisible Salamanders attack discussed above.

When in doubt, just use Signal. It’s free, open source, private, and secure.

The reason you hear less about Signal on blogs like this is because, when people like me reviews their code, we don’t find these sorts of problems. I’ve tried to find problems before.

If you want a federated, desktop-first experience with your end-to-end encryption without a phone number, I don’t have any immediate replacement recommendations. Alternatives exist, but there’s no clear better option that’s production-ready today.

If you want all of the above and mobile support too, with Tor support as a first-class feature enabled by default, Open Privacy is developing Cwtch. It’s still beta software, though, and doesn’t support images or video yet. You also can’t install it through the Google Play Store (although that will probably change when they’re out of beta).

Looking forward, Signal recently announced the launch of anti-spam and spam-reporting features. This could indicate that the phone number requirement could be vanishing soon. (They already have a desktop client, after all.) If that happens, I implore everyone to ditch Threema immediately.

Disclosure Timeline

This is all zero-day. I did not notify Threema ahead of time with these findings.

Threema talks a big talk–calling themselves more private/secure than Signal and spreading FUD instead of an honest comparison.

If you’re going to engage in dishonest behavior, I’m going to treat you the same way I treat other charlatans. Especially when your dishonesty will deceive users into trusting an inferior product with their most sensitive and intimate conversations.

Threema also like to use the term “responsible disclosure” (which is a term mostly used by vendors to gaslight security researchers into thinking full disclosure is unethical) instead of the correct term (coordinated disclosure).

Additionally, in cryptography, immediate full disclosure is preferred over coordinated disclosure or non-disclosure. The responsibility of a security engineer is to protect the users, not the vendors, so in many cases, full disclosure is responsible disclosure.

That’s just a pet peeve of mine, though. Can we please dispense of this paleologism?

If you’re curious about the title, Threema’s three strikes were:

1. Arrogance (claiming to be more private than Signal)
2. Dishonesty (attempting to deceive their users about Signal’s privacy compared with Threema)
3. Making amateur mistakes in their custom cryptography designs (see: everything I wrote above this section)

7 replies on “Threema: Three Strikes, You’re Out”

Samsays:

Hi Soatok

Thanks for this extensive review. I am a Signal/Threema and user and value such disclosure a lot (even though I only understand parts of the technical details).
I wonder what your thoughts are on the “National Security Letters” which are used by the US government. Other countries obviously have similar mechanisms, but in my understanding this means that e.g. the FBI can theoretically subpoena the hell out of an organization without it beeing known to the public for an indefinite amount of time and without a judges authorization… (my information is based on the story from the internet archive organization). This always lets me hesitate a bit from trusting US based services.

Thanks for the article
(Also: Why are you blue? 😉

My thoughts on National Security Letters are as such:

1. They suck, and should not exist.
2. People vastly overestimate the kinds of information that NSLs can be used for. According to the EFF, they can be used to obtain: customer’s name, address, length of service, communications (phone and Internet) records, and banking and other financial and credit information.

This means they can’t be used to compel a company to backdoor their product/service. And that’s what a lot of people expect NSLs to be capable of.

Despite being based in the US, Signal doesn’t know your name or address. who you’re talking to, or your financial information. If they never collect it, an NSL can’t be used to obtain it.

Waltsays:

I enjoy reading your blog posts they have a good balance of approachability and rigor. I will preface my question with the caveat that I am not an expert and they are asked in earnest and not criticism. This one led to a couple of questions that might be appropriate for clarification or another blog post depending on their length.
Can expound on the fingerprint bypass in either this post or another. It seems like for 2 ** 64 to be the threshold for finding useful collisions there would need to be an impossible number of legitimate users (otherwise you’d just be finding collisions with yourself). Furthermore, I believe you would need to find a collision in both directions between parties in communication, decreasing the attack probability further and making it not a straightforward birthday problem application.
You seem to indicate that hashing the identity with the fingerprint and truncation is still bad. This would appear to remove the birthday attack. Is the issue that truncating the hash weakens it below 128 bits? Is 128 bits not enough if so why? Is it an issue with an inconsistent strength in primitive and paying and giving an overly optimistic impression of the end strength?

“It seems like for 2 ** 64 to be the threshold for finding useful collisions there would need to be an impossible number of legitimate users (otherwise you’d just be finding collisions with yourself).”

If you were trying to create an untargeted collision, 2**64 is the attack cost. If you’re trying for a targeted attack, you’d need a preimage attack.

“You seem to indicate that hashing the identity with the fingerprint and truncation is still bad. This would appear to remove the birthday attack. Is the issue that truncating the hash weakens it below 128 bits?”

It’s still bad because the security threshold is only 64 bits, not 128 bits. You always use the lowest number for attack cost when certifying an application. However, it would be sufficient to mitigate untargeted attacks, so I’m left wondering why they didn’t do that.

Waltsays:

Ref the birthday attack, only the (presumably infinitesimal) minority of collisions with a legitimate user matter though? Alternatively stated wouldn’t the overwhelming majority of collisions be where you control both colliding keys, and thus don’t need the collision to impersonate. Consider the degenerate case where there are only two legitimate users on the system and each attacker generated key/id and the probability of each attacker generated key colliding with a legitimate user is 2/(2**128) vs the impossible case where there are 2**128 legitimate users and every attacker generated key collides with a legitimate user. Furthermore since you need to have a collision for both parties you are MitM ing, then don’t you also need a probability of two parties communicating to estimate the probability of being able to MitM a connection?

If you can sub the public key out (there are 2**252 or so Curve25519 keypairs, there are 2**128 fiingerprints, so you can get 2**124 public keys for each fingerprint, and a multi-user preimage cost is 2**104.

I don’t know why everyone is obsessing over a certificational weakness so much. The Invisible Salamanders attack is the real interesting one.

Danielsays:

thank you for your article. The lack of PFS has bothered me for a long time. Nice to read from someone who confirms that transport security is not enough in this context.

This site uses Akismet to reduce spam. Learn how your comment data is processed.