Correspondence between proof and public key

[BasileiosKal]

In general, I was under the impression that a signature can be used to derive proofs that would be validated with only 1 specific key (the issuers PK).

That does not seem to be the case. The holder can present proofs for credentials signed from an issuer with public key PK, that will be validated with PK * y = P2 * (x*y), where y a scalar chosen by the holder. My question is: Is this dangerous?? It is not really a forgery. It may compromise the issuer's and/or holder's accountability though, i.e., an issuer may falsely claim that they never signed a specific credential or a holder that they never possessed (and used to create an spk) a credential signed from that issuer.

You can find the detailed mathematics here: https://hackmd.io/@Vasileios/HyuXt_kf9
and a reproduction here: https://github.com/BasileiosKal/dif-bbs-issue

In general the method is the following; Let the holder having the signature (A, s, e) on some messages. Let also the holder wanting to create a proof that would be validated with PK * y instead of PK, for some scalar y. During spkGen they will calculate Abar_f = A’ * y * e + B * r1 * y and D_f = B * r1 * y + H0 * r2. Note that e(Abar_f, P2) = e(A', PK * y). Changing some additional values in the proof, the holder can present the spk; (A’, Abar_f, D_f, …) that will be validated with PK * y.

A similar method works with a signature. The holder can present (A*(y^-1), s, e*y) which is a valid signature for the key PK * y (which is why the above method doesn't go against the security proofs given in the literature, i.e., a bbs proof, proves knowledge of a signature not only from the secret key x but also for a signature from the "secret key" y * x).

If a mitigation is needed, maybe including the issuer's PK as one of the signed messages will be an efficient solution, that solves the issuer’s and/or holder’s accountability issue.

[mikelodder7]

The PK is known by the verifier so if the holder does this then it won’t validate properly

[tplooker]

@mikelodder7 that is probably a valid assumption to make in many circumstances, however if it is the position we take, we need to document it in the security considerations. e.g a verifier should be aware when trusting the verifier to supply the public key of the signer to verify that this condition exists.

[mikelodder7]

Agreed

[tplooker]

The fact this computation on the public key exists without a mitigation also degrades the non-repudiable nature of signatures also (e.g an issuer could use it as a way to say "i didn't sign the signature used to generate this spk")

[tplooker]

Where a valid mitigation could be @mikelodder7's suggestion above.

[BasileiosKal]

The PK is known by the verifier so if the holder does this then it won’t validate properly

Agreed. That is why there is not really a forgery here. However to @tplooker point, it does degrade the non-repudiable property of the protocol. Another example can be that a malicious issuer could claim that they originally signed a specific credential (and that the holder should pay them for that service for example).

In general i would be interested if there is also any other way to take advantage of that. Regardless IMO its kinda a weird property (with easy mitigation) that i would expect to not hold though. IMO, protocol designers need to be aware of it, and its possible mitigation, as to not introduce any vulnerabilities because they assumed otherwise.

[mikelodder7]

Actually there’s no need for any mitigation here. The technique could apply to ANY signature and public key. If the issuer alters their public key then no signature will verify or proof. The advantage of pairing based signatures is they can actually recover the signature to a working state but ECDSA schnorr and Ed25519 cannot.

[tplooker]

I think the threat model here is the holder creates a proof with a PK = PK * y and transmits the PK to the verifier alongside the spk and the verifier ends up concluding the underlying signature proven by the spk was not signed by the private key associated to PK instead of PK *y. How does this apply to ECDSA and Ed25519 when they dont feature an spk phase

[tplooker]

OR the signer uses the fact that the holder can do this while generating the proof to repudiate (deny) the underlying signature associated to the SPK.

[mikelodder7]

The same problem exists with BLS signatures too. The verifier in ANY case should not get the public key from the holder. The point I’m saying is if the public key changes in any way the other signatures fall apart. The holder isn’t forging a proof here but randomizing it. That’s why There sometimes called randomizable signatures

[mikelodder7]

The signer could do this anyway

[tplooker]

Ok so are you saying it would be sufficient to just add something along the lines of "The verifier in ANY case should not get the public key from the holder" to the security considerations section?

[mikelodder7]

That’s why holders should call verify whenever they receive a signature regardless of the scheme including Ed25519. That’s just good practice in general

[mikelodder7]

We could, but to me it’s good practice to never trust the holder. You trust the signer therefore you get the key information from them

[BasileiosKal]

I completely agree that we should never trust the holder however the issue is not about that (after all if the holder is allowed to present whatever pk they want they can just forge whatever credential they choose). The issue has to do with untrusted issuers. The above issue essentially says that there is no way currently to hold accountable an issuer for a credential they signed when it comes to the proofs. This to me seems like it could be a problem in some scenarios (which i don't think its true for other signatures schemes).

[mikelodder7]

But I can do that anyway as a issuer without having to do this method.

[BasileiosKal]

I don't see how. The signature it self guarantees the non-repudiable property. How could i do the same thing when it comes to a proof (i.e., claim it was from a different pk??)

[mikelodder7]

To hold the issuer accountable requires them to register the key. Otherwise the issuer can just delete the signing key and claim they didn’t create it.

[BasileiosKal]

True, my point though is that they can do that even if they register their key. What if they register their key, use it to sign a credential and then claim they never did sign that credential themselves but it was signed by someone else?? Or what if they register my pk squared to a not so careful CA and claim that they are the ones signing my credentials?? You cant prove them wrong in those cases without a mitigation (It is not only about claiming they never signed something, they can also claim they did sign something they haven't).

[tplooker]

The PK is now apart of the signature domain introduced in #95 addressing this issue.