Tox Handshake Vulnerable to KCI

[zx2c4]

Hello,

I found this source code confusingly written (and downright scary at times) and the specification woefully underspecified and inexplicit, so it's entirely possible my understanding of the handshake is inaccurate. But on the off-chance that 5 minutes of source code review at 4am yielded something accurate, here is my understanding of the handshake:

Peer A (Alice) has the longterm static keypair (S_A^{pub}, S_A^{priv}). Peer A has the session-generated ephemeral keypair (E_A^{pub}, E_A^{priv}). Peer B (Bob) has the longterm static keypair (S_B^{pub}, S_B^{priv}). Peer B has the session-generated ephemeral keypair (E_B^{pub}, E_B^{priv}).

Message 1: A -> B

XAEAD(key=ECDH(S_A^{priv}, S_B^{pub}), payload=E_A^{pub})

Message 2: B -> A

XAEAD(key=ECDH(S_B^{priv}, S_A^{pub}), payload=E_B^{pub})

Session Key Derivation

ECDH(E_A^{priv}, E_B^{pub}) = ECDH(E_B^{priv}, E_A^{pub})

Is this an accurate representation of the handshake? If so, keep reading. If not, you may safely stop reading here, close the issue, and accept my apologies for the misunderstanding.

The issue is that this naive handshake is vulnerable to key-compromise impersonation, something that basically all modern authenticated key exchanges (AKEs) are designed to protect against. Concretely, the issue is that if A's longterm static private key is stolen, an attacker can impersonate anybody to A without A realizing. Let's say that Mallory, M, has stolen A's private key and wants to pretend to be B:

Message 1: M -> A

XAEAD(key=ECDH(S_A^{priv}, S_B^{pub}), payload=E_M^{pub})

Message 2: A -> M

XAEAD(key=ECDH(S_A^{priv}, S_B^{pub}), payload=E_A^{pub})

Session Key Derivation

ECDH(E_A^{priv}, E_M^{pub}) = ECDH(E_M^{priv}, E_A^{pub})

A now thinks he is talking to B, but is actually talking to M.

Perhaps Tox doesn't care about this, or about many of the threat models that modern AKEs are designed to protect against, in which case, probably it's fine to continue using your homebrewed crypto. But if you actually desire some kind of high assurance security, I strongly recommend not building your own protocols and instead use something designed by an educated expert, such as Noise.

This is just what immediately leaped out at me after a few short minutes of review. I haven't even begun to look at key derivation and other interesting aspects (are you guys really just using raw ECDH results as keys?).

Again, apologies if this doesn't actually represent the handshake you're using; I'm not 100% certain. But in case it does, then let this be a wake-up call to developers not to roll your own crypto, as well as a wake-up call to users not to rely on crypto software written by non-experts.

[iphydf]

Hi Jason, thanks for the report. We are aware of all three issues you've mentioned, but it's great to have them written down. I'll explain a bit of background about what we're doing here, and the reasons for why issues like this have not been addressed.

We started the TokTok project about a year ago with a (now slightly outdated) plan. We inherited toxcore and the protocol it implements from the Tox project. We're now in some mix of phase 1 and 2, where we slowly improve the code while keeping the protocol exactly the same, with all its flaws and shortcomings. You've described one of them, but there are others. We should be more explicit about this on the website (I have filed an issue for this just now).

Initially, the plan was for us to not touch toxcore at all, and instead rewrite the specification, which does contain all the information we need, just not in an obvious way. That plan relied on others working on toxcore. Since nobody would take on the toxcore part, we had to take it on ourselves, which is the main reason we're not as far along in the plan as we had initially hoped.

The new plan is roughly:

1. Improve toxcore code base, not making any protocol changes, with focus on testability.
2. Implement a formal model of the protocol and run equivalence tests between it and c-toxcore. This part goes together with improving the spec, since the model is the formal version of the textual spec. Up to this point, we actively ignore any design flaws and focus purely on ensuring that the implementation matches the specification.
3. Publish a threat model. Implement attacks on network, random users, and specific users. Still not changing the protocol.
4. Redesign the protocol and make a single cutover from old protocol to the new one.

We do have crypto experts on board, but they are very much closing their eyes to the issues most of the time. I might have more to say about this, but not in public. I'm happy to discuss in private (IRC/email/ricochet) if you're interested.

I think the main action we can take related to this particular issue right now is to implement the attack. This was supposed to happen in step 3, but I don't see good reasons to keep it that far in the future. Perhaps it's a good time to publish all known attacks and their implications somewhere.

