Cryptographic leakage

Cryptographic leakage is information about secret inputs or internal state that an observer obtains through the interfaces or observations admitted by a security model. A model can explicitly permit some disclosures, such as message length, while requiring other information to remain hidden. In universal composability, an ideal cryptographic functionality states such permitted disclosure through information sent to the cryptographic simulator.^[ref]

A simple cryptographic leakage function writes the disclosed value as $L=\ell (X)$, where $X$ is a secret random variable. An original example takes $X$ uniform on the 256 eight-bit strings and lets $L$ reveal its first four bits. Before observing $L$, every complete secret has probability $1/256$. Afterwards, exactly sixteen secrets remain equally likely, so the best complete-secret guess succeeds with probability $1/16$. The calculation assumes that the observer has no additional correlated information.

Using information entropy measured in bits, this example givesHere $H(X\mid L)$ is conditional entropy and $I(X;L)$ is mutual information. Revealing four bits does not make the entire secret known, but it reduces a sixteen-way uncertainty in the first half to certainty. Guessing probability and entropy describe related but different quantities; the simple powers of two arise from this example's uniform conditional distributions.

Length disclosure gives another operational example. Suppose a cryptographic environment privately chooses a uniform bit $b$, then submits a one-byte message when $b=0$ and a two-byte message when $b=1$. Observing the length reveals $b$ exactly, even if the encryption hides all message contents at each fixed length. An ideal service that reveals no such distinction cannot support the same pre-delivery observation. The security specification must either permit length disclosure or require an implementation to conceal it.

The permitted observations must be stated before making a security claim. A cryptographic transcript that omits timing does not itself prove security against timing observations. Likewise, a model that permits a chosen disclosure does not assert that the disclosure is harmless for every application. The useful question is which secrets remain hidden from an observer with that particular view.

A cryptographic leakage function specifies which observation of secret state is disclosed in a model. A deterministic version writes $L=\ell (X)$, where $X$ is a secret random variable. It is a description of an observer's information, not an encryption algorithm. An ideal cryptographic functionality can explicitly send permitted disclosures to its cryptographic simulator; Canetti's secure-communication example permits disclosure of message length.^[ref]

For an observed value $l$ of positive probability, possible secrets lie in its preimage under $\ell$. Their posterior probabilities areEqual likelihood within that set requires a uniform prior there; it is not a consequence of the word leakage.

An original example takes $X$ uniform on all eight-bit strings and lets $\ell (X)$ be its Hamming weight. The disclosure has only nine possible values, but its consequences vary. If $L=4$, there are $\left(\genfrac{}{}{0ex}{}{8}{4}\right)=70$ equally likely secrets and the best exact guess succeeds with probability $1/70$. If $L=0$, the secret is certainly the all-zero string. A rare disclosure can therefore determine the complete secret even though the observation is encoded in only four bits.

Averaging optimal exact-guess success over all disclosed weights givescompared with $1/256$ before observation. This Hamming-weight leakage of a uniform bit string distinguishes an average guessing probability from the worst conditional outcome.

Specify repeated observations and any correlated side information too. Two individually limited disclosures can jointly identify a secret. A randomized or noisy observation is described by a conditional channel rather than only a deterministic function. Stating an allowed cryptographic leakage function makes a security claim precise; it does not establish that the disclosure is harmless for every application.

Let $X$ be uniformly distributed over the $2^n$ bit strings of length $n$, and disclose only its Hamming weight $W$, the number of one-bits. This is a deterministic cryptographic leakage function. Its consequences depend on the observed weight, even though $W$ has only $n+1$ possible values. A permitted disclosure belongs in the security model; the existence of that model does not establish that the disclosure is harmless.^[ref]

There are $\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ strings of weight $w$. Hence $W$ has a binomial distribution, and conditional probability givesfor each compatible string $x$. The optimal complete-string guess therefore succeeds with probability $1/\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ after that observation. For $n=4$, observing $w=2$ leaves six equally likely strings; observing $w=0$ identifies 0000 exactly.

Averaging over disclosed weights yieldscompared with $2^{-n}$ before disclosure. For four bits this changes $1/16$ to $5/16$. The worst conditional outcome has success probability one. An average guarantee and a guarantee for every observation are consequently different claims.

The information entropy calculation answers another question. Since $W$ is determined by $X$, the mutual information satisfies $I(X;W)=H(W)$ andFor $n=4$, $H(W)\approx 2.03064$ bits and $H(X\mid W)\approx 1.96936$ bits. These entropy values are not obtained by taking the logarithm of the average guessing probability. All calculations here assume the uniform prior and no additional correlated observation.