Unambiguous Message Framing in Cryptographic Protocols

Every cryptographic protocol begins with a parsing problem that it never states as one: two implementations must extract the same structured message from the same bytes. When they cannot, the difference becomes an attack surface, because an attacker who controls the bytes can build a string that one parser reads as a signature over “amount: 100” and another reads as a signature over “amount: 100, payee: attacker”. Neither parser is wrong by its own rules. The protocol is wrong for having two sets of rules.

The requirement that eliminates this is unambiguous encoding: for every valid message there is exactly one byte string that encodes it, and every byte string decodes to at most one message. Stated in the other direction, the encoder must be injective. This is a stronger requirement than “the format is well-defined”, and it is the property that protocols most often fail to check.

Length-prefixed fields and the nesting problem

The oldest framing device is a length prefix: a fixed-width integer followed by that many bytes of payload. TLS handshake messages use a one-byte type and a three-byte big-endian length; TLS records use a two-byte length; the inner content types and extensions each carry their own two-byte lengths. The nesting is deliberate, because each layer needs to know where it ends before it can interpret its contents.

A length prefix is unambiguous only if it is exactly one width, always present, and never optional. Variable-width or self-describing lengths are where ambiguity enters. Consider a format where a field is either a length-prefixed blob or a null-terminated string depending on a type tag, with the tag itself encoded as a variable-length integer. An attacker can now choose among several encodings of the same tag, and unless the decoder rejects all but one, the byte string is ambiguous even though the abstract message is not.

DER, the distinguished encoding rules of ASN.1, is the canonical example of a specification that closes those holes by construction. It fixes the length encoding (definite length only, minimal number of bytes), forbids the constructed form of primitive types, requires that set-of elements be sorted by their encodings, and specifies exactly how booleans and integers are represented. A DER decoder that accepts a non-minimal length has broken the guarantee even if it produces the right value, because the byte string it accepted is one that a strict decoder would reject, and signatures computed over it may be reinterpreted elsewhere.

The most consequential historical instance of this class is BER versus DER in certificate parsing. X.509 certificates are signed over a DER encoding, and a parser that accepts BER, which permits indefinite lengths and constructed strings, can be shown two different byte strings for the same certificate. The signature verifies over one; the fields are read from the other. The defences are unglamorous: reject non-minimal lengths, reject indefinite lengths, reject trailing bytes after the structure, and compare the re-encoded form against the input when the format permits it.

Signatures over structured data need a single byte string

When a signature covers a message, the verifier must reconstruct exactly the bytes the signer hashed. Any slack in that reconstruction is a signature that can be moved to a different message. Three constructions recur, and their differences are instructive.

Sign the encoded bytes directly. The signer encodes the message canonically and signs the resulting octets. The verifier decodes, re-encodes canonically, and compares the result to the received octets before verifying; if the comparison fails, verification fails even though the signature might have been valid over the received bytes. The re-encode-and-compare step is the whole defence, and it costs one extra encoding per verification.

Sign a hash of a domain-separated structure. The message is hashed together with a fixed prefix that identifies the protocol, the version, and the purpose. Because the prefix is constant and the hash is over the whole encoded structure, moving the signature to another purpose requires finding a collision. The prefix must be a fixed-length string that cannot be confused with any valid message body; the standard practice is a fixed number of bytes, sometimes padded to a round length, so that no attacker-chosen field can be placed at the start of the hashed input.

Sign a length-prefixed concatenation of fields. This is the construction TLS 1.3 uses for CertificateVerify: 64 bytes of 0x20, a context string, a zero byte, and the transcript hash. The 64 space bytes are the domain separator; the context string distinguishes client from server and the signature algorithm family; the zero byte guarantees that the context string, which is variable-length within its family, cannot extend into the digest.

RSA PKCS #1 v1.5 in RFC 8017 shows the same concern in a different place. The signature is over an encoded DigestInfo structure that wraps the hash together with an identifier for the hash algorithm, so a signature made with one hash cannot be presented as a signature made with another. The encoding is DER, so the canonicality requirement applies to it as well: a verifier that accepts a non-minimal length inside DigestInfo has accepted a byte string that a strict implementation would reject, which is exactly the slack a re-encoding attack needs.

The failure mode to watch for in all three is what happens when a field is empty. If a structure is prefix || field1 || field2 and both fields are attacker-influenced, an empty field1 lets the attacker’s field2 begin immediately after the prefix, which may coincide with the encoding of a different message in which the prefix is longer. Length-prefixing each field removes the coincidence.

Canonical forms for maps and sets

Ordered sequences are easy: the encoding is the concatenation, and injectivity follows from injectivity of the elements. Maps and sets are not, because they have an order-independent abstract meaning and a concrete encoding that must pick an order.

CBOR’s deterministic encoding rules handle this by requiring that map keys be sorted in a specified order and that integers use the shortest form that represents them. Without the sorting rule, the same map has as many encodings as it has key orderings, and a signature over one encoding does not cover the abstract map. Without the shortest-form rule, the same integer has multiple encodings and the same problem appears one level down.

JSON has neither rule in the base specification, which is why protocols that sign JSON adopt an external canonicalisation profile. The recurring difficulties are number formatting (is 1.0 the same as 1?), duplicate keys (which value wins, or is the document rejected?), Unicode escaping (\u00e9 versus the literal UTF-8 bytes), and insignificant whitespace. A profile that answers all four is workable; a profile that answers three is a signature that can be moved.

The general rule is that a canonical encoding must be specified as a function, not as a set of examples. “Keys are sorted by their UTF-8 byte sequences, compared as unsigned bytes” is a function. “Keys are sorted alphabetically” is not, because it does not say what happens with non-ASCII, with equal keys, or with keys that differ only in case.

/// Encode a field with a two-byte big-endian length prefix.
/// Rejects fields that cannot be represented, rather than truncating.
fn put_len_prefixed(out: &mut Vec<u8>, field: &[u8]) -> Result<(), &'static str> {
    let len = u16::try_from(field.len()).map_err(|_| "field exceeds 65535 bytes")?;
    out.extend_from_slice(&len.to_be_bytes());
    out.extend_from_slice(field);
    Ok(())
}

/// Decode exactly one length-prefixed field, requiring the buffer to be
/// fully consumed by the caller's framing layer.
fn get_len_prefixed<'a>(buf: &mut &'a [u8]) -> Result<&'a [u8], &'static str> {
    if buf.len() < 2 {
        return Err("truncated length prefix");
    }
    let (head, rest) = buf.split_at(2);
    let len = u16::from_be_bytes([head[0], head[1]]) as usize;
    if rest.len() < len {
        return Err("truncated field body");
    }
    let (field, tail) = rest.split_at(len);
    *buf = tail;
    Ok(field)
}

The important property in that pair is that the decoder consumes exactly len bytes and hands the remainder back, so the caller can require that the remainder be empty at the end of the message. A decoder that scans for a delimiter instead of trusting the length cannot make that guarantee.

Attacks that live in the ambiguity

Textbook differential parsing attacks are worth naming because they show what the abstract requirement protects.

Signature stripping and re-encoding. A verifier that parses a certificate, extracts the fields it cares about, and verifies the signature over a re-encoded version of those fields will accept a certificate whose original encoding differs, provided the re-encoding matches. The attacker supplies the malformed original and relies on the verifier’s tolerance. Rejecting the original by comparing bytes prevents this; parsing leniently and re-encoding does not, because the verifier has already discarded the evidence.

Field confusion through shared prefixes. A MAC computed over id || amount where id is variable-length can be reinterpreted as a MAC over a different (id, amount) split. The attacker moves bytes from the end of the id into the start of the amount. Length-prefixing the id makes the split explicit.

Type confusion in tagged unions. A structure with a type tag and a payload whose layout depends on the tag is unambiguous only if the tag is encoded once, in one place, and cannot be overridden by a field inside the payload. Formats that allow a payload to repeat the tag, or that allow a “any” type whose contents are self-describing, invite a parser to read the outer tag and an application to act on the inner one.

Truncation and extension. A message that is accepted with trailing bytes appended is a message whose signature covers a prefix of what was received. The receiver must either reject trailing bytes or prove that the trailing bytes are inert. Protocols that carry optional extensions at the end of a structure should make the extension block itself length-prefixed and covered by the signature, not appended after it.

Where this connects to the rest of the protocol

Framing is not a preliminary to the cryptographic design; it is part of it. The transcript hash described in transcript hashing and handshake binding is only meaningful if both sides agree on the message boundaries, which is exactly what a length prefix supplies. The label encoding in domain separation and labelled key derivation is the same idea applied to a string that feeds a KDF rather than a parser.

A practical test for a new format is to write the decoder first and ask, for every accepted byte string, whether re-encoding the decoded value reproduces the input exactly. If the answer is no for any input, the format is not canonical, and any signature over it must be accompanied by a re-encode-and-compare check. Where the format cannot be made canonical, the alternative is to sign a hash of the abstract message under a domain-separated prefix, which moves the requirement from the format to the hash function.