Signing Key Rotation and the Proof-of-Rotation Lineage

A signing key has a fixed lifetime in practice even when its certificate has not expired: the machine that holds it gets replaced, the HSM’s contract ends, an employee with access leaves, or the algorithm becomes weak. Rotating the key is straightforward for a system that installs software once. It is hard for a system whose identity model is “the same key means the same app”, because the whole point of pinning the key is to refuse a package signed by a different one.

The naive answer is to keep the old key forever, which converts a security problem into a permanent one. The other naive answer is to accept a new key on the strength of a server-side record, which moves the trust anchor from the signature to the server. APK Signature Scheme v3 does neither: it carries a proof, inside the signed package, that the new key was authorised by the old one.

What the proof has to establish

The verifier’s question is narrow. It has a package signed with key K₂ and, on the device, a record that the installed app was signed with K₁. It must decide whether K₂ is a legitimate successor to K₁.

Three properties are needed. The proof must be verifiable offline, because a device may check for updates while offline and because the signature check happens before any network access is possible. It must be non-transferable, in the sense that it authorises this succession and not a general ability for K₁ to sign anything as K₂. And it must be bounded in depth, because a chain of successions is itself a liability: if any link can be forged, the whole chain is worthless, and an unbounded chain gives an attacker unbounded attempts at finding a weak link.

The construction that satisfies all three is a chain of certificates, each cross-signed by its predecessor. Node n contains the public key of the new signer and a signature over that node, computed with the private key of node n−1. The final node in the chain is the key that signs the APK. Verification walks from the known key forward: each step checks a signature made by the key established in the previous step.

lineage:
  node 0: cert(K1)                      <- anchor, known to the device
  node 1: cert(K2) + sig_K1(node 1)
  node 2: cert(K3) + sig_K2(node 2)
  ...
  node n: cert(Kn) + sig_K(n-1)(node n)  <- signs the APK

Each node’s signature covers the node’s own contents, including the certificate it introduces, so a node cannot be reordered or spliced. The chain is stored in the APK’s signing block as a proof-of-rotation structure attached to the signer, which means it travels with the package and is covered by the same whole-file digest described in APK signing block layout that covers everything else.

Verification against a device that has no history

The interesting case is not the device that already trusts K₁. It is the device that has never installed the app, or one that has been wiped, or one that is installing the app for the first time from a package signed by K₃. That device has no prior record to compare against, so the chain cannot be verified from a local anchor.

The platform’s answer is to require the lineage to be present in full and to verify its internal consistency, then accept the newest key as the app’s identity while recording the lineage for future comparisons. The trust decision for a fresh install rests on the storefront having served the package, not on the chain — the chain establishes continuity, not authenticity of the first key. This is a real weakening, and it is why the lineage is not a substitute for the store’s own key management; it is what makes an update possible without one.

The device that does have history compares differently. It reads the installed package’s signing certificate, walks the lineage in the new package to find that certificate, and if it is found, accepts the successor. If the installed certificate does not appear in the lineage, the new package is a different app as far as the installer is concerned, and the update is refused unless the signatures happen to match outright.

There is a version-dependent subtlety in that walk. Older platforms that understand only the earlier signature schemes cannot read the lineage at all, and see a package signed by an unknown key. Those devices refuse the update. The practical consequence is that a rotation cannot be performed in a single step for a population that includes old devices: the package must continue to be signed by the old key for them, while newer devices accept the new key. Scheme v3.1 exists for exactly this, carrying both the new signature and a declaration of the minimum SDK at which the new key applies, so that the old signature governs below that boundary and the new one above it.

Rotation is a one-way transition with a grace period

Once a package signed by K₂ has been installed on a device, a package signed by K₁ is not a valid update, even though K₁ is the older and more established key. The lineage runs forward only. Reverting to the old key after a rotation has been delivered requires either a new lineage entry that proves K₁ is a successor of K₂, which is impossible without K₂’s private key, or a reinstall that discards the app’s identity.

That asymmetry is why rotation is scheduled with a grace period rather than switched. The sequence is: publish packages signed by both keys, with the new key applying above a minimum SDK and the old key below it; wait for the population on old platforms to age out or for the minimum supported SDK to rise; then publish packages signed only by the new key. The middle phase is the expensive one, because every package carries two signatures and two digest computations, and because the signing infrastructure must hold both keys.

The grace period also protects against a mistake in the lineage itself. A lineage that is malformed, or that names the wrong predecessor, is discovered when devices reject the update — and at that point the previous packages, signed by the old key, are still valid for devices that have not updated. Without the overlap there is no way back.

Where the keys live, and why that shapes the plan

A signing key that exists as a file on a build machine is a key that can be copied, and a copied key cannot be distinguished from the original by any signature scheme. Hardware-backed storage changes the property: the private key is generated inside a module that will not export it, and signing is a request to that module. The module enforces its own access policy and can be configured to refuse export attempts even from an administrator.

The cost is operational. A hardware module has a throughput limit on signing operations, so a build farm that signs thousands of artifacts per day needs either a queue in front of the module or a split between a high-volume key for development builds and a low-volume key for release builds. It also has an availability requirement: if the module is offline, no release can be signed, which makes it a single point of failure for the entire release process and therefore something that needs its own redundancy and its own disaster plan.

Key escrow is the other half of the trade. A key held only in hardware cannot be recovered if the module is destroyed, which means the app can never be updated again — the identity is lost, and every installed copy becomes unupdatable. Escrow reintroduces the exposure that hardware storage was meant to remove. The usual resolution is a split: the release key is held in hardware and never escrowed, while the store’s own signing infrastructure holds an equivalent key that can re-sign, with the store’s account recovery as the path back. That is the arrangement the major stores offer, and it converts the escrow question from “where is the copy” to “who can authorise its use”.

What the lineage does not cover

The proof binds keys, not code. It says nothing about whether the package signed by the new key is a legitimate build of the same app, only that whoever holds the new key is entitled to sign as the app. An attacker who obtains the new key after a rotation has the same power as an attacker who obtained the old one before it.

It also does not bind the package name across a change. The lineage is attached to a signer, and the installer’s identity for an app is the pair of package name and signing certificate; rotating the key changes one half of that pair, which is why the lineage check has to happen in the installer’s update path rather than in general certificate validation. A package with a new key and a new lineage is still a different app if its package name differs, and the lineage provides no help there.

Finally, the lineage’s depth limit is a real constraint rather than a theoretical one. Each rotation adds a node, and the structure is checked in full at verification time, so the cost of verification grows with the number of rotations performed. An organisation that rotates on a schedule accumulates nodes, and the practical guidance is to rotate rarely and deliberately — treating rotation as an incident-response capability and a scheduled hygiene task, not as a per-release step. The alternative, a per-release key, would make the lineage the largest structure in the package and would gain nothing, since the property that matters is that the key is not compromised, not that it is young.