Archive for February, 2015

A simple method of key verification for multi-device key exchange

There are tons of devices around with practically no user faced interface at all, which need to communicate securely with other devices. This includes devices such as a wireless thermometer communicating with a HVAC unit or a wireless lock on your door communicating with your phone when you tell it what keys to accept. The risks include violation of privacy, physical damage and economic loss.

With the current Internet of Things trend there will only be more of this type of devices in the future. To be able to use these devices securely you need to ensure there are no room for anybody to attempt to MITM these connections (to intercept it so that they are in the middle and can see and manipulate all data), but practically ensuring that can be incredibly hard if the devices don’t even have a screen.

My idea for how to achieve it securely, with minimal interaction required from the user that links the devices together, is to show a visual pattern derived from a shared key.

But since most devices don’t have any interface beyond a single LED light, that could typically be hard to achieve. But that’s fortunately not a dead end, because the simple solution is to let the two devices you’re linking together both show the exact same on/off blinking pattern, perfectly synchronized, while you hold them edge to edge. If the patterns are identical, they have the same key (details below on how this can be guaranteed). If you see that they don’t blink in perfect synchronization, then you know the devices you are trying to link do NOT have a secure direct connection to each other.

So how do you link them together in the first place? There’s lots of methods, including using NFC and holding them together, temporarily using a wired connection (this likely won’t be common for consumer grade devices), using radio based method similar to WiFi WPS (press a button on both devices), and more. The two options likely to become the most common of those are the simultaneous button press method for wireless devices and NFC. While NFC has reasonable MITM resistance as a result of its design (simultaneously interfering with both parties of a connection is nearly impossible), that doesn’t guarantee that the user will notice an attack (attacking by connecting to the devices one at a time would still work).

So by confirming that two devices have a secure communication link by comparing blink patterns, it becomes easy to ensure configuration can be done securely for a wide range of devices. But how can we be sure of this? What can two devices communicate to allow security through comparing a blink pattern? Thanks to cryptographic key exchange this is easy, since all the devices have to do is to generate a large secret number each and perform an algorithm together like Diffie-Hellman. When two devices perform DH together, they generate a shared large secret number that no other device can know. This allows the devices to communicate securely by using this large number as an encryption key. And it also allows us to verify that it is these two devices that are talking to each other by running that number through a one-way transformation like a cryptographic hash function, and using that to generate the pattern to show – and only the two devices that were part of the same DH key exchange will show the same pattern.

If anybody tries to attack the connection and perform DH key exchange with the devices separately, they will end up having DIFFERENT secret numbers and will therefore NOT show the same blink pattern.

Note that due to human visual bias, there’s a certain risk with showing a pattern with very few components (to barely have more bits than what an attacker can bruteforce) you can’t just display the binary version of the hashed key this way, since the risk is too large that many different combinations of blink patterns would be confused with each other. This can however be solved easily, you can use a form of key expansion with a hash function to give you more unique bits to compare. One way to do this is by doing an iterated HMAC. With HMAC-SHA256 you get 256 bits to compare per HMAC key. So computing HMAC(Diffie-Hellman shared secret key, iteration number) for 10 iterations you get 2560 bits to compare. There’s actually a better way to expand the shared key into enough bits, that’s reliable and fairly independent of what key exchange algorithm you deploy: SHA3’s SHAKE256 algorithm. It’s something kind of in between a hash and a stream cipher, called an extendable-output function (XOF). You get to select how many bits of output you want, and it will process the input data and give you precisely that many bits out. You want 2500 bits exactly? That’s what it will give you. This means that if the user looks at the pattern for long enough, he WILL be able to identify mismatches. 


To achieve strong security, you only need for approximately 100+ pairs of bits to be identical to ensure bruteforce is unachievable – and in this setup, it means the user only needs to be able to verify that 4% of the full pattern is identical. So if you have a blink pattern where the blink rate is at 5 bits per second, continously comparing the pattern for any 20 seconds out of the 512 seconds it would take for the pattern to start repeating would correspond to verifying that 100 bits is identical. Of course the blinking would need to be kept synchronized, which would require the devices to synchronize their clocks before starting and could also require them to keep doing so while the blink pattern is showing to prevent “drift”.

There are of course other possible methods than just on/off blink. You could have an RGB LED to represent multiple bits for every blink. You could also have geometric patterns shown on a screen when holding the screens of two devices up against each other. You could even do the same thing for mechanical/haptic outputs like Braille screens so that blind people can do it too.

What if you can’t hold the two devices physically close to each other? You could use another device as a “courier”. As one example, by letting your smartphone perform key exchange through this method with both devices one by one, it could also then tell the two devices how to connect to each other and what encryption key to use. This way your smartphone would act as a trusted proxy for key exhange. It would also be possible to have a dedicated device for this, such as a small NFC tag with an RGB LED and a smartcard like chip to perform the key exchange with both devices. Using a tag like that would make configuration of new devices as simple as to hold it against the devices and comparing the pattern, and then the connection is secure, with minimal user interaction.

Then there’s the question of how to tell the devices that the key exchange was a success or not. Typically most devices will have at least ONE button somewhere. It could be as easy as one press = success, two presses = start over. If there’s no button, and they are the type of devices that just run one task as soon as they get power, then you could use multiple NFC taps in place of button presses. The device could respond with a long solid flash to confirm a successfull key exchange or repeated on/off blinking to show it did reset itself.

Originally posted here: http://www.reddit.com/r/Bitcoin/comments/2uah2b/weve_launched_the_coolwallet_on_indigogo/co6rru6

Relevant prior art (found via Google, there may be more):
http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=7E99A2B9922A0AE79CF6CAC65634FD8C?doi=10.1.1.41.1574
http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=7E99A2B9922A0AE79CF6CAC65634FD8C?doi=10.1.1.126.4242

Advertisements
%d bloggers like this: