idnits 2.17.1 draft-hao-schnorr-06.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 (April 26, 2017) is 2556 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 541 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 April 26, 2017 5 Expires: October 28, 2017 7 Schnorr NIZK Proof: Non-interactive Zero Knowledge Proof for Discrete 8 Logarithm 9 draft-hao-schnorr-06 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 October 28, 2017. 39 Copyright Notice 41 Copyright (c) 2017 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 . . . . . . . . . . 8 68 3.4. Computation Cost . . . . . . . . . . . . . . . . . . . . 8 69 4. Variants of Schnorr NIZK proof . . . . . . . . . . . . . . . 8 70 5. Applications of Schnorr NIZK proof . . . . . . . . . . . . . 9 71 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 72 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 73 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 74 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 75 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 76 9.2. Informative References . . . . . . . . . . . . . . . . . 12 77 9.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 12 78 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 12 80 1. Introduction 82 A well-known principle for designing robust public key protocols 83 states as follows: "Do not assume that a message you receive has a 84 particular form (such as g^r for known r) unless you can check this" 85 [AN95]. This is the sixth of the eight principles defined by Ross 86 Anderson and Roger Needham at Crypto'95. Hence, it is also known as 87 the "sixth principle". In the past thirty years, many public key 88 protocols failed to prevent attacks, which can be explained by the 89 violation of this principle [Hao10]. 91 While there may be several ways to satisfy the sixth principle, this 92 document describes one technique that allows one to prove the 93 knowledge of a discrete logarithm (e.g., r for g^r) without revealing 94 its value. This technique is called the Schnorr NIZK proof, which is 95 a non-interactive variant of the three-pass Schnorr identification 96 scheme [Stinson06]. The original Schnorr identification scheme is 97 made non-interactive through a Fiat-Shamir transformation [FS86], 98 assuming that there exists a secure cryptographic hash function 99 (i.e., the so-called random oracle model). 101 The Schnorr NIZK proof can be implemented over a finite field or an 102 elliptic curve (EC). The technical specification is basically the 103 same, except that the underlying cyclic group is different. For 104 completeness, this document describes the Schnorr NIZK proof in both 105 the finite field and the EC settings. 107 1.1. Requirements Language 109 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 110 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 111 document are to be interpreted as described in RFC 2119 [RFC2119]. 113 1.2. Notations 115 The following notations are used in this document: 117 o Alice: the assumed identity of the prover in the protocol 119 o Bob: the assumed identity of the verifier in the protocol 121 o a | b: a divides b 123 o a || b: concatenation of a and b 125 o [a, b]: the interval of integers between and including a and b 127 o t: the bit length of the challenge chosen by Bob 129 o H: a secure cryptographic hash function 131 o p: a large prime 133 o q: a large prime divisor of p-1, i.e., q | p-1 135 o Zp*: a multiplicative group of integers modulo p 137 o Gq: a subgroup of Zp* with prime order q 139 o g: a generator of Gq 141 o g^x: g raised to the power of x 143 o a mod b: a modulo b 144 o Fp: a finite field of p elements where p is a prime 146 o E(Fp): an elliptic curve defined over Fp 148 o G: a generator of the subgroup over E(Fp) with prime order n 150 o n: the order of G 152 o h: the cofactor of the subgroup generated by G, which is equal to 153 the order of the elliptic curve divided by n 155 o P x [b]: multiplication of a point P with a scalar b over E(Fp) 157 2. Schnorr NIZK Proof over Finite Field 159 2.1. Group Parameters 161 When implemented over a finite field, the Schnorr NIZK proof may use 162 the same group setting as DSA [FIPS186-4]. Let p and q be two large 163 primes with q | p-1. Let Gq denote the subgroup of Zp* of prime 164 order q, and g be a generator for the subgroup. Refer to NIST [1] 165 for values of (p, q, g) that provide different security levels. A 166 level of 128-bit security or above is recommended. Here DSA groups 167 are used only as an example. Other multiplicative groups where the 168 discrete logarithm problem (DLP) is intractable are also suitable for 169 the implementation of the Schnorr NIZK proof. 171 2.2. Schnorr Identification Scheme 173 The Schnorr identification scheme runs interactively between Alice 174 (prover) and Bob (verifier). In the setup of the scheme, Alice 175 publishes her public key X = g^x mod p where x is the private key 176 chosen uniformly at random from [0, q-1]. 178 The protocol works in three passes: 180 1. Alice chooses a number v uniformly at random from [0, q-1] and 181 computes V = g^v mod p. She sends V to Bob. 183 2. Bob chooses a challenge c uniformly at random from [0, 2^t-1], 184 where t is the bit length of the challenge (say t = 160). Bob 185 sends c to Alice. 187 3. Alice computes b = v - x * c mod q and sends it to Bob. 189 At the end of the protocol, Bob performs the following checks. If 190 any check fails, the identification is unsuccessful. 192 1. To verify X is within [1, p-1] and X^q = 1 mod p; 194 2. To verify V = g^r * X^c mod p. 196 The first check ensures that X is a valid public key, hence the 197 discrete logarithm of X with respect to the base g actually exists. 198 It is worth noting that some applications may specifically exclude 199 the identity element as a valid public key. In that case, one shall 200 check X is within [2, p-1] instead of [1, p-1]. 202 The process is summarized in the following diagram. 204 Information Flows in Schnorr Identification Scheme over Finite Field 206 Alice Bob 207 ------- ----- 209 choose random v from [0, q-1] 211 compute V = g^v mod p -- V -> 213 compute b = v-x*c mod q <- c -- choose random c from [0, 2^t-1] 215 -- b -> check 1) X is a valid public key 216 2) V = g^b * X^c mod p 218 2.3. Non-Interactive Zero-Knowledge Proof 220 The Schnorr NIZK proof is obtained from the interactive Schnorr 221 identification scheme through a Fiat-Shamir transformation [FS86]. 222 This transformation involves using a secure cryptographic hash 223 function to issue the challenge instead. More specifically, the 224 challenge is redefined as c = H(g || g^v || g^x || UserID || 225 OtherInfo), where UserID is a unique identifier for the prover and 226 OtherInfo is optional data. Here, the hash function H shall be a 227 secure cryptographic hash function, e.g., SHA-256, SHA-384, SHA-512, 228 SHA3-256, SHA3-384 and SHA3-512. The bit length of the hash output 229 should be at least equal to the order q of the considered subgroup. 231 The OtherInfo is defined to allow flexible inclusion of contextual 232 information (also known as "labels" in [ABM15]) in the Schnorr NIZK 233 proof so that the technique defined in this document can be generally 234 useful. For example, some security protocols built on top of the 235 Schnorr NIZK proof may wish to include more contextual information 236 such as the protocol name, timestamp and so on. The exact items (if 237 any) in OtherInfo shall be left to specific protocols to define. 238 However, the format of OtherInfo in any specific protocol must be 239 fixed and explicitly defined in the protocol specification. 241 Within the hash function, there must be a clear boundary between any 242 two concatenated items. It is recommended that one should always 243 prepend each item with a 4-byte integer that represents the byte 244 length of that item. The OtherInfo may contain multiple sub-items. 245 In that case, the same rule shall apply to ensure a clear boundary 246 between adjacent sub-items. 248 2.4. Computation Cost 250 In summary, to prove the knowledge of the exponent for X = g^x, Alice 251 generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V = 252 g^v mod p, r = v - x*c mod q}, where c = H(g || g^v || g^x || 253 UserID || OtherInfo). 255 To generate a Schnorr NIZK proof, the cost is roughly one modular 256 exponentiation: that is to compute g^v mod p. In practice, this 257 exponentiation may be pre-computed in the off-line manner to optimize 258 efficiency. The cost of the remaining operations (random number 259 generation, modular multiplication and hashing) is negligible as 260 compared with the modular exponentiation. 262 To verify the Schnorr NIZK proof, the cost is approximately two 263 exponentiations: one for computing X^q mod p and the other for 264 computing g^r * X^c mod p. (It takes roughly one exponentiation to 265 compute the latter using a simultaneous exponentiation technique as 266 described in [MOV96].) 268 3. Schnorr NIZK Proof over Elliptic Curve 270 3.1. Group Parameters 272 When implemented over an elliptic curve, the Schnorr NIZK proof may 273 use the same EC setting as ECDSA [FIPS186-4]. For the illustration 274 purpose, only curves over the prime fields (e.g., NIST P-256) are 275 described here. Other curves over the binary fields (see 276 [FIPS186-4]) that are suitable for ECDSA can also be used for 277 implementing the Schnorr NIZK proof. Let E(Fp) be an elliptic curve 278 defined over a finite field Fp where p is a large prime. Let G be a 279 base point on the curve that serves as a generator for the subgroup 280 over E(Fp) of prime order n. The cofactor of the subgroup is denoted 281 h, which is usually a small value (not more than 4). Details on EC 282 operations, such as addition, negation and scalar multiplications, 283 can be found in [MOV96]. Date types and conversions including 284 elliptic-curve-point-to-octet-string and vice versa can be found in 285 Section 2.3 of [SEC1]. Here the NIST curves are used only as an 286 example. Other secure curves such as Curve25519 are also suitable 287 for the implementation as long as the elliptic curve discrete 288 logarithm problem (ECDLP) remains intractable. 290 3.2. Schnorr Identification Scheme 292 In the setup of the scheme, Alice publishes her public key Q = G x 293 [x] where x is the private key chosen uniformly at random from [1, 294 n-1]. 296 The protocol works in three passes: 298 1. Alice chooses a number v uniformly at random from [1, n-1] and 299 computes V = G x [v]. She sends V to Bob. 301 2. Bob chooses a challenge c uniformly at random from [0, 2^t-1], 302 where t is the bit length of the challenge (say t = 80). Bob 303 sends c to Alice. 305 3. Alice computes b = v - x * c mod n and sends it to Bob. 307 At the end of the protocol, Bob performs the following checks. If 308 any check fails, the verification is unsuccessful. 310 1. To verify X is a valid point on the curve and X x [h] is not the 311 point at infinity; 313 2. To verify V = G x [b] + Q x [c]. 315 The first check ensures that X is a valid public key, hence the 316 discrete logarithm of X with respect to the base G actually exists. 317 Unlike in the DSA-like group setting where a full modular 318 exponentiation is required to validate a public key, in the ECDSA- 319 like setting, the public key validation incurs almost negligible cost 320 due to the cofactor being small (e.g., 1, 2 or 4). 322 The process is summarized in the following diagram. 324 Information Flows in Schnorr Identification Scheme over Elliptic Curve 326 Alice Bob 327 ------- ----- 329 choose random v from [1, n-1] 331 compute V = G x [v] -- V -> 333 compute b = v - x * c mod n <- c -- choose random c from [0, 2^t-1] 335 -- b -> check 1) X is a valid public key 336 2) V = G x [b] + Q x [c] 338 3.3. Non-Interactive Zero-Knowledge Proof 340 Same as before, the non-interactive variant is obtained through a 341 Fiat-Shamir transformation [FS86], by using a secure cryptographic 342 hash function to issue the challenge instead. The challenge c is 343 defined as c = H(G || V || Q || UserID || OtherInfo), where UserID is 344 a unique identifier for the prover and OtherInfo is optional data as 345 explained earlier. 347 3.4. Computation Cost 349 In summary, to prove the knowledge of the discrete logarithm for Q = 350 G x [x] with respect to base G over the elliptic curve, Alice 351 generates a Schnorr NIZK proof that contains: {UserID, OtherInfo, V = 352 G x [v], r = v - x*c mod n}, where c = H(G || V || Q || UserID || 353 OtherInfo). 355 To generate a Schnorr NIZK proof, the cost is one scalar 356 multiplication: that is to compute G x [v]. 358 To verify the Schnorr NIZK proof in the EC setting, the cost is 359 approximately one multiplication over the elliptic curve: i.e., 360 computing G x [r] + Q x [c] (using the same simultaneous computation 361 technique as before). The cost of public key validation in the EC 362 setting is essentially free. 364 4. Variants of Schnorr NIZK proof 366 In the finite field setting, the prover sends (V, b) (along with 367 userID and OtherInfo), and the verifier first computes c, and then 368 checks for V = g^b * X^c mod p. This requires the transmission of an 369 element V of Zp, whose size is typically between 2048 and 3072 bits, 370 and an element b of Zq whose size is typically between 224 and 256 371 bits. It is possible to reduce the amount of transmitted data to two 372 elements of Zq as below. 374 In the modified variant, the prover works exactly the same as before, 375 except that it sends (c, b) instead of (V, b). The verifier computes 376 V = g^b * X^c mod p and then checks whether H(g || V || g^x || 377 UserID || OtherInfo) = c. The security of this modified variant 378 follows from the fact that one can compute V from (c, b) and c from 379 (V, b). Therefore, sending (c, b) is equivalent to sending (V, c, 380 b), which in turn is equivalent to sending (V, b). Thus, the size of 381 the Schnorr NIZK proof is significantly reduced. However, the 382 computation costs for both the prover and the verifier stay the same. 384 The same optimization technique also applies to the elliptic curve 385 setting by replacing (V, b) with (c, b), but the benefit is much 386 limited. When V is encoded in the compressed form, this optimization 387 only saves 1 bit. The computation costs for generating and verifying 388 the NIZK proof remain the same as before. 390 5. Applications of Schnorr NIZK proof 392 Some key exchange protocols, such as J-PAKE [HR08] and YAK [Hao10], 393 rely on the Schnorr NIZK proof to ensure participants have the 394 knowledge of discrete logarithms, hence following the protocol 395 specification honestly. The technique described in this document can 396 be directly applied to those protocols. 398 The inclusion of OtherInfo also makes the Schnorr NIZK proof 399 generally useful and flexible to cater for a wide range of 400 applications. For example, the described technique may be used to 401 allow a user to demonstrate the Proof-Of-Possession (PoP) of a long- 402 term private key to a Certificate Authority (CA) during the public 403 key registration phrase. It must be ensured that the hash contains 404 data that links the proof to one particular key registration 405 procedure, e.g., by including the CA name, the expiry date, the 406 applicant's email contact and so on to the OtherInfo. In this case, 407 the Schnorr NIZK proof is functionally equivalent to a self-signed 408 Certificate Signing Request generated by using DSA or ECDSA. 410 6. Security Considerations 412 The Schnorr identification protocol has been proven to satisfy the 413 following properties, assuming that the verifier is honest and the 414 discrete logarithm problem is intractable (see [Stinson06]). 416 1. Completeness -- a prover who knows the discrete logarithm is 417 always able to pass the verification challenge. 419 2. Soundness -- an adversary who does not know the discrete 420 logarithm has only a negligible probability (i.e., 2^(-t)) to 421 pass the verification challenge. 423 3. Honest verifier zero-knowledge -- a prover leaks no more than one 424 bit information to the honest verifier: whether the prover knows 425 the discrete logarithm. 427 The Fiat-Shamir transformation is a standard technique to transform a 428 three-pass interactive Zero Knowledge Proof protocol (in which the 429 verifier chooses a random challenge) to a non-interactive one, 430 assuming that there exists a secure cryptographic hash function. 431 Since the hash function is publicly defined, the prover is able to 432 compute the challenge by itself, hence making the protocol non- 433 interactive. In this case, the hash function (more precisely, the 434 random oracle in the security proof) implements an honest verifier, 435 because it assigns a uniformly random challenge c to each commitment 436 (g^v or G x [v]) sent by the prover. This is exactly what an honest 437 verifier would do. 439 It is important to note that in Schnorr's identification scheme and 440 its non-interactive variant, a secure random number generator is 441 required. In particular, bad randomness in v may reveal the secret 442 discrete logarithm. For example, suppose the same random value V = 443 g^v mod p is used twice by the prover (e.g., because its random 444 number generator failed), but the verifier chooses different 445 challenges c and c' (or the hash function is used on two different 446 OtherInfo data, producing two different values c and c'). The 447 adversary now observes two proof transcripts (V, c, b) and (V, c', 448 b'), based on which he can compute the secret key x by: (b-b')/(c'-c) 449 = (v-x*c-v+x*c')/(c'-c) = x mod q. 451 More generally, such an attack may even work for a slightly better 452 (but still bad) random number generator, where the value v is not 453 repeated, but the adversary knows a relation between two values v and 454 v' such as v' = v + w for some known value w. Suppose the adversary 455 observes two proof transcripts (V, c, b) and (V', c', b'). He can 456 compute the secret key x by: (b-b'+w)/(c'-c) = (v-x*c-v- 457 w+x*c'+w)/(c'-c) = x mod q. This example reinforces the importance 458 of using a secure random number generator to generate the ephemeral 459 secret v in Schnorr's schemes. 461 Finally, when a security protocol relies on the Schnorr NIZK proof 462 for proving the knowledge of a discrete logarithm in a non- 463 interactive way, the threat of replay attacks shall be considered. 464 For example, the Schnorr NIZK proof might be replayed back to the 465 prover itself (to introduce some undesirable correlation between 466 items in a cryptographic protocol). This particular attack is 467 prevented by the inclusion of the unique UserID into the hash. The 468 verifier shall check the prover's UserID is a valid identity and is 469 different from its own. Depending on the context of specific 470 protocols, other forms of replay attacks should be considered, and 471 appropriate contextual information included into OtherInfo whenever 472 necessary. 474 7. IANA Considerations 476 This document has no actions for IANA. 478 8. Acknowledgements 480 The editor of this document would like to thank Dylan Clarke, Robert 481 Ransom, Siamak Shahandashti, Robert Cragie, Stanislav Smyshlyaev and 482 Tibor Jager for many useful comments. Tibor Jager contributed the 483 optimization technique and discussion the vulnerability issue when 484 the ephemeral secret v is not generated randomly. This work is 485 supported by the EPSRC First Grant (EP/J011541/1) and the ERC 486 Starting Grant (No. 306994). 488 9. References 490 9.1. Normative References 492 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 493 Requirement Levels", BCP 14, RFC 2119, 494 DOI 10.17487/RFC2119, March 1997, 495 . 497 [SEC1] "Standards for Efficient Cryptography. SEC 1: Elliptic 498 Curve Cryptography", SECG SEC1-v2, May 2004, 499 . 501 [ABM15] Abdalla, M., Benhamouda, F., and P. MacKenzie, "Security 502 of the J-PAKE Password-Authenticated Key Exchange 503 Protocol", IEEE Symposium on Security and Privacy, May 504 2015. 506 [AN95] Anderson, R. and R. Needham, "Robustness principles for 507 public key protocols", Proceedings of the 15th Annual 508 International Cryptology Conference on Advances in 509 Cryptology, 1995. 511 [FS86] Fiat, A. and A. Shamir, "How to Prove Yourself: Practical 512 Solutions to Identification and Signature Problems", 513 Proceedings of the 6th Annual International Cryptology 514 Conference on Advances in Cryptology, 1986. 516 [MOV96] Menezes, A., Oorschot, P., and S. Vanstone, "Handbook of 517 Applied Cryptography", 1996. 519 [Stinson06] 520 Stinson, D., "Cryptography: Theory and Practice (3rd 521 Edition)", CRC, 2006. 523 9.2. Informative References 525 [FIPS186-4] 526 "Federal Information Processing Standards Publication 527 186-4: Specifications for the Digital Signature Standard 528 (DSS)", July 2013, . 531 [HR08] Hao, F. and P. Ryan, "Password Authenticated Key Exchange 532 by Juggling", the 16th Workshop on Security Protocols, 533 May 2008. 535 [Hao10] Hao, F., "On Robust Key Agreement Based on Public Key 536 Authentication", the 14th International Conference on 537 Financial Cryptography and Data Security, February 2010. 539 9.3. URIs 541 [1] http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ 542 DSA2_All.pdf 544 Author's Address 546 Feng Hao (editor) 547 Newcastle University (UK) 548 Claremont Tower, School of Computing Science, Newcastle University 549 Newcastle Upon Tyne 550 United Kingdom 552 Phone: +44 (0)191-208-6384 553 EMail: feng.hao@ncl.ac.uk