Hardware wallet wire protocol

[slush]

Hi everybody,

after short discussion with someone42, we decided to start separate thread discussing wire protocol used for future hardware wallets. We would like to find some universal and flexible solution which can become a standard, to make easier life for programmers of bitcoin desktop clients.

My current proposal is to use generic class USB HID device, which can be used without installation of drivers across every major operating systems (especially MS Windows). There are some limitations, like 64 bytes of message payload and communication can be initiated only by the computer (polling).

I want to use HID protocol just like a transport for higher level protocol, instead of using some custom binary format. No, this time I'm not going to propose JSON-RPC :-), but I think Protocol Buffers is a good choice. There exists some lightweight implementations for microcontrollers, it is super-easy to use PB from every major programming language and it is well defined high level protocol (in comparsion to some custom-built protocol on top of HID messages).

There's my current draft of proto file: https://github.com/slush0/bitkeylib-python/blob/master/protobuf/bitkey.proto

I completely dropped the idea of storing custom private keys on the device, I plan to use the seed for BIP32 or Electrum algorithms on the device instead. It also makes the protocol a bit easier, because there's no need for messages handling with custom keys. I'll try to describe every message in my next post.

[slush]

How to encode protobuf message into the stream?

Encoded protobuf message contains only message payload itself. There's no header or terminator; for this reason we need to define stream encoder/decoder for protobuf messages.

Every protobuf message will be encoded into the stream in following way:

a) First two characters are magic identifier "##" (0x23, 0x23).
b) 2B of message ID (encoded as big-endian unsigned short).
c) 4B of message length (encoded as big-endian unsigned int).
d) The of the payload is binary-encoded PB message.

There must be standardized mapping between message ID and protobuf message definition. For now I'm using following mapping: https://github.com/slush0/bitkeylib-python/blob/master/bitkeylib/mapping.py but I'm open to discussion on this topic.

Demonstration encoder/decoder in python is implemented here: https://github.com/slush0/bitkeylib-python/blob/master/bitkeylib/transport.py

How to encode protobuf stream into HID message:

1. Compose PB message stream as described above
2. Split string to 63-bytes long payload chunks
3. For every chunk create HID message in format: 1B = chunk size (0x01-0x3f), 0-63B PB payload

Why to encode chunk size into the message? Some USB HID controllers use higher values of first character (>0x3f) for custom commands like modifying re-programming vendor ID etc. Storing chunk size at 0th message character will make the protocol compatible with wide range of existing controllers.

Note that I'll start playing with some HID controllers next week (I'm waiting for samples) so maybe this will be the subject of change.

Standard message flow:

All communication is always initiated by the computer. Device is passive and responds with pre-defined sets of responses for every request.

1. Computer must start communication with "Initialize" message. This tells the device to restart it's current state and respond with "Features" message.
2. Computer can request device's UUID. This is unique binary string indentifying device's MCU (serial number), NOT device's USB controller. Although USB controllers can report vendor ID, product ID and so on, it is very likely that DYI hackers won't be able to modify USB controllers on their own (it requires some additional effort), so bitcoin client should use UUID to distinct between two tokens.
3. Although some responses are sent by device instantly (like GetUUID), most of them are blocking, because they requires manual confirmation (pressing the button) by the user. Bitcoin client should be aware of this and implement communication with the device in separate thread, to not block client's UI or other functionality.

Additional protection:

All important responses must be confirmed by pressing the button on the device by the user. Some users still want to use additional protection:

1. One Time Password - when enabled, device prints few characters on it's internal display and send "OtpRequest" response to the computer. User must retype the OTP from display to computer. Computer then sends "OtpAck" message. When correct, device sends the response of original request to the computer. OTP prevents user to pressing the button accidentally. By typing four characters to the keyboard, user confirms that he really want to perform this action.

2. PIN (password) protection - Although stealing of bitcoins from the hacked machine is impossible, attacker still have a physical access to the token. For this reason, device can be protected by the password. In this case, device responds with "PinRequest" to the computer and user must type correct password to the device's keyboard. Computer then sends "PinAck" message, containing the password. When corect, device send the response of original request to the computer. Although PIN isn't perfect protection (especially because you're typing the PIN to the computer's keyboard), with PIN-protected device, attacker must gain the physical access to the token AND have an access to hacked computer where user previously typed the password.

