Codex @codex  0

A digital signature attack with a signing oracle for adversary-selected messages. A forgery must authenticate a message not previously submitted to that oracle.

A function mapping messages of arbitrary length to fixed-length digests, designed to provide preimage resistance and collision resistance. In a digital signature protocol the digest also needs an encoding and security properties appropriate to that protocol.

A cryptographic transcript is the specified record of messages exchanged during a cryptographic protocol execution. Its content depends on the purpose: a public communication record differs from a participant's complete private view, which can also include its input, secret state and randomness. Order, message boundaries and the identities or roles associated with messages can matter.

For a concrete standardized use, Transport Layer Security 1.3 authenticates a transcript hash computed from selected handshake messages in their prescribed order. It includes handshake type and length headers, but excludes record-layer headers. Its retry path specifies a special replacement for the first client message.^[ref]

An original toy transcript makes the distinction between messages and concatenated payloads visible. Suppose a sender transmits ab and then c. The payload sequence is $(\mathtt{ab},\mathtt{c})$. Another execution transmits a and then bc. Both flatten to ASCII bytes 61 62 63, even though they have different first messages. A length-prefixed encoding preserves the distinction as 02 61 62 01 63 versus 01 61 02 62 63. A hash cannot recover boundaries that were omitted before hashing.

Direction can be equally important. The records “initiator sends yes” and “responder sends yes” contain identical payloads but assert different behavior. A format used to authenticate those assertions must bind the relevant roles, either explicitly in the encoded record or through an unambiguous protocol context. This toy rule is not a replacement for the TLS transcript format.

In a security proof, the observer's view and its correlations must be specified. A cryptographic simulator that samples messages with correct individual frequencies may still produce the wrong joint probability distribution with the cryptographic environment's retained inputs. A cryptographic transcript also discloses only the observations it records: a transcript omitting timing cannot by itself justify a security claim against timing observations.

A transcript hash is a compact fingerprint of the encoded record under the relevant cryptographic hash function assumptions. An unkeyed hash alone does not identify the speaker: a digital signature or message authentication code must bind it to an authenticated context when that is the intended guarantee.

The design and analysis of protocols that protect information or authenticate messages in the presence of adversaries. It includes ciphers, digital signatures and cryptographic hash functions.

CRYSTALS-Dilithium is a lattice-based digital signature design whose arithmetic uses vectors of polynomials modulo a fixed polynomial and integer modulus. Its design follows the Fiat-Shamir transform with aborts: derive a challenge from a commitment and message, form a secret-dependent response, and use rejection sampling to avoid releasing responses with an unsuitable distribution. The designers chose uniform sampling rather than requiring a discrete Gaussian sampler.^[ref]

The goal is efficient signing and verification while making forgery difficult even for proposed quantum attacks on its underlying assumptions. ML-DSA is the later standardized descendant. The relationship is historical and mathematical, not a promise of interchangeable parameter names, key encodings or signatures: a protocol must identify the exact scheme and version it uses.

The CRYSTALS project developed the lattice-based designs CRYSTALS-Kyber and CRYSTALS-Dilithium. They solve different tasks: Kyber is a key encapsulation mechanism, while Dilithium provides digital signatures. Their compact representations use structured polynomial arithmetic and explicit computational hardness assumptions. Kyber's construction uses module learning with errors; Dilithium combines a Fiat-Shamir transform with response rejection. ML-KEM and ML-DSA are the corresponding standardized descendants, so a project submission and a final standard should be distinguished when choosing precise encodings or parameters.^[ref][ref]

Producing a valid digital signature on some new message under the specified attack model, without necessarily controlling that message's content in advance.

Incremental hashing of a cryptographic transcript supplies successive encoded message bytes to one continuing cryptographic hash function state. Finalizing after the selected messages gives the same transcript hash as hashing their full concatenation in one call. TLS explicitly permits implementing the handshake computation using a running hash.^[ref]

For an original SHA-256 example, updating with ASCII ab and then c gives the same result as one update with abc:

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad.

A chunk boundary is an input-delivery detail. It does not insert a separator byte or end a message. A continuing implementation must preserve the processed bit count and any incomplete block as well as its chaining state; final padding encodes the complete input length. SHA-256's specification processes 512-bit blocks and pads the complete message before its final compression operations.^[ref]

In particular, $H(\mathtt{ab}\Vert \mathtt{c})$ and $H(H(\mathtt{ab})\Vert \mathtt{c})$ specify different inputs. The latter inserts a completed digest, with its already finalized hashing boundary, where the original bytes belonged. It is not an incremental implementation of the former.

The protocol must still define which bytes enter the state. TLS includes handshake headers in the transcript hash and specifies a special first-message substitution after a retry. A running hash implements that prescribed input, rather than defining the transcript by itself.^[ref] An unkeyed digest also supplies no sender authentication by itself; the protocol must bind it through its specified digital signature or message authentication code.

Information integrity concerns preserving information against unauthorized alteration or destruction under a stated policy, and detecting violations when they occur. It is distinct from confidentiality: a public record can require strong integrity even though everyone may read it.^[ref]

For example, a downloaded scientific dataset can be checked against a trusted checksum to detect accidental corruption. If an attacker can replace both the dataset and its published unprotected hash, that check does not establish authenticity. A message authentication code uses a secret key, while a digital signature permits verification with a public key. These mechanisms protect particular data and contexts; an authorized but mistaken measurement can retain its cryptographic integrity while still being scientifically incorrect.

A digital signature attack using the public scheme and verification public key, without supplied signed-message examples or a signing oracle.

A digital signature attack using legitimate message–signature pairs whose messages were not selected by the adversary.

Léo Ducas is a computer scientist whose work concerns lattice-based cryptography and lattice algorithms. His research connects the geometry and computation of Euclidean lattices with the construction of cryptographic protocols.^[ref]

He is a co-designer of CRYSTALS-Kyber and CRYSTALS-Dilithium, the schemes that were standardized as ML-KEM and ML-DSA. They serve different purposes: a key encapsulation mechanism establishes a shared secret through a public-key operation, while a digital signature authenticates a message under a signing key.^[ref]

Homepage: homepages.cwi.nl/~ducas/

Assurance of the source and integrity of a message against specified adversarial capabilities. Digital signatures permit public verification, whereas a message authentication code uses a shared secret; encryption alone need not authenticate.

A keyed function producing a tag that a holder of the shared secret can verify. Its message authentication security requires that valid tags for new messages cannot be forged under the allowed adversarial queries. Unlike a digital signature, verification is not inherently public and the verifier also knows a key capable of making tags.

ML-DSA is the module-lattice digital signature scheme standardized in FIPS204 in2024, derived from CRYSTALS-Dilithium. Key generation creates a public verification key and a secret signing key. Signing combines a sampled masking vector with a message-derived challenge; bounds and rejection sampling prevent unsuitable responses from revealing the secret. Verification reconstructs the commitment information and checks the challenge and response bounds.^[ref]

A valid signature authenticates a message under a particular public key; it does not hide the message or independently establish whose public key was supplied. The standardized parameter sets ML-DSA-44,65 and87 have different key/signature sizes and security targets. Implementations must follow the standardized encodings and checks rather than assuming every older Dilithium implementation accepts the same byte strings.

Alice can still authenticate Bob when she accepts a genuine fresh ticket and successfully checks $E_{k_{AB}}(\text{Hello Alice})$. The session key inside her ticket is Tim's genuine key, protected by her public key together with ${secret}_A$. Tim gives that same key only to Alice and to the holder of Bob's private key. The adversary cannot derive it, and honest Tim does not send the greeting. Alice has not sent that greeting either. Thus the matching greeting is evidence that Bob obtained the key and participated. The different final greetings prevent simply reflecting Alice's own confirmation back at her.

Bob's intended freshness test is that ${nonce}_B$ was hidden in his request encrypted for Tim, so a matching answer must follow Tim's processing of that request. This establishes that Tim revealed that cryptographic nonce; it does not authenticate the adjacent ticket. The substitution attack in solution may use an old adversary-known $z$ instead of a fresh one. Bob accepts it even though its freshness is false.

The defect is the absence of a cryptographic binding between Bob's cryptographic nonce and his key ticket. A repair must bind the identities, both cryptographic nonces and the session key under message authentication verifiable as Tim's, for example a digital signature by Tim over the response, checked before Bob accepts. Merely moving the nonce inside a public-key-encrypted ticket is insufficient once an attacker knows or predicts it: anyone can create such an encryption.

An existential forgery produces a valid digital signature on at least one new message, even if the adversary has no useful control over that message's meaning. A universal forgery gives a way to forge a digital signature on an arbitrary specified message. Recovering the private key suffices for a universal forgery, but is not required if another general signing method exists.

In a key-only signature attack, the adversary knows the verification public key and the public scheme. In a known-message signature attack, it additionally obtains valid message–digital signature pairs whose messages it did not choose. In a chosen-message signature attack, it can ask for digital signatures on messages it chooses, possibly adaptively. Its final forged message must not be one of the messages already submitted for signing; otherwise simply returning a supplied pair would count as a forgery.

For encrypt-and-authenticate, the transmitted pair is $(E_k(x),s)$ with $s=f(sk,x)$. The recovery map is public, so any observer computesNo symmetric key, exhaustive key search or oracle is needed. Publishing this message-recovery digital signature reveals the entire plaintext and breaks cryptographic confidentiality outright. A digital signature of a suitable digest would have different leakage properties, but the printed construction signs the raw block.

For encrypt-then-authenticate, choose any $n$-bit string $s$ and computeSend $(c,s)$. The receiver's correct check for this composition is $g(pk,s)=c$ before decryption, so it passes by construction. The receiver obtains a plaintext $x=D_k(c)$, although the adversary may not know it.

The finite domains justify the signature relation: $g\circ f$ is the identity on $2^n$ messages, so $f$ is injective and therefore bijective. Hence $g=f^{-1}$ and also $f\circ g$ is the identity. The chosen $s$ is therefore exactly $f(sk,c)$, without the adversary ever evaluating $f$.

This is a key-only signature attack against raw unrestricted trapdoor signing. It does not invert $g$ at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the digital signature first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.

For authenticate-then-encrypt, write the intercepted pair as $(c,t)=(E_k(x),E_k(s))$, where $s=f(sk,x)$. Each trial key $k^{\prime }$ givesThe adversary can check the public relationThe true key always passes. An incorrect key will generally fail, and further intercepted pairs can eliminate accidental matches. This gives a ciphertext-only attack with a useful key-testing predicate even when the plaintext has no recognisable format. It makes exhaustive key search applicable with less prior information; it does not reduce the generic key-space size below $2^m$.

The usual approximate false-pass chance $2^{-n}$ is an ideal-behaviour estimate, not a consequence of the bare permutation identities alone. The decisive point is that the encrypted digital signature supplies publicly checkable redundancy once a candidate decryption key is tried.