### [Crypto-panel] Review of draft-hao-schnorr-05

Tibor Jager <tibor.jager@upb.de> Mon, 06 March 2017 09:01 UTC

Return-Path: <tibor.jager@upb.de>

X-Original-To: crypto-panel@ietfa.amsl.com

Delivered-To: crypto-panel@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 264A212955D
for <crypto-panel@ietfa.amsl.com>; Mon, 6 Mar 2017 01:01:41 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -4.2

X-Spam-Level:

X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3]
autolearn=ham autolearn_force=no

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id aGYqxcgq9_A9 for <crypto-panel@ietfa.amsl.com>;
Mon, 6 Mar 2017 01:01:38 -0800 (PST)

Received: from mail.uni-paderborn.de (mail.uni-paderborn.de [131.234.142.9])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 81EA012947F
for <crypto-panel@irtf.org>; Mon, 6 Mar 2017 01:01:38 -0800 (PST)

To: rfc-ise@rfc-editor.org, n.brownlee@auckland.ac.nz

From: Tibor Jager <tibor.jager@upb.de>

Message-ID: <4330c8f7-f402-2642-2f8b-0adc691723a3@upb.de>

Date: Mon, 6 Mar 2017 10:01:31 +0100

User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0)
Gecko/20100101 Thunderbird/45.7.1

MIME-Version: 1.0

Content-Type: text/plain; charset=utf-8

Content-Transfer-Encoding: 8bit

X-IMT-Spam-Score: 0.0 ()

X-PMX-Version: 6.3.3.2656215, Antispam-Engine: 2.7.2.2107409,
Antispam-Data: 2017.3.6.85417, AntiVirus-Engine: 5.35.0,
AntiVirus-Data: 2017.3.6.5350001

X-IMT-Authenticated-Sender: uid=tjager,ou=People,o=upb,c=de

Archived-At: <https://mailarchive.ietf.org/arch/msg/crypto-panel/As8pC5ZZkeWNSM2GExW4OZF1-Yc>

X-Mailman-Approved-At: Mon, 06 Mar 2017 08:05:18 -0800

Cc: crypto-panel@irtf.org, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>

Subject: [Crypto-panel] Review of draft-hao-schnorr-05

X-BeenThere: crypto-panel@irtf.org

X-Mailman-Version: 2.1.17

Precedence: list

List-Id: <crypto-panel.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/crypto-panel>,
<mailto:crypto-panel-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/crypto-panel/>

List-Post: <mailto:crypto-panel@irtf.org>

List-Help: <mailto:crypto-panel-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/crypto-panel>,
<mailto:crypto-panel-request@irtf.org?subject=subscribe>

X-List-Received-Date: Mon, 06 Mar 2017 09:01:41 -0000

Dear Nick et al., Please find below my review of draft-hao-schnorr-05. Best regards, Tibor Document: draft-hao-schnorr-05 Reviewer: Tibor Jager Review Date: 2017-03-03 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.

- [Crypto-panel] Review of draft-hao-schnorr-05 Tibor Jager