Key Formats

September 22, 2017 (Last Modified: November 28, 2023)

Page content

Update: After a little digging, I understand where the leading 0x00 comes from on the EC public key.

I’ve recently been working on the MCUboot project. A key feature of this bootloader is its use of digital signatures to verify images both before performing upgrades, and optionally, also before running them. The code currently supports RSA and ECDSA signatures, and we are working on adding support for EdDSA signatures (specifically Ed25519).

In addition to the specific algorithms used to make and verify the signatures, using signatures requires developing the protocol used to communicate the signatures. Often, protocols are though of as the data that is communicated over a communication channel, such as a network connection. However, the concept of a protocol applies just as much to the bootloader; the difference being that the communicating parties are separated in time. In addition, the communication only flows in one direction.

There are several parties involved. The most obvious one being the bootloader itself. Since this is verifying signatures, we will refer to it as V. The party that signs the images will be S. In addition, there is a party that will generate the public and private keys, which we will call G.

Specific to MCUboot, the tool imgtool.py is used for both G to generate the key, and S to sign images (it will likely be used by different parties), and the verification V happens within the startup code in the bootloader.

RSA

RSA is one of the first practical public-key cryptosystems, and is still widely used. RSA is well understood, and reasonable fast. Its primary disadvantage is that the values used (both public and private keys, as well as the signatures themselves) are quite large for a given security level. For example, in MCUboot, we use a 2048-bit RSA key, which makes for signatures that contain 256 bytes of signature payload.

Because of its age, there are several different encoding formats used for RSA keys. For private and public key storage, that defined in PKCS1 (also RFC3447) define formats for the private a public keys. Both are DER-encoded ASN.1 sequences. The public key is generally written in PEM format, which consists of a header and footer text line surrounding the base-64 encoded representation of the DER encoded data.

Since the signature is a single large integer, we can simply directly use the byte representation of this integer as the signature. MCUboot defines a TLV format to hold the signature payload, and these 256 bytes are the direct payload.

Because of the ubiquity of these formats, most of the libraries for doing RSA already support encoding in this format. The private key file is interoperable with other tools, including openssl.

ECDSA

ECDSA is another signature algorithm based on the Digital Signature Algorithm (DSA), but using elliptic curves instead the discrete logarithm problem. An additional complexity for elliptic curves is that the particular curve must be chosen. Most elliptic curve implementations are optimized for specific curves, and this, therefore, limits the choices of curves. For MCUboot, we have chosen the “prime256v1” (NIST P-256) curve. There are, however, some concerns about the security of this curve.

RFC5915 defines an encoding for EC private keys, which we use to provide interoperability with openssl. The public key format is described in RFC5480, with the key always encoded in the uncompressed form. In our case, the algorithm identified must always be: id-ecPublicKey, secp256r1. The private key is:

ECPrivateKey ::= SEQUENCE {
  version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
  privateKey     OCTET STRING,
  parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,
  publicKey  [1] BIT STRING OPTIONAL
}

The DER bit string encoding prefixes the data with a single octet that indicates how many bits of the last octet aren’t part of the data item. In this case, since the key is always in full octets, this will always be zero.

The publicKey payload itself is encoded in “uncompressed” format, which is 0x04 followed by the 32-bytes of ‘x’ and 32-bytes of ‘y’, making the total payload 66 bytes (1 byte for the 0x04, and 1 byte for the 0x00 and the 66 bytes of the two coordinates.

Note that many DER encoding/decoding libraries leave this leading octet bit count up to the caller, although others, such as the openssl encoder take care of it for the caller.

The ECDSA signature itself is encoded as an ASN.1 sequence of INTEGERS for just the two values. See MCUB-85 for a issue regarding extrapdding, however. It is unclear where this format came from.

PKCS 8

In addition to the above specialized key encoding formats, PKCS8 RFC5208 defines a private key file format that works with multiple algorithsm. Instead of the algorithm being specified out of band (in the PEM header), the ASN.1 encoding includes an object identifier to describe the particular algorithm used.

The openssl documentation states

this command uses the traditional SSLeay compatible format for private key encryption: newer applications should use the more secure PKCS#8 format using the pkcs8 utility.

The MCUboot tooling doesn’t currently support password protected private key files. Both the ECDSA and RSA formats above have ways of protecting the private key files, but are less secure than the format described in pkcs8.

If we desire to implement password protection in the imgtool.py tooling, moving both RSA and ECDSA to pkcs8 would be a good idea.

Ed25519

There is ongoing work (at the time of this writing) to add support for the EdDSA digital signature algorithm using Curve25519 (the combination frequently called Ed25519). Although some of the benefits of this algorithm, such as high performance aren’t really applicable to a very memory constrained device that MCUboot is intended to run on. There is some additional safety that can be gained by using this curve.

Tracking down the key and signature formats for Ed25519 is a bit harder, since the use of this key is new. The essence is to use PKCS8 for the key storage format, and for an OID to use, use this draft which defines the OID 1.3.101.112 for id-Curve25519ph.

Most digital signature algorithms operate on a hash of the message. Ed25519 is unique in expecting to be given the message itself. It generates a prefix to the message before hashing it, which mitigates prefix attacks that may be found on the hash function.

However, the current implementations do this by requiring RAM buffers slightly larger than the image being signed. Since we don’t have this kind of RAM in MCUboot, we instead use Ed25519 to sign a hash of the image. This is known as “pre hashing”. It effectively bypasses the mitigation of the prefix attack, but allows the algorithm to be used with limited RAM. This RAM usage is strictly an implementation issue, and could be fixed if the additional security is desired.

As far as the signature encoding goes, Ed25519 defines its signature as a block of 64 bytes (it is encoded internally). There is no need to encode it further. If the public key is also placed directly in the bootloader, it would allow an Ed25519 build of MCUboot to avoid bringing in the DER decoder, saving additional space.

Conclusion

Cryptographic protocols, and associated standards can easily feel like a maze of twisty passages, all alike. I’ve attempted to summarize what I have learned about the formats and protocols we’re using in MCUboot, although there are still a few things I don’t understand, and seem to just be hard coded.