5
$\begingroup$

I'm wondering if and how the current public key certificate infrastructure is guarded against 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.

Unless I err, 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.

Update: I asked again there, where questions about policies belong.

Improve this question
$\endgroup$
3
  • $\begingroup$ FYI, I've just talked to a sec.se mod about the migration of this Q. It turned out that apparently it requires a crypto person to verify this attack and / or to understand the attack and then make the call on whether / how it is dealt with using their in-depth knowledge of established policies. In either case crypto-knowledge was deemed neccessary which is apparently the main reason why it was migrated. $\endgroup$
    – SEJPM
    Commented Jun 15, 2017 at 12:53
  • $\begingroup$ @SEJPM: I'm reasonably confident that the RSA math checks. I do have doubts about if CAs prevent it, and also pesky details like if real signatures usually embed a public key identifier, which would need to be changed, making Eva's argument slightly more protracted. That's why I did not ask on CSE. In any case, I advise ignoring the issue as a matter of dispute resolution policy, as I recently voiced; just curious about if there are attempts at preventing the thing. $\endgroup$
    – fgrieu ♦
    Commented Jun 15, 2017 at 14:49
  • 1
    $\begingroup$ My computations were wrong; I forget about the $\bmod N_e$ step, which effectively randomizes the $\bmod r_f$ value... $\endgroup$
    – poncho
    Commented Jun 15, 2017 at 15:00

1 Answer 1

Reset to default
2
$\begingroup$

From a cryptography perspective, this works as advertised; Eve and Frita can generate signature keys where a nontrivial fraction of signatures for one key will validate with the other.

That said:

  • It is trivial to detect this, if anyone looks. If we suspect that Eve and Frita are colluding (which we may, if someone demonstrates a signature that validates with both public keys), then a simple computation of $\text{gcd}( N_e, N_f )$ will reveal it. Alternatively, if someone just checks either $N_e$ or $N_f$ for small factors, that'd show that something nonkosher is going on. While I don't believe most CA's routinely check the public keys submitted to them for small factors, there might be some that do (and it certainly would not be expensive, compared to the other operations CA's must do).

  • It's not clear if this is actually an attack; $S$ is a valid signature for $M$ under $Pub_e$, and Eve cannot argue that it's not. Eve's argument of 'maybe Frita did it' doesn't address the question of 'how did Frita forge a signature of Eve's key'.

  • Also, as for your question of 'maybe real signatures embed a public key identifier', no, they do not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You'll notice that Eve uses CA Carol, while Frida uses another CA Carl, precisely to avoid the countermeasure that you suggested. I do not rule out that there are other trickery leading to mostly the same result with RSA or other signature schemes (perhaps with restriction to $\text{Pub}_f$ generated after $M$, or/and a single $S$), perhaps not easily detectable. But regardless, I agree that this is not a valid attack, and that resolution (if any) should be by discounting Eve's argument as a matter of policy. $\endgroup$
    – fgrieu ♦
    Commented Jun 15, 2017 at 15:10
  • 1
    $\begingroup$ @fgrieu: actually, using different CA's won't address either of my suggested detection methods. Computing $\text{gcd}(N_e, N_f)$ would be done only after someone has a signature that validates with both, not something I'd expect a CA to do. As for checking for small factors, a CA can do that with only one of the keys. $\endgroup$
    – poncho
    Commented Jun 15, 2017 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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