[zx2c4]

Hi @iphydf,

Thanks for your response. So, it sounds like you're aware that this is an issue and confirm that indeed the handshake follows this construction and is therefore vulnerable to KCI.

In that case, I strongly recommend that you put a large red disclaimer on the Tox website and in all applications indicating to users that Tox is not secure. As is, the security assurances made on the website, marketing, and in-app GUI are dangerous.

[azet]

Hi,

It seems either someone micromanaged too much or you guys got the wrong workflow figured out entirely.

Initially, the plan was for us to not touch toxcore at all, and instead rewrite the specification, which does contain all the information we need, just not in an obvious way. That plan relied on others working on toxcore. Since nobody would take on the toxcore part, we had to take it on ourselves, which is the main reason we're not as far along in the plan as we had initially hoped.

Upkeep of the core and porting is more important than fixing fundamental security flaws in the protocol itself, which, apparently, is live and used by people? This does not make sense to me.

The new plan is roughly:

1. Improve toxcore code base, not making any protocol changes, with focus on testability.
2. Implement a formal model of the protocol and run equivalence tests between it and c-toxcore. This part goes together with improving the spec, since the model is the formal version of the textual spec. Up to this point, we actively ignore any design flaws and focus purely on ensuring that the implementation matches the specification.
3. Publish a threat model. Implement attacks on network, random users, and specific users. Still not changing the protocol.
4. Redesign the protocol and make a single cutover from old protocol to the new one.

Usually I'd start with a threat model, so you can think about what/whom you want to defend against/protect, which attack vectors are relevant, etc. - a formal model sounds nice, but having a rough idea about how the protocol should look like first is maybe a better entry point. Modeling, testing etc should be done if you have a rough impression of what you're actually working on.

Sorry I'm just very confused by this response. Marking the project "experimental" after the fact is also problematic as you already have a user-base you need to care about (which of course means upkeep of your core, but first of all you want to supply them with strong security, as this is the point of the whole project, I take it? Your website says so.).

[iphydf]

Now there are two discussions in this thread.

Roadmap/workflow

@azet here is a thought process:

• We want Tox to be secure for a well-specified and published definition of secure (i.e. threat model).
• We have a largely undocumented, untested, and not well-understood code base of about 19 ksloc (C).
• Thus, any change we make has the potential to make Tox less secure, running counter to our goal.
• We could throw away all the code and rewrite using a different protocol with different security properties, but it would take a while.
• we are working with very tight resources: a few volunteers with limited time.
• It would be very hard to motivate those few people to drop a working product and write a whole new one. I've actually tried, but there is no audience for such plans.
• It seems to me that the route we're taking is one that allows us to reach the goal with the starting point we inherited.

I would be quite interested in your thoughts around this, and perhaps we can steer in a different direction that's better for the project.

Security properties

First I should note the obvious, which is that exclaiming "X is not secure" is as useless a thing as saying "X is secure". As @zx2c4 correctly said, it depends on the threat model. There are very few ways to make information transmission secure to every possible known and unknown attack (and then a crowbar to the wrist can break that security as well).

Regarding the particular issue:

• KCI depends on getting a user's secret key. If your secret key is compromised, you have several things to worry about, KCI is only one of them.
• Preventing KCI in the current protocol is possible but would break deniability in the simple case.

Regarding the general issue of "oh my god tox is not secure don't use it": this is slightly overreacting to the actual issues. As said, there are a number of possible attacks on individuals or on the network, but if secret keys remain secret, none of those attacks can compromise message content.

Tox provides some strong security guarantees. We haven't got to the point where we can enumerate them properly, given the general lack of understanding of the code and specification. This is the point we are currently working on: improving the code and at the same time improving our understanding of it, so that we can make large scale changes in a safe way.

@zx2c4 can you point at the part of the Noise spec that explains how deniability is achieved?

[zx2c4]

Regarding the general issue of "oh my god tox is not secure don't use it": this is slightly overreacting to the actual issues.

I think when your homebrewed crypto protocol falls to basic crypto 101 vulnerabilities that modern AKEs are explicitly designed to prevent, it's time to pin up the red banners telling people not to use your stuff.

And to put this in context - this is what I found after a few minutes of scrolling. Judging by your replies, I'm a bit frightened to look in more depth...

[iphydf]

I agree that we should tell users about the particular security guarantees Tox does and does not provide. We will add this to the website.

I would be interested in discussing further action if you're willing to talk. I would also be interested in discussing the implications of your findings if you're interested in looking more in depth and sharing what you think of it.

By the way, do you consider OTR secure or should they put up a red banner as well? What about the SIGMA protocol? Both these protocols provide a different set of security properties. The left and right set differences are non-empty.

For discussion of the current protocol I would like to ask you to direct questions at @irungentoo, who created the design and implementation of this protocol.

Can you point at the part of the Noise spec that explains how deniability is achieved? Also, can you point me to the parts of the code that you reviewed and whose logic you found to be of concern?

[zx2c4]

You might benefit from a bit of humility before comparing your protocol to OTR and SIGMA, both of which were groundbreaking works created by experts, as opposed to a slapdash protocol that has neither a specification for any coherent evaluation of security properties nor a sturdy codebase.

[iphydf]

I'm sorry I made it sound like I'm comparing us to them. I was asking about your opinion regarding these protocols, which both provide and lack certain security properties. I am still interested in your evaluation of the importance of each of their security properties, especially wrt. a similar lack or presence of these properties in Tox.

I'm also sorry to learn that a discussion I was hoping to be respectful and constructive has so quickly degenerated. I am sorry for the slightly snarky comment about those other protocols and red banners. I hope we can go back to where we started: a constructive discussion.

As said, we are quite aware of the situation we have inherited, and we are actively working on improving it. Your help in this endeavour would be greatly appreciated.

[GrayHatter]

For anyone reading this, without a crypto background. The assertions being made are the same as saying: the lock on your house is broken because if someone steals your keys they can unlock your door.

I agree with iphy on this, the reaction and outrage doesn't match the reality of the issue. All of it sounds like concern trolling to me.

[zx2c4]

the lock on your house is broken because if someone steals your keys they can unlock your door.

That's not a great analogy. KCI is a bit more subtle than that.

All of it sounds like concern trolling to me.

No, not really. As I wrote in the original post: if you don't actually care about having a secure protocol that meets modern expectations of an AKE, by all means defend and justify your homemade situation. However, if you're interested in gaining the trust of users and confirmation from cryptographers, you'd benefit immensely from not trying to tout the current situation as secure, but rather put up a large scary warning indicating to your users that you're working on it but that you're not there yet.

I was asking about your opinion regarding these protocols, which both provide and lack certain security properties. I am still interested in your evaluation of the importance of each of their security properties, especially wrt. a similar lack or presence of these properties in Tox. I hope we can go back to where we started: a constructive discussion. As said, we are quite aware of the situation we have inherited, and we are actively working on improving it. Your help in this endeavour would be greatly appreciated.

I think the best place to design a new crypto protocol is probably not a Github issue report. Take some time, write it out, work out the details, talk to your professors, etc. Alternatively, spend time reading existing papers and evaluating if they fit what you want and whether they have an implementation ready built for you to use. Message boards are a pretty bad place for ad-hoc design of something so critical.

---

Anyway, I'll tuck out now for a little while to see how this evolves. I've done my part. There's an vuln found in 5 minutes of review. There's homebrewed crypto. There's a "a largely undocumented, untested, and not well-understood code base of about 19 ksloc (C)" (@iphydf). Now it's up to you how you want to handle this. Treat it as serious and worthy of a red "do not use" banner, if you'd like to give the impression that you care about the same standards of security that the world of cryptographers do. Carry on as usual if you simply want your thing to continue to be casually used by people who don't care that much and are okay with using naive constructions.

[GrayHatter]

Also, if you personally are worried about someone stealing your key without you knowing. And your friends aren't rapidly disconnecting and reconnecting. No one else has your key.

[GrayHatter]

put up a large scary warning indicating to your users that you're working on it but that you're not there yet.

You're right, a totally rational and nuanced response to an attack that would quickly become discovered.

Because you don't seem interested in discussing anything other than a low risk attack in hyperbolic style. I'm going to make sure this this thread doesn't devolve into what it already has started to. Anyone who would like a deeper discussion can join #toktok on freenode.

[lvh]

I'm a cryptographer. I disagree with the lock analogy assertion that it's trivial or obvious. Being able to impersonate someone whose secrets have been compromised is, indeed, obvious; KCI works in the other direction. I don't think the other direction is obvious at all. (I agree that the tone is not one I'd use, but that's neither here nor there.)

[nbraud]

@lvh I agree that KCI is a non-intuitive (to users, at least) issue.
I also agree with @GrayHatter that it isn't a “let's set our pants on fire and run around screaming” kind of issue, as it requires first a key compromise.

However, I would be even more interested in moving that conversation away from the name-calling and back in rational, constructive discussion. That seems to be a much harder problem, unfortunately :(

[lvh]

@nbraud OK, does that mean you agree with the suggested resolution in the form of documenting the known attacks, including the handshake not being secure against KCI?

[lvh]

@GrayHatter When you say "an attack that would quickly become discovered", is that because you're asserting that adversaries can't compromise keys without you finding out, or is there some other subtlety I'm missing?

[iphydf]

I'm still interested in having this discussion. KCI is an interesting and important topic, and I'd like to know more about @zx2c4's and @lvh's thoughts here.

I would also like to give @irungentoo a chance to weigh in on the concrete issue. In my experience, Tox solves some security issues in a non-obvious way. I have looked around the code and specification several times and found a number of issues, most of which I have later found out were somehow mitigated by non-obvious means. It is quite possible that the same is true in this case. I think it's reasonable to wait for the person who knows the protocol best to provide insight.

@lvh: we should and will definitely be documenting known attacks.

[nbraud]

@zx2c4 As mentioned by others, the plan is to provide users a single-cutoff switch to a better protocol, with a documented threat model & security claims.

The current “slapdash protocol”, along with its lack of an actual spec and of a robust implementation, is what we inherited from @irungentoo . As @iphydf mentioned, the goal is to first gain an understanding of where we stand and develop a robust codebase, so as to be able to provide a sane upgrade path.

Of course, part of that is documenting the current protocol's failings, in particular which security properties it fails to provide, under which threat models, and why they are relevant to users.
I don't believe, however, that putting a big fat warning that “everything is broken” is accurate or helpful to users, though.

[nbraud]

@lvh Sure, see above answer. You were just a bit too fast ;-)

PS: I should have specified that I'm not the most active contributor here, in part due to issues outside of my control, so don't take my opinion as representative of what other TokTok contributors think.

[paragonie-scott]

Just an aside:

The best thing to do in situations like this is to make a clean break. Start over with a secure protocol (in this case AKE) rather than try to smoothly transition users towards a secure protocol and introduce downgrade attacks.

[GrayHatter]

@GrayHatter When you say "an attack that would quickly become discovered", is that because you're asserting that adversaries can't compromise keys without you finding out, or is there some other subtlety I'm missing?

Because of how the protcol works, if someone else tried to impersonate you, your friends would rapidly connect and disconnect from you. You can see what this would look like in the client by running the same tox "profile" on two systems at the same time.

[eternaleye]

@GrayHatter: The issue of KCI is not "I stole your key, now I can pretend to be you" - it's "I stole your key; now whenever you try to talk to someone, I can gaslight you instead, pretending to be them"

This is best combined with any of the MANY techniques for network-level interception, such that you never even have a chance to talk to anyone but the attacker

(This then trivially bootstraps to a fully-general MITM).

[kebolio]

would like to mention that "Noise" could also be be called "homebrewed crypto" in that someone has actually sat down and written it. It is also Yet Another Encrypted Messaging Protocol, like there has never been enough of them (OTR, insecure Axolotl gimmick)

[lvh]

@kebolio I don't think that's a statement you could get cryptographers to support (certainly not me). Noise is peer-reviewed, and explicitly highlights many issues and how it addresses them, including specifically AKE KCI.

[nbraud]

@eternaleye As far a I get @GrayHatter's point, the user being impersonated (Alice) would see the user whose key was compromised (Bob) rapidly connect and disconnect while the attack is ongoing.
Of course, running the attack while Alice is offline likely sidesteps the issue.

[eternaleye]

@nbraud That would be true if it wasn't trivial to deny the connection to Alice using network-level techniques.

[goldroom]

@horusra
Yes, there is an update to this issue.

I wrote my master thesis on “Adopting the Noise key exchange in Tox”. You can download the full master thesis from here: https://pub.fh-campuswien.ac.at/obvfcwhsacc/content/titleinfo/5430137

I presented the results of my master thesis at Remote Chaos Experience (rC3): https://media.ccc.de/v/rc3-709912-adopting_the_noise_key_exchange_in_tox
Talk slides are available here: https://pretalx.rc3.studio/media/rc3-channels-2020/submissions/PWNJYW/resources/Buchberger_ToxNoise_rC3_0zhUC7T.pdf

As @zx2c4 wrote in the initial post, the handshake is not easy to understand based on the existing spec and implementation. My thesis includes a detailed description of Tox’ handshake, including the (KCI-vulnerable) authenticated key exchange (AKE), all exchanged messages and all performed computations (see chapter 2.4). Hopefully this will be used for further security analysis.

The DHT key pairs, which are used to calculate a shared secret in the cookie phase of the Tox handshake, make an actual KCI-attack on the Tox’ AKE more complicated than the simplified description from @zx2c4. This is because

• M needs to obtain the X25519 static private key S_A^{priv} from A to impersonate B to A
• M needs to obtain the X25519 static public key from B (S_B^{pub} or B’s Tox ID) to be able to impersonate them to A
• A and B need to be online at the same time because the attacker is not able to initiate a handshake on their own due to the usage of a shared secret based on the DHT key pairs during the cookie phase of the handshake. If it’s possible for M to spoof B’s DHT key pair, M could initiate a handshake on their own. I didn’t have time to look at the DHT module during my thesis, therefore I’m not sure if this is possible.
• The attacker needs to have control over the network between A and B (i.e. the internet -> NSA-style) to be able to intercept and drop packets
• The attacker would need to reimplement toxcore because it's not possible to exploit KCI by using the "normal" toxcore

Anyway, this vulnerability should be fixed. I created a PoC implementation which is based on the Noise-C library: https://github.com/goldroom/c-toxcore/tree/tb_noise_handshake_IK_noise_patch
The PoC implementation in it’s current state shouldn’t be used in practice. Also it’s not backwards compatible.

I added AKE-related comments to net_crypto.c, hopefully they are also helpful for other people to gather more understanding of Tox’ handshake implementation.

In future work the Noise IK pattern should be implemented directly in toxcore instead of using Noise-C (cf. Wireguard).

Maybe @lvh is also interested in this update.

[ghost]

@goldroom Wow, great work I had no idea so much was done already.
Then my only concern that remains is the mobile client, I just checked the android version and the one in fdroid has not been updated since 2 years ago and on the google store there are a lot of issue it seems from user reviews
What is the current end-user focus exactly? what client for what platform? (meaning, what client is the most complete and up to date to promote for the average IM user)

[anthonybilinski]

There are a few different mobile clients on Android, I'm not sure which one you're referencing.
These three are all being updated regularly:

• aTox (android design, stock, polished)
• TRIfA (featureful, extended protocol, uses a fork of c-toxcore)
• Protox (Qt based, I don't know that much else about this one)

Antox on android hasn't been maintained in a few years, which might be what you're looking at.

If you're talking about platforms in general,

• qTox is probably the most used desktop GUI client, runs on Linux/Windows/macOS
• uTox is lighter weight, runs on Linux/Windows
• Toxic is ncurses based, probably the most polished of the three

If you see the "Tok" apps, note that those are unaffiliated with Toktok, are closed source, and seem to use some modified version of Tox that isn't distributed. I wouldn't recommend using those.

[ghost]

@anthonybilinski Thank you for this post, however, why is the main site then only listing Antox for android? Why is this not removed when it hasn't been maintained for years? The site doesn't mention anything about aTox, TRIfA or Protox

https://tox.chat/clients.html

[anthonybilinski]

Good point, looks like maybe because of you pointing it out, Antox is being removed and aTox is being added: Tox/tox.chat#228. I'm not sure about the other two though, I'm not really involved in the site and I'm not sure how clients are chosen to be on there.

[peepo5]

i've seen too much lazy developer while reading through this thread

[emdee-is]

@goldroom I'm glad your are tackling this issue and hope you get pthe funding from NLnet.. A thought after reading your gist: could you comment on the following uninformed conjecture:

Although the KCI is exploitable for impersonation with presumably a huge effort, handshake disruption might be achievable by much more modest means.

I.e. denial-of-service, which might suit some adversaries just fine.

[goldroom]

See https://blog.tox.chat/2023/03/redesign-of-toxs-cryptographic-handshake/ for more information on this issue.

[eqn-group]

Hello,
I hope you all are doing good. Is there any update on "redesign of tox cryptographic handshake"?
Furthermore, is there any active discussion happening over mailing list or tox gc itself?

Best regards,

[goldroom]

@eqn-group did you read the blog post? Contact information is provided there. Development discussion is currently mostly happening via the NGC group 360497DA684BCE2A500C1AF9B3A5CE949BBB9F6FB1F91589806FB04CA039E313.

[goldroom]

This is issue is fixed with #2450.