**Javascript disabled?**Like other modern websites, the IETF Datatracker relies on Javascript. Please enable Javascript for full functionality.

#
Shepherd writeup

draft-hao-schnorr

ISE write-up for: draft-hao-schnorr-06 Abstract: "This document describes Schnorr NIZK proof, a non-interactive variant of the three-pass Schnorr identification scheme. The Schnorr NIZK proof allows one to prove the knowledge of a discrete logarithm without leaking any information about its value. It can serve as a useful building block for many cryptographic protocols to ensure the participants follow the protocol specification honestly. This document specifies the Schnorr NIZK proof in both the finite field and the elliptic curve settings." This draft has no IANA Considerations. The draft has not been discussed in any IETF WG. It was reviewed for me by Stanislav Smyshlyaev and Tibor Jager. The authors have made the changes suggested by the reviewers. - - - - - Stanislav Smyshlyaev's Review Overall opinion: Minor changes needed The -05 version addresses most of my concerns described in my brief review for -04 version (in October 2016), but I’d still prefer some changes to be made. The Schnorr signature scheme and the Schnorr NIZK proof have a difficult history (including their relationship with DSA) – and I think it is quite a good idea to have an RFC on them. We’ve had a discussion with Feng Hao after -04 version, now I am not against publication of Schnorr NIZK in a separate RFC (without signature scheme, though), so, in my opinion, only minor changes are still needed. In my previous review I said that it would be useful to give certain recommendations about hash functions and elliptic curve parameters. Though some words are now given, I’d recommend to change terms a bit: collision resistance is not the property that is really needed for random oracle model. Tibor’s proposal of saying “secure cryptographic hash function” seems to be a good option – in this case we won’t go too far into details, but would prevent using something non-cryptographic (e.g. HighwayHash). And instead of saying “Recommended hash functions include…” I’d prefer to see a more relaxed phrase like “e.g. SHA-256, SHA-512, …”. I am not really sure that the comment about a simultaneous exponentiation technique in 2.4 and in 3.4 is needed. The issue is that g (or G) is always known beforehand (even before Bob is aware of Alice’s ID and her X (or Q) ) – so the table for powers of g (or G) can be precomputed beforehand, which would make simultaneous exponentiation (with a necessity to generate a precomputation table for a pair of (g, X) ) ineffective. Anyway, that’s not critical and may remain unchanged, if the author wants it. Though originally the scheme was named “an identification scheme”, the scheme actually implements authentication (assumed identities are known before the start of the protocol) thus I’d prefer to revise the terms in the paper a bit. The comment about the public key validation (for a case of a small cofactor) in 3.4 should be specified a little – leaving only a reference for [MOV96] looks not very convenient here: e.g. to say that at least it must be verified that Q satisfies the curve equation and that 4*Q is nonzero. At the beginning of Section 4 I’d recommend to revise a phrase “to ensure participants follow the specification properly” – maybe just to say about participants possessing secret values? In my opinion, the statement about equivalent proofs for DSA/ECDSA either needs further deep comments (the models, the known results etc.) or just to be removed. I think that in the current form it does not add anything helpful, but leaves the reader unsatisfied, in fact there is a lot of positive results for DSA/ECDSA (and a lot of additional results for ISO/IEC 14888-3 EC-RDSA). In Section 5 the phrase “The assumption of an honest verifier naturally holds because the verifier can be anyone” should be removed – it’s very unclear and misleading, in my opinion. It seems to me that the document is useful and should become an RFC in a slightly revised form. - - - - - Tibor Jager's Review Summary: This is a review of draft-hao-schnorr-05. It proposes several changes to the specification and suggests an efficiency improvement to the non-interactive variant of the protocols. ---------------------------------------- Major comments: ---------------------------------------- §2.2, "Bob chooses challenge c ... uniformly at random from [0,2^t-1] ... (e.g. t=80)" The standard security proof of Schnorr's ID scheme assumes that c is chosen uniformly at random from [0,q-1], where q is the subgroup order. Section §5 mentions the provable security of Schnorr's ID-scheme and the resulting NIZK-PoK, however, this applies only if the protocol specified in this RFC matches the protocol considered in the security proof. In the non-interactive setting, where c is derived with a hash function, it will of course be inconvenient to demand c \in [0,q-1]. In this setting, one should require that 2^t is at least equal to the order q of the considered subgroup. In general, t=80 seems to be too small, because colliding c-values may enable attacks. Setting t to be twice the desired "security in bits" (e.g., t=256 for "128-bit security") seems more reasonable. ---------------------------------------- §2.3, "the hash function H shall be collision-resistant" Collision-resistance alone is not sufficient to instantiate the Fiat-Shamir construction securely. A contrived but illustrative example: requiring only collision-resistance may mislead people implementing this RFC into instantiating H with the identity map (or any other injective function which is not a "good" cryptographic hash function). Such an instantiation of H would be collision-resistant, but the resulting NIZK protocol derived by applying the Fiat-Shamir transform is completely insecure. Actually, the hash function must "approximate a random oracle reasonably well". Therefore I suggest to replace "the hash function H shall be collision-resistant" with "the hash function H must be a secure cryptographic hash function, like e.g. SHA-256, SHA-512, ...". (This comment applies also to §5 "Security Considerations") ---------------------------------------- §2.3, "Usually, the boundary is implicitly defined, once the length of items is publicly known" Different protocols may use parameters of different size, therefore assuming implicit boundaries seems dangerous. In particular, it may enable cross-protocol attacks that exploit the fact that different protocols may use different parameter sizes. Therefore it seems useful to always require explicit boundaries here. This would also reduce flexibility, and therefore improve interoperability of implementations. ---------------------------------------- §2.3, description of the non-interactive protocol: In the current instantiation of the non-interactive protocol, the prover sends (V,b) (along with UserID and OtherInfo), and the verifier first computes c, and then checks for V = g^b * X^c mod p. Assuming typical choices of p and q, this requires the transmission of an element V of Zp, whose size is somewhere between 1024 and 4096 bits, and an element b of Zq with expected size of about 160-512 bits. It seems possible to reduce the amount of transmitted data to two elements of Zq, by replacing (V,b) with (c,b): - The prover of this optimised variant works exactly as in the protocol described in the current document, except that it sends (c,b) instead of (V,b) - The verifier computes V = g^b * X^c, and then checks whether H(g || V || g^x || UserID || OtherInfo) = c. This is a standard trick to reduce the size of Schnorr signatures, which seems to be applicable here, too. The security of this modified variant follows from the fact that one can compute V from (c,b), and c from (V,b) (and the additional public parameters). Therefore sending (c,b) is equivalent to sending (V,c,b), which in turn is equivalent to sending (V,b). ---------------------------------------- §2.4, verification of proofs: The full verification procedure of proofs (including verification of group membership) should not be described in the "Computational Costs" section, but earlier in the protocol specification (§2.2 and §2.3). ---------------------------------------- §3.3, using only the x-coordinates of points as hash inputs: Is there any important reason why only the x-coordinates are used as input to the hash function here? Hashing the entire group element seems more compatible with the security proof of Schnorr's ID scheme, and seems not to incur significant additional costs. ---------------------------------------- §5, "The assumption of an honest verifier naturally holds because the verifier can be anyone." I was not able to follow this argument. Actually, the reason why the Fiat-Shamir transform requires only an honest-verifier ID scheme is because the hash function (more precisely, the random oracle in the security proof) implements an honest verifier, because it assigns a uniformly random challenge c to each g^v sent by the prover to the hash function oracle - this is exactly what a honest verifier would do. ---------------------------------------- §5, vulnerability to bad randomness. Using Schnorr's ID scheme or its non-interactive variant with bad randomness v in g^v mod p may reveal the secret discrete logarithm whose knowledge the prover wants to prove. For example, if the same random value V = g^v mod p is used twice by the prover (e.g. because its random number generator fails), but the verifier chooses different challenges c, c' (or the hash function is used on two different OtherData, producing two different values c, c'), then this reveals the prover's secret key: The adversary observes two proof transcripts (V,c,b) and (V,c',b'), which both verify. Then it computes (b-b')/(c'-c) = (v-xc - v+xc')/(c'-c) = x mod p which reveals the secret key x of the prover. More generally, such an attack may even work for a slightly better (but still bad) random number generator, where the value v is not repeated, but the adversary knows a relation between two values v,v', such as v' = v+r for some known value r. More precisely: Suppose that the adversary observes two proof transcripts (V,c,b) and (V',c',b'), which both verify. Suppose also that the adversary knows that V' = g^v' = g^(v+r) = V * g^r mod p. Then it computes (b-b'+r)/(c'-c) mod p = (v-xc - v-r+xc' + r) / (c-c') mod p = x mod p Such potential weaknesses of Schnorr's ID scheme should be explained very clearly in the Security Considerations section. ---------------------------------------- Minor comments: ---------------------------------------- §1.2 Notation In the "mod p" setting, q denotes the order of the (sub)group generated by generator g. In the elliptic curve setting, q denote the characteristic of the base field Fq, while n denotes the order of the group. For clarity, it would be useful to let q denote the order of (sub)groups throughout the document, to avoid confusion, and choose a different character for the characteristic of the base field of the elliptic curve group. ---------------------------------------- §2.2, "...must be a subgroup element ... which anyone can verify". Please specify here how verification works exactly, or at least refer to another part of the document which specifies this. ---------------------------------------- §3.2, "Alice publishes her public key Q = G x [x]". The double meaning of symbol "x", first denoting multiplication and then denoting a value x, is a bit unfortunate here. The earlier sections used * as a symbol for multiplication. One may consider replacing the above with "Q = G * [x]" Furthermore, the value Q is not necessarily an actual "public key" in all possible applications of the protocol standardised in this RFC. In some protocol, it may e.g. be a message sent to establish a key via a Diffie-Hellman like protocol, etc., while other values are used as actual public keys. Instead, one could simply write "Alice publishes an elliptic curve point Q = G * [x] of which she wants to prove knowledge of the discrete logarithm w.r.t. generator G". (This comment applies also to §3.4, etc.) ---------------------------------------- §4, "the OtherInfo should include extra information": As also explained in the RFC draft, the non-interactive protocol is vulnerable to replay attacks. In particular, if the protocol is used as a Proof-of-Possession of the long-term secret to a CA, then it MUST be ensured that the hash contains data that links the proof to one particular key registration procedure. ---------------------------------------- §5, "A non-interactive ZK proof is often called a signature scheme" While there exists a natural relation between ZK proofs and digital signatures, the above statement is not true and therefore misleading. E.g., one cannot simply replace a NIZK proof with a signature scheme in general. I think one can safely delete this sentence, it seems not to add anything relevant to the specification of the protocol. - - - - -Back