idnits 2.17.1 draft-hao-schnorr-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (November 14, 2016) is 2713 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 485 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force F. Hao, Ed. 3 Internet-Draft Newcastle University (UK) 4 Intended status: Informational November 14, 2016 5 Expires: May 18, 2017 7 Schnorr NIZK Proof: Non-interactive Zero Knowledge Proof for Discrete 8 Logarithm 9 draft-hao-schnorr-05 11 Abstract 13 This document describes Schnorr NIZK proof, a non-interactive variant 14 of the three-pass Schnorr identification scheme. The Schnorr NIZK 15 proof allows one to prove the knowledge of a discrete logarithm 16 without leaking any information about its value. It can serve as a 17 useful building block for many cryptographic protocols to ensure the 18 participants follow the protocol specification honestly. This 19 document specifies the Schnorr NIZK proof in both the finite field 20 and the elliptic curve settings. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on May 18, 2017. 39 Copyright Notice 41 Copyright (c) 2016 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 57 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 58 1.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2. Schnorr NIZK Proof over Finite Field . . . . . . . . . . . . 4 60 2.1. Group Parameters . . . . . . . . . . . . . . . . . . . . 4 61 2.2. Schnorr Identification Scheme . . . . . . . . . . . . . . 4 62 2.3. Non-Interactive Zero-Knowledge Proof . . . . . . . . . . 5 63 2.4. Computation Cost . . . . . . . . . . . . . . . . . . . . 6 64 3. Schnorr NIZK Proof over Elliptic Curve . . . . . . . . . . . 6 65 3.1. Group Parameters . . . . . . . . . . . . . . . . . . . . 6 66 3.2. Schnorr Identification Scheme . . . . . . . . . . . . . . 7 67 3.3. Non-Interactive Zero-Knowledge Proof . . . . . . . . . . 7 68 3.4. Computation Cost . . . . . . . . . . . . . . . . . . . . 8 69 4. Applications of Schnorr NIZK proof . . . . . . . . . . . . . 8 70 5. Security Considerations . . . . . . . . . . . . . . . . . . . 9 71 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 72 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10 73 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 74 8.1. Normative References . . . . . . . . . . . . . . . . . . 10 75 8.2. Informative References . . . . . . . . . . . . . . . . . 10 76 8.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 11 77 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 79 1. Introduction 81 A well-known principle for designing robust public key protocols 82 states as follows: "Do not assume that a message you receive has a 83 particular form (such as g^r for known r) unless you can check this" 84 [AN95]. This is the sixth of the eight principles defined by Ross 85 Anderson and Roger Needham at Crypto'95. Hence, it is also known as 86 the "sixth principle". In the past thirty years, many public key 87 protocols failed to prevent attacks, which can be explained by the 88 violation of this principle [Hao10]. 90 While there may be several ways to satisfy the sixth principle, this 91 document describes one technique that allows one to prove the 92 knowledge of a discrete logarithm (e.g., r for g^r) without revealing 93 its value. This technique is called the Schnorr NIZK proof, which is 94 a non-interactive variant of the three-pass Schnorr identification 95 scheme [Stinson06]. The original Schnorr identification scheme is 96 made non-interactive through a Fiat-Shamir transformation [FS86], 97 assuming that there exists a secure cryptographic hash function 98 (i.e., the so-called random oracle model). 100 The Schnorr NIZK proof can be implemented over a finite field or an 101 elliptic curve (EC). The technical specification is basically the 102 same, except that the underlying cyclic group is different. For 103 completeness, this document describes the Schnorr NIZK proof in both 104 the finite field and the EC settings. 106 1.1. Requirements Language 108 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 109 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 110 document are to be interpreted as described in RFC 2119 [RFC2119]. 112 1.2. Notations 114 The following notations are used in this document: 116 o Alice: the assumed identity of the prover in the protocol 118 o Bob: the assumed identity of the verifier in the protocol 120 o a || b: concatenation of a and b 122 o t: the bit length of the challenge chosen by Bob 124 o H: a secure cryptographic hash function 126 o p: a large prime 128 o q: a large prime divisor of p-1, i.e., q | p-1 130 o Zp*: a multiplicative group of integers modulo p 132 o Gq: a subgroup of Zp* with prime order q 134 o g: a generator of Gq 136 o g^x: g raised to the power of x 138 o a mod b: a modulo b 140 o Fq: a finite field of q elements where q is a prime 142 o E(Fq): an elliptic curve defined over Fq 144 o G: a generator of the subgroup over E(Fq) with prime order n 145 o n: the order of G 147 o h: the cofactor of the subgroup generated by G, as defined by h 148 = |E(Fq)|/n 150 o P x [b]: multiplication of a point P with a scalar b over E(Fq) 152 o P.x: the x coordinate of a point P over E(Fq) 154 2. Schnorr NIZK Proof over Finite Field 156 2.1. Group Parameters 158 When implemented over a finite field, the Schnorr NIZK proof may use 159 the same group setting as DSA. Let p and q be two large primes with 160 q | p-1. Let Gq denote the subgroup of Zp* of prime order q, and g 161 be a generator for the subgroup. Refer to NIST [1] for values of (p, 162 q, g) that provide different security levels. Here DSA groups are 163 used only as an example. Other multiplicative groups where the 164 discrete logarithm problem (DLP) is intractable are also suitable for 165 the implementation of the Schnorr NIZK proof. 167 2.2. Schnorr Identification Scheme 169 The Schnorr identification scheme runs interactively between Alice 170 (prover) and Bob (verifier). In the setup of the scheme, Alice 171 publishes her public key X = g^x mod p where x is the private key 172 chosen uniformly at random from [0, q-1]. The value X must be an 173 element in the subgroup Gq, which anyone can verify. This is to 174 ensure that the discrete logarithm of X with respect to the base g 175 actually exists. 177 The protocol works in three passes: 179 1. Alice chooses a number v uniformly at random from [0, q-1] and 180 computes V = g^v mod p. She sends V to Bob. 182 2. Bob chooses a challenge c uniformly at random from [0, 2^t-1], 183 where t is the bit length of the challenge (say t = 80). Bob 184 sends c to Alice. 186 3. Alice computes b = v - x * c mod q and sends it to Bob. 188 At the end of the protocol, Bob checks if the following equality 189 holds: V = g^b * X^c mod p. The verification succeeds only if the 190 equality holds. The process is summarized in the following diagram. 192 Information Flows in Schnorr Identification Scheme 194 Alice Bob 195 ------- ----- 197 choose random v from [0, q-1] 199 compute V = g^v mod p -- V -> 201 compute b = v-x*c mod q <- c -- choose random c from [0, 2^t-1] 203 -- b -> check if V = g^b * X^c mod p? 205 2.3. Non-Interactive Zero-Knowledge Proof 207 The Schnorr NIZK proof is obtained from the interactive Schnorr 208 identification scheme through a Fiat-Shamir transformation [FS86]. 209 This transformation involves using a secure cryptographic hash 210 function to issue the challenge instead. More specifically, the 211 challenge is redefined as c = H(g || g^v || g^x || UserID || 212 OtherInfo), where UserID is a unique identifier for the prover and 213 OtherInfo is optional data. Here, the hash function H shall be 214 collision-resistant. Recommended hash functions include SHA-256, 215 SHA-384, SHA-512, SHA3-256, SHA-384 and SHA3-512. 217 The OtherInfo is defined to allow flexible inclusion of contextual 218 information (also known as "labels" in [ABM15]) in the Schnorr NIZK 219 proof so that the technique defined in this document can be generally 220 useful. For example, some security protocols built on top of the 221 Schnorr NIZK proof may wish to include more contextual information 222 such as the protocol name, timestamp and so on. The exact items (if 223 any) in OtherInfo shall be left to specific protocols to define. 224 However, the format of OtherInfo in any specific protocol must be 225 fixed and explicitly defined in the protocol specification. 227 Within the hash function, there must be a clear boundary between the 228 concatenated items. Usually, the boundary is implicitly defined once 229 the length of each item is publicly known. However, in the general 230 case, it is safer to define the boundary explicitly. It is 231 recommended that one should always prepend each item with a 4-byte 232 integer that represents the byte length of the item. The OtherInfo 233 may contain multiple sub-items. In that case, the same rule shall 234 apply to ensure a clear boundary between adjacent sub-items. 236 2.4. Computation Cost 238 In summary, to prove the knowledge of the exponent for X = g^x, Alice 239 generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V = 240 g^v mod p, r = v - x*c mod q}, where c = H(g || g^v || g^x || 241 UserID || OtherInfo). 243 To generate a Schnorr NIZK proof, the cost is roughly one modular 244 exponentiation: that is to compute g^v mod p. In practice, this 245 exponentiation may be pre-computed in the off-line manner to optimize 246 efficiency. The cost of the remaining operations (random number 247 generation, modular multiplication and hashing) is negligible as 248 compared with the modular exponentiation. 250 To verify the Schnorr NIZK proof, the following computations shall be 251 performed. 253 1. To verify X is within [1, p-1] and X^q = 1 mod p 255 2. To verify V = g^r * X^c mod p 257 Hence, the cost of verifying a Schnorr NIZK proof is approximately 258 two exponentiations: one for computing X^q mod p and the other for 259 computing g^r * X^c mod p. (It takes roughly one exponentiation to 260 compute the latter using a simultaneous exponentiation technique as 261 described in [MOV96].) 263 It is worth noting that some applications may specifically exclude 264 the identity element as a valid public key. In that case, one shall 265 check X is within [2, p-1] instead of [1, p-1]. Also note that in 266 the DSA-like group setting, it requires a full modular exponentiation 267 to validate a public key, but in the ECDSA-like setting, the public 268 key validation incurs almost negligible cost due to the cofactor 269 being very small (see [MOV96]). 271 3. Schnorr NIZK Proof over Elliptic Curve 273 3.1. Group Parameters 275 When implemented over an elliptic curve, the Schnorr NIZK proof may 276 use the same EC setting as ECDSA, e.g., NIST P-256, P-384, and P-521 277 [NISTCurve]. Let E(Fq) be an elliptic curve defined over a finite 278 field Fq where q is a large prime. Let G be a base point on the 279 curve that serves as a generator for the subgroup over E(Fq) of prime 280 order n. The cofactor of the subgroup is denoted h, which is usually 281 a small value (not more than 4). Details on EC operations, such as 282 addition, negation and scalar multiplications, can be found in 283 [MOV96]. Here the NIST curves are used only as an example. Other 284 secure curves such as Curve25519 are also suitable for the 285 implementation as long as the elliptic curve discrete logarithm 286 problem (ECDLP) remains intractable. 288 3.2. Schnorr Identification Scheme 290 In the setup of the scheme, Alice publishes her public key Q = G x 291 [x] where x is the private key chosen uniformly at random from [1, 292 n-1]. The value Q must be an element in the subgroup over the 293 elliptic curve, which anyone can verify. 295 The protocol works in three passes: 297 1. Alice chooses a number v uniformly at random from [1, n-1] and 298 computes V = G x [v]. She sends V to Bob. 300 2. Bob chooses a challenge c uniformly at random from [0, 2^t-1], 301 where t is the bit length of the challenge (say t = 80). Bob 302 sends c to Alice. 304 3. Alice computes b = v - x * c mod n and sends it to Bob. 306 At the end of the protocol, Bob checks if the following equality 307 holds: V = G x [b] + Q x [c]. The verification succeeds only if the 308 equality holds. The process is summarized in the following diagram. 310 Information Flows in Schnorr Identification Scheme 312 Alice Bob 313 ------- ----- 315 choose random v from [1, n-1] 317 compute V = G x [v] -- V -> 319 compute b = v - x * c mod n <- c -- choose random c from [0, 2^t-1] 321 -- b -> check if V = G x [b] + Q x [c]? 323 3.3. Non-Interactive Zero-Knowledge Proof 325 Same as before, the non-interactive variant is obtained through a 326 Fiat-Shamir transformation [FS86], by using a secure cryptographic 327 hash function to issue the challenge instead. Note that G, V and Q 328 are points on the curve. In practice, it is sufficient to include 329 only the x coordinate of the point into the hash function. Hence, 330 let G.x, V.x and Q.x be the x coordinates of these points 331 respectively. The challenge c is defined as c = H(G.x || V.x || 332 Q.x || UserID || OtherInfo), where UserID is a unique identifier for 333 the prover and OtherInfo is optional data as explained earlier. 335 3.4. Computation Cost 337 In summary, to prove the knowledge of the discrete logarithm for Q = 338 G x [x] with respect to base G over the elliptic curve, Alice 339 generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V = 340 G x [v], r = v - x*c mod n}, where c = H(G.x || V.x || Q.x || 341 UserID || OtherInfo). 343 To generate a Schnorr NIZK proof, the cost is one scalar 344 multiplication: that is to compute G x [v]. 346 To verify the Schnorr NIZK proof in the EC setting, the following 347 computations shall be performed. 349 1. To verify Q is a valid public key in the subgroup over E(Fq) 351 2. To verify V = G x [r] + Q x [c] 353 In the EC setting where the cofactor is small (say 1, 2 or 4), 354 validating the public key Q is essentially free (see [MOV96]). The 355 cost of verifying a Schnorr NIZK proof in the EC setting is 356 approximately one multiplication over the elliptic curve: i.e., 357 computing G x [r] + Q x [c] (using the same simultaneous computation 358 technique as before). 360 4. Applications of Schnorr NIZK proof 362 Some key exchange protocols, such as J-PAKE [HR08] and YAK [Hao10], 363 rely on the Schnorr NIZK proof to ensure participants in the protocol 364 follow the specification honestly. Hence, the technique described in 365 this document can be directly applied to those protocols. 367 The inclusion of OtherInfo also makes the Schnorr NIZK proof 368 generally useful and sufficiently flexible to cater for a wide range 369 of applications. For example, the described technique may be used to 370 allow a user to demonstrate the Proof-Of-Possession (PoP) of a long- 371 term private key to a Certificate Authority (CA) during the public 372 key registration phrase. Accordingly, the OtherInfo should include 373 extra information such as the CA name, the expiry date, the 374 applicant's email contact and so on. In this case, the Schnorr NIZK 375 proof is equivalent to a self-signed Certificate Signing Request 376 generated by using DSA or ECDSA, except that its security is 377 underpinned by well-established security proofs [Stinson06] while 378 equivalent proofs are lacking in DSA or ECDSA. 380 5. Security Considerations 382 The Schnorr identification protocol has been proven to satisfy the 383 following properties, assuming that the verifier is honest and the 384 discrete logarithm problem is intractable (see [Stinson06]). 386 1. Completeness -- a prover who knows the discrete logarithm is 387 always able to pass the verification challenge. 389 2. Soundness -- an adversary who does not know the discrete 390 logarithm has only a negligible probability (i.e., 2^(-t)) to 391 pass the verification challenge. 393 3. Honest verifier zero-knowledge -- a prover leaks no more than one 394 bit information to the honest verifier: whether the prover knows 395 the discrete logarithm. 397 The Fiat-Shamir transformation is a standard technique to transform a 398 three-pass interactive Zero Knowledge Proof protocol (in which the 399 verifier chooses a random challenge) to a non-interactive one, 400 assuming that there exists a secure (collision-resistant) hash 401 function. Since the hash function is publicly defined, the prover is 402 able to compute the challenge by itself, hence making the protocol 403 non-interactive. The assumption of an honest verifier naturally 404 holds because the verifier can be anyone. 406 A non-interactive Zero Knowledge Proof is often called a signature 407 scheme. However, it should be noted that the Schnorr NIZK proof 408 described in this document is different from the original Schnorr 409 signature scheme (see [Stinson06]) in that it is specifically 410 designed as a proof of knowledge of the discrete logarithm rather 411 than a general-purpose digital signing algorithm. 413 When a security protocol relies on the Schnorr NIZK proof for proving 414 the knowledge of a discrete logarithm in a non-interactive way, the 415 threat of replay attacks shall be considered. For example, the 416 Schnorr NIZK proof might be replayed back to the prover itself (to 417 introduce some undesirable correlation between items in a 418 cryptographic protocol). This particular attack is prevented by the 419 inclusion of the unique UserID into the hash. The verifier shall 420 check the prover's UserID is a valid identity and is different from 421 its own. Depending on the context of specific protocols, other forms 422 of replay attacks should be considered, and appropriate contextual 423 information included into OtherInfo whenever necessary. 425 6. IANA Considerations 427 This document has no actions for IANA. 429 7. Acknowledgements 431 The editor of this document would like to thank Dylan Clarke, Robert 432 Ransom, Siamak Shahandashti, Robert Cragie and Stanislav Smyshlyaev 433 for useful comments. This work is supported by the EPSRC First Grant 434 (EP/J011541/1) and the ERC Starting Grant (No. 306994). 436 8. References 438 8.1. Normative References 440 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 441 Requirement Levels", BCP 14, RFC 2119, 442 DOI 10.17487/RFC2119, March 1997, 443 . 445 [ABM15] Abdalla, M., Benhamouda, F., and P. MacKenzie, "Security 446 of the J-PAKE Password-Authenticated Key Exchange 447 Protocol", IEEE Symposium on Security and Privacy, May 448 2015. 450 [AN95] Anderson, R. and R. Needham, "Robustness principles for 451 public key protocols", Proceedings of the 15th Annual 452 International Cryptology Conference on Advances in 453 Cryptology, 1995. 455 [FS86] Fiat, A. and A. Shamir, "How to Prove Yourself: Practical 456 Solutions to Identification and Signature Problems", 457 Proceedings of the 6th Annual International Cryptology 458 Conference on Advances in Cryptology, 1986. 460 [MOV96] Menezes, A., Oorschot, P., and S. Vanstone, "Handbook of 461 Applied Cryptography", 1996. 463 [Stinson06] 464 Stinson, D., "Cryptography: Theory and Practice (3rd 465 Edition)", CRC, 2006. 467 8.2. Informative References 469 [NISTCurve] 470 "Recommended Elliptic Curves for Federal Government use", 471 July 1999, 472 . 475 [HR08] Hao, F. and P. Ryan, "Password Authenticated Key Exchange 476 by Juggling", the 16th Workshop on Security Protocols, 477 May 2008. 479 [Hao10] Hao, F., "On Robust Key Agreement Based on Public Key 480 Authentication", the 14th International Conference on 481 Financial Cryptography and Data Security, February 2010. 483 8.3. URIs 485 [1] http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ 486 DSA2_All.pdf 488 Author's Address 490 Feng Hao (editor) 491 Newcastle University (UK) 492 Claremont Tower, School of Computing Science, Newcastle University 493 Newcastle Upon Tyne 494 United Kingdom 496 Phone: +44 (0)191-208-6384 497 EMail: feng.hao@ncl.ac.uk