2

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 Certe, made by honest CA Carol; checks it the usual way; and assumes she knows Eve's public kev Pube.
  • 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 Pube 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 Certf, made by honest CA Carl; checks it the usual way; and assumes she knows Frida's public key Pubf.
  • Alice verifies that indeed M, S, and Pubf match!
  • Pube and Pubf are different, and Alice finds them unremarkable, as well as Certe and Certf; 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 Pube or Pubf, 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 Pube and Pubf are different. This may work with other signature schemes (perhaps with slight relaxations: single signature S, allowing Frida's certificate Certs 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=F4=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 re=101 and rf=103; and jointly generate their respective RSA modulus Ne and Nf with Ne=re⋅p⋅q, Nf=rf⋅p⋅q, 22047<Ne<Nf<22048, p and q large random primes with gcd(p-1,65537)=1=gcd(q-1,65537).
  • Eve computes her private exponent de=e-1 mod LCM(re-1,p-1,q-1) matching her public key Pube=(Ne,e) with e=65537. Frida does similarly for df matching her public key Pubf=(Nf,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 Pubf: about one signature among rf 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.
1

I think the main problem is that Eve has full control over the private key, the message to sign and thus the signature. This full control enables her to collude with Frida which has the same amount of control.

If Eve signs a message which contains an obligation to Alice then this message should contain a part which is defined by Alice, like a random token. This way Eve looses full control over the message and colluding with Frida is no longer possible.

  • What I detail in the second part of the question there does not require any manipulation of the message M, or weakness of the hash; it works unchanged with the proposed countermeasure. This is an attack on the trust model some have about digital signatures, which is different from the one cryptographers usually study. – fgrieu Jun 15 '17 at 21:25
  • @fgrieu: I agree but it depends on the specifics of the application where you use certificates. For example in TLS the authentication of the server is done using certificates. But the message which needs to be signed by the server is based on client input which makes the attack you describe impossible. But in other situations this is different and thus it is good to be aware of this possible attack and defeat it by making sure that the signer has no full control of the message - or at least being aware that this attack would be possible. – Steffen Ullrich Jun 15 '17 at 21:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.