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!
Informally, a signature scheme with message recovery is one where some or all of the message is embedded in the signature. That can reduce the size of the signed message, sometime by a proportion approaching 2, e.g. for RSA public-key certificates.
$$\begin{array}{ll} \mathsf{Gen},\mathsf{Sign},\mathsf{Ver}&\text{Key generation, signature, verification algorithms.}\\ \operatorname{Pub}, \operatorname{Priv}&\text{Public and private keys (bitsrings).}\\ M_r&\text{‘Recoverable’ message.}\\ M'_r&\text{‘Recovered’ message, equal to }M_r\text{ on successful verification.}\\ M_n&\text{‘Non-recoverable’ message, equivalently ‘clear’ or ‘visible’.}\\ S&\text{Signature.}\\ \end{array}$$
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]:
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}$.
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).
Some schemes also offer partial message recovery : signature generation breaks the message $M$ into $M_r$ and $M_n$ in a public, scheme-defined manner, with $|M|=|M_r|+|M_n|$; it is assumed that $M_n$ [the non-recoverable part] is made an additional input of the signature verification function (as in signature with appendix); while $M_r$ [the recoverable part] replaces $M$ in the output of the verification function, which becomes $(b,M_r)$.
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_n)=(\text{true},M_r)$, where $M_r$ and $M_n$ 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_n$ and $S\in\{0,1\}^*$ with $V_{K_\text{pub}}(S,M_n)=(\text{true},M_r)$, and such that the oracle was not queried with $M$ obtained by recombining $M_r$ and $M_n$.
Typically, $|S|$ is fixed for a given public key, but independent of $|M|$; and $|M_n|=0$ for $|M|$ below some threshold. For $k$-bit security, $|M_r|\le|S|-k$ must hold, or equivalently $|M_n|\ge|M|-|S|+k$
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 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_r\|M_n$. The recoverable part $M_r$ is at the beginning 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_n$ is empty for short $M$ [and always a byte-string even when $M$ is not, thus $|M_r|\equiv|M|\pmod 8$]; $M_n$ is often transmitted unmodified along the signed message, but could be implicit in whole or in part (e.g. a version number). When $M_n$ 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_r$, 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_r$ 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_r$ and, for partial message recovery, the non-recovered $M_n$ obtained by other means.
I refer to EMV 4.4, 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 parametrization 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]. They are available in BouncyCastle as ISO9796d2PSSSigner.
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_n$
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.
