Anti-Rollback Counters and Version Monotonicity

A signature proves an image is authentic. It does not prove the image is current. An attacker holding a device that accepts any authentic image can present a signed image from two years ago, one with a known vulnerability that was subsequently fixed, and the device will verify it and run it. Every check passes. The version in the header is authentic and the signature over it is valid.

Anti-rollback is the mechanism that makes version numbers mean something. It converts a version field from a description into a constraint, and the constraint has to be enforced with state that survives erasure of everything else.

The downgrade is not a forgery

The reason anti-rollback is a separate problem from signing is that the attacker is not creating anything. They are replaying. Nothing in the signature scheme prevents this, because the signature is exactly what the legitimate vendor produced for that older image.

The attack surface is any interface that accepts an image: a local update port, a network update service, a debug interface if it is left enabled. Each of them, if it accepts a validly signed image without comparing versions, is a downgrade path. The consequence depends on the product. A device rolled back to a version with a fixed buffer overflow becomes exploitable again. A device rolled back to a version with a different data format may corrupt stored records. A device rolled back to a version that does not understand a hardware revision may fail to operate at all.

There is a legitimate case for downgrade, which is the reason the constraint has to be configurable rather than absolute. A new image that fails in a way trial boot does not catch may need to be replaced by an older known-good one. If the counter has already advanced past the older image’s version, the rollback is blocked by the same mechanism that blocks the attack. This tension is real and the resolution is a design decision: either the counter advances only on confirmation, so an unconfirmed image never raises the floor, or a privileged recovery path can lower it. The first is the usual choice because it needs no privileged path, and it means a failed update can always be reverted, which is the property that makes trial boot, confirmation, and automatic rollback work.

A counter without a battery

The counter must be monotonic across power loss, which rules out a plain variable in RAM and a plain variable in flash. A flash word cannot be incremented in place, because programming can only clear bits, so incrementing a value requires an erase of its sector, which is the same window that makes single-copy metadata unsafe.

The standard construction is a counter made of bits that are programmed one at a time, in a fixed order, so that the number of programmed bits is the value. An erase is needed only when the region is exhausted, and the erase resets the counter to zero, which is why the region is paired with a floor elsewhere.

The unary form is the simplest: a region of N bits, all initially 1, and incrementing means programming the lowest still-set bit to 0. The value is the number of zeros counted from the start of the region. Programming one bit is atomic in the sense that matters: the bit is either still 1 or it has become 0, and there is no intermediate state a reader could misinterpret as a different value. A power loss during the programming of bit k leaves the counter at either k-1 or k, both valid, differing by one increment. That is the same property the metadata log achieves by appending, expressed in a smaller space.

/* Unary bit counter. Bit i is programmed to 0 once the counter has
   reached i+1, so the value is the length of the leading run of zeros.
   A partially programmed bit reads as either state, never as a third. */
static uint32_t counter_read(const uint32_t *w, unsigned nwords)
{
    uint32_t v = 0;
    for (uint32_t i = 0; i < nwords * 32u; i++) {
        if (w[i / 32u] & (1u << (i % 32u)))
            break;                    /* first erased bit ends the run */
        v++;
    }
    return v;
}

static int counter_increment(uint32_t *w, unsigned nwords)
{
    uint32_t v = counter_read(w, nwords);
    if (v == nwords * 32u)
        return -1;                    /* region exhausted: needs an erase */
    return flash_program_bit(&w[v / 32u], v % 32u);  /* one bit, 1 -> 0 */
}

The cost is space: N increments require N bits, so a counter that must reach a million requires a megabit, which is far too much for on-chip storage. The space can be compressed by treating the region as a binary number, but the compression reintroduces the tearing problem. Stored as the complement of the value, because erased flash reads as all ones and that pattern has to mean zero, the counter holds 0xFFFFFFFE for one and 0xFFFFFFFD for two, and that step is not a programming operation at all: it clears bit 1 and sets bit 0, and flash cannot set a bit. Values whose encoding needs a bit set are simply unreachable by incremental programming. Even where a step clears bits only, as 0xFFFFFFF7 to 0xFFFFFFF0 does for eight to fifteen, it may clear three at once, and a power loss partway through leaves a pattern that is neither the old nor the new value. If that pattern happens to encode some other number, the counter jumps.

