# Can CKM_RSA_PKCS signature be made secure by lowering its maximum input size?

The CKM_RSA_PKCS Mechanism in PKCS#11 v2.20 section 12.1.6 PKCS #1 v1.5 RSA is a signature scheme commonly used to implement RSASSA-PKCS1-v1_5 of PKCS#1 signature of data hashed externally to a PKCS#11 token (such as an HSM).

With an RSA modulus $N$ of $k$ bytes ($2^{8k-8}\le N<2^{8k}$), CKM_RSA_PKCS signature

• accepts any bytestring message to sign $\text{T}$ of $t$ bytes with $t\le t_\text{max}=k-11$; we note $T$ the corresponding integer per big-endian convention ($0\le T<2^{8t}$);
• forms a message representative $R=2^{8k-15}-2^{8t+8}+T$
equivalently: $\text{R}=\text{'00'}\|\text{'01'}\|\text{'FF'}\|\dots\|\text{'FF'}\|\text{'00'}\|\text{T}$ of $k$ bytes, among which $k-t-3\ge8$ bytes at $\text{'FF'}$ starting from the third byte;
• computes $S=R^d\bmod N$ (that's the textbook RSA private key function);
• outputs the signature $\text{S}$ as $k$ bytes per big-endian convention.

The verification procedure checks that $\text{S}$ is $k$ bytes, $S<N$, and compares $S^e\bmod N$ to $R$ corresponding to an alleged message $\text{T}$ of at most $t_\text{max}$ bytes (or, in message recovery mode, $\text{T}$ and its size $t\le t_\text{max}$ are determined from $S^e\bmod N$, and are an output of the signature verification procedure).

CKM_RSA_PKCS signature is not secure when the adversary can obtain the signature of largely chosen messages: it is easy to find distinct $\text{T}_0$,$\text{T}_1$,$\text{T}_2$,$\text{T}_3$ leading to $R_0\cdot R_1=R_2\cdot R_3$, and thus $S_0=S_1^{-1}\cdot S_2\cdot S_3\bmod N$, an (existential) forgery.
Example for 1024-bit RSA: $k=128$, $t=80$, $T_0=2^{632}$, $T_1=2^{377}-2^{16}$, $T_2=0$, $T_3=2^{632}+2^{377}-2^{16}+1$.

Can CKM_RSA_PKCS signature be made secure by lowering its maximum input size? If yes, how does security relate to $t_\text{max}$ and $k$? The adversary's goal is to forge an admissible signature $\text{S}$ that was not obtained from the signer.

Hypothetical case where the issue matters: a time-stamping server generates and appends an 8-byte time-stamp in seconds to any bytestring it receives up to $t_\text{max}-8$ bytes (intended to be the hash of a message by a method irrelevant to the server), and provides the corresponding CKM_RSA_PKCS signature. An adversary able to query the server can forge a signature for the SHA-512 hash of (a slight variant of) any message, that passes verification and appears to have been made by the server before the attack. Techniques from Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures apply, and the attack is much easier, since only the forged signature is bound to have a hash in its message representative.