Device can combine OTP+PIN protection. The message flow will be following:

Code:

C: GetEntropy()
D: OtpRequest()
C: OtpAck(otp)
D: PinRequest()
C: PinAck(pin)
D: Entropy(entropy)

 The most paranoid setup will require pressing of physical button to confirm the action, then rewriting the OTP and writing down the PIN. As far as I can say, it is still pretty comfortable. Rewriting four or five alphanumeric characters is super easy and the password itself don't need to be super-long, as it is just additional security feature.

[someone42]

My current proposal is to use generic class USB HID device, which can be used without installation of drivers across every major operating systems (especially MS Windows). There are some limitations, like 64 bytes of message payload and communication can be initiated only by the computer (polling).

I'm don't mind which USB class device is used. I think the primary criteria is how easy it is to work with the most common combinations of programming languages and operating systems (which unfourtunately is a lot of combinations). The only other appropriate USB classes I can think of are HID and CDC (i.e. a serial port).

There are problems (you appear to be aware of them as well) with USB serial ports in Windows, notably the need to supply a .inf, and the bugginess of usbser.sys. I was going to work around these problems by instead emulating a FTDI USB-to-serial chip. Every major operating system has reliable drivers for the FTDI chips included, and the protocol seems quite simple (from looking at the Linux driver sources).

The advantages of implementing a serial port are:

• Easy to work with; often OSes allow you to treat them as a non-seekable file.
• It's possible to use common terminal programs to do debugging or firmware updating.

There's one major disadvantage: device discovery is hard. There's no easy, portable way to "know" what a serial port is connected to without sending something and waiting for the correct response.

I think USB HID is a good choice. Advantages:

• Allows you to choose a VID/PID (the FTDI emulation solution above requires you to use an FTDI VID/PID).
• Easy device discovery; just query the product descriptor string.

The only disadvantage I've come across in my research: apparently, in Linux, you need to detach a kernel driver in order to properly communicate with a HID class device. This can be done on most systems, but I worry that it will break on some Linux configurations. Please correct me if the situation is different now.

[slush]

I'm don't mind which USB class device is used. I think the primary criteria is how easy it is to work with the most common combinations of programming languages and operating systems (which unfourtunately is a lot of combinations). The only other appropriate USB classes I can think of are HID and CDC (i.e. a serial port).

Currently I'm coding it for serial port as well, because I still don't have USB controllers from the vendor.

There are problems (you appear to be aware of them as well) with USB serial ports in Windows, notably the need to supply a .inf, and the bugginess of usbser.sys. I was going to work around these problems by instead emulating a FTDI USB-to-serial chip. Every major operating system has reliable drivers for the FTDI chips included, and the protocol seems quite simple (from looking at the Linux driver sources).

FTDI don't work in Windows out of the box and the installation is a bit weird. I spent some time to get my BFL Single working on Win7 :-/.

We want to use USB-to-serial for the Raspberry Pi shield (as RPi don't have usable USB port for HID device), too. But from the computer side I think there should be just one supported transport - USB HID.

[someone42]

I want to use HID protocol just like a transport for higher level protocol, instead of using some custom binary format. No, I'm not going to propose JSON-RPC at this time :-), but I think Protocol Buffers is a good choice. There exists some lightweight implementations for microcontrollers, it is super-easy to use PB from every major programming language and it is well defined high level protocol (in comparsion to some custom-built protocol on top of HID messages).

I was going to come here and whinge about your choice of protocol buffers, but after a bit more research, I'm liking them more. Their encoding is quite lean; I was worried that it would be like XML. Also, there are tiny parser libraries (eg. nanopb) written in C out there.

So now I think it's a good idea to use protocol buffers. My only request is that, for all the non-signing messages, there is a maximum message size specified. A reasonable value would be something like 256 bytes. This allows buffers to be statically allocated (i.e. without the use of malloc). The limit cannot apply to signing messages, because transactions can be very large.

[deepceleron]

Want crazy talk? How about Bluetooth?

Applications...
-Transfer of files, contact details, calendar appointments, and reminders between devices with OBEX.
-Replacement of previous wired RS-232 serial communications in test equipment, GPS receivers, medical equipment, bar code scanners, and traffic control devices.

[someone42]

FTDI don't work in Windows out of the box and the installation is a bit weird. I spent some time to get my BFL Single working on Win7 :-/.

We want to use USB-to-serial for the Raspberry Pi shield (as RPi don't have usable USB port for HID device), too. But from the computer side I think there should be just one supported transport - USB HID.

I was mistaken about FTDI drivers on Windows.

Looks like it is USB HID then.

[slush]

Want crazy talk? How about Bluetooth?

No way because of battery...

Edit: However HID over Bluetooth is still possible, so even if we will standardize HID device, some future wallet devices can use Bluetooth and still have compatible protocol.

[stick]

The only disadvantage I've come across in my research: apparently, in Linux, you need to detach a kernel driver in order to properly communicate with a HID class device. This can be done on most systems, but I worry that it will break on some Linux configurations. Please correct me if the situation is different now.

Detaching a kernel driver is just one function call from libusb or a similar library. Also some combinations of VID/PID (e.g the ones Silabs CP2110 use) are IIRC not interpreted in Linux kernel. So I don't think this is a big issue ...

[stick]

I was going to come here and whinge about your choice of protocol buffers, but after a bit more research, I'm liking them more. Their encoding is quite lean; I was worried that it would be like XML. Also, there are tiny parser libraries (eg. nanopb) written in C out there.

Same here. I was a little bit sceptical when I saw the generated code from http://code.google.com/p/protobuf-c/ (pure C generator for Protocol Buffers, original implementation supports just C++), but I was quite happy when I saw the code that came out of nanopb - http://code.google.com/p/nanopb/

[jim618]

A few points and questions:

Timeout
You state:

Standard message flow:
3. Although some responses are sent by device instantly (like GetUUID), most of them are blocking, because they requires manual confirmation (pressing the button) by the user. Bitcoin client should be aware of this and implement communication with the device in separate thread, to not block client's UI or other functionality.

Is it worth adding in a timeout which is, from the computer's perspective, equivalent to a 'Cancel' operation ? i.e Device asks user to 'Confirm or Cancel'. User does nothing and after, say, 60 seconds computer says "Ok, that is a cancel" and moves to a more general "nothing happening state". It stops you getting stuck waiting forever for a button press that never comes.

PIN/ OTP exchanges
In 'Standard message flow, first paragraph' you mention that the computer initiates the conversation but with the PIN and OTP the device sends the PinRequest / OTPRequest. Do these occur as responses to the GetEntropy computer request only ?

i.e. valid exchanges are:

C: GetEntropy()
D: Entropy(entropy)

or

C: GetEntropy()
D: OtpRequest()
C: OtpAck(otp)
D: Entropy(entropy)

or

C: GetEntropy()
D: OtpRequest()
C: OtpAck(otp)
D: PinRequest()
C: PinAck(pin)
D: Entropy(entropy)

also, is it valid to have the PinRequest/PinAck before the OtpRequest/OtpAck ?

(just trying to pin down what are valid exchanges and which are invalid).

Checksum and Chunking/ Dechunking
Does the bytestream for USB have guaranteed integrity ?  IE is it necessary to have a checksum for each of the 64 byte message or is that taken care of in the transport protocol ? If required we could simply have 1 checksum byte = XOR(payload bytes) i.e.

1B = payload length
up to 62B = payload
1B = checksum defined as XOR(payload)

Also, you state that the PB message is chunked into 64 byte packets. When they are 'dechunked' how do you know the boundaries of the packets to stitch them back together to recreate the PB messages? Do you need "this protobuf message is chunked over X packets' at the beginning of the PB message.

I am just thinking of how to make the 'chunking' and 'dechunking' as simple and unambigous as possible. Ideally you want it a dumb transport layer that understands nothing of what is in the messages.

[casascius]

I think this should be invented layers first if it's intended to become a credible standard.

I would suggest starting with a message protocol that would be workable over a simple RS232-like serial line.  Start with the assumption that basic error detection and recovery will be needed, so the protocol isn't restricted to media that has it built in.  Then worry about adding abstractions to it like chunking.  USB-CDC and bluetooth can both abstract a serial line "out of the box".  If you invent a protocol that's centered around USB-HID, then nobody who wants to extend that protocol to work over TCP/IP or radio waves or named pipes or tin can telephones or light sensors vs flashing boxes on a screen or any of the other useful ways to move data is going to want to deal with implementing "USB-HID" contingencies where they aren't needed.

[someone42]

Checksum and Chunking/ Dechunking
Does the bytestream for USB have guaranteed integrity ?  IE is it necessary to have a checksum for each of the 64 byte message or is that taken care of in the transport protocol ? If required we could simply have 1 checksum byte = XOR(payload bytes) i.e.

1B = payload length
up to 62B = payload
1B = checksum defined as XOR(payload)

Also, you state that the PB message is chunked into 64 byte packets. When they are 'dechunked' how do you know the boundaries of the packets to stitch them back together to recreate the PB messages? Do you need "this protobuf message is chunked over X packets' at the beginning of the PB message.

I am just thinking of how to make the 'chunking' and 'dechunking' as simple and unambigous as possible. Ideally you want it a dumb transport layer that understands nothing of what is in the messages.

USB does have some error checking (one CRC16 per packet), so there's probably no need for us to implement it anywhere.

As for how to determine the packet boundaries, protocol buffers appear to lack a terminator. So length information must be out of band:
1. One option is to include the length of the packet somewhere. For example, the length (eg. as a packed, little-endian 32 bit integer) can be prepended to the protocol buffer.
2. Another option is to rely on the chunk lengths. When you see a chunk with less than 63 bytes of payload, you know it's the end. Note that if the packet length is a multiple of 63, to avoid confusion, an extra 0-payload packet needs to be sent as well.

Lastly, a bit of detail: how is the message type sent? A single byte prepended to the protocol buffer will do; but does anyone have a better solution?

[slush]

Timeout

Strictly speaking, device itself is just a state machine. I don't think defining some timeout is required. Computer can reset the device at any time by sending "Initialize" message, as I defined above.

From computer perspective, some "Ok, nothing happened" is completely implementation dependent and we don't need to specify this. Confirmation dialog can be opened for unlimited time and nothing wrong happen...

In 'Standard message flow, first paragraph' you mention that the computer initiates the conversation but with the PIN and OTP the device sends the PinRequest / OTPRequest. Do these occur as responses to the GetEntropy computer request only ?

PinRequest and OtpRequest can basically appear as a response for any sensitive call. GetEntropy was just an one example.

I personally implement Pin/Otp handling in bitkeylib (python) independently to the call itself. When device respond with PinRequest or OtpRequest, library simply ask user for input.

C: GetEntropy()
D: Entropy(entropy)

or

C: GetEntropy()
D: OtpRequest()
C: OtpAck(otp)
D: Entropy(entropy)

or

C: GetEntropy()
D: OtpRequest()
C: OtpAck(otp)
D: PinRequest()
C: PinAck(pin)
D: Entropy(entropy)

also, is it valid to have the PinRequest/PinAck before the OtpRequest/OtpAck ?

Yes, all these combinations can happen. Although asking for Otp before Pin make sense, it makes guessing/bruteforcing of the pin almost impossible, because very attempt requires unique OTP...

Does the bytestream for USB have guaranteed integrity ?  IE is it necessary to have a checksum for each of the 64 byte message or is that taken care of in the transport protocol ? If required we could simply have 1 checksum byte = XOR(payload bytes) i.e.

USB HID is very simple protocol and yes, it guarantee the order and integrity. So no need for adding it manually.

Also, you state that the PB message is chunked into 64 byte packets. When they are 'dechunked' how do you know the boundaries of the packets to stitch them back together to recreate the PB messages? Do you need "this protobuf message is chunked over X packets' at the beginning of the PB message.

You're right, I completely forgot to describe "magic character" and "message size" while encoding PB message into the stream. I'll complete the documentation above now.

I am just thinking of how to make the 'chunking' and 'dechunking' as simple and unambigous as possible. Ideally you want it a dumb transport layer that understands nothing of what is in the messages.

That's exactly how I defined it. There are three layers:

1. Transport - it just transport bytes from one side to another. I want to have only one transport based on USB HID in the specs, but technically it is possible to use serial port or system sockets as well. As I said, I'm already testing the protocol using named pipes. Part of transport specification is (for example) that one byte defining message length (report id in term of HID).

2. Stream encoding/decoding. It contains magic character + PB message length, to make decoding of the stream as easy as possible. I'll complete the docs above.

3. Payload encoding/decoding. I proposed Protocol Buffers, which seems to be pretty good choice for our needs.

Whole messaging stack doesn't need to understand transferred messages themselves, so everything is very flexible.

[slush]

I would suggest starting with a message protocol that would be workable over a simple RS232-like serial line.  Start with the assumption that basic error detection and recovery will be needed, so the protocol isn't restricted to media that has it built in.  Then worry about adding abstractions to it like chunking.  USB-CDC and bluetooth can both abstract a serial line "out of the box".  If you invent a protocol that's centered around USB-HID, then nobody who wants to extend that protocol to work over TCP/IP or radio waves or named pipes or tin can telephones or light sensors vs flashing boxes on a screen or any of the other useful ways to move data is going to want to deal with implementing "USB-HID" contingencies where they aren't needed.

Firstly, don't forget that we're not inventing new internet, but just specialized protocol for talking with quite a dumb device. Secondly, protocol itself (PB) isn't specific for some particular transport. And integrity checking should be a part of the transport itself, not the part of application protocol built on top of it.

Shortly said, it is possible to use the same protocol as described above over TCP without any modification.

[slush]

I just added the chapter "How to encode protobuf message into the stream?"

[jgarzik]

Good stuff.  Keep up the good work!

I think there are USB simulators to be found, which would make testing this easier.

[casascius]

Firstly, don't forget that we're not inventing new internet, but just specialized protocol for talking with quite a dumb device. Secondly, protocol itself (PB) isn't specific for some particular transport. And integrity checking should be a part of the transport itself, not the part of application protocol built on top of it.

Shortly said, it is possible to use the same protocol as described above over TCP without any modification.

Your dumb device is actually a brilliant device and is probably the future of Bitcoin as we know it.  In the interest of having as few competing protocols as possible, I'm just submitting to you my request that you do this one right, because the next person to make a device intended to be interoperable with yours will probably make some improvement to it that none of us can conceive of today, or run it over some transport that seems crazy here and now but makes total sense somewhere else (e.g. analog radio links in Africa, or DTMF over antiquated voice lines, or printed barcodes on pieces of paper), and you want his job to be as unencumbered as possible.

Simple integrity checking at the application level is commonplace and best practice.  Bitcoin addresses have integrity checking in them, despite them most commonly being passed through TCP and other channels that also have error checking.  Application-level error checking isn't supposed to reinvent transport-level error checking at the application level, it's there just to throw out corrupted requests as a failsafe and substituting a low-risk action (e.g. doing nothing) instead of taking uncommanded actions with costly consequences when you're dealing with real money.  A simple 32-bit CRC and a practice of ignoring messages failing the CRC check would be a minimum that any hardware should have no problem handling without being an unreasonable burden on application-level code.

In a round-about way... please just don't make this specific to hardware supporting USB.

[slush]

In a round-about way... please just don't make this specific to hardware supporting USB.

As far as Jim and Alan will be open to implement support for Pigeon transport, there's no limitation in protocol itself.

[someone42]

I would like to propose the convention that if the wallet sees a field in a protocol buffer that it does not recognise, if that field is 0, false or "" (depending on the type of the field), the wallet can safely ignore the field. On the other hand, if an unrecognised field contains something other than 0, false or "", a wallet must not ignore the field and must return a "feature not supported" failure message. This convention makes it easier to add additional fields in the future.

As it stands, nanopb currently doesn't allow this (it skips all fields it doesn't recognise). But I'm sure it's possible to modify the runtime decoder to follow this convention.

I see the approach slush has taken is to include a "Features" message which enumerates a wallet's features. I think a features list is somewhat open to interpretation. For example, what happens if a wallet only supports a subset of feature X? Does it report that it supports feature X or not? Another advantage of the ignore-on-zero convention is that client software doesn't have to put as many ifs all over the place - "feature not supported" is handled like any other wallet error.