On Fri, 2016-09-30 at 20:53 +0000, Alex Davidson wrote:
We've updated aspects of the original spec, the newest spec can now be viewed here: https://github.com/cloudflare/challenge-bypass-specification. We're happy to hear comments from any of you on the design and on the capacity of the solution for preserving anonymity.
I noticed full domain hash (FDH) do not appear. Instead I'm reading :
For both PK and SIGN: 2048-bit RSA using OAEP and PSS (respectively) for normal operations.
For H: SHA256
For MAC: HMAC-SHA256
PSS is completely incompatible with blind signatures because the signer must provide randomness. You could maybe fix this with some sort of cut & choose or zero knowledge scheme for choosing the randomness, but..
All the security proofs for RSA blind signatures just replace PSS with FDH anyways. In fact, CloudFlare might not need a FDH for verification because hash factoring attacks sound implausible, but worse..
There is nothing about how the blinding factors get chosen!
There are absolutely brutal deanonymization attack on blind signatures where the blinding factor is not created using a full domain PRNG, probably your FDH for the signature. In this case, I really mean full domain where you (1) generate a random 2048 bit number, (2) test that it's less than the RSA modulus n, and (3) throw it away and start again if it is not. On average, this requires generating two 2048 bit numbers because n should lie half way between 2^2047 and 2^2048, but obviously a malicious exchange could pick a small n to make the clients do a bit more work.
There are more issues with blind Schnorr signatures, but they look susceptible to this attack too. The blind BLS signature scheme somes with different concerns :
- I'm worried that, if the mint can afford to pick an weak public key, then they have interesting attacks, so maybe client's must validate that the mint's public key does not lie in some dangerous subgroup somehow.
- Pairing-based schemes are dangerous for anonymity applications because the pairing makes them fail decisional Diffie-Hellman, which anonymity tends to require. As I understand the BLS paper, we have e( H(M)*g^r, sigma ) = e( (H(M)*g^r)^x, H(M)) so the mint sees the two rhs of the pairing during signing, and sees the two lhs during verification, so they can perform an intersection attack to deanonymize the user. I imagine this is prevented by the pairing being asymmetric with no way to move sigma or H(M) from G_1 to G_2, so no way to compute these particular pairing. I'm nervous about treating the asymmetry of the pairing as a security property though, well the little pairing-based crypto work I've read does not cover it. Worse, another pairing e between G_1 and G_1 works just fine, so if the curve is already pairing friendly then how do you know this bad pairing does not exist? Also, an H : {0,1}* -> G_2 compatible with the original H : {0,1}* -> G_1 might still work for the original good pairing e. I'm happy to ask our local experts on pairing, but ultimately I'd need to write up an array of theoretical attacks and ask Tanja Lange who I should ask.
I know it's annoying to work with someone else's specs, codebase, etc., but these are the sort of issues I've dealt with in Taler, so it might behoove you guys too track us a bit more closely. Aside from ways you might benefit from our experience, we might benefit from you guys wanting to do stuff in the HTTP header, actually we've maybe already moved that way for our Javascript-free HTTP API.
Best, Jeff