The resolution is to keep the binary encoding but to make each increment an append rather than an in-place modification. A record holding the new value, a sequence number, and a checksum is written to the log described in boot metadata persistence and the commit record, and the counter’s value is the newest valid record. The log’s own rotation supplies the erase, and the counter inherits the property that a torn write is ignored rather than misread.

The conservative reading matters in both forms. A partially completed increment can leave bits cleared that belong to a value the device never reached, so the reader must take the largest value that is definitely reached, not the value the pattern appears to encode. Taking the smaller value is safe: it may accept an image the device should reject, for one boot, and the next increment corrects it. Taking the larger value rejects the running image and leaves the device unable to boot.

Where the counter must live

The counter is only useful if the update path cannot reset it. That puts it in the same category as the public key, and the same options apply: one-time-programmable memory, a write-protected flash region locked by configuration, or a secure element. The choice interacts with the increment frequency, because OTP memory cannot be reused and a counter in OTP can only advance as many times as there are OTP bits available.

A design that ships with 32 OTP bits for the counter supports 32 version increments over the product’s life. That is often enough for a device with a ten-year life and annual releases, and it is nowhere near enough for a device updated weekly. The resolution for frequent updates is to keep the low-order part of the counter in ordinary flash and the high-order part in OTP, advancing the OTP part only when the flash part would wrap. The flash part is protected by the same log structure as the metadata; the OTP part provides the floor that a flash erase cannot lower.

The split introduces a failure mode: if the flash part is erased and the OTP part has not advanced, the effective counter drops to the OTP floor, which is lower than the true value. The window is bounded by how often the OTP part advances, and the usual mitigation is to advance the OTP part well before the flash part is exhausted, at the cost of OTP bits.

A second placement question is whether the counter is per-device or per-image. A per-device counter records how far this device has been advanced. A per-image floor records the minimum version the device will accept. They are the same number when every accepted image raises the floor, and different when an image is rejected after being written. The per-device form is what the hardware can enforce; the per-image form is what the vendor’s release process reasons about. Conflating them produces a device that refuses an image the vendor considers current.

Version comparison is not subtraction

Once the counter exists, the bootloader compares the image’s version against it. The comparison is where implementations acquire bugs, because versions are usually encoded as packed integers and subtraction is the wrong operation.

If the version is a 32-bit integer that increments by one per release, comparison is a plain unsigned greater-or-equal. If the version is packed as major, minor, and patch in bitfields, comparison must be field by field from the most significant, because subtracting packed values does not produce a meaningful ordering: a minor increment can carry into the major field and produce a number that is larger, which happens to work, or the fields can be sized such that the carry is lost, which does not.

A third encoding is a version string, which is the worst of the options because it requires parsing in the bootloader and string comparison does not order 1.10 after 1.9. If the image carries a string for display, it should carry an integer for comparison, and the two should be derived from the same source so they cannot disagree.

The comparison also has to handle the case where the counter is ahead of every image the device can obtain. A device whose counter was advanced by a factory test image, or by an image that was later withdrawn, will refuse the current release. Recovery requires a privileged path to lower the counter, which is exactly the path the attack needs, so such a path is usually absent and the device is returned. This is a strong argument for advancing the counter only on confirmed images and for never advancing it in a factory test that is not itself a release.

The counter and the slot layout interact

A device with two slots and a counter has three version numbers to reconcile: the version of the image in each slot and the counter’s floor. The bootloader must decide which images are bootable, and the rules are not symmetric.

The running image must always be bootable, even if the counter has advanced past its version, because otherwise a device whose counter was advanced by a partially completed update would refuse to boot the image it is currently running. The floor therefore applies to promotion, not to the currently active slot. This asymmetry is what makes a failed update recoverable: the new image advanced the counter on confirmation, then something else went wrong, and the old image must still run.

The inactive slot’s image is subject to the floor when it is being considered for promotion. An image below the floor is intact, signed, and not bootable, which is a distinct state that the bootloader must be able to report and that the metadata must be able to record. Treating it as corrupt sends the device into recovery mode for a condition that is a policy rejection, not damage.

The interaction with swap arrangements is worse, because a swap exchanges the two slots and therefore moves images across version boundaries. A swap that is interrupted leaves part of each image in the wrong slot, and the counter’s floor applies to a slot whose contents are not a coherent image at all. Implementations handle this by making the swap resumable and by treating an incomplete swap as a state to be completed rather than as an image to be validated, which requires the metadata to record swap progress separately from image state.