Signature Verification and Where the Root Key Lives

An integrity check answers whether an image arrived intact. It does not answer whether the image came from someone entitled to replace firmware. A CRC is linear and can be recomputed by anyone; a hash is unkeyed and can be recomputed by anyone. The only mechanism that distinguishes an authorised image from an arbitrary one is a digital signature, verified against a public key that the device trusts and that an attacker cannot replace.

The engineering difficulty is not the mathematics. It is that the verification must happen in the bootloader, on a microcontroller, before any code the attacker controls has run, using a key that is itself stored somewhere the attacker cannot write.

The two-part structure of a signed image

Signing is applied to a digest, not to the image. The build computes a hash over the header and body, signs that hash with a private key, and appends the signature. Verification reverses the process: the bootloader recomputes the hash over the same range and verifies the signature against that hash and the public key.

This structure has three consequences that shape the implementation. The signature is a fixed-size field whose position must be known before parsing begins, so the image layout places it at a fixed offset or in a trailer of known length. The hash range must exclude the signature field, exactly as it excludes the digest field in the unsigned case discussed in image header and integrity validation, and for the same reason: a value cannot cover itself. And the bootloader needs two passes of work, hashing and verifying, with different resource profiles.

Hash-then-sign also means the hash function is part of the trust boundary. If the image is hashed with SHA-256 and the signature covers that digest, then a collision in SHA-256 would let an attacker produce a different image with the same digest and a valid signature. The signature scheme does not protect against a broken hash; it protects against modification of the digest. This is why the hash must be chosen from the same family the signature scheme is specified against rather than picked for convenience.

Which algorithms fit in a bootloader

Three families are in practical use, and they differ by orders of magnitude in the resources they demand.

RSA verification with a small public exponent is the cheapest option per byte of key. The public exponent is typically 65537, which is 2^16 + 1 and therefore has only two set bits, so the modular exponentiation reduces to sixteen modular squarings plus one multiplication for a 2048-bit modulus. The modulus itself must be stored, which is 256 bytes for RSA-2048 and 384 bytes for RSA-3072, and the intermediate values require a buffer of modulus size. Signature verification with a small exponent is therefore feasible on a small core, and it is why RSA remains common in firmware bootloaders even where ECC is preferred elsewhere. The cost is signature size: 256 bytes for RSA-2048.

ECDSA over a prime curve requires a point multiplication and a modular inversion, both of which need a big-integer library and a buffer of roughly twice the field size. Verification is dominated by two scalar multiplications, and the operation count is much higher than an RSA verification with a small exponent, though the key and signature are far smaller: a P-256 public key is 64 bytes and a signature is 64 bytes. The trade is space for time, and in a bootloader both are scarce.

Ed25519, the Edwards-curve scheme specified in RFC 8032, is the most recent of the three and has properties that suit constrained implementations. Verification computes [S]B - [k]A, a double-scalar multiplication on a twisted Edwards curve whose addition formulas are complete: there are no exceptional cases to branch on, which is what makes a constant-time implementation simpler than one for a prime-curve ECDSA. The arithmetic is defined over a field with a particularly efficient reduction, and the scheme is deterministic, so signing the same message twice produces the same signature and no per-signature randomness is required. Ed25519 public keys are 32 bytes and signatures are 64 bytes. Verification still requires the two scalar multiplications, so it is not free, but the small key and signature sizes and the smaller, branch-free verification code are what make it attractive where flash and stack are both tight.

The choice also depends on what the silicon provides. Parts with a cryptographic accelerator may implement only one or two of these, and a hardware hash engine is far more common than a hardware public-key engine. Where a hash accelerator exists, the hashing pass becomes nearly free and the public-key operation dominates the boot budget; where it does not, hashing a large image at software speed can cost more than the signature check.

/* Verify a detached signature over the header-plus-body region. The
   hash and signature calls stand for whatever implementation the
   bootloader carries; only their shape matters here. The signature
   sits in the trailer, outside the hashed range. */
struct signed_image {
    struct image_header hdr;      /* includes a digest field */
    uint8_t  body[];
    /* trailer, at hdr.image_length + sizeof hdr:
       uint8_t signature[SIG_LEN]; */
};

static int verify_image(const struct signed_image *img, const uint8_t *pubkey)
{
    uint8_t digest[HASH_LEN];
    struct sha256_ctx ctx;
    struct image_header hdr = img->hdr;
    const uint8_t *sig = (const uint8_t *)img + sizeof img->hdr + img->hdr.image_length;

    /* Hash the header with its digest field zeroed, then the body.
       The signature sits beyond image_length and is not covered. */
    memset(hdr.digest, 0, sizeof hdr.digest);
    sha256_init(&ctx);
    sha256_update(&ctx, &hdr, sizeof hdr);
    sha256_update(&ctx, img->body, img->hdr.image_length);
    sha256_final(&ctx, digest);

    if (memcmp(digest, img->hdr.digest, HASH_LEN) != 0)
        return -1;                                /* cheap rejection first */
    return ed25519_verify(sig, digest, HASH_LEN, pubkey);
}

