Adding the revealed messages to the chalenge to avoid forgery

[BasileiosKal]

The following is a method that could possibly allow the prover to reveal messages for which they don't have a signature, taking advantage of the Fiat–Shamir challenge not containing the revealed messages. Let the prover with a signature (A, e, s) on messages msg_1, msg_2 and msg_3, creating an spk revealing only msg_1. Going through the spkGen process the prover will calculate

C2_prover = D*(-r3~) +H0 * (s~) + H_2 * m~_2 + H_3 * m~_3

The proof value will be,

spk = (Abar, A’, D, c, e^, r2^, r3^, s^, m^_2, m^_3)

From the verification process we know that if T = P1 + H_1 * msg_1 then

#EQ1: T*c + D * (-r3^) + H0*s^ + H_2 * m^_2 + H_3 * m^_3 = C2_prover

Let the prover now calculate the following,

1. c’ = c ^ -1 mod q
2. msg_adv = m^_2 * c'

and instead of revealing spk, they send spk2,

spk2 = (Abar, A’, D, c, e^, r2^, r3^, s^, m^_3)

with revealed messages msg_1 and msg_adv.

The verifier receiving spk2 and msg_1, msg_adv will calculate C1_verifier, C2_verifier and check the pairing equality. Note that since Abar, A’, D, c, e^, r2^ remain the same between spk and spk2, C1_prover = C1_verifier and e(A', PK) = e(Abar, P2). To calculate C2_verifier the verifier will first calculate T2 as,

T2 = P1 + H_1 * msg_1 + H_2 * msg_adv = P1 + H_1 * msg_1 + H_2 * (m^_2 * c')

From that the verifier will calculate,

C2_verifier = T2*c + D * (-r3^) + H0*s^ + H_3 * m^_3 =
   = D * (-r3^) + H0*s^ + (P1 + H_1 * msg_1) * c +  H_2 * (m^_2 * c' * c)  H_3 * m^_3 =  
   = D * (-r3^) + H0*s^ + T * c +  H_2 * m^_2 +  H_3 * m^_3  = C2_prover

The last equality follows from #EQ1. As a result, the verification will succeed for msg_1 and msg_adv.

Obviously, this should not be possible, since this proves knowledge of a signature that the prover doesn't have (which contains msg_adv). If I'm correct on the above, most likely the only issue is with the Fiat–Shamir heuristic. Note that if the protocol was interactive, that method will not work, since the prover would have to "commit" to the messages prior of getting the challenge c. Hence we should also pass the revealed messages to the hash of the challenge during spkGen and spkVerify, to "commit" them before the challenge is created.

[mikelodder7]

No this is not correct. BBS+ is unforgeable like ECDSA. This includes in proofs. You have a bug in your math. If you compute it correctly you can’t forge proofs or signatures

[tplooker]

@mikelodder7 can you highlight the bug in the maths here?

[mikelodder7]

The problem is sending msg_adv and not m^_2. m^_2 = m~_2 +cm_2. msg_adv = m_2c' + m_2. If you calculate with that difference the equation does not balance. @BasileiosKal. ^^

[andrewwhitehead]

It appears to work in my quick test. I think just adding the number of revealed messages to the challenge hash might be sufficient, unless there's a way to do the same thing in reverse to make that balance.

[mikelodder7]

So your saying I should have over 1/c* my first name as the revealed message? In practice will someone believe that? No. The procedure for revealed messages should include the mapping of how they got to the cryptographic value.

[mikelodder7]

For example, let's assume m_2 is my first name. The mapping is hash to Z_q*. If I received msg_adv, I would hash to Z_q* and check it. The hashing effectively destroys the 1/c computation and the proof fails.

[mikelodder7]

I'm not seeing how this is even working. Just tried in my rust code and it fails.

[andrewwhitehead]

It would probably not be useful for any hashed values, but it could work for numeric values since the prover can run the protocol many times until they get a msg_adv value within a useful range.

[BasileiosKal]

I do also agree this is hard to take advantage in practice but we should be protected against it either way.

A forgery is still dangerous IMO. If it's a name we talking about this may not be of use but what if it's a revocation ID and I'm able to present a different one??

The message mappings are not mandatory and IMO the proof should be safe without them. We could make hashing of the messages mandatory but I think there are simpler solutions.

I think just adding the number of revealed messages to the challenge hash might be sufficien

Yeap that may be anotherore efficient solution

[mikelodder7]

Still not seeing how this attack even works. I just tried it and my proof fails.

[andrewwhitehead]

I added a reproduction here. (Edit: updated to add the unforged proof check.)

[mikelodder7]

@andrewwhitehead That example is not using an unsigned message. The point of this is that mh isn't even signed. Try it with another random message that's not in the signature.

[andrewwhitehead]

@mikelodder7 The point is that the proof verifies with the revealed message m_adv which is not the same as what was signed (mh).

[andrewwhitehead]

Actually, it's not sufficient to add the number of revealed messages, I believe the actual revealed messages have to be added to the hash to prevent substitution.

[tplooker]

I remember @christianpaquin mentioning on a WG call that UProve included a similar mechanism?

[christianpaquin]

I remember @christianpaquin mentioning on a WG call that UProve included a similar mechanism?

Yes, in the U-Prove spec, the prover hashes (among other things) the disclosed attribute indices and their values (see c_p calculation on page 18).

[BasileiosKal]

The problem is sending msg_adv and not m^_2. m^_2 = m~_2 +cm_2. msg_adv = m_2c' + m_2. If you calculate with that difference the equation does not balance. @BasileiosKal. ^^

If we take msg_adv = m~_2 * c' + msg_2 then when the verifier calculates C2 they will get

C2_verifier = (P1 + H_1 * msg_1 + H_2 * (m~_2*c' + msg_2))*c + D * (-r3^) + H0*s^ + H_3 * m^_3 =
   = D * (-r3^) + H0*s^ + (P1 + H_1 * msg_1 + H_2 * msg_2) * c  + H_2 * m~_2 + H_3 * m^_3 =  
   = D * (-r3~) + H0*s~ - (P1 + H0*s + H_1 * msg_1 + H_2 * msg_2  + H_3 * msg_3) * c  + ...
         ... + (P1 + H_1 * msg_1 + H_2 * msg_2) * c  + H0*(s*c) + H_2 * m~_2 + H_3 * m~_3  + H_3 * msg_3 *  c =
   = D * (-r3~) + H0*s~ + H_2 * m~_2 + H_3 * m~_3 = C2_prover

So i don't see where I'm wrong to be honest, but i could be missing something.

[BasileiosKal]

Actually, it's not sufficient to add the number of revealed messages, I believe the actual revealed messages have to be added to the hash to prevent substitution.

Right, I guess nothing stops the prover from passing the "wrong" number of messages from the start (i.e., 2 in the example above). Maybe, aside from the revealed messages, we should also pass the H_i (or their indexes) similar to what U-prove does?? @christianpaquin where there any attacks that passing things like <D> and <C> in the challenge avoided, or it was for general good security practices??

[tplooker]

@BasileiosKal is this addressed via #95 or are there still updates we need to make to the proof challenge?