Summary

  • RFC 3218 treated a CMS recipient's errors and timing as part of the cryptographic interface. If malformed RSAES-PKCS1-v1_5 blocks could be distinguished from well-formed blocks carrying a wrong content-encryption key, repeated queries could reveal the protected key material.
  • Its random-filling countermeasure replaced a malformed unwrap with a new random CEK of the expected length and continued into content and integrity processing. The substitute was deliberately not the right key; its purpose was to make the earlier failure indistinguishable from an ordinary later one.

The dangerous output was not plaintext. It was a yes-or-no answer about the shape of plaintext that the recipient refused to show.

That distinction explains why an attack against RSA encryption could begin with what looked like harmless error handling. A CMS recipient held a private RSA key. The attacker held a captured encrypted content-encryption key, or CEK, and could submit related ciphertexts. The recipient never had to print the decrypted block. It only had to behave one way when the block satisfied PKCS #1 v1.5 formatting and another way when it did not.

In 1998, Daniel Bleichenbacher showed how that single bit could support an adaptive chosen-ciphertext attack. The attacker transformed a ciphertext, observed whether a server treated the result as conforming, and chose the next transformation from everything learned so far. A succession of tiny answers narrowed the numerical interval containing the hidden plaintext. The private key remained inside the recipient; its decisions did the decryption work in public.

RFC 3218 carried that lesson into Cryptographic Message Syntax. It was published in January 2002 as an Informational RFC, not as a new encryption format. Its problem was operational: CMS implementations already used RSA PKCS #1 v1.5 to transport the symmetric key that protected message content. What should a recipient do when it could not replace that deployed format immediately?

The encoded block had a rigid grammar. It began with 00 02, continued with at least eight nonzero random padding octets, inserted a zero separator, and ended with the transported value. In CMS that final value was the CEK. A private-key operation could therefore return bytes without returning a syntactically valid key-transport block.

That was the first boundary RFC 3218 had to protect. RSA exponentiation completing was not the same as the encoded block being valid. A valid block was not the same as carrying a CEK of the expected algorithm and length. A correctly sized CEK was not necessarily the CEK used by the sender. Content decryption producing bytes did not mean those bytes passed integrity checks. And even authenticated content did not by itself prove that an application accepted or acted on it.

An implementation that collapsed those stages internally would be hard to audit. An implementation that exposed them externally could become an oracle.

The Million Message Attack took its name from an operational estimate. RFC 3218 described a captured ciphertext C and transformed values of the form C' = C * S^e mod n. Roughly one transformation in 2^16 would yield a plaintext beginning with the expected two octets. Under the conditions the RFC examined, the complete interaction could take on the order of 2^20 messages and responses.

That number was not a law of nature or an exact budget for every target. It expressed the shape of the threat. A million requests would be absurd if each required a person to open a message and answer it. It became plausible when the recipient was an automated mailing-list agent or another unattended service that decrypted, classified and replied at machine scale.

Automation changed the attacker’s resource from patience into traffic. The recipient supplied the repetition.

CMS offered several possible outcomes after a submitted wrapped key arrived. The RSA block might be malformed. It might be well formed but contain a bogus CEK. A bogus CEK might lead to an integrity failure. If the content had no authenticated integrity, random-looking plaintext might still produce apparently valid CBC padding by chance. The genuine CEK might be recovered, but for a transformed attack query that outcome was extraordinarily unlikely.

The attack did not require all those outcomes to be visible. It required the first one—bad PKCS #1 formatting—to be distinguishable from the later outcomes caused by a well-formed but wrong key. Different diagnostic text could do it. So could a reply versus silence, a connection reset, a mail bounce, a signature-error notice, or a repeatable timing gap.

RFC 3218's main countermeasure was called random filling. If PKCS #1 decoding failed, the recipient would not stop at that branch. It would generate a cryptographically random CEK of the length expected by the selected content-encryption algorithm and continue as though RSA unwrapping had produced that value.

The recipient would then attempt content decryption. It would perform the normal signature, MAC, padding or application checks available for the message. Eventually the invented key would almost certainly cause an ordinary downstream failure. The externally reported error and the time taken to reach it should resemble the path followed by a correctly formatted block containing a wrong CEK.

The random key was therefore not a backup secret. It did not recover the sender's CEK, preserve the message, or make the ciphertext usable. It was disposable state introduced to erase a branch from the attacker's observation surface. Its correctness consisted precisely in being unpredictable and almost certainly wrong.

That is why a fixed fallback key would be catastrophic. A developer might prefer one constant because it is easy to test and avoids calling a random generator on an error path. But an attacker who learned or guessed the constant could encrypt CMS content under it, combine that content with a malformed RSA-wrapped key, and submit the package. If the recipient entered the fallback branch, the content could decrypt successfully. If it did not, the package would fail. The alleged countermeasure would manufacture a stronger oracle.

RFC 3218 required fresh cryptographically random material. Reuse would give the failure branch a stable semantic identity. The attacker could stop asking whether the padding was valid and ask whether the recipient had chosen the known substitute.

Even fresh randomness could leak if generated only after failure and if generation was observably slow. The RFC therefore proposed a less intuitive implementation strategy: generate a random candidate for every message, before knowing whether it will be needed, and discard it after a valid unwrap. The successful and unsuccessful paths then pay a similar randomness cost.

This was not a universal proof of constant time. Memory access, parsing, logging, network behavior and later application work could still differ. It was an instruction to remove one obvious timing branch instead of congratulating the error string for being uniform.

Length created another hidden branch. A generic RSA/PKCS #1 layer might know that the encoded block was syntactically valid without knowing whether the application expected an eight-byte, sixteen-byte, twenty-four-byte or thirty-two-byte CEK. If that low layer returned the value and a higher CMS layer rejected the wrong length in a visibly different way, the oracle simply moved upward.

The length-aware layer also had to randomize. A well-formed block with a CEK inappropriate for the selected content cipher had to enter the same concealed downstream path. The design responsibility crossed software boundaries: the cryptographic primitive could not provide the whole defense if it lacked the algorithm context needed to recognize every invalid case.

RFC 3218 discussed stronger validation as a way to increase the attacker's work. Check every required padding octet, not merely the leading 00 02. Check CEK length. For DES-family algorithms, check key parity where applicable. Each extra condition reduced the chance that a random transformed block would pass.

But stricter checking did not change the governing rule. A rarer oracle was still an oracle. If the recipient announced which condition failed, the attacker could continue collecting the bit, only at a higher cost.

Unauthenticated CBC content made the downstream path especially ambiguous. A random decryption might end in bytes that looked like padding. If an implementation simply trusted the last octet as a truncation count, RFC 3218 estimated an apparent success probability around one in 32. Verifying that every padding octet carried the required value reduced it toward one in 255.

Those probabilities did not make random plaintext meaningful. They showed why “the decryptor returned a padded buffer” was a weak acceptance event. A MAC or signature supplied a stronger later rejection point. Yet even authenticated content did not permit the recipient to expose the earlier padding result separately; the whole defense depended on keeping the initial branch from becoming a query response.

OAEP offered a cleaner cryptographic direction. PKCS #1 v2.0 had specified RSAES-OAEP, and RFC 3218 said the attack under discussion did not apply to it. But OAEP was wire-incompatible with PKCS #1 v1.5. A sender and recipient had to agree on the new encoding, while installed CMS software, certificates, algorithm identifiers and interoperability expectations remained attached to the old one.

The transition problem was therefore not solved by naming the better primitive. Running systems needed a safe behavior while the old format still existed. RFC 3218 was a compatibility countermeasure: constrain what a legacy recipient revealed until deployments could move.

TLS had encountered the same family of danger around RSA-encrypted premaster secrets. Its specifications instructed servers to continue with random material rather than reveal whether the encrypted secret had bad formatting or a wrong version. The resemblance is instructive, but the receipts were protocol-specific. A CMS mail processor and a TLS handshake exposed different later behaviors, state machines and application consequences.

The discipline was broader than the code pattern: do not let an early parser answer a question that the outer protocol cannot safely answer. The outer protocol must decide what failure can be revealed, how much work must still occur, and which later event can carry the final rejection.

RFC 3218 did not claim that random filling authenticated messages, stopped every timing channel, repaired a compromised private key, or proved an implementation secure. It did not publish a deployment census. Its achievement was narrower and more durable. It made a recipient acknowledge that silence has to be engineered. When one internal distinction can be queried repeatedly, error handling is part of the cryptosystem.