>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..

Yeah this is a mistake in the specification - thanks for pointing it out. We planned to use a FDH hash for this operation.

>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.

I agree that the blinding factors should be chosen carefully and this is something that is currently being built into the extension we're developing. I'll add this explicitly to the document as well as it is an important consideration. 

Regarding the possibility of a malicious edge using a small modulus n. Given that there will only be one public signing key available at any time and since this will be publicly available (and checked by the clients using the CT log) it will be difficult to get away with this without clients realising.

>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 :

Thanks for the update on the security of BLS signatures. I haven't thought about these too much and they were added to the spec more as just an afterthought in case we wanted to explore an alternative to RSA. I had a conversation with Filippo a while ago and he mentioned that Tanja thought that going with RSA for now was probably the best idea due to the relative simplicity of the scheme. I'm open to re-engaging in the conversation however and if there are genuine attacks on this scheme then we'd have to consider something else.