# Description of signatures with message recovery (as in ISO/IEC 9796-2 and EMV Signatures)

I'd like to get an overview of how the signatures with message recovery work, especially in case EMV and other smart card systems. Is there a nice overview available without being required to read the whole ISO/IEC 9796-2?

I've already had a look at the “Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures” paper… but there, only the encoding function was listed and I couldn't really understand how the signature is verified and recovered. Thanks!

-
Can you restrict to ISO/IEC 9796-2 scheme 1, both message and modulus of size multiple of 8 bits, and implicit use of SHA-1 as the hash (as in the linked paper, and EMV)? If yes, is there anything not clear after reading EMV 4.3, Book 2, Annex A2.1? – fgrieu Jun 22 '14 at 18:33
thanks a lot, @fgrieu, that is exactly what I was looking for. What confused me was the recovery part, namely how the message $M=M_{1}||M_{2}$ can be recovered from the signature if the signature contains $M_{1}$ and $h(M_{2})$. Then I read the standard ISO 9796-2 (yes, I had to do it eventually :)) and surprise, here what I found there: "The recoverable part [i.e.$M_{1}$] will be recovered from the signature during the verification process, whereas the non-recoverable part [$M_{2}$] must be made available to the verifier by other means (e.g. it can be sent or stored with the signature). – OnTarget Jun 23 '14 at 8:30
However, now I have another question, namely, who can explain the following claim from ISO 9796-2: "NOTE 1 For practical purposes, an application may wish to structure the message M to ensure that data it wants to be explicitly stored or transmitted (e.g., address information) is allocated to the non-recoverable message part M2..." Does it matter in which part of the message such data is transmitted? (it must be recovered anyway...) (the example of the address I didn't get either :)) – OnTarget Jun 23 '14 at 8:31
By the way, what are the efficiency gain of such signatures (with recovery) compared to the ones with appendix? – OnTarget Jun 23 '14 at 8:51
In an EMV context, yes $m\equiv n\equiv 0\pmod 8$ holds, because (for $m$) all messages are bytes, and (for $n$) public modulus has size multiple of 8 (and even 32, perhaps 64) by some (AFAIK unwritten) rule, as demonstrated (AFAIK, only) by the fact that EMV's ISO/IEC 9796-2 padding starts with '6A' (yes that's circular). However, $n\equiv 0\pmod 8$ does NOT hold in a PKCS#1 context. Messages with a number of bits not multiple of 8 are a rarity, but ISO/IEC 9796-2 also covers that. – fgrieu Jun 24 '14 at 16:27

Informally, a signature scheme with message recovery is one where some or all of the message is embedded in the signature, allowing to conserve bandwidth when transmitting a signed message, compared to a signature scheme with appendix.

### Total message recovery

A signature scheme with total message recovery [some sources make total implicit, e.g. the HAC section 11.2.3] can be formally defined as three functions [easily computable, with a compact and public definition]:

• a key generation function
• with inputs
• some parameters (in particular for key size)
• a random bitstring,
• with output a public/private key pair $(K_\text{pub},K_\text{priv})$,
• a signature function $\mathcal S$
• with inputs
• same parameters
• $K_\text{priv}$ obtained from the output of the key generation function
• any message $M$ in some large subset $\mathbb M$ of the set of bitstrings $\{0,1\}^*$
• an (optional) random bitstring [that is used in ISO/IEC 9796-2 scheme 2]
• with output a bitstring designated as the signed message $S=\mathcal S_{K_\text{priv}}(M)$,
• a verification function $\mathcal V$
• with inputs
• same parameters
• $K_\text{pub}$ obtained from the output of the key generation function
• any bitstring $S\in\{0,1\}^*$
• with output a pair $(b,M)=\mathcal V_{K_\text{pub}}(S)$ with
• $b$ a boolean, either $\text{false}$ [bad signature] or $\text{true}$ [good signature]
• a bitstring $M$

such that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M))=(\text{true},M)$.

A signature scheme with total message recovery is defined to be existentially secure [or equivalently: secure in a chosen-messages setup] if a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S)=(\text{true},M)$, and such that the oracle was not queried with $M$.

Notice that in a signature scheme with total message recovery, $M$ is an output of the message verification function; when it is an input in a signature scheme with appendix. Recovering $M$ from the signed message $S$ requires evaluating $\mathcal V_{K_\text{pub}}(S)$, and in particular knowledge of $K_\text{pub}$.

It is trivial to transform a secure signature scheme with appendix [such as any of the signature schemes in PKCS#1] into a secure signature scheme with message recovery: construct the signed message of the new scheme by concatenating the message to the signature of the original scheme; and extract $M$ and that original signature from the signature of the new scheme, before applying the original verification procedure and giving its result as the boolean output of the new scheme. Practical signature schemes with message recovery are not constructed in this way, for they have an additional goal: make the signed message as short as possible. This is especially useful with RSA: signature schemes with message recovery can reduce the size of the signed message [by a proportion sometime approaching 2, e.g. for public-key certificates], while keeping fast signature verification.

For $k$-bit security, the size of signature and message must obey $|M|\le|S|-k$ (for odds of success of a trivial adversary not querying the oracle and trying $S$ at random are at least $2^{|M|-|S|}$, assuming $|S|$ is fixed for a given $|M|$ and all messages of size $|M|$ can be signed).

### Partial message recovery

Some schemes also offer partial message recovery: signature generation breaks the message $M$ into $M_1$ and $M_2$ in a public, scheme-defined manner, with $|M|=|M_1|+|M_2|$; it is assumed that $M_2$ [the non-recoverable part] is made an additional input of the signature verification function (as in signature with appendix); while $M_1$ [the recoverable part] replaces $M$ in the output of the verification function, which becomes $(b,M_1)$.

The correctness requirement becomes that for all parameters and random seed(s), $\forall M\in\mathcal M, V_{K_\text{pub}}(S_{K_\text{priv}}(M),M_2)=(\text{true},M_1)$, where $M_1$ and $M_2$ are extracted from $M$ in a prescribed manner, and can be recombined into $M$.

The security requirement becomes that a computationally bounded adversary, given $K_\text{pub}$ and access to an oracle producing $S_{K_\text{priv}}(M)$ when given any $M\in\mathbb M$, can not with sizable odds exhibit $M_2$ and $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S,M_2)=(\text{true},M_1)$, and such that the oracle was not queried with $M$ obtained by recombining $M_1$ and $M_2$.

Typically, $|S|$ is fixed for a given public key, but independent of $|M|$; and $|M_2|=0$ for $|M|$ below some threshold. For $k$-bit security, $|M_1|\le|S|-k$ must hold, or equivalently $|M_2|\ge|M|-|S|+k$

It is easy to turn any secure signature scheme with partial message recovery into a secure signature scheme with total message recovery (by appending $M_2$ to the signature of the original scheme). The reverse is also possible if the $M_2$ fraction of $M$ appears verbatim in $S$ at some unambiguous position, given the parameters (and possibly the public-key and the rest of the signature).

### Practice

The first standard message scheme with message recovery was ISO/IEC 9796:1991 [later renamed ISO/IEC 9796-1, but never approved under this name]. It did not use a hash, because standard hashes where then a novelty. It featured only total message recovery, and had the constraint $|M|\le|S|/2$ (within a few bits). It was broken in a chosen-messages setup [first within 1 bit; then fully (password obtained by subscribing to a mailing list) but with many messages; then with another attack that obtains the signature of $k$ extra messages from that of $k+2$ chosen other messages for most practical arguments]; and was withdrawn in 2000.

The second standard message scheme was ISO/IEC 9796-2:1997, now known as scheme 1 of ISO/IEC 9796-2. It improves on ISO/IEC 9796:1991 by using a hash, which allows a more compact signed message, and partial message recovery. Scheme 1 of ISO/IEC 9796-2 was broken in a chosen-messages setup [the best known attack is that in the paper (alternate link) noted in the question], but remains secure in practice when the adversary is restricted to obtaining signature of messages not specifically constructed to enable an attack. ISO/IEC 9796-2:2002 enforced a minimum hash width of $h=160$ as a mitigating measure, added schemes 2 and 3 intended to fix security for good, defined the so-called alternative signature production and opening functions that practice demanded, and included as normative the previously informative non-alternative signature production and opening functions. Amendment 1:2008 to ISO/IEC 9796-2:2002 added an ASN.1 module. ISO/IEC 9796-2:2010 makes only purely editorial changes AFAIK, beyond consolidating that amendment.

In ISO/IEC 9796-2, the message $M$ to be signed is subdivided as $M=M_1\|M_2$. The recoverable part $M_1$ is at the begging of the message, of some maximum size determined by the parameters; it is transmitted embedded into the signature $S$, which has size fixed by public key parameters. The non-recoverable part $M_2$ is empty for short $M$ [and always a bytestring even when $M$ is not, thus $|M_1|\equiv|M|\pmod 8$]; $M_2$ is often transmitted unmodified along the signed message, but could be implicit in whole or in part (e.g. a version number). When $M_2$ is empty [resp. non-empty], the scheme operates in total [resp. partial] recovery mode.

Scheme 1 of ISO/IEC 9796-2 is deterministic. For signature, a message representative is formed by concatenating prescribed padding, $M_1$, the hash of the whole message $M$, and other prescribed padding; the underlying [RSA-like] private-key function is then applied to obtain the signature, which is about the size of the public modulus. For verification of the signature and message recovery, after preliminary checks, the underlying public-key function is applied; the padding in that result is checked; the recovered $M_1$ is extracted from that result; and the hash extracted from that result is compared to the hash of the message reconstructed from the recovered $M_1$ and, for partial message recovery, the non-recovered $M_2$ obtained by other means.

I refer to EMV 4.3, Book 2, Annex A2.1, for a detailed exposition of ISO/IEC 9796-2 scheme 1, restricted to $n\equiv m\equiv 0\pmod 8$, SHA-1 (thus $h=160$), implicit hash identifier, $m\gt n+176$ [that is partial message recovery], and the so-called alternative signature production and opening functions RSASP1 and RSAVP1 in PKCS#1. This parameterization is common in Smart Cards, and directly supported [including with total message recovery] by Java Card 2.2.x/Classic.

Scheme 2 of ISO/IEC 9796-2 is randomized [and correspondingly has the signed message larger than scheme 1 in many use cases], with a security argument resembling that of RSASSA-PSS of PKCS#1, applicable including in a chosen-messages setup. Scheme 3 is a special case of scheme 2 with the random bitstring reduced to empty. The split of message into recoverable and non-recoverable portions is such that scheme 3 can be used as functional equivalent to scheme 1 with restored security in a chosen-messages setup [although I know no formal security argument].

Assuming an $n$-bit public modulus, when sending an $m$-bit message and its signature, the signed message of ISO/IEC 9796-2 schemes 1 or 3 has about $\min(n,m+h+16)$ bits where $h$ is the width of a hash [SHA-1 is popular, giving $h=160$]. This allows a significant [at least when considering proportion] size saving for messages with $m$ commensurate to $n$, such as public-key certificates [compare to $m+n$ bits using the schemes in PKCS#1]. For example: with $n=1984$, $h=160$, $m=2000$ [250 bytes], the signed message may use $2176$ bits [272 bytes, rather than 498 bytes with PKCS#1]: $1984$ bits [248 bytes] for the RSA cryptogram, conveying $1808$ useful bits [226 bytes] forming the recoverable part of the message; and $192$ bits [24 bytes] forming the non-recoverable part of the message.

ISO/IEC 9796-2 has a maze of features and parameters: three schemes; many hashes; optional hash identifier [intended to allow interoperability in contexts where the signer decides which hash is used, without requiring guesswork on the verifier side]; modulus of size not multiple of 8; messages of size not multiple of 8 when the hash allows; total or partial message recovery; either RSA or Rabin signature scheme [an analog with even public exponent]; and two slightly different options of RSA signature production and opening functions: those not designated as alternative sign as $x\mapsto \min(x^d\bmod N, N-(x^d\bmod N))$ which saves one bit over the alternative: PKCS#1's RSASP1. EMV originally referred to ISO/IEC 9796-2:1997, but only uses partial message recovery, the alternative functions not alluded to in this standard, and now refers to ISO/IEC 9796-2:2010 without stating the scheme, functions, or other options. The European Digital Tachograph [annex 1B, appendix 11] does just as EMV when it refers to ISO/IEC 9796-2 in a signature context for certificates, but also refers to ISO/IEC 9796-2 in its authentication and key agreement scheme where it uses scheme 1 with total message recovery [thus different padding than EMV] and the non-alternative signature production and opening functions of that standard [because that enables re-encryption of the signature using a different private key with the same modulus size as the signature key, regardless of which modulus is smaller].

ISO/IEC 9796:1991, ISO/IEC 9796-2, and EMSR3 of P1363a (similar to ISO/IEC 9796-2) use RSA or Rabin as the underlying public-key cryposystem. There's also ISO/IEC 9796-3, the similar EMSR1, and EMSR2, that use the Discrete Logarithm (possibly over an Elliptic Curve group).

Regarding the note in ISO/IEC 9796-2:2010 quoted in that comment to the question:

For practical purposes, an application may wish to structure the message $M$ to ensure that data it wants to be explicitly stored or transmitted (e.g., address information) is allocated to the non-recoverable message part $M_2$

That's intended to draw attention to the fact that only the non-recoverable part of the signed message [if any] is intelligible before verification of the signature. As a consequence, information that needs to be readily available before or absent signature verification is better placed in that non-recoverable part of the message, rather than in the recoverable part.

As a real-life illustration: contrary to the recommendation in this note, in the aforementioned European Digital Tachograph specification, the message in a certificate [defined by Annex 1B, appendix 11, 3.3.1 CSM_017] has the identification [designated CAR] of the public key of the authority that produced that certificate placed near the beginning, thus in the recoverable part of the message, thus unintelligible before signature verification, which can be a problem to decide which public key is appropriate to verify that certificate, absent context. To avoid this, a copy of CAR, designated X.CAR, was appended at the end of the signed certificate [defined in 3.3.2 CSM_018], allowing not reading the certification authority's certificate if it is already known and its public key cached, and giving a chance to know what allegedly generated a certificate even if it fails to verify. That complication increases the certificate size by 8 bytes, and creates confusion about if an hypothetical certificate with its X.CAR not matching CAR is deemed valid, and what/who is deemed to have generated it; that could have been avoided if CAR had been at the end of the certificate data, thus in the non-recoverable portion.

-
That may actually be longer than the standard :) – Maarten Bodewes Jun 28 '14 at 2:03