Author Archives: fgrieu

I’m wondering if and how the current public key certificate infrastructure is dealing with the following scenario:

• Honest Alice obtains Eve’s public key certificate Cert_e, made by honest CA Carol; checks it the usual way; and assumes she knows Eve’s public kev Pub_e.
• Alice generates a message M mentioning obligation by Eve, sends it towards Eve, and receives apparently from Eve a signature S; Alice verifies that M, S, and Pub_e match.
• Later, Eve denies having approved M or produced S; suggests that S must be by Frida; and as argument asserts that S also checks against Frida’s certified public key.
• Alice obtain Frida’s public key certificate Cert_f, made by honest CA Carl; checks it the usual way; and assumes she knows Frida’s public key Pub_f.
• Alice verifies that indeed M, S, and Pub_f match!
• Pub_e and Pub_f are different, and Alice finds them unremarkable, as well as Cert_e and Cert_f; these carry a certification date earlier than the generation of M by Alice; there was no certificate revocation.
• Alice obtains other (M, S) pairs attributed to Eve and Frida; they verify against only one of Pub_e or Pub_f, as intended.

This was previously asked here on security.SE, moderated out for confirmation (that we now have) that the method in the last section allows Eve to pull this trick (with the cooperation of Frida or by tricking her, when using RSA signature per PKCS#1v2 as practiced, and unless all CAs take more precautions than advertised in their Certification Practices Statements).

That fact leaves the rational part of a cryptographer unmoved: the theoretical security definition of a signature scheme is not broken, and the only mild surprise is that Pub_e and Pub_f are different. This may work with other signature schemes (perhaps with slight relaxations: single signature S, allowing Frida’s certificate Cert_s to be generated after message M is sent to Eve, letting Eve alter a part of M that does not render to the naked eye..). And while the simple method in the end of the question is detectable if Alice or a judge understands the math of RSA and does a specific feasible check, there is no cryptographic insurance that an analog exists for all attacks and signature schemes.

Is this issue currently dealt with? If not, should that be, and how? Some ideas:

• Have the problem dealt with in policies for dispute resolution in electronic signature, by explicitly stating that in the circumstance Alice can choose to hold either Eve of Frida responsible for having signed M, regardless of denegation of either.
• Amend our definition of what’s a secure signature scheme in order to prevent this, and accordingly improve the existing schemes (in the case of PKCS#1v2, it appears that the problem is fixed by mandatorily setting the existing tag input of the signature scheme to the hash of the signer’s public key, and checking this as a necessary condition for signature validity).

Please consider that this is about policies, which is on-topic (if not currently a tag).

Update: the message being a random challenge as in TLS is no obstacle: Eve can authenticate as Eve to Alice and communicate with her, then deny being involved in the communication and assert Frida was, on the ground that logs of the TLS transaction produced by Alice verify against Frida’s public key certificate as well as they do for Eve’s, even though their public keys differ. Alice can’t tell if she was communicating with Eve, or Frida, or another party. The best Alice can hope demonstrate is that both Eve and Frida must have acted at least negligently if the CAs did their job as advertised and the signature scheme used is secure.

That scenario could happen with 2048-bit RSA, usual e=F₄=65537, and RSASSA-PSS as signature, assuming Eve and Frida are crooks operating as follows:

• Eve and Frida jointly choose two distinct small close primes, say r_e=101 and r_f=103; and jointly generate their respective RSA modulus N_e and N_f with N_e=r_e⋅p⋅q, N_f=r_f⋅p⋅q, 2²⁰⁴⁷<N_e<N_f<2²⁰⁴⁸, p and q large random primes with gcd(p-1,65537)=1=gcd(q-1,65537).
• Eve computes her private exponent d_e=e^-1 mod LCM(r_e-1,p-1,q-1) matching her public key Pub_e=(N_e,e) with e=65537. Frida does similarly for d_f matching her public key Pub_f=(N_f,e).
• Eve and Frida obtain their certificate the normal way; the only caveat is that they avoid CAs that check for small factors in public modulus.
• When Eve generates a signature using RSASSA-PSS, she proceeds normally, except that she additionally checks the signature against Pub_f: about one signature among r_f pass this test! Eve iterates signing until finding a signature for M matching her intention to later attribute the signature to Frida, or not. Frida does similarly.

Continue reading Dealing with signature verifying against multiple certified public keys→