SESAME (SErial Secure Adaptable Message Exchange)

Introduction

Microcontrollers often communicate with each other using a UART connection. Before such a serial connection can be used by the ECHO protocol, a mechanism is needed to initialize communication and prevent overflowing buffers on the peer. Furthermore, a means to secure the communication is required. For these purposes the SESAME protocol stack is developed.

SESAME consists of several layers, first using COBS (Consistent Overhead Byte Stuffing) to divide the stream of bytes into delimited packets, second a window protocol to prevent overflowing buffers, and third (optional) a layer that provides security.

Diagram

SESAME layer COBS

The first layer divides the stream of bytes of the serial communication into a number of packets. The purpose of this is to present well-defined packets to higher layers in the SESAME stack, where those higher layers can then define packet formats.

As specified by the COBS protocol, packets are separated by 0 bytes. This means that any 0 bytes inside the payload must be replaced. This is done by adding a first byte to the payload, which points to the first 0 byte in the payload. That 0 byte is then replaced by the index of the next 0 byte, etc. If no 0 byte is present within 254 bytes is present then an extra overhead byte is inserted. Please see the COBS specification for details.

SESAME layer Windowed

Using the Windowed layer, both sides of the communication notify and update their peer of available window size. A peer can only send packets up to the available window. Four packet types are defined:

  1. Init

  2. InitResponse

  3. ReleaseWindow

  4. Message

Init

Sending an Init packet initializes the protocol. An Init packet has one 16-bit unsigned parameter size which specifies the available window size, encoded in little endian order. An Init packet must be responded to with an InitResponse packet. Before receiving an InitResponse, a peer must assume that no window is available, so further packets may not be sent.

Init packet
Figure 1. Init packet

An Init packet consumes no window, and may always be sent. This results in an edge case resulting in an overflow, which works like this: Peer A sends an Init packet at an inconvenient moment. That packet may overflow peer B’s buffer. In that case, that overflow must result in peer B concluding that an Init packet has been received; it can then respond with an Init packet of its own, advertising its available window, and then reading peer A’s window size from its InitResponse packet. This way, the data lost in the overflown Init packet is retrieved. Since a sender has an empty buffer before sending an Init packet, that will not result in a repeated exchange of Init packets.

InitResponse

When an Init packet has been received, a host will clear its buffer, and advertise available buffer space using the InitResponse packet. Similar to the Init packet, the InitResponse packet has one 16-bit unsigned parameter size encoded in little endian which advertises available buffer size.

InitResponse packet
Figure 2. InitResponse packet

An InitResponse packet consumes 5 window bytes: 3 for the packet contents, 2 for the COBS layer (1 for the COBS overhead byte, one for the terminating 0).

ReleaseWindow

When a host has processed incoming packets, and therefore frees up buffer space, it advertises the freed up space using the ReleaseWindow packet. The ReleaseWindow packet has one 16-bit unsigned parameter size encoded in little endian which specifies the amount of bytes in the buffer freed up in addition to already known free space.

ReleaseWindow packet
Figure 3. ReleaseWindow packet

Message

Data sent by higher protocol layers are sent by Message packets. Each Message packet consumes a window amount equal to the size of that packet plus the COBS overhead of that specific packet, plus its terminating 0.

Message packet
Figure 4. Message packet

Quality Of Implementation

When implementing the Window layer, there are a few considerations:

  1. In order to avoid continuous exchanges of ReleaseWindow packets, hosts should only release window sizes bigger than 5. When determining the buffer size needed to exchange packets, the size of the biggest packet should be increased by 5 to accommodate for a ReleaseWindow packet.

  2. A sender should only send a message when enough window remains to also send a a ReleaseWindow packet. Otherwise, if both peers consume each other’s window, the protocol would enter a deadlock since neither peer is allowed to send a ReleaseWindow packet.

  3. If enough buffer space is available, a sender should avoid consuming the entire peer’s buffer with one message. This would result in the sender sending a big message, the peer processing that message and responding with a window release message, for which the sender had to wait until it sends its next message. Instead, a sender should send packets of only half the peer’s window size at a time. This enables the peer to process the packet, and send a window release while the sender is sending the next message.

SESAME layer Secured

This protocol layer provides confidentiality and integrity by encrypting packets and appending a MAC (Message Authentication Code). Since SESAME is geared towards embedded systems, and is not intended to be as flexible as a protocol like TLS, for simplicity some very specific choices are made regarding cryptographic schemes.

Encryption and authentication is done with AES-128 in GCM mode. AES-128-GCM requires a 128 bit key and an 128 bit Initialisation Vector (IV). Both directions of communication require their own unique key/IV pair.

Each message is encrypted with AES-128-GCM with the key and IV as parameters. This results in a cyphertext of size equal to the size of the message, plus a 16 byte MAC. Since in GCM IVs may not be reused, the IV is incremented in a specific way to avoid using the same IV twice: After each message, treat the IV as a 128-bit unsigned Big Endian number, and add 264 to it (discarding any overflow). This way, the protocol can securely handle 264 messages each of size at most 264 before a re-negotiation of keys is necessary.

Key establishment is not a responsiblity of the Secured layer; but care must be taken that the same key/IV pair should not be reused for different sessions, since encrypting two messages using the same key/IV pair will result in the XOR of the bit pattern of those two plaintext messages to be equal to the XOR of the bit pattern of the two cyphertexts of those messages.

There is one exception to that rule: If the first message sent consists of at least 128 bits of random data, then security is not compromised. The only information leaked is the XOR of two times 128 bits of random data, from which an attacker still learns nothing. One possible scheme of key establishment is therefore to hardcode the four Key and IV values for sending and receiving on both hosts, and to choose random new Key/IV values right after initialization.

After each initialization of the lower protocol layers (after receiving the Init packet in the Windowed layer), keys are reset to their default value, and key negotiation must start over before other messages are sent.

Symmetric key establishment

Many differrent ways exist to establish which keys the peers are going to use for the Secured layer; which scheme to use heavily depends on the context in which SESAME is used. Two schemes are defined in this specification.

Key Establishment: Hardcoded Keys

Both peers can be configured with hardcoded keys when implementers are confident that attackers can not extract those keys from the microcontrollers in which SESAME is implemented. A fixed key/IV pair is chosen for sending data from peer A to peer B, and a fixed key/IV pair is chosen for sending data from peer B to peer A. However, as indicated before, care must be taken to not send two messages under the same key. Therefore, before sending any other messages, each peer generates a new random key/IV pair, and uses the ActivateNewKeyMaterial method of the SymmetricKeyEstablishment ECHO service (see appendix) to send this pair to their peer. Upon reception of this method, a peer uses the presented key/IV pair for encryption of subsequent messages that it sends.

Key Establishment: Key Negotiation with Diffie-Hellman

In this scheme, a host does not need to be pre-programmed with the keys used by its peer. Instead, the Diffie-Hellman scheme is used to have the two peers negotiate the required key/IV pairs. In order to withstand man-in-the-middle attacks, the key exchange messages are signed, and the signature of a received key exchange message is verified by the receiving party.

The messages used for exchanging the Diffie-Hellman messages and certificates are sent over ECHO. Obviously, symmetric keys have not yet been established at that point. The secure layer is therefore configured with keys and IVs that consist of all zeroes. Implementations must take care that before the keys and IVs of the secure layer are replaced by the result of Diffie-Hellman key exchange are the only ECHO messages exchanged are of the Diffie-Hellman protocol.

In order to verify the signature, a party must either have the certificate of its peer, or have a root certificate by which the peer’s certificate’s validity is checked. In the latter case, a peer will use the PresentCertificate method of the DiffieHellmanKeyEstablishment ECHO service to inform its peer of a certificate to be used. A certificate is either presented in PEM or in DER format. A party will verify each certificate presented in this way by validating it against either one of the installed root certificates, or one of the earlier presented certificates.

After any certificate exchange, a party will generate a new Elliptic Curve Diffie-Hellman public/private key pair on the 256-bit curve defined by FIPS 186-5 and SEC1 (SECP256R1). It will then encode its public key (which is a point of the elliptic curve) in the 65-byte uncompressed representation as defined in SEC1 paragraph 2.3.3. It then uses ECDSA on the same SECP256R1 curve to compute the signature values r and s. After computing the public/private key and the signatures, it sends the public key and the r and s values using the Exchange method of the DiffieHellmanKeyEstablishment ECHO interface to its peer.

Upon reception, the peer uses the public key included in the received certificate to check the signature r and s of the presented public key. If this signature is correct, it computes the shared secret using its own private key and the peer’s public key using the Diffie-Hellman scheme. Key expansion is performed on the shared secret to generate enough material for the required key/IV pairs in this way: HMAC-DRBG-SHA256 is seeded with the shared secret, and generates 4 times 128 bits of data. The first 128 bits of data is KeyA, the next IVA, then KeyB, then IVB. Both parties perform a lexicographical compare of their Diffie-Hellman public keys. The party with public key that compares greater than the public key of its peer uses KeyA and IVA for sending data, the other party uses KeyB and IVB for sending data.

When key exchange is done, both parties can start sending other ECHO data than the key exchange messages.

ECHO over SESAME

ECHO is used over SESAME by serializing ECHO messages, dividing those messages into a series of chunks suitable to send over SESAME (so the maximum buffer size advertised by the peer must be taken into account), and sending those chunks. On the receiving end, those chunks are reassembled, and parsed as ECHO messages. Since ECHO is able to handle a continuous stream of data, multiple ECHO messages being concatenated do not pose any difficulties.

Appendix: Typical sequence

This sequence diagram shows a typical sequence of the SESAME protocol being initialized and a message being sent. The Secured layer is left out in this sequence.

Typical sequence
Figure 5. Typical sequence

Appendix: Implementation in amp-embedded-infra-lib

The protocol layers and key establishment schemes defined here are implemented in amp-embedded-infra-lib. Most of the classes are part of services/util.

The classes implementing the protocol layers are:

  1. SesameCobs (services/util/SesameCobs.hpp)

  2. SesameWindowed (services/util/SesameWindowed.hpp)

  3. SesameSecured (services/utilSesameSecured.hpp)

EchoOnSesame (services/util/EchoOnSesame.hpp) places ECHO on top of SESAME without security; main_::EchoOnSesame<max packet size> (services/util/EchoInstantiation) instantiates EchoOnSesame, SesameCobs and SesameWindowed to form a full ECHO on SESAME stack on top of a UART.

EchoPolicySymmetricKey (services/util/EchoPolicySymmetricKey.hpp) adds a policy to implement the Hardcoded Keys scheme on top of SESAME with security.

EchoPolicyDiffieHellman (services/util/EchoPolicyDiffieHellman.hpp) adds a policy to implement the Diffie-Hellman scheme on top of SESAME with security. This class is instantiated with one root certificate which is used to verify one certificate received by a peer.

Appendix: SesameSecurity.proto

syntax = "proto3";

import "EchoAttributes.proto";

package sesame_security;

message SymmetricKeyMaterial
{
    bytes key = 1 [(bytes_size) = 16];
    bytes iv = 2 [(bytes_size) = 16];
}

message DiffieHellmanMaterial
{
    // This method uses an EC Diffie-Hellman exchange over the 256-bit curve defined by FIPS 186-4 and SEC1
    bytes publicKey = 1 [(bytes_size) = 65];
    // The signature will be computed over the publicKey using the sender's certificate, which uses EC DSA over the same curve as the EC DH operation
    bytes signatureR = 2 [(bytes_size) = 32];
    bytes signatureS = 3 [(bytes_size) = 32];
}

message Certificate
{
    // DER-encoded X.509 certificate, signed by a CA
    bytes certificate = 1 [(bytes_size) = 512];
}

message CertificatePrivateKey
{
    // DER-encoded private key
    bytes privateKey = 1 [(bytes_size) = 121];
}

service SymmetricKeyEstablishment
{
    option (service_id) = 3;

    rpc ActivateNewKeyMaterial(SymmetricKeyMaterial) returns (Nothing) { option (method_id) = 1; }
}

service DiffieHellmanKeyEstablishment
{
    option (service_id) = 4;

    rpc Exchange(DiffieHellmanMaterial) returns (Nothing) { option (method_id) = 1; }
    rpc PresentCertificate(Certificate) returns (Nothing) { option (method_id) = 2; }
}

message SymmetricKeyFile
{
    SymmetricKeyMaterial sendBySelf = 1;
    SymmetricKeyMaterial sendByOther = 2;
}