# How do SignRecover and VerifyRecover work?

In PKCS#11, there are the SignRecover and VerifyRecover methods,
where the data can be recovered from the signature. How do these methods work?
Can I implement signrecover and verifyrecover with openssl?

• I want to implement this methods using at least one mechanism. – sfallahdoost Mar 7 '15 at 21:14

TL;DR: they might not.

PKCS#11 is a standard for the software interface to cryptographic tokens (such as HSMs or Smart Cards), aiming at compatibility between implementations made by different token vendors. It also allows the same API to use various cryptographic mechanisms performing similar tasks by changing only a few values, mostly the Mechanisms parameter (an integer with a standard-assigned value) and some sizes.

PKCS#11 was written under supervision of RSA Security, and archives of that period are linked from EMC's PKCS#11 page. PKCS#11 moved to OASIS, which turned these into (in particular) Base Standard v2.40c01 (2014-12-23) and Current Mechanisms v2.40c01 (2014-12-23); these are scheduled for approval on 2015-04-15 with minor changes.

PKCS#11 has an API for signature schemes with (total) message recovery; that is, a kind of signature scheme where the (whole) message being signed is conveyed in the cryptogram of the signature, and is an output of the signature verification, rather than an input (as in the case in a signature scheme with appendix, e.g. RSASSA-PKCS1-V1_5 or RSASSA-PSS of PKCS#1).

For signature production, C_SignRecoverInit and C_SignRecover are to signature schemes with (total) message recovery what C_SignInit and C_Sign are to signature schemes with appendix, with exactly the same interface. For signature verification, C_VerifyRecoverInit and C_VerifyRecover are to signature schemes with message recovery what C_VerifyInit and C_Verify are to signature schemes with appendix, with a difference in the interface of C_VerifyRecover: it produces as output the recovered message (nominally identical to the message passed on input to C_SignRecover), when C_Verify receives as input the message to verify (nominally identical to the message passed on input to C_Sign).

Reference: Definition of C_VerifyRecover, and my memory.

CKM_RSA_X_509 is the simplest Mechanism that may be supported with C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover. Basically that's textbook RSA.

For the CKM_RSA_X_509 Mechanism, ignoring checks pertaining to the session state:

• C_SignRecover perform just as C_Sign; that is:

• checks that the size of the message to sign is at most $k$ bytes where $256^{k-1}\le N<256^k$ and $N$ is the RSA public modulus
• converts it to integer $m$ by big-endian conventions
• checks $m<N$
• produces $s=m^d\pmod N$ where $e$ is the RSA private exponent
• converts $s$ to $k$ bytes by big-endian conventions, and output it.
• C_VerifyRecover

• checks that the size of the signature is exactly $k$ bytes
• converts it to integer $s$ by big-endian conventions
• checks $s<N$
• produces $m=s^e\pmod N$ where $e$ is the RSA public exponent
• converts $m$ to $k$ bytes by big-endian conventions, and outputs it.

Reference: Definition of the CKM_RSA_X_509 Mechanism; its table of sizes of inputs and outputs (where £ is to be read as ≤); and my memory.

## Cautionary notes:

The CKM_RSA_X_509 Mechanism should only be used as a building block, because textbook RSA is unsafe.

The CKM_RSA_9796 Mechanism, used as example of signature schemes with message recovery in PKCS#11, should not be used, and is not secure under chosen-message attack, even though that was among its design goals. It is (a slight variant of) ISO/IEC 9796:1991 (perhaps on sale here), but withdrawn and next to forgotten (it was planned to be rechristened ISO/IEC 9796-1 but suffered fatal wounds before the ceremony formal approval: forgery is possible from the signature of 3 chosen messages).

The CKM_RSA_PKCS Mechanism (which may support signature with message recovery) should not be used to sign a message under direct control of the adversary, because it is not secure under chosen-message attack (it was not intended to be; variants that hash the message as required by RSASSA-PKCS1-V1_5, such as CKM_SHA256_RSA_PKCS, are stronger, but still are not recommendable except for compatibility with existing systems).

PKCS#11 does not have an API for signature schemes with partial message recovery, and does not support ISO/IEC 9796-2 (any scheme), which is often how message recovery is used (e.g. in Smart Cards for EMV banking, European Digital Tachograph certificates); ISO/IEC 9796-2 with PKCS#11 is thus typically implemented on top of PKCS#11 with CKM_RSA_X_509, or as a proprietary extension, or perhaps as an internal component of a (possibly standard) Mechanism such as CKM_CMS_SIG, rather than by PKCS#11.

Profiles v2.40c01 (2014-12-23), which lists features of PKCS#11 which support is required for conformance, is mum about message recovery; draw your own conclusions about the level of support it has among tokens found in the field. I have seen an implementation which documentation plain omits the SR/VR column in the all-important matrix of Mechanism vs Function support (yet dutifully mentions C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover has no limitation).

• thanks fgrieu,what is your reference for this description? – sfallahdoost Mar 9 '15 at 16:15
• @sfallahdoost: I added my references; I admit they are not crystal clear, and some of implementing PKCS#11 requires experience in the field. – fgrieu Mar 9 '15 at 22:47