Summary

  • Debian's May 2008 OpenSSL update corrected a Debian-specific random-number-generator defect, but every weak SSH, OpenVPN, DNSSEC or X.509 key already generated remained structurally valid and portable. An unaffected machine could still accept an imported weak key.
  • Repair required several independently executed acts: patch the generator, detect or conservatively identify suspect credentials, create replacements under corrected entropy, authenticate and distribute them, remove old authorizations or revoke certificates, and prove that material relying parties now refused the old key.

The fix changed tomorrow

At 14:06 Central European time on 13 May 2008, Debian published a short security advisory with an unusually long operational shadow. The random-number generator in Debian's OpenSSL package was predictable. Cryptographic key material produced by affected versions could be guessed. The patched packages changed what the next call to the generator would do.

They changed nothing about the key generated the day before.

That distinction made CVE-2008-0166 more than a package-maintenance incident. A weak RSA key did not carry a damaged header. An SSH public key made from deficient entropy could still parse, match its private half and satisfy the protocol. An X.509 certificate containing that key could still have a valid issuer signature and an unexpired validity period. A VPN peer could still load the file. The defect lived in the history of how the secret was chosen, not in whether the resulting credential obeyed its format.

Debian's DSA-1571-1 therefore did not stop at “upgrade OpenSSL.” It recommended recreating from scratch all cryptographic key material generated by Debian OpenSSL versions beginning with 0.9.8c-1. It warned that DSA keys ever used on affected systems for signing or authentication should also be considered compromised, because a predictable or repeated signing nonce can expose a DSA private key even if that key was originally generated elsewhere.

Ubuntu's notice drew the geographic boundary correctly. Debian-derived operating systems carried the defective generator. Other systems did not become vulnerable merely by running OpenSSL. They could nevertheless become relying parties for weak keys imported from affected machines. The repair perimeter followed the credential, not the operating-system label.

This was the first central lesson: a generator patch is prospective. Authority already granted to its outputs is retrospective state scattered across other systems.

A maintenance change compressed the secret space

The origin record deserves precision because simplified retellings often become blame stories. Debian bug #363516 opened in April 2006 around Valgrind's reports that OpenSSL's random-number generator read uninitialised memory. The discussion considered how to avoid noisy diagnostics. Debian's later record clarifies that the compiled vulnerable change first appeared in package version 0.9.8c-1, after a modified md_rand.c was moved into the path actually used by the build.

The mistake removed mixing operations that contributed input to the random pool. Debian's SSLkeys documentation explains the practical result in a bounded model: the broken generator was effectively seeded by the process identifier, with 32,767 possible streams in each of three architecture classes—98,301 streams in that model. For common key types and sizes, defenders and attackers could enumerate candidate keys rather than search an intended cryptographic space.

That number needs two qualifications. It is not a universal count of every weak credential, because applications could call the generator differently and blacklists covered particular algorithms, sizes and architectures. It is also not a count of exploited systems. Official sources establish that key material was guessable and that serious secondary effects were possible; they do not provide a complete exploitation census.

What the number does establish is the inversion of normal public-key economics. A public key is meant to be safe to distribute because deriving its private half is computationally impractical. Here, public distribution helped identify which member of a small precomputed family was in use. The credential retained formal cryptographic shape while losing the scarcity on which its authority depended.

Debian patched code, then suspended trust

Debian's own infrastructure response showed that its maintainers understood the difference between repair and retirement. Minutes after DSA-1571, the project disabled public-key authentication on Debian systems. Services that relied on key-based transfers or rebuild triggers could not simply continue because the library package had been updated. Administrators had to demonstrate that the credentials were safe or replace them.

The next day's DSA-1576-1 converted that operating problem into OpenSSH controls. Updated packages depended on corrected OpenSSL libraries and installed openssh-blacklist. Where a weak user key could be recognized, the server would reject it. Host keys could be regenerated, subject to an administrator prompt. Users were told to inspect their own identities, system host keys and authorization files with ssh-vulnkey.

The workflow then crossed the machine boundary. A regenerated server host key would trigger SSH's alarming “REMOTE HOST IDENTIFICATION HAS CHANGED” warning on clients. The warning was correct: the identity assertion had changed. A safe repair required the user to obtain the new fingerprint through a trustworthy channel before editing known_hosts. Automatically suppressing the warning would preserve convenience by erasing the very local veto that made host-key pinning useful.

User keys required the opposite propagation direction. The user generated a new pair, delivered the new public half to each server and removed the old line from every authorized_keys or authorized_keys2 file. Generating a replacement without deleting the old authorization created an additional credential; it did not retire the weak one.

The patch, blacklist, key pair, trusted-channel fingerprint and authorization entry were therefore five different entities under different owners. Calling all five “the SSH fix” would hide the gaps where old authority could survive.

A blacklist was an executable veto, not an oracle

The finite candidate space made an unusual defensive control possible. Debian and Ubuntu distributed hashes or representations of known weak public keys. A patched SSH server could compare an offered credential with that set and refuse it locally. Ubuntu extended similar checking to OpenVPN material and X.509 keys through openssl-vulnkey.

This is a striking example of running-code authority in its narrow technical sense. Publishing a list did not disable a key. A receiving application disabled it only when the relevant blacklist was installed, the key form was covered and the rejection branch executed.

The limits were visible immediately. DSA-1576-1 said weak user keys would be rejected “where possible” and warned that detection could not cover every case. ssh-vulnkey could return Unknown (no blacklist information). Ubuntu correctly instructed users not to translate that result into “safe.” When provenance was uncertain, the safer course was replacement.

Two days after the first OpenSSH advisory, DSA-1576-2 corrected the tool because authorized_keys lines beginning with options—such as a forced command or a prohibition on port forwarding—could be ignored during scanning. Some compromised keys might not appear in the report even though the server still accepted them. In June, Ubuntu expanded blacklist coverage and tool inputs, adding checks for certificate requests, raw moduli and additional RSA sizes.

These updates are not footnotes. They expose a general rule for security automation: a negative scan result is only as strong as the scanner's parser, corpus and entity coverage. A blacklist can make a known-bad population cheap to refuse. It cannot prove the absence of weak keys produced through a different call pattern, key length, architecture, copy path or unsupported format.

The control was still valuable. It turned public evidence into a local denial mechanism and could stop a future upload of a known weak key even on a system whose generator had never been affected. Its legitimate authority was proportional to its evidence: refuse the enumerated credential, report unknown coverage honestly and leave broader provenance decisions to the operator.

One flaw, several retirement protocols

The incident spread across applications because OpenSSL supplied randomness to more than TLS. CERT listed SSH, OpenVPN, DNSSEC and X.509 material among affected classes. Debian's application inventory extended further. Yet there was no universal “revoke key” operation.

For SSH user authentication, authority lived in remote authorization files. Retirement meant removing every old public-key line and testing that the weak private key could no longer log in. For SSH server identity, authority lived in client-side known_hosts state and the user's decision about a new fingerprint. Replacement without authenticated communication could train users to approve an interception.

For OpenVPN shared keys, all peers needed coordinated replacement. For certificate-based VPNs, the private key and certificate had to be replaced and the old credential rejected according to the deployment's issuer and revocation design. Ubuntu warned that key material generated for other systems had to be found and replaced there as well.

For public or private X.509 certificates, generating a new private key was only the beginning. The subject needed a replacement certificate; the old certificate needed revocation where issuer policy and infrastructure allowed it; servers needed the new chain; and clients needed to consult or otherwise learn the relevant status. RFC 5280 defines certificate and revocation-list processing, but the existence of a revocation mechanism does not prove that every relying party fetched fresh status before accepting a chain.

For DNSSEC, the key could be embedded in a signed delegation and cached validation state. Retirement required protocol-specific rollover and coordination, not merely deletion from the machine that created it. The same principle applied to automation accounts, backup jobs and build systems: the old key could be present in a remote system no one associated with the original host.

The correct unit of remediation was therefore not “the server.” It was the credential lineage: generator, key, copies, certificates, authorizations, peers, caches and every material acceptance point.

Validity survived legitimacy

Weak keys made an uncomfortable boundary visible. Cryptographic verification answers a constrained question: does this signature correspond to this public key, or does this private key prove possession relative to the offered public half? It does not answer whether the secret was unpredictable, whether it was stolen, whether its holder remains authorized or whether the relying party's copy should still confer access.

Before blacklist deployment or authorization removal, an attacker presenting the guessed private key could produce a mathematically valid SSH proof. The protocol did not fail to compute. The authorization system failed to distinguish the legitimate holder from anyone who could reconstruct the same secret.

This is where Heng Lu's disclosed running-code and practical-sovereignty notes provide a useful analytical lens. A project advisory could identify the failure; a distribution could ship a patch; a certificate authority could issue status; an operator could announce a rollover. None of those statements became effective refusal until the system controlling access executed the corresponding rule. Technical dependence on Debian's packages did not give Debian a universal switch over every imported key. Conversely, an unaffected platform could not claim to be outside the incident if its own running configuration still accepted one.

The doctrine should not be inflated. Heng Lu's notes are not evidence for the Debian chronology, and this incident does not settle every question about institutional legitimacy. It demonstrates the narrower mechanism: operational authority resides where acceptance is implemented, and a formal record can remain technically valid after the factual basis for relying on it has collapsed.

The evidence ledger that remediation needed

A defensible response would maintain four linked ledgers.

The generation ledger records where and when a key was created, which library and package version supplied randomness, the algorithm and size, and whether a hardware or application-specific generator displaced the vulnerable path. Without this provenance, “the host is now patched” says nothing about an old key file.

The distribution ledger records every location that received the public or private material: servers, authorized_keys, known_hosts, VPN peers, certificate requests, appliances, backups and external partners. This is the ledger most organizations lacked because credentials were treated as files rather than authority relationships.

The replacement ledger binds the old fingerprint to a new one, states how the replacement was authenticated, records the issuer or owner action and identifies the person responsible for each relying-party update. It prevents a new key from being mistaken for a completed retirement.

The rejection ledger proves that old authority has ended. A weak SSH user key fails on each material server. A deprecated host key is absent from active service. A revoked certificate is rejected by tested client populations under fresh status. A VPN peer refuses the old shared secret. Exceptions are named, bounded and expiring.

Patch compliance belongs in the first ledger. Incident closure belongs in the fourth.

Evidence limits

The official record is rich about the defect, package versions, response instructions and detection boundaries. It does not establish how many weak keys were produced, how many crossed onto other systems or how many attacks succeeded. This article therefore does not convert a small theoretical key family into an exploitation count.

Nor does it classify every credential generated on a Debian-derived host as affected. GnuPG and GnuTLS used different random generators; applications varied. File modification times could be changed by backup or clock errors. Blacklist coverage was deliberately incomplete and evolved after disclosure. Automatic host-key handling differed by package and administrator choice. A reissued certificate did not guarantee universal revocation checking.

The strongest supported conclusion is operational: the corrected generator prevented new instances through that path, while old credentials required separate discovery and rejection wherever they had acquired authority.

Sources