search

QubesOS / qubes-issues

The Qubes OS Project issue tracker
https://www.qubes-os.org/doc/issue-tracking/
543 stars 48 forks source link

USG keyboard hardware proxy #2518

Open andrewdavidwong opened 7 years ago

andrewdavidwong commented 7 years ago

Community Dev: @robertfisk PoC: https://github.com/robertfisk/USG Discussion: https://groups.google.com/d/msg/qubes-users/MEzOZ_naupo/mpWcCjLSDgAJ

Description (https://github.com/QubesOS/qubes-issues/issues/2507#issuecomment-265894809):

IMHO much better solution for USB keyboard problem would be to have a piece of hardware plugged between USB keyboard and PC (based on https://github.com/robertfisk/USG?), to encrypt and integrity-protect the events. And then decrypt them in dom0 and check integrity protection, and only then pass them down to input devices stack. This should at least partially guard against malicious USB VM. It still will be able to perform timing based attacks to guess what you're typing - not sure how accurate such attacks are currently. Such device could introduce artificial delay (like - inject queued events every 50ms) to at least partially mitigate such attacks.

v6ak commented 7 years ago

Not sure where it is the right place to discuss, but maybe here if I mention @robertfisk.

What's the current status? Do you heed help with anything? I was thinking about something similar, maybe rather as a modified keyboard firmware. I am currently not sure if the AVR chip on my keyboard is powerful enough, though.

I have few ideas:

Key exchange

First level (PoC quality) would be a key compiled in firmware. This requires advanced user who generates a random key, compiles and flashes the firmware. And the user has to flash it securely, i.e., not over a compromised USBVM. Easy to implement, hard to use.

Second level could look like Bluetooth SPP. After some Diffie-Hellman key exchange, user would authenticate it by typing few characters on the keyboard and pressing enter. This can perform mutual authentication.

Side channels

Actually, maybe we don't need to introduce any. USB is host-driven and performs polling on rate like 100Hz. So, keyboard would send the same information every 10ms. This could hide all timing side channels that are involved by design. It does not guarantee not introducing any side channel in implementation, though.

This design could also allow some real-time guarantees: Attacker cannot defer key presses much.

Encryption vs. authentication

I believe both encryption and authentication can be useful there. If there is not enough time for both, I am not 100% sure what to prefer:

Of course, if possible, I would prefer having both.

Dropped packets

I would not fear assuming that we have no dropped packets. With proper design, this will probably make the next packets rejected because of wrong sequence number. In such case, I believe it is OK to reset the connection and maybe inform user. (Without informing the user, malicious USBVM could still drop few packets by its choice without being noticed.)

robertfisk commented 7 years ago

I don't have much experience writing crypto apps so I'm going to need some advice on choosing the general strategy, crypto algorithms, etc. But I can make some comments on implementation details...

Are we protecting our keystrokes from a malicious sys-usb VM, or a malicious device? Or both?

My guess is "both", which means we have to perform nested crypto on both Downstream and Upstream??? Any advice or comments are welcome!

jpouellet commented 7 years ago

I don't have much experience writing crypto apps so I'm going to need some advice on choosing the general strategy, crypto algorithms, etc.

The universal advice is never roll your own ;)

You may want something simpler than a full TLS stack, in which case NaCl (or its heavier but more friendly to use direct descendant libsodium) is probably what you want.

NaCl authors have ported it to even an 8-bit AVR (see https://cryptojedi.org/papers/avrnacl-20130514.pdf), so I'm sure it would be no problem on your big fancy ARM with lots of flash to spare :)

But I can make some comments on implementation details...

  • ST supports PolarSSL / mbedTLS on their STM32 micros. It would make things much easier to use crypto functions supported by this library.
  • We have about 95kB of flash (program) space available on the USG v1.0 micros, out of 128kB total. This should be plenty of space for our crypto functions.
  • We need to decide which microprocessor performs which crypto operation. The "Upstream" micro talks to the PC, so can be compromised by the sys-usb VM. The "Downstream" micro talks to the keyboard or other USB device, and can be compromised by a malicious device. So we need to answer the question:
  • Are we protecting our keystrokes from a malicious sys-usb VM, or a malicious device? Or both?

My guess is "both", which means we have to perform nested crypto on both Downstream and Upstream??? Any advice or comments are welcome!

It is my understanding that there are two primary motivations:

  1. Securely isolating individual USB devices when you only have a single USB controller to assign via PCI-passthrough to a single sys-usb VM.

  2. Securely interacting with a USB device without needing to trust our USB controller.

Both of these scenarios treat the devices below the USG as trusted, and distrust the things on the other (computer) side.

If our keyboard or flash drive or whatever itself is malicious, then I do not see what is to be gained by authenticity- and integrity-protecting malicious keystrokes, etc.

This to me suggests to do the crypto on the downstream side.

jpouellet commented 7 years ago

If our keyboard or flash drive or whatever itself is malicious, then I do not see what is to be gained by authenticity- and integrity-protecting malicious keystrokes, etc.

Nor cryptographically protecting the fact that yes, this usb rocket launcher is suddently trying to also pretend to be a hub and keyboard and mouse. "Great! I've authenticated that it is indeed trying to attack me, and my USB controller with compromised firmware can't see how!" -- I could be wrong, but I see no benefit.

v6ak commented 7 years ago

For sake of brevity, I'll define “keyboard system” as our endpoint. It can be either a standard keyboard with USG proxy or a keyboard with patched firmware. I assume there is some protection from flashing by malicious sys-usb, as it would be pointless without that.

  • ST supports PolarSSL / mbedTLS on their STM32 micros. It would make things much easier to use crypto functions supported by this library.

I admit was thinking in much more embedded style, because I'd like to see it on Ergodox with Teensy 2.0 with 8-bit AVR ATMEGA32U4.

Well, if you want full-blown TLS between keyboard system and dom0, then I suspect it will be rather rejected as something too complex in dom0. Even in the case when you strip the TLS down (one TLS version, one ciphersuite, …).

OTOH, implementing all on low-level crypto primitives is not ideal, either. I know (and have seen) many potential vulnerabilities that can occur. Maybe libsodium can offer a good tradeoff, I'll look closer.

While I had some elegant very embedded idea that could require just performing one AES block encryption (on properly formatted data) for encryption, authentication and replay attack prevention (remember, keyboard sends just 8-byte packets, so there is some space left in 16-byte block), I am not so confident to suggest it. I can describe it if someone is confident enough to review it.

  • We need to decide which microprocessor performs which crypto operation. The "Upstream" micro talks to the PC, so can be compromised by the sys-usb VM. The "Downstream" micro talks to the keyboard or other USB device, and can be compromised by a malicious device. So we need to answer the question:

I'd assume that dom0 and the keyboard system is trusted and other parts (sys-usb, other USB devices that can interfere) are untrusted. If you had an untrusted keyboard and wanted to type your pasword on it and control whole your computed over it, you would probably need some crypto in your head in order to make it secure. ☺

Maybe you are trying to design a single USG device that could work both as firewall (i.e., for untrusted devices) and secure input proxy (i.e., for output devices). I am not sure if it is a good idea to have both in a single device:

When considering two separate devices for USG HID and USG firewall, I am not sure if USG HID really needs two separate CPUs. It should not need to process much of untrusted input. More importantly, the input is not going to be complex, but rather something fixed-length. Most importantly, the untrusted input it would process is rather going to be crypto-related, which cannot be moved to a separate untrusted CPU.

Few other notes

Side channels

We can measure time of crypto operations. As we are not running on any OS and we are encrypting fixed-length data, we should ideally get constant time for encryption. In real world, some interrupts might make it different, but maybe we can create some testing environment that does not have such issues.

Power-related side channels might be a bit more tricky to detect. OTOH, one capacitor could make them noisy enough.

More complex keyboards

Some keyboards do not behave just as one keyboard, but they also do have multimedia keys, scroll keys, trackpoint, touchpad etc. So, they can behave as multiple keyboards and mouse in ode device. I'm not suggesting those have to be supported in the first version, I'm just foreseeing some challenges that could affect hardware selection. For example, Arduino Due would need the keyboard to behave just as a single device.

jpouellet commented 7 years ago

Most importantly, the untrusted input it would process is rather going to be crypto-related, which cannot be moved to a separate untrusted CPU.

Can you elaborate on this point? I don't see why it couldn't be moved to e.g. a third processor between the two, isolating from memory corruption issues in either side's USB stack.

v6ak commented 7 years ago

OK, the USB protocol itself was something I did not have so much on my mind. So, the 3 CPU setup could look like this:

  1. One CPU (USB host) handles translation between USB keyboard and some simpler protocol that contains just the keypresses, reported as 8 bytes chunks (modifiers + reserved byte + up to six keys), plus initial metadata plus LED control.
  2. One CPU handles encryption and authentication. This would be the trusted one. It would handle very little untrusted inputs (provided that we trust the keyboard), mostly some handshakes (nonce from dom0 for initialization, initial key exchange) and LED status*. And even if we consider the keyboard as untrusted, it would not perform difficult processing on its input, just encrypting its keypresses and maybe its initial message**.
  3. One CPU (USB guest) handles USB enumeration etc. and translates a simple protocol to USB.

But when looking at it, I see:

*) Well, LED status is not something I've deeply thought about. I prefer stateless keyboard and don't use (or even have) status LEDs on my keyboard. I don't think they usually contain some very sensitive information and obscuring side channels might look a but paranoid here. **) I haven't thought about reporting keyboard capabilities much. But maybe the first version can skip it fully if there is some challenge.

On May 27, 2017 12:13:22 AM GMT+02:00, Jean-Philippe Ouellet notifications@github.com wrote:

Most importantly, the untrusted input it would process is rather going to be crypto-related, which cannot be moved to a separate untrusted CPU.

Can you elaborate on this point? I don't see why it couldn't be moved to e.g. a third processor between the two, isolating from memory corruption issues in either side's USB stack.

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/QubesOS/qubes-issues/issues/2518#issuecomment-304398755

-- Sent from my fruity BlackBerry pocket computer powered by Android with K-9 Mail. Please excuse my brevity.

robertfisk commented 7 years ago

Warning: epic post below...

Ok, so our threat model is a compromised sys-usb who wants to sniff our keys, and we assume the keyboard firmware is not compromised (either our own firmware, or protected by a USG firewall and clean from the factory (!)). If both sys-usb and the keyboard firmware are infected with cooperating malware then the task becomes more difficult (see issues below).

Libsodium looks fine to me, and its license is compatible with the (slightly weird) ST middleware license as used by the USG.

Issues

Here are a few issues as I see them:

  1. The crypto will have to protect against a hostile sys-usb performing MITM. Diffie-Hellman key exchange requires a public/private keypair on each end, so both Dom0 and the keyboard encryption firmware will hold a private key that is not known by sys-usb. But the Dom0 code and firmware code is public so the attacker can find them. Unless both ends contain a unique generated keypair signed by another master key? This sounds like it will cause some logistic difficulties for both ends...

  2. If our encryption device does not use a 3-CPU fully isolated architecture, it is essential that we protect the keyboard's firmware from attack from sys-usb. If both the keyboard and sys-usb are infected with cooperating malware, a 1-CPU or 2-CPU encryption system is vulnerable to compromise by the keyboard firmware. The encryption can then be disabled.

  3. I need to remind everyone that prototyping and preparing hardware for production costs real money. Think hundreds of dollars for a simple one-chip ATMEGA board, up to thousands for more complex designs. I have already paid this cost while developing the USG, which can be used with any operating system. If we limit the market to only Qubes users the volumes will be very small and only the simplest designs would be possible. In particular, a 3-CPU solution would have to sell for over US$100 each. This would then reduce the sales volume even more, and reduce the number of people able to use the enhanced security.

Switching encryption mode

Assuming sys-usb is hostile, our keyboard firmware must send only encrypted keystrokes. Otherwise sys-usb could report to Dom0 that a normal keyboard is connected, and report to the keyboard that it is connected to a non-Qubes system, and then proceed to sniff the unencrypted keystrokes. But interacting with the bios and Grub boot menu requires an unencrypted keyboard. So the user will have to unplug/replug the encryption device, or move a switch to change between encrypted and unencrypted modes.

The USG can be programmed with encrypted-keyboard firmware while still providing firewall functionality. In this case the keyboard encryption would be always-on, and switching to unencrypted mode would require replugging the keyboard into a standard USG, or unprotected into sys-usb (a really bad idea, see issue 2 above). Ideally the encryption could be enabled with a switch, but we will also need a really f'n bright green/red LED to remind the user what mode they are in. I plan to implement the switch/LED modification in the future, as it is also useful for a read-only mass storage mode.

Hardware

So we come to the question of which hardware architecture to choose. The 3-CPU solution may be the most robust against attacks, but as discussed in issue 3 above is impractical for cost reasons.

A 2-CPU solution like the USG protects the encryption from attacks by a hostile sys-usb. It does not protect the encryption from a hostile keyboard, or hostile sys-usb/keyboard sandwich (issue 2 above). Therefore Dom0 decryption code should be resistant to exploits in the encrypted payload, and the user should take steps to ensure that sys-usb cannot compromise their keyboard directly. The main advantage is that the hardware is already developed at no cost to Qubes users.

The 1-CPU solution needs some discussion. It is simple enough that it may be possible to design Qubes-specific hardware. Although the low volumes and desired low sale price means it will have to be done on a volunteer basis, I cannot say I will have time to do this! Perhaps we could find an off-the-shelf solution like an Arduino with separate device and host ports.

Then we need to ask if the 1-CPU solution is secure against attacks from a hostile sys-usb. I cannot say this for certain! One would have to very closely analyse the USB embedded device driver stack, and even then you cannot analyse the internal state of the USB device controller hardware (the hardware has its own state machine). The USG was designed with the assumption that any USB connection (device or host) will allow compromise, and I think we should make the same assumption here. This rules out a simple 1-CPU design.

But we can also use an FTDI chip on the computer side, as mentioned by v6ak. I will call this the 1.5-CPU option. You could do this with an off-the-shelf FTDI serial converter and an arduino with OTG or host port. Because we are making a non-standard keyboard, we can ask sys-usb to look for a FTDI serial port instead of a standard USB keyboard. This will isolate the keyboard encryption from a malicious sys-usb in the same way as the 2-CPU solution. However there is one disadvantage, which is that we are introducing some untrusted firmware into our system contained in the FTDI chip. This cannot attack our keyboard encryption, but it can attack sys-usb. In this aspect, a 2-CPU solution like the USG is safer overall than a 1.5-CPU solution.

The only reason we would choose a 1.5-CPU solution is if it was significantly cheaper. It may be cheaper at high volumes, but I don't think we have that market. You also need someone to pay the development costs, and it won't be me because once was enough! You would also have the months-long hardware development process, and the task of re-creating the functions of the USG firmware in another embedded processor. For these reasons I suggest using the USG as our hardware platform.

Moving Forward

I can develop USG firmware to support this feature, but I won't be able to do the Dom0 or sys-usb code. If someone wants to do that, we can work on the encryption details and how the keyboard will report itself to sys-usb.

v6ak commented 7 years ago

In the meantime, I've tried to sniff USB keyboard traffic and it does not look like it polls the way I thought. The polling mechanism is somewhat lower-level.

Anyway, this doesn't mean we cannot go this way. We can, however, introduce some powersave mode like „if there isn't any new keystroke for 5s, don't transfer anything.

If both sys-usb and the keyboard firmware are infected with cooperating malware

I would skip this case, as an infected keyboard is already bad enough.

Libsodium looks fine to me

On AVR, it preliminarily looks fine, except for RNG, which looks a it like a challenge a bit.

When mentioning AVRs: They use Harvard architecture, which can theoretically make them safer against buffer overflow attacks – provided that we lock the flash memory. Thanks to separate memory for program and data, attacker can jump just to the code, not to arbitrary data, which can limit the impact of buffer overflow. But without making the device non-updateable, attacker can still just jump to bootloader: https://arxiv.org/pdf/0901.3482

On issue 1 (key exchange): This is a pretty standard issue with existing solutions:

a. Just make it configurable. It does not even need DH. This is PoC-style solution and requires some care (e.g., a separate trusted USBVM). b. TOFU (Trust On First Use) – just assume that the first connection is secure. Just a more friendly version of the former. Note: In whis case, neither dom0 nor keyboard system shall just blindly accept any request for new pairing, as this would allow renegotiation attacks. c. Full solution inspired by Bluetooth SPP. The DH outputs not only the key, but also some verification code, which matches on both ends. The user would need to type the code from dom0 on the keyboard. The code wouldn't be sent, just verified by the CPU that handles crypto.

Note that there might be some issues on reduced keyboards, like not being able to type the code. But this can be easily solved by using a different keyboard when pairing.

On issue 2: As I've said, I would just assume the keyboard is not compromised.

But interacting with the bios and Grub boot menu requires an unencrypted keyboard. So the user will have to unplug/replug the encryption device, or move a switch to change between encrypted and unencrypted modes.

I'm OK with such limitations. For laptops, it can be also solved by using the internal keyboard.

The USG can be programmed with encrypted-keyboard firmware while still providing firewall functionality.

I am not sure if I understand this part, but I see this as complex and error-prone from user's perspective, without gaining much:

I can develop USG firmware to support this feature, but I won't be able to do the Dom0 or sys-usb code.

I hope the sys-usb part will not be much harder than USB hello world (after all, it is just a stupid proxy that is not supposed to understand the data much) and the dom0 part could be inspired by the qubes-input-proxy-receiver. Sure, this will require some experimenting for me, but it looks doable.

Regards, Vít Šesták 'v6ak'

On June 3, 2017 12:36:45 PM GMT+02:00, robertfisk notifications@github.com wrote:

Warning: epic post below...

Ok, so our threat model is a compromised sys-usb who wants to sniff our keys, and we assume the keyboard firmware is not compromised (either our own firmware, or protected by a USG firewall and clean from the factory (!)). If both sys-usb and the keyboard firmware are infected with cooperating malware then the task becomes more difficult (see issues below).

Libsodium looks fine to me, and its license is compatible with the (slightly weird) ST middleware license as used by the USG.

Issues

Here are a few issues as I see them:

  1. The crypto will have to protect against a hostile sys-usb performing MITM. Diffie-Hellman key exchange requires a public/private keypair on each end, so both Dom0 and the keyboard encryption firmware will hold a private key that is not known by sys-usb. But the Dom0 code and firmware code is public so the attacker can find them. Unless both ends contain a unique generated keypair signed by another master key? This sounds like it will cause some logistic difficulties for both ends...

  2. If our encryption device does not use a 3-CPU fully isolated architecture, it is essential that we protect the keyboard's firmware from attack from sys-usb. If both the keyboard and sys-usb are infected with cooperating malware, a 1-CPU or 2-CPU encryption system is vulnerable to compromise by the keyboard firmware. The encryption can then be disabled.

  3. I need to remind everyone that prototyping and preparing hardware for production costs real money. Think hundreds of dollars for a simple one-chip ATMEGA board, up to thousands for more complex designs. I have already paid this cost while developing the USG, which can be used with any operating system. If we limit the market to only Qubes users the volumes will be very small and only the simplest designs would be possible. In particular, a 3-CPU solution would have to sell for over US$100 each. This would then reduce the sales volume even more, and reduce the number of people able to use the enhanced security.

Switching encryption mode

Assuming sys-usb is hostile, our keyboard firmware must send only encrypted keystrokes. Otherwise sys-usb could report to Dom0 that a normal keyboard is connected, and report to the keyboard that it is connected to a non-Qubes system, and then proceed to sniff the unencrypted keystrokes. But interacting with the bios and Grub boot menu requires an unencrypted keyboard. So the user will have to unplug/replug the encryption device, or move a switch to change between encrypted and unencrypted modes.

The USG can be programmed with encrypted-keyboard firmware while still providing firewall functionality. In this case the keyboard encryption would be always-on, and switching to unencrypted mode would require replugging the keyboard into a standard USG, or unprotected into sys-usb (a really bad idea, see issue 2 above). Ideally the encryption could be enabled with a switch, but we will also need a really f'n bright green/red LED to remind the user what mode they are in. I plan to implement the switch/LED modification in the future, as it is also useful for a read-only mass storage mode.

Hardware

So we come to the question of which hardware architecture to choose. The 3-CPU solution may be the most robust against attacks, but as discussed in issue 3 above is impractical for cost reasons.

A 2-CPU solution like the USG protects the encryption from attacks by a hostile sys-usb. It does not protect the encryption from a hostile keyboard, or hostile sys-usb/keyboard sandwich (issue 2 above). Therefore Dom0 decryption code should be resistant to exploits in the encrypted payload, and the user should take steps to ensure that sys-usb cannot compromise their keyboard directly. The main advantage is that the hardware is already developed at no cost to Qubes users.

The 1-CPU solution needs some discussion. It is simple enough that it may be possible to design Qubes-specific hardware. Although the low volumes and desired low sale price means it will have to be done on a volunteer basis, I cannot say I will have time to do this! Perhaps we could find an off-the-shelf solution like an Arduino with separate device and host ports.

Then we need to ask if the 1-CPU solution is secure against attacks from a hostile sys-usb. I cannot say this for certain! One would have to very closely analyse the USB embedded device driver stack, and even then you cannot analyse the internal state of the USB device controller hardware (the hardware has its own state machine). The USG was designed with the assumption that any USB connection (device or host) will allow compromise, and I think we should make the same assumption here. This rules out a simple 1-CPU design.

But we can also use an FTDI chip on the computer side, as mentioned by v6ak. I will call this the 1.5-CPU option. You could do this with an off-the-shelf FTDI serial converter and an arduino with OTG or host port. Because we are making a non-standard keyboard, we can ask sys-usb to look for a FTDI serial port instead of a standard USB keyboard. This will isolate the keyboard encryption from a malicious sys-usb in the same way as the 2-CPU solution. However there is one disadvantage, which is that we are introducing some untrusted firmware into our system contained in the FTDI chip. This cannot attack our keyboard encryption, but it can attack sys-usb. In this aspect, a 2-CPU solution like the USG is safer overall than a 1.5-CPU solution.

The only reason we would choose a 1.5-CPU solution is if it was significantly cheaper. It may be cheaper at high volumes, but I don't think we have that market. You also need someone to pay the development costs, and it won't be me because once was enough! You would also have the months-long hardware development process, and the task of re-creating the functions of the USG firmware in another embedded processor. For these reasons I suggest using the USG as our hardware platform.

Moving Forward

I can develop USG firmware to support this feature, but I won't be able to do the Dom0 or sys-usb code. If someone wants to do that, we can work on the encryption details and how the keyboard will report itself to sys-usb.

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/QubesOS/qubes-issues/issues/2518#issuecomment-305966806

-- Sent from my fruity BlackBerry pocket computer powered by Android with K-9 Mail. Please excuse my brevity.

robertfisk commented 7 years ago

It sounds like you have some specific hardware in mind. Is this a keyboard or an inline USB device? Off-the-shelf? Development board? Any user assembly required?

v6ak commented 7 years ago

What sounds like I have a specific hardware in mind? Well, there are two places when I thought about some specific hardware:

When thinking about the protocol, I'd first design some variant that assumes some secret is already transferred. I'd skip real-time properties (so malicious sys-usb could delay any keypress provided it is not reordered), powersave. I'd go with a fixed polling rate at 100Hz. I'd address authenticity, confidentiality (including selected side channels) and replay attack prevention. From side channels, I'd like to prevent timing attack, but ignore attacks based on power analysis. I also would like to focus on keypresses and not on LED indicators. This is not to say we cannot widen the scope in the future, I just want to focus on important things.

So, let's assume we have some shared secret and we want to connect the keyboard. We need an unique nonce to be generated on both sides (dom0 and keyboard system). Without a nonce generated by keyboard system, malicious sys-usb can force the keyboard to key/IV reuse. Without nonce generated by dom0, attacker could replay some key sequences to dom0.

So, we have a long-lived secret and not-so-secret nonces from both sides, so the parties now have enough information to communicate to each other according to some symmetric encryption scheme. We can either:

a. Use the long-lived secret as key. In this case, we have to be more careful about IVs in order not to repeat them across sessions. b. Derive a key from all the data (long-lived secret and both nonces), so we don't have to care about reusing IVs across sessions, as we use a different key. Note that we can use a simple hash function like SHA2 (not PBKDF2/bcrypt/scrypt), as we don't derive the key from a low-entropy source.

The latter approach seems to be a bit more universal and might have a higher performance in some cases.

We have few options mentioned in symmetric authenticated encryption (one option) and AEAD (four options):

So, the ciphersuite will probably also depend on AES hadrware acceleration and its support in libsodium. OTOH, if we today pick one, it should be easy to change it in the future.

jpouellet commented 7 years ago

For the crypto between the trusted side of the device and the VM, it may be worth de-duplicating effort by stealing the design from the CrypTech people, who are designing a secure channel between their HSM and its client. I think the goals seem sufficiently aligned, and I believe the CrypTech folks have enough competent engineers and interested eyeballs to get the details right.

https://wiki.cryptech.is/wiki/SecureChannel was just posted on the CrypTech mailing list. I will cross-reference there in case anyone there is interested in this as well.

andrewdavidwong commented 5 years ago

@robertfisk, are you still working on this, or are your waiting for your PoC to be reviewed?

robertfisk commented 5 years ago

We've had some discussion here but nobody has stepped up to develop the sys-usb and Dom0 code. Unfortunately I don't have the time to implement the entire system myself.

I'd be happy to develop the firmware as a branch of the USG but I'll need some assistance to create the other components of the system. Any takers?

v6ak commented 5 years ago

The dom0 part should not be excessively hard. The PoC could be just one executable (+ about two short files for RPC definition and policy) that:

  1. reads the input from sys-usb
  2. decrypts and checks authentication (basically counterpart of the crypto code in USG) – well, some handshake might be needed
  3. passes keystrokes to /dev/input or so (sample code can be found in the code of the current Qubes USB proxy).
  4. Maybe it can also pass some data (LED states) to the keyboard, but that can be out of PoC scope.

Proper initial key exchange can be also out of PoC scope. Let's assume that is the user will enter a random key before compilation. (USB VM needs to be trusted when flashing anyway… A disposable USB VM might be useful there.)

The sys-net part might be tricky a bit, as USB is AFAIR more complex than just pidirectional pipe. But aside from that, it would be just a dump pipe between USB and stdin/stdout. Some glue (systemd service file and udev rules) can be inspired by qubes-input-proxy-sender.

When we agree on the protocol, I can try to implement the two parts. But I am not sure how to test the code without the counterpart. (I see, you might have the same issue, just from the other part.) Sure, some unit tests will help, but still… Maybe some Arduino-based mock?

Also note that I am not directly interested in USG for keyboard, as it does not fit my needs. I would rather want to integrate it with my keyboard firmware, because it works as both keyboard and mouse and connects as multiple device, which is not AFAIR supported by USG hardware. But if the USG code is portable enough, I probably could port it to the firmware, unless I hit size limit.

Note that I cannot start right now, as I have some other tasks to do. I expect to be available about July 19. -- Sent from my fruity BlackBerry phone. Please excuse my brevity.

marmarek commented 5 years ago

IMO crypto part here may be challenging, because we have small plaintext data packets, with not-so-high latency requirements (20ms may be ok, 100ms rather not). Some issues:

As for the key exchange - indeed compile time should be enough for PoC.

The sys-net part might be tricky a bit, as USB is AFAIR more complex than just pidirectional pipe.

Yes, but you can use HID reports as more-or-less a transport layer for arbitrary packets.

v6ak commented 5 years ago

IMO crypto part here may be challenging, because we have small plaintext data packets, with not-so-high latency requirements (20ms may be ok, 100ms rather not).

You are right. IIRC I was looking for performance of AES on some relevant CPUs and 20ms seems to be achievable. Meybe the idea about 100Hz above is related to it.

Some issues:

  • timing based attacks
  • replay protection

Thanks for pointing this out, I have both in my mind. (You can find strings “replay” and “timing” in this discussion.)

Yes, but you can use HID reports as more-or-less a transport layer for arbitrary packets.

I didn't know these. I was thinking about some kind of USB COM emulation. Maybe any of them will do what we need at a different effort. @robertfisk, what's your opinion? -- Sent from my fruity BlackBerry phone. Please excuse my brevity.

robertfisk commented 5 years ago

@v6ak Great, I think we can work together to implement the encrypted protocol.

I understand your preferred dev platform is the Teensy 2 with an Atmega 32U4? Can you point me to a Ergodox firmware repository I can fork? While I have reservations about the encryption being done on a chip directly connected to sys-usb, I think it is worthwhile to maintain more than one type of supported hardware. I can also send you a USG for dev purposes.

While reviewing the libsodium documentation I saw a recommendation to use libhydrogen for constrained embedded systems: https://github.com/jedisct1/libhydrogen/wiki

I am (slowly) reviewing USB documentation, and will have some recommendations for our transport layer in a week or two. I think by July 19 we should have a plan in place.

v6ak commented 5 years ago

Hello @robertfisk, I am sorry for the delay.

I am using this firmware: https://docker.pkg.github.com/cub-uanic/tmk_keyboard

For transport layer, do you think that USB COM is OK? IIUC, this would be super easy to implement in sys-usb just with Bash pipe redirection and some udev rules.

I have also started with writing some draft of the protocol (more or less, consolidated comments from this thread). I have realized we probably need a CSRNG in the keyboard system. Without that, we probably can't make it secure. Do you think it is feasible? This might require to add some sensor that measures some noise.

robertfisk commented 5 years ago

Hi @v6ak, here's a similarly delayed reply...

Transport layer

I agree with Marek that HID reports are a better choice than emulated serial for our application. This is what the Yubikey uses in U2F mode. We can send packets up to 64 bytes large, up to 1000 times per second. We only need a udev rule to match our device, then access /dev/hidraw using libudev. We can locate our device by looking for a specific usage page and usage in the HID report descriptor as described in the FIDO CTAP protocol specification: https://fidoalliance.org/specs/fido-v2.0-rd-20170927/fido-client-to-authenticator-protocol-v2.0-rd-20170927.html#hid-device-implementation

Our implementation can likely be based on Yubico's libfido2. Although ours will be much simpler as we don't need to support session management with multiple software clients: https://github.com/Yubico/libfido2

Random number generation

There is no hardware random number generator in the USG, and probably none in the Atmega either. AFAIK our only source of entropy is the timing of interrupts on the USB bus. In the case of the Atmega this is the host USB bus, and thus attacker controlled. Probably not a good idea to rely on that. The USG will be performing encryption on the downstream side, so USB interrupts will be coming from the presumably trusted keyboard. This will get us some entropy but it certainly won't be cryptographically secure. Could we get by with just a nonce on the device side?

v6ak commented 5 years ago

Hello,

In transport layer: OK, this is the harder way to implement in USBVM, but it should be still doable. Do you see some advantages of HID reports to the serial line emulation?

The Fido library is an interesting idea as they likely want to solve similar issues. At least, it can be a source of inspiration.

Ad RNG:

Also, we could relax the requirements on RNG a bit. There are two purposes for RNG:

marmarek commented 5 years ago

In transport layer: OK, this is the harder way to implement in USBVM, but it should be still doable.

Should still be easy, there is /dev/hidraw0 and also multiple easy libraries (including python bindings).

Do you see some advantages of HID reports to the serial line emulation?

I think mostly stream vs packets. But also easier to provide distinct metadata of the device (and avoid ModemManager trying to talk to it as it was a modem...).

For dom0, we probably would need such library, but I see there two pitfalls. First, we would need the library there to allow working in split mode (or to emulate the USB device in dom0, which is probably not what I would like to do).

See input-proxy - it already has a code to drive uinput device - an input device backed by an user space. It's done in C, but trivial to do that in other languages as well.

Second, we would need an additional library outside of Fedora repo in dom0.

What do you mean? You need decryption stuff anyway, anything else?

v6ak commented 5 years ago

For dom0, we probably would need such library, but I see there two pitfalls. First, we would need the library there to allow working in split mode (or to emulate the USB device in dom0, which is probably not what I would like to do).

See input-proxy - it already has a code to drive uinput device - an input device backed by an user space. It's done in C, but trivial to do that in other languages as well.

Second, we would need an additional library outside of Fedora repo in dom0.

What do you mean? You need decryption stuff anyway, anything else?

Maybe I did not write that clearly, but both points were related to the idea od using libfido. That is, libfido probably wasn't designed with the dom0–USBVM split in the mind and also it is not in Fedora repo.

robertfisk commented 5 years ago

Do you see some advantages of HID reports to the serial line emulation?

I think mostly stream vs packets. But also easier to provide distinct metadata of the device (and avoid ModemManager trying to talk to it as it was a modem...).

I agree. Serial emulation requires implementing our own packetiser with timeouts, while HID will give us the packets directly. We also have to deal with device detection - both ModemManager talking to us, and us querying other serial devices like modems. By example, my JTAG programmer appears as /dev/ttyUSB0 and the last thing I want is for the input proxy to open the port and break something.

Whereas using the HID method, nobody will interfere with the device and it will sit quietly until the input proxy finds it. To me this appears a much cleaner solution.

We shouldn't need libfido in dom0, we should only need to decode the packets passed from sys-usb.

Entropy

I have seen some implementations based on transistors or capacitors. Is this way feasible with USG?

A hardware noise source is not as easy to design as one might think. Adding one to the USG would take several weeks of design work and cost around $1000 before production can start. That's just not going to happen for a niche product.

There are two purposes for RNG:

To prevent attacks based on a replay from USBVM. (Those attacks could lead to cryptographic issues and potential decryption.) For those purposes, just uniqueness is enough. Even counters would be good enough. However, this would require us to implement counters in a way that does not kill flash memory… maybe some kind of wear leveling… I see this might get non-trivial.

I was about to describe how we could implement a nonce using spare flash memory, but then I remembered that the USG locks its flash memory on startup to avoid a badUSB device permanently compromising one side of the firewall. This prevents us saving our nonce value between restarts.

This leaves us to rely on weaker sources of entropy - the timing of USB interrupts and the content of HID packets received by the keyboard. It won't be considered cryptographically secure, but should be enough to set a nonce starting value for the session.

For initial key exchange (like Bluetooth SPP) in future versions (after MVP). Thus requires CSRNG. This however happens rarely. If this takes one minute, it is inconvenient a bit, but given the (in)frequency if such operation, it can be OK.

We can ask the user to bash on the keyboard until enough entropy is gathered... !

ioleo commented 4 years ago

Would it be possible to restrict external keyboard/pointer devices to certain applications? Example, I'd like to use graphical tablet and external keyboard over USB, but I only need it in context of GIMP window. So, as soon as I focus on dom0 or any other app in the same VM (say, Firefox or Terminal), these devices could be blocked from sending any events?

robertfisk commented 4 years ago

That would be a question for the dom0-side developer (which I am not unfortunately)

ioleo commented 4 years ago

@andrewdavidwong can you bring it to attention to the right person?

andrewdavidwong commented 4 years ago

@v6ak, are you still willing to be the dom0-side developer for this?

DemiMarie commented 4 years ago

@robertfisk Sadly, without a cryptographically secure RNG, I do not believe that this can be implemented securely. The problem is that the USG device is entirely deterministic and stateless, which means that replay attacks are trivial. Adding randomness externally won’t work because there is no way to know that said randomness can be trusted.

One workaround I am aware of is for the device to have a secret asymmetric key injected at the factory. dom0 would then encrypt data using the corresponding public key, and the resulting shared secret would be used to secure communication. For this to be acceptably secure, however, the USG would need a tamper-resistant secure cryptoprocessor, which would most likely be too expensive. Otherwise, anyone who gained access to the device later could obtain the key and use it to decrypt past traffic.

As far as the USB interface is concerned, the best solution I can come up with is to use an ARM chip where the USB hardware cannot perform DMA transfers, and which has an MMU. This means that seL4 (a formally verified microkernel) can be used for isolation. The verification of seL4 is only valid for a specific ARM board, but if I know which board will be used, I can ask the seL4 developers how difficult it would be to port the verification to it. The drivers would need to be implemented in userspace, and without DMA performance would likely be poor.

marmarek commented 4 years ago

It all depends on the threat model. I'd focus about scenario where another USB device compromises sys-usb - the solution should prevent compromised sys-usb to sniff keyboard traffic, or to inject key strokes. But I would not consider physical attacks on the USG device itself in the scope, simply because it is unrealistic to protect against them - attacker having physical access to that device, could also install a hardware implant in the keyboard itself, or the keyboard-side of the USG device. For the same reasons, attacks from the keyboard-side of the USG device are less important in this use case (contrary to the original USG purpose). In this model, tamper-resistant key storage is not necessary. But RNG is still an issue. Same as key exchange. Perhaps user can help with this in some way - for example by typing some initial seed/key/whatever on the keyboard after entering some special initialization key combo?

As for "anyone who gained access to the device later could obtain the key and use it to decrypt past traffic", that should be easy-ish to protect against, by key rotation. Once you have provisioned secure communication channel, you can use it to periodically rotate keys, and then USG can erase old ones. I think this can be even done without interactive channel by generating new key (or a seed for the key) by hashing old one. Having old key both sides can generate new one, but having just new one key you cannot derive old ones nor decrypt old traffic.

DemiMarie commented 4 years ago

We can use standard Curve25519 ECDH for the key exchange, possibly with a post-quantum algorithm (NTRU?) mixed in for additional protection. Authentication would be handled by having dom0 put the keyboard in a special mode (indicated by a hardware light) and display a hash of the key exchange. The user then enters the hash into the keyboard, and the USG checks the hash against expected value. If they match, it means that the key exchange is valid and subsequent traffic cannot be intercepted or tampered with.

Key rotation is indeed easy, but it requires a RNG on the device. And requiring the device to re-pair every time is a horrible user experience, so the device will need to be stateful as well.

From my perspective, this is an ideal use-case for a RISC-V or ARM microcontroller with an MMU. That means that seL4 can be used for isolation, so the host-facing USB stack need not be trusted. One will need to disable DMA, though, and make sure that the USB driver cannot re-enable it.

marmarek commented 4 years ago

Key rotation is indeed easy, but it requires a RNG on the device.

Not necessary if you have secure communication channel set before - you could send new keys from the host, or generate based on the old ones. This won't protect against decrypting future communication in case of the current key compromise, but will protect against decrypting old communication. To have forward secrecy, I think indeed full re-pair would be needed which is bad UX.

As for the isolation, please note the USG device have two separate microcontrollers - one for the host USB side and one for the device USB - specifically to isolate those USB stacks from each other.

DemiMarie commented 4 years ago

That still leaves the question of how the keys will get on to the device to begin with. I would strongly prefer if they were generated on the device itself, which (again) requires an RNG. Furthermore, the USG is stateless, which is incompatible with persistent pairing.

Instead of a separate device, it seems that a much better approach would be for the keyboard itself to handle the crypto, which might be possible with modern open-source keyboard firmware.

DemiMarie commented 2 years ago

Conclusions so far: