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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.