How KDE Connect encryption works

The goal of this post is that the security experts out there find flaws in our design so we could improve the security of KDE Connect, which is an important point. Probably this will get too technical if you don’t know what RSA keys are, so proceed under your own responsibility ;).

The first thing we need in KDE Connect is the discovery of other devices. At the moment we provide a single backend that uses UDP broadcast to achieve this. When a device connects to a new network, it sends a broadcast message with its ID and name plus how to reach it (that is: IP and port). Other devices will react to that broadcast sending back their own contact information, so both devices know each other.  (Note: We tried Avahi instead of a manual UDP broadcast, but finally we didn’t use it because the Android implementation is of extreme poor quality and also multicast is sometimes blocked by routers :( ).

At this point the devices can ‘talk’ between them, but they don’t trust each other until the intervention of the user, so they will discard any incoming package that is not a pairing request.

Each device has a unique pair of RSA public and private keys. When the user decides to start the pairing process from a device, that device sends its public key to the other device. If the other device accepts the pairing (it will show a message to the user with a timeout asking to do so), it will send back its own public key, so now both devices will be able to send encrypted packages (using their peer’s public key) to each other, that only the expected recipient will be able to read.

Pairing diagram

Note that the public key can easily be retrieved from a device, just by starting the pairing process with it. So only with that key and the device ID (also public) you would be able to fake a device and send encrypted packages to any other in its name (even though you would not be able to decrypt the answer, since you don’t have the private key of the device you are faking). To solve this issue, we will require a both-way encrypted handshaking (which is not implemented yet):

  • Device 1 sends some random number encrypted with Device 2’s key
  • Device 2 decrypts the number and encrypts it again with Device 1 public key
  • Device 1 decrypts the number and checks it is the same it originally sent (so Device 2 have the correct private key to decrypt it).
  • The same happens swapping Device 1 and Device 2

Do you think that the security this provides is enough or are we missing something? Would be better to have a different pair of public/private key for each device, instead of a single one?

Thank you all and happy hacking!

About these ads

19 thoughts on “How KDE Connect encryption works

  1. After the handshaking you will also need to use the random number (now a shared secret) in every message (for example using it as a key for symmetric encryption). Otherwise an attacker could wait for a successful handshake and then pose as one of the devices.
    What about signing every message instead?

  2. Assuming that one of the two devices has a camera, could you not make things user interaction free if the other device would generate some QR code that the camera enabled device could use to authenticate itself with the first device?

  3. I have a few questions and suggestions. First I would like to know whether the unique ID is leaking any private data and why you need a unique ID in the first place? Why not just broadcast the public key?

    For the ideas about how to secure it? Why not just use Diffie-Hellman key exchange protocol instead inventing your own (which looks quite similar). I like the idea of encrypting the key exchange protocol. The nice side effect of DH would be that you can in that way generate a session key.

    Another question I have is how long you will keep the session initialization open (syn-flood attack)?

    And last but not least I have a suggestion: did you think about certificate based authentification. That is that you use an X.509 certificate for the devices and that a device can be configured to automatically connect if the certificate is signed by a specific CA (obviously this makes only sense if one generates the own certs)? This could be quite handy as an alternative to the secure pairing.

  4. > it will send back its own public key
    You need to check somehow, if this is really the key of the second device, otherwise an attacker could send it’s own key and make the first device think, that he is the second device.

  5. Well, there are a couple things here.

    For one, this entire protocol is vulnerable to a man-in-the-middle attack because there’s no a priori root of trust for the public keys.

    This can be mitigated in a similar manner to how bluetooth does it – show something on both sides and ask the user to confirm that they match. A good option might be an Identicon[1] generated from the public key fingerprints of the devices – visual comparisons often work better than textual ones.

    Since a man-in-the-middle attack involves the attacker negotiating a key with each side by pretending to be the other and passing messages back and forth by reencrypting/resigning them, it would cause the Identicons to differ.

    Aside from that, my primary recommendation is _do not roll your own crypto_.

    Instead, generate self-signed (R|D|EC)SA-(EC?)DHE certificates and use TLS (and/or DTLS) in TOFU[2] (Trust On First Use) mode, along with the user verification I mentioned above.

    RSA and (EC)DSA in those ciphersuites are used for their signature capabilities, to authenticate the Diffie-Hellman key exchange.

    Diffie-Hellman (and the elliptic-curve variant) offer perfect forward secrecy – that means even if your certificate and private key are compromised, your past session keys are not recoverable by an adversary. This is an advantage over the ciphersuites that also use RSA for the key exchange.

    The elliptic curve variants of Diffie-Hellman and DSA result in reduced key sizes, but there’s historically been patent FUD in the vicinity of ECC so that would benefit from further investigation before you decide.

    [1] https://en.wikipedia.org/wiki/Identicon
    [2] http://www.gnutls.org/manual/html_node/Verifying-a-certificate-using-trust-on-first-use-authentication.html

  6. Your problem sounds pretty much like what DTLS (https://tools.ietf.org/html/rfc6347) does when used with mutual authentication. Martin already pointed out the DH key exchange which is part of TLS and thus also DTLS. By using it you get a pretty safe and well researched way to send encrypted data.

    The picture above is a bit extended. Instead of the plain RSA public key exchange you use X509 certificates. The DTLS implementation takes care of the dirty details, freeing you from this difficult task. Think of timing, known plaintext and so on attacks.
    After exchanging the certificates for the first time, the application can opt the user to accept the received certificate. This is similar to when you first connect to an ssh server. All subsequent sessions can then automatically establish a secure session.

    If you decide against the standard DTLS protocol I nevertheless strongly advise you to read through the Security Considerations section of the RFC. Also take a look at the TLS 1.2 RFC, it contains a lot more information which also applies. It contains pointers to the already found and fixed security flaws in the older versions (pre 1.2). They are most probably hitting you as well in your protocol if you are not careful.
    If however you decide in favor of DTLS, I also recommend to use the GCM based cipher suites rather than the CBC ones. DHE provides you with perfect forward secrecy which could also be a nice gimmick. Avoid versions prior to 1.2 if you don’t have a strong reason to use them.

  7. This doesn’t handle the problem of trusting that the public key sent by the device initially actually belongs to the owner of the device (or that the device is owned by the person you think). Of course, creating a web of trust is not easy, but it should absolutely be emphasized to the users that they cannot trust the key by default.

    Ignoring the current issue of whether the key truly identifies the device or person, and assuming that there is a web of trust or meatspace confirmation of the key’s identity…. It would be much better to not need a key for each device, but rather to use the key itself as the identity, which should be used across devices by the person who owns the key (otherwise you have to verify the true identity behind countless keys, decreasing security).

    As far as making sure that that the person sending the public key really has the private key, that’s entirely the point of signing. Any public key that’s sent should be signed with the private key. Honestly it concerns me to know that key signing wasn’t the first thing considered, rather than cross-encrypting a shared secret.
    Of course, there are existing key exchange protocols which should be used.

    I’m curious, what library are you using to generate and use the RSA keys? Is a user able to provide their own key (and thus an existing web of trust)?

  8. As the ConcernedCitizen already mentioned, even with the changes you suggest this is vulnerable to man-in-the-middle attacks. I can just generate a new private/public key pair for a device with the same name/unique ID as Alice, and then pretend to Bob I am Alice and pretend to Alice I am Bob. Unless the UI confirmation dialogue requires the two parties to actually authenticate the keys (by comparing fingerprints, or like OTR does it), you cannot counteract active attacks.

    Using a DH key exchange (with the messages signed with the original RSA key) would not only authenticate that only the two parties which run the protocol know the secret, it would also provide perfect forward-secrecy if you use the session key for further encryption. Remember that encryption in no way replaces authentication, so the “Further encrypted communication” be better authenticated as well. This can be done using a symmetric MAC with a key derived from the session key – that’s much less costly than using asymmetric keys all the time. The “derived from” part here is important, all crypto guarantees break down if you use the *same* key for two different primitives.

    However, re-inventing a crypto protocol is in general a bad idea, and more often than not it’s done entirely wrong, even by experienced crypto designers. The same applies to re-implementing a protocol. So I really urge you to find implementations of an existing protocol which has been formally verified that suits your needs.

    Feel free to contact me if you have further questions. Also, if you want to dive a bit more into the cryptography, “Introduction to Modern Cryptography” by Katz & Lindell is a great book, but i’s a bit heavy on the maths side. But then, that’s how modern cryptography works ;-)

  9. Chiming in to echo Ralf’s suggestions, and suggest also that you use the Botan library, which has implementations of all these things (DH key exchange, key derivation, symmetric encryption using a wide variety of available ciphers and modes, etc) with an excellent (C++) API. It’s also used elsewhere in KDE, I believe.

  10. I wrote a reply yesterday along the same lines as those that have since been posted but it seems to have been swallowed up.

    My point, as others, was don’t roll your own encrypted channel.

    I am not a security expert and I used to be guilty of thinking that the security guys were crazy for shouting about silly little technicalities. However as a programmer and a mathematician I have read a good few security and cryptography papers and I have come to realize that the threats posed by these crazy technicalities are serious.

    I hope that KDE Connect on the desktop and mobile becomes successful enough that it is the subject of a targeted attempt to find an exploit, and I hope that when that happens it is not rolling it’s own security.

    Take a read of this paper which introduces the security library NaCl and gives a good flavour of the sort of security issues you are bound to miss:

    http://cr.yp.to/highspeed/coolnacl-20120725.pdf

  11. as long as you dont have another third party with which you have trusty connections, MITM is always possible. That said, your protocol sucks. CryptoStudents break exactly such protocols for homework (i know that, i had to :D). Please rely on known protocols. (like the nacl-stuff for example)

  12. I’ll have to agree with Alex Elsayed, Tobias Wich, ConcernedCitizen and Ralf. Even with Robert and dennis, although their advice is rather negative.

    The way you describe the protocol is very naive, which indicates you do not have much experience in cryptography. This is dangerous – cryptography (much like mountain climbing) is one of these fields where a little knowledge is worse than no knowlege. I’m writing not to try to hurt you, but to dissuade you from using this scheme and opt for another – preferably an existing verified scheme.

    That being said, I’m very happy to see developers of new protocols trying to make them secure-by-design, rather than going for plain text and then pushing security into the protocol after the fact.

  13. I already explained my recommendation earlier, but Arik’s response made me realize I should really explain my point of view more. I’m not any sort of crypto expert; rather, I’m someone who finds it very interesting but is aware of my own lack of experience – I know just enough to realize I don’t know much.

    When I was just getting going with this interest, I picked up Schneier’s Applied Cryptography. The following paragraph has stuck with me ever since:

    “Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break. It’s not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.”

    The is often rephrased as “Any person can invent a security system so clever that she or he can’t think of how to break it,” and is generally the underlying reason for the advice “Don’t roll your own cryptography.”

    For the most part, anyone rolling their own crypto doesn’t _have_ years to let it be analyzed; usually the best-in-field cryptanalysts aren’t aware it exists either.

    That’s why it’s a much safer idea to use existing algorithms and protocols in well-tested ways.

    TLS and DTLS in trust-on-first-use with a prompt for the user to check “Are these two things the same” is well-understood indeed; it’s basically the same method as SSH uses for authentication and TLS has weathered a great deal of scrutiny over time.

    For a more specific example of “a system so clever the author could not break it” I’ll turn to Phil Zimmerman, who had some… missteps before PGP’s privacy was _actually_ pretty good:

    “When I was in college in the early seventies, I devised what I believed was a brilliant encryption scheme. A simple pseudorandom number stream was added to the plaintext stream to create ciphertext. This would seemingly thwart any frequency analysis of the ciphertext, and would be uncrackable even to the most resourceful Government intelligence agencies. I felt so smug about my achievement. So cock-sure.

    Years later, I discovered this same scheme in several introductory cryptography texts and tutorial papers. How nice. Other cryptographers had thought of the same scheme. Unfortunately, the scheme was presented as a simple homework assignment on how to use elementary cryptanalytic techniques to trivially crack it. So much for my brilliant scheme.”

    I _will_ echo Arik’s statement that you’re on the right path, though – Even if you’re making missteps in the protocol, at least you’re _thinking_ about it. And to go further, you’re _asking for advice_. I cannot overstate how critical that last point is – the feedback here may be in the general vein of “don’t do that,” but if you never asked at all you’d be releasing something exploitable. Being willing to ask is the most crucial part of finding the right answer, and that puts you in a good position. All that’s left is to take what advice you get, and keep asking good questions!

  14. I agree completely with the “only reinvent crypto if you’re a cryptographer” sentiment, but wouldn’t the attack surface area be significantly reduced if KDE Connect only activated itself for a whitelist of nominated wireless networks? Defense in depth, and all that.

    I don’t have KDE Connect installed at the moment, so maybe this has already been done. If not, although I am unfamiliar with Android programming, I’m sure it couldn’t be as hard as writing your own crypto ;P

    Nonetheless, another great piece of KDE software, well done Albert :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s