Tox Handshake Vulnerable to KCI
github.com
github.com
The way you generally fix this is by providing appropriate binding between long-term and short-term secret. MQV does this with some weird group-breaking, but another way to do it would be, e.g.:
session_key
= H(l_A*E_B + e_A*L_B) (as computed by Alice)
= H(l_B*E_A + e_B*L_A) (as computer by Bob)
Another classic way to do this is by signing the handshake, but that has its own share of problems. For example, the KCI attacks on TLS worked because an certificate was being used as a static DH key.
Why is KCI a vulnerability? Yes, I understand that the situation is reverse from a normal crypto; but still, when your keys are stolen, you are screwed anyway, your messages can be forged, it can lead to MITM, ...
How is that fundamentally so different from KCI. When someone steals your keys, security doesn't apply anymore; how can a threat model include "but what if someone steals the private keys".
Let me illustrate by examples:
Instead of KCI, consider forward secrecy. As long as the secret key is maintained forever, you don't care about forward secrecy. However, we generally agree that forward secrecy is a desirable property. If key compromise doesn't matter, why does Tox bother to get forward secrecy? Because the outcome of key compromise matters.
Instead of GCM, consider with something like CBC+HMAC-SHA256 and GCM-SIV or HS1. All take some added data per encryption in addition to a key: either a nonce or an IV. In the case of GCM, a nonce being reused is catastrophic failure: trivial forgeries and quite probably ciphertext decryption. With the other ciphersuites, there is some other failure, but nowhere near as bad. Yes, you shouldn't have repeated the nonce, but the problem is that that happens, and the question is how screwed you are when it does. Why do we care about NMR crypto? Because the outcome of nonce reuse matters.
KCI is just another example. Yes, it only matters when something has gone wrong. But there is a functional difference between "the attacker gets to impersonate me" and "the attacker can pretend to be anyone to me" (KCI), just like there's a difference between "the attacker can impersonate me" and "the attacker can decrypt all communications, past and present" (PFS).
Just like PFS, not having KCI-resistance as a property is a choice. There is no downside to having it. So, it is as much of a vuln as not having PFS would be.
> "the attacker gets to impersonate me" and "the attacker can pretend to be anyone to me" (KCI)
Both seem similarly catastrophic to me in a real life scenario. I cannot imagine a scenario when one is OK and one isn't. I don't see the hierarchy.
Also, thanks a lot for mentioning GCM-SIV to me! I like GCM, but the nonce reuse is scary :)
Protocols aren't primitives. Secure primitives certainly do not imply secure protocols (Example: AES is a secure block cipher, but AES-ECB is clearly not a secure way to encrypt messages). Secure protocols mostly imply secure primitives. (Counterexample: a protocol using HMAC-MD5 doesn't have forgery issues even though MD5 is not a secure hash function.)
There are several levels of "homebrew" of "roll-your-own" cryptography:
- Designing your own block ciphers or hash functions. - Designing your own compositions of primitives, like AE or MAC. - Designing your own protocols, like TLS or Noise.
This vulnerability exists on that third level. As a consequence, this isn't a repudiation of NaCl or libsodium. They're excellent libraries. Curve25519 is a DH primitive, and there's no DH vulnerability here. The problem is that it's not an AKE, and that's what you're using it as. The docs clearly enumerate what it does and does not do:
Security model
crypto_scalarmult is designed to be strong as a component of various
well-known "hashed Diffie–Hellman" applications. In particular, it is
designed to make the "computational Diffie–Hellman" problem (CDH) difficult
with respect to the standard base.
crypto_scalarmult is also designed to make CDH difficult with respect to
other nontrivial bases. In particular, if a represented group element has
small order, then it is annihilated by all represented scalars. This feature
allows protocols to avoid validating membership in the subgroup generated by
the standard base.
NaCl does not make any promises regarding the "decisional Diffie–Hellman"
problem (DDH), the "static Diffie–Hellman" problem (SDH), etc. Users are
responsible for hashing group elements.
The claim that libsodium doesn't give you the tools to produce a secure AKE is incorrect. Firstly, you can do a traditional signing key exchanges. Secondly, Noise is a proof from construction; there are implementations of the Noise protocol available on the site, and you'll see that it defines a KCI-secure AKE that you can implement using nothing but NaCl/libsodium.
Finally, as much as I try to draw this conversation away from individuals and towards technical discussion, I hope you'll find that I've tried pretty hard both here and in general to provide constructive contributions, and trying to educate those who'll listen. And, I tell people to consult a cryptographer, although you could do a lot worse than NaCl as a set of solid primitives :)
If a chainsaw does a bad job of cutting an apple, it's not a bad chainsaw.
https://nacl.cr.yp.to/box.html and I assume the relevant quote is The crypto_box function is not meant to provide non-repudiation. On the contrary: the crypto_box function guarantees repudiability. A receiver can freely modify a boxed message, and therefore cannot convince third parties that this particular message came from the sender. The sender and receiver are nevertheless protected against forgeries by other parties. In the terminology of https://groups.google.com/group/sci.crypt/msg/ec5c18b23b11d8..., crypto_box uses "public-key authenticators" rather than "public-key signatures."
Users who want public verifiability (or receiver-assisted public verifiability) should instead use signatures (or signcryption). Signature support is a high priority for NaCl; a signature API will be described in subsequent NaCl documentation.
If people want to discuss security, I'm game. But given the amount of energy I've spent removing the discussion from individuals and bringing it back to technology, I do not have to put up with having a bunch of accusations leveled at me.
The attacker in this scenario not only gets access to message plaintext but can also cause messages to be generated that wouldn't ordinarily be sent.
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.
In contrast, some of the Tox team's response makes me want to take up drinking. The "crypto secret club gimmick" remark in particular.
I take full responsibility for everything I said, but I hope I don't need to take responsibility for other people's posts. As nbraud (who is in fact a contributor) noted, this has nothing to do with a secret club. I like to think that all actual contributors are open for discussion and willing to learn what they do not yet know.
I would never ask you to do so! Thanks for clarifying.
People, please stay away from Tox.
By actually following the thread, I got the opposite idea. Its current active developers are well aware of Tox's flaws, do actually know what they're doing, and have a plan. They're being addressed.
This is a much better attitude than seen elsewhere (such as in Telegram).
And, in the first place, this is being overblown. As GrayHatter succintly puts it:
> 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.
KCI doesn't allow you to impersonate A, if you steal A's long term static keys. I mean, if you do that, you can, that much is obvious. But that's not what KCI is. It allows you to impersonate anyone else to A, if you steal A's keys and they cannot tell you are a lying impersonator. It works the other way around.
If A got his keys stolen, he's indeed in for some trouble.
This is slippery-slope weasel-wording. The particular impersonation-to-A scenario is well known (due to a standard DH key agreement property) and can be protected against (see lvh's top comment for examples how it's possible to do that).
Please.
> The particular impersonation-to-A scenario is well known (due to a standard DH key agreement property) and can be protected against (see lvh's top comment for examples how it's possible to do that).
Yes, it's an excellent explanation. But ultimately, while this should be fixed, it is not critical, as it requires A's private keys be stolen.
For the layman, without touching into the crypto details, the analogy GreyHatter made is not so bad.
(I've made the same point in more detail here: https://news.ycombinator.com/item?id=13395294)
No, I wouldn't. I've only seen this reply after reading the post you're referencing, which I found quite elucidating.
I would, however, note there's a huge difference in consequences. Without forward secrecy, old communications would be compromised when the private key is. This isn't comparable to anything about future conversations after the key is stolen, a situation where I'd personally have way lower security expectations and would be surprised if this wasn't the case among the general public, outside the crypto community.
In the first place, short of another HeartBleed-style vulnerability (not impossible, as heartbleed demonstrated), the key being stolen would typically involve a serious compromise of an endpoint, where the attacker achieves enough execution to install a rootkit, at which stage, with KCI or without, the attacker can present to the compromised user whatever they want.
I do, to some degree, understand the attitude of the current developers behind the toktok toxcore fork. They want to read and understand the code, then produce documentation about the code and the protocol, and only at that point (with all the information available) tackle the design issues, including this arguably low priority KCI issue. I believe it reasonable, particularly after considering that they're spending about zero effort in promoting its use to the general public.
While it's pretty fair and I'm sure welcomed for their code to be looked at and vulnerabilities found, all things considered, I do not think it's, at all, fair to give them and their early-stages project the kind of negative spotlight they're getting.
The specific claim about future communications is having people impersonate anyone to _you_, not you to anyone. I don't think this is obvious to the general public. More importantly, this implies that the victim knows their key has been compromised.
My point was that I don't think it's obvious to the general public, either, that they can have any expectation after their key is compromised. Forward secrecy, some of them might have even heard about, particularly in the present climate where ssllabs is requiring it for its A grade.
> More importantly, this implies that the victim knows their key has been compromised.
I threw in some talk about my and the general public's expectations about the scenario where an endpoint's key is compromised, but I don't think I included knowing it actually happened among these expectations. The rootkit scenario which I expect as most common compromise (endpoint machine utterly compromised) kind of implied the user is none the wiser.
I'm not sure there's anyone out there that expects an Amiga guru meditation style alert saying "Your private key has been compromised!" to appear.
> The vast majority of key compromises are operational screwups with data disclosure, they generally do not lead to arbitrary code execution.
This is honestly surprising.
https://github.com/TokTok/c-toxcore/issues/426#issuecomment-...
What's part am I missing that if we used hash(long_key pair + emp_key pair) protects us if the long term is known by an attacker? Why couldn't the attacker intercept the emp_keys.
I'm assuming there's no key signing done here.
"We have a largely undocumented, untested, and not well-understood code base of about 19 ksloc (C)."
Oh lord. Then another zinger from the same author:
"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."
Stay away!
I am working on Tox because the basic architecture is sound, even though there are some easy to fix security issues. I've started on a well-documented rewrite, but I had to put that on hold to make time for toxcore itself. Zetok has been working on a rust rewrite. I have good hopes for that project and I support it in any way I can.
We are actively working on making the 19k lines of C code better tested, better understood, and better documented. This takes time, but we're focussing on it and I believe we are making good progress.
Again, I can understand that such a statement incites fear, but saying anything else would be a lie. We're working on it.
If your intention is the same as mine (https://github.com/TokTok/website/blob/master/toktok/mission...), then I would hope we can work together in some way. Whether that means helping with discovery of security flaws, by helping us clarify sections of the spec (at this point we can't really call it a spec yet, it's more of a brain dump of the original author), or any other way, I'm happy to discuss opportunities.
If your intention is to incite rage and hatred, our discussion is over. I hope we can do the former.
EDIT: This last sentence is not intended to point at anyone in particular. It's more of a general "you". I'm thankful to zx2c4 for starting the discussion.
Thanks for the honesty. It's very much appreciated. I'd hate for somebody to somehow miss critical facts like these, and make a dangerous decision for themselves.
> If your intention is to incite rage and hatred
What a mystifying insinuation, especially toward somebody who actually took the time to try and write a clear explanation of the vulnerability and what KCI is and how resistance to it is an expectation of any modern AKE, etc. Such subtle jabs and hostility toward well-intentioned bug reporters doesn't inspire much faith.
Please, improve this. As a user I want Tox to be secure. But also, as a user, I'll use it rather than Skype even if it does have some concerns. It's a genuine, open source, Skype replacement that more-or-less works. The encryption stuff is just the icing on the cake.
It would be a great project even with zero encryption.
/ramblerant
I think it's a recurring comment (If you know the problem, why don't you fix it), because it's really easy to drive by, shit all over someone's project (that they've put a lot of time into) then move on, leaving everyone who still cares about the project to feel shitty. This is in to way directed at you. You've been nothing but helpful, supportive, and understanding! You're most certainly one of the good ones. But not everyone else got that award for today.
He says that is impossible and you need B's key to impersonate B when talking to A.
Could anyone that knows more about this than I do step in to clarify? Thanks!
To do an exchange, you send me A, and I send you B. You compute the DH exchange with B and a, and I compute it with A and b. The important property of the DH function is that computing DH(B,a) is the same thing as computing DH(A,b).
Now, if I steal your secret key 'a', I can do two things. One, I can obviously impersonate you. But two, I can impersonate anyone else, because I can calculate the shared secret. The reason for this is that I need your private key, but I only need the other parties public key.
Let's say you try to communicate with me now and someone has stolen 'a'. They can already have my public key, B, because it is public. Thus, when the exchange happens, you send me A. The attacker knows the secret key, 'a', already. So the attacker can intercept the communication, calculate the DH exchange of 'a' (which they stole) and 'B' (my public key), and they have calculated the shared secret. It is not possible for you to tell you have exchanged with the attacker, and not me. They never need my private key, only my public key, which will come through during the handshake. So it can always be intercepted. Remember, DH(B,a) and DH(A,b) are the same, so if both sides calculate DH(B,a), that's completely legitimate.
This is a very simplified view (and I haven't looked at the bug report in detail, TBQH, so the case for Tox is probably slightly different), but it explains why if your keys are stolen, anyone can be impersonated to you: because the impersonator only needs public information (public keys) from that point on to forge any exchange.
Alice's long-term static keypair is S_A/s_a
Alice's long-term static public key signature(signed by a trusted third party) is sign_A
Bob's long-term static keypair is S_B/s_b
Bob's long-term static public key signature(signed by a trusted third party) is sign_B
Alice's per-session ephemeral keypair is E_A/e_a
Bob's per-session ephemeral keypair is E_B/e_b
Alice sends S_A|sign_A|E_A|sign(data=E_A, key=s_a)
Bob sends S_B|sign_B|E_B|sign(data=E_B, key=s_b)
Shared key is generated with kdf(ecdh(E_A, e_b)) == kdf(ecdh(E_B, e_a))
The handshake depends on forming a shared secret. They do by computing an ECDH, which has the property:
ECDH(private A, public B) = ECDH(private B, public A)
So, if you control private A, you can form the shared secret that A relies on for verifying anybody else's identity. Reasonable AKEs protect against this; Tox's naive one does not. So, instead of requiring two compromised keys for a man in the middle between one peer pairs (A<-->B), you only need one compromised key for a man in the middle between infinite key pairs (A<-->{everybody}).
So they acknowledged this is not true in their issue tracker, but not publicly? Further, they internally claim they don't know what threats it faces, don't understand what those threats are, and don't want to worry at this time about what insecurity they have?
Also: "a largely undocumented, untested, and not well-understood code base of about 19 ksloc (C)" from one of their own developers.
This is quite disappointing.
Man can make it, man can break it.
I do think that making such claims without any backing security proofs is quite bold. In TokTok, we've avoided that and instead say: our aim is to bring security software to everyone. We don't claim that the software is already secure, but we have confidence in the general architecture and are working towards provable security. Part of that is a formal specification (not the human language spec) helping us provide users and cryptographers with a security proof. We are aware of some flaws, and have concrete plans (roadmap) to fix them.
I know that saying things like that statement you quoted doesn't improve confidence, but I think that saying "we're very secure" without proof is simply a lie. Many projects out there, some similar to Tox, claim security but aren't actually proven secure.
We are now simply a group of people who believe in the idea and want to make it reality. I am affiliated with TokTok, not with Tox.
Regarding public acknowledgement: I will update the TokTok website shortly.