The ordering in that function matters for boot time on a device that receives many bad images, which is exactly the case an attacker creates. Comparing the digest first rejects a corrupt image without spending a scalar multiplication. It is not a security measure, since an attacker who can forge a digest can also skip it, but it keeps a device from being made to spend its boot budget on garbage.

Key storage and the trust anchor

A public key stored in the same flash as the application is not a trust anchor. An attacker who can write the application slot can write the key region too, substitute a key they control, sign an arbitrary image, and the bootloader will verify it happily. The verification is then a consistency check, not a trust decision.

The anchor must therefore be in storage the update path cannot write. Three options exist on microcontrollers, and they differ in how much they cost and how much they can hold.

One-time-programmable memory, often implemented as fuses or as a dedicated OTP array, can be written once and never changed. Storing a 32-byte public key there is a natural fit: it is exactly the size of an Ed25519 key, and there is no need to rotate it. The cost is that a mistake is permanent, and a device whose key was programmed incorrectly cannot be recovered except by replacement. Some parts provide a small number of OTP words and a lock bit per region, which allows a staged process: program, test, then lock.

A protected region of the main flash, locked by the debug interface and by a write-protection setting in the boot configuration, is the second option. It is cheaper in silicon and weaker in one specific way: the protection is a configuration bit, and configuration bits can sometimes be changed by the same mechanisms that change the flash, particularly through a debug port that is not permanently disabled. If the part allows the protection to be lifted after the product ships, the anchor is only as strong as the provisioning process.

A dedicated secure element or a part with an immutable ROM that holds a key hash is the third option. The bootloader’s own public key is then not the anchor; the anchor is a hash of the bootloader, verified by ROM code that cannot be modified. This is the arrangement NIST SP 800-193 describes as a chain of trust rooted in immutable code, and it is the strongest of the three because the anchor is not a key at all but a digest of a known program.

The chain matters because a bootloader that verifies the application is itself code that can be replaced unless something verifies it. A design with a single verification stage protects against application replacement and not against bootloader replacement. Two stages, where an immutable first stage verifies a second-stage bootloader which verifies the application, extend the chain at the cost of an extra flash region and an extra boot step. Each stage must verify the next stage’s image before executing it, and each stage’s key must be stored where the previous stage can read it but nothing later can write it.

What verification cannot establish

Signature verification proves that the image was signed by the holder of a private key corresponding to a trusted public key, and that the image has not changed since. Four things follow from that, and none of them is what people assume.

It does not prove the image is safe to run. A signed image that hangs, or that drives an output into a damaging state, verifies correctly. Trial boot and rollback are orthogonal and remain necessary, which is why trial boot, confirmation, and automatic rollback applies to signed images exactly as it does to unsigned ones.

It does not prove the image is newer than what is installed. The signature covers the version field, but it says nothing about whether that version is acceptable. An attacker with access to an old signed image can replay it, and the device will verify it successfully. Preventing that requires a monotonic counter, which is the subject of anti-rollback counters and version monotonicity.

It does not protect against a key that is later compromised. A device provisioned with a key that leaks remains vulnerable to any image signed with that key, forever, unless the device can be told to distrust it. Key revocation in firmware is hard precisely because the mechanism that would deliver the revocation is the mechanism being secured.

It does not cover the metadata. The bootloader’s decision about which slot to boot is not signed, and an attacker who can write the metadata can direct the device to boot an older, validly signed image. The metadata’s own integrity check detects accidental corruption, not deliberate modification, unless it is stored in a region the attacker cannot reach.

Time and memory budgets

Verification happens before the application runs, so its cost is added to every boot, and on a device that must respond to an external event within a bounded interval, that cost is a design constraint rather than an implementation detail.

Hashing dominates for large images without hardware acceleration. SHA-256 processes 64 bytes per block through 64 rounds, so a 1 MiB image requires 16384 block compressions, and at a few cycles per round on a small core that is a substantial fraction of a second. Hashing only the declared image length rather than the whole slot halves the work when slots are twice the image size. Hashing once at install time and recording the result is cheaper still, and it is safe only if the recording cannot be forged and the slot cannot change afterwards.

Public-key verification is a fixed cost independent of image size: one or two scalar multiplications for ECC, or a modular exponentiation for RSA. On a core without acceleration it can be tens of milliseconds, and on a core with a hardware engine it can be a few milliseconds. Stack usage is the other constraint: big-integer arithmetic needs buffers of key size, and a 2048-bit RSA verification can require a kilobyte of stack or more if implemented naively. In a bootloader with a few kilobytes of RAM, that is a real budget item and a common source of stack overflow that manifests as a fault in the middle of verification.

The practical arrangement is to keep verification in the bootloader and out of the application, so that the cost is paid once at boot rather than on every application start, and to make the bootloader’s own verification path as small as possible. A bootloader that pulls in a general-purpose cryptography library for one signature check will often be larger than the application it verifies.