| < draft-irtf-cfrg-eddsa-07.txt | draft-irtf-cfrg-eddsa-08.txt > | |||
|---|---|---|---|---|
| Network Working Group S. Josefsson | Network Working Group S. Josefsson | |||
| Internet-Draft SJD AB | Internet-Draft SJD AB | |||
| Intended status: Informational I. Liusvaara | Intended status: Informational I. Liusvaara | |||
| Expires: February 19, 2017 Independent | Expires: February 20, 2017 Independent | |||
| August 18, 2016 | August 19, 2016 | |||
| Edwards-curve Digital Signature Algorithm (EdDSA) | Edwards-curve Digital Signature Algorithm (EdDSA) | |||
| draft-irtf-cfrg-eddsa-07 | draft-irtf-cfrg-eddsa-08 | |||
| Abstract | Abstract | |||
| The elliptic curve signature scheme Edwards-curve Digital Signature | The elliptic curve signature scheme Edwards-curve Digital Signature | |||
| Algorithm (EdDSA) is described. The algorithm is instantiated with | Algorithm (EdDSA) is described. The algorithm is instantiated with | |||
| recommended parameters for the edwards25519 and edwards448 curves. | recommended parameters for the edwards25519 and edwards448 curves. | |||
| An example implementation and test vectors are provided. | An example implementation and test vectors are provided. | |||
| Status of This Memo | Status of This Memo | |||
| skipping to change at page 1, line 34 ¶ | skipping to change at page 1, line 34 ¶ | |||
| Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||
| Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||
| working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||
| Drafts is at http://datatracker.ietf.org/drafts/current/. | Drafts is at http://datatracker.ietf.org/drafts/current/. | |||
| Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||
| and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||
| time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||
| material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||
| This Internet-Draft will expire on February 19, 2017. | This Internet-Draft will expire on February 20, 2017. | |||
| Copyright Notice | Copyright Notice | |||
| Copyright (c) 2016 IETF Trust and the persons identified as the | Copyright (c) 2016 IETF Trust and the persons identified as the | |||
| document authors. All rights reserved. | document authors. All rights reserved. | |||
| This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||
| Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||
| (http://trustee.ietf.org/license-info) in effect on the date of | (http://trustee.ietf.org/license-info) in effect on the date of | |||
| publication of this document. Please review these documents | publication of this document. Please review these documents | |||
| skipping to change at page 4, line 37 ¶ | skipping to change at page 4, line 37 ¶ | |||
| a >= b a is greater than or equal to b | a >= b a is greater than or equal to b | |||
| i+j sum of i and j | i+j sum of i and j | |||
| i*j multiplication of i and j | i*j multiplication of i and j | |||
| i-j subtraction of j from i | i-j subtraction of j from i | |||
| i/j division of i by j | i/j division of i by j | |||
| i x j cartesian product of i and j | i x j Cartesian product of i and j | |||
| (u,v) Elliptic curve point with x coordinate u and y coordinate v | (u,v) Elliptic curve point with x coordinate u and y coordinate v | |||
| SHAKE256(x, y) The y first octets of SHAKE256 [FIPS202] output for | SHAKE256(x, y) The y first octets of SHAKE256 [FIPS202] output for | |||
| input x | input x | |||
| OCTET(x) The octet with value x | OCTET(x) The octet with value x | |||
| OLEN(x) The number of octets in string x | OLEN(x) The number of octets in string x | |||
| skipping to change at page 10, line 41 ¶ | skipping to change at page 10, line 41 ¶ | |||
| x^2 = a (mod p). Then x is a square root. | x^2 = a (mod p). Then x is a square root. | |||
| x^2 = -a (mod p). Then 2^((p-1)/4) * x is a square root. | x^2 = -a (mod p). Then 2^((p-1)/4) * x is a square root. | |||
| a is not a square modulo p. | a is not a square modulo p. | |||
| 5.1.2. Encoding | 5.1.2. Encoding | |||
| All values are coded as octet strings, integers are coded using | All values are coded as octet strings, integers are coded using | |||
| little endian convention, i.e., a 32-octet string h h[0],...h[31] | little-endian convention, i.e., a 32-octet string h h[0],...h[31] | |||
| represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31]. | represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31]. | |||
| A curve point (x,y), with coordinates in the range 0 <= x,y < p, is | A curve point (x,y), with coordinates in the range 0 <= x,y < p, is | |||
| coded as follows. First, encode the y-coordinate as a little-endian | coded as follows. First, encode the y-coordinate as a little-endian | |||
| string of 32 octets. The most significant bit of the final octet is | string of 32 octets. The most significant bit of the final octet is | |||
| always zero. To form the encoding of the point, copy the least | always zero. To form the encoding of the point, copy the least | |||
| significant bit of the x-coordinate to the most significant bit of | significant bit of the x-coordinate to the most significant bit of | |||
| the final octet. | the final octet. | |||
| 5.1.3. Decoding | 5.1.3. Decoding | |||
| skipping to change at page 11, line 51 ¶ | skipping to change at page 11, line 51 ¶ | |||
| 5.1.4. Point addition | 5.1.4. Point addition | |||
| For point addition, the following method is recommended. A point | For point addition, the following method is recommended. A point | |||
| (x,y) is represented in extended homogeneous coordinates (X, Y, Z, | (x,y) is represented in extended homogeneous coordinates (X, Y, Z, | |||
| T), with x = X/Z, y = Y/Z, x * y = T/Z. | T), with x = X/Z, y = Y/Z, x * y = T/Z. | |||
| The neutral point is (0,1), or equivalently in extended homogeneous | The neutral point is (0,1), or equivalently in extended homogeneous | |||
| coordinates (0, Z, Z, 0) for any nonzero Z. | coordinates (0, Z, Z, 0) for any nonzero Z. | |||
| The following formulas for adding two points, (x3,y3) = | The following formulas for adding two points, (x3,y3) = | |||
| (x1,y1)+(x2,y2) on twisted edwards curves with a=-1, square a and | (x1,y1)+(x2,y2) on twisted Edwards curves with a=-1, square a and | |||
| non-square d are described in [Edwards-revisited], section 3.1, and | non-square d are described in [Edwards-revisited], section 3.1, and | |||
| in [EFD-TWISTED-ADD]. They are complete, i.e., they work for any | in [EFD-TWISTED-ADD]. They are complete, i.e., they work for any | |||
| pair of valid input points. | pair of valid input points. | |||
| A = (Y1-X1)*(Y2-X2) | A = (Y1-X1)*(Y2-X2) | |||
| B = (Y1+X1)*(Y2+X2) | B = (Y1+X1)*(Y2+X2) | |||
| C = T1*2*d*T2 | C = T1*2*d*T2 | |||
| D = Z1*2*Z2 | D = Z1*2*Z2 | |||
| E = B-A | E = B-A | |||
| F = D-C | F = D-C | |||
| G = D+C | G = D+C | |||
| H = B+A | H = B+A | |||
| X3 = E*F | X3 = E*F | |||
| Y3 = G*H | Y3 = G*H | |||
| T3 = E*H | T3 = E*H | |||
| Z3 = F*G | Z3 = F*G | |||
| For point doubling, (x3,y3) = (x1,y1)+(x1,y1), one could just | For point doubling, (x3,y3) = (x1,y1)+(x1,y1), one could just | |||
| substitute equal points in above (because of completeness, such | substitute equal points in above (because of completeness, such | |||
| substitution is valid), and observe that four multiplies turn into | substitution is valid), and observe that four multiplications turn | |||
| squarings. However, using the formulas described in | into squares. However, using the formulas described in | |||
| [Edwards-revisited], section 3.2, and in [EFD-TWISTED-DBL] saves a | [Edwards-revisited], section 3.2, and in [EFD-TWISTED-DBL] saves a | |||
| few smaller operations. | few smaller operations. | |||
| A = X1^2 | A = X1^2 | |||
| B = Y1^2 | B = Y1^2 | |||
| C = 2*Z1^2 | C = 2*Z1^2 | |||
| H = A+B | H = A+B | |||
| E = H-(X1+Y1)^2 | E = H-(X1+Y1)^2 | |||
| G = A-B | G = A-B | |||
| F = C+G | F = C+G | |||
| skipping to change at page 16, line 28 ¶ | skipping to change at page 16, line 28 ¶ | |||
| which would have been detected before, or a calculation error. | which would have been detected before, or a calculation error. | |||
| For point decoding or "decompression", square roots modulo p are | For point decoding or "decompression", square roots modulo p are | |||
| needed. They can be computed by first computing candidate root x = a | needed. They can be computed by first computing candidate root x = a | |||
| ^ (p+1)/4 (mod p) and then checking if x^2 = a. If it is, then x is | ^ (p+1)/4 (mod p) and then checking if x^2 = a. If it is, then x is | |||
| square root of a; if it isn't, then a does not have a square root. | square root of a; if it isn't, then a does not have a square root. | |||
| 5.2.2. Encoding | 5.2.2. Encoding | |||
| All values are coded as octet strings, and integers are coded using | All values are coded as octet strings, and integers are coded using | |||
| little endian convention, i.e., a 57-octet string h h[0],...h[56] | little-endian convention, i.e., a 57-octet string h h[0],...h[56] | |||
| represents the integer h[0] + 2^8 * h[1] + ... + 2^448 * h[56]. | represents the integer h[0] + 2^8 * h[1] + ... + 2^448 * h[56]. | |||
| A curve point (x,y), with coordinates in the range 0 <= x,y < p, is | A curve point (x,y), with coordinates in the range 0 <= x,y < p, is | |||
| coded as follows. First, encode the y-coordinate as a little-endian | coded as follows. First, encode the y-coordinate as a little-endian | |||
| string of 57 octets. The final octet is always zero. To form the | string of 57 octets. The final octet is always zero. To form the | |||
| encoding of the point, copy the least significant bit of the | encoding of the point, copy the least significant bit of the | |||
| x-coordinate to the most significant bit of the final octet. | x-coordinate to the most significant bit of the final octet. | |||
| 5.2.3. Decoding | 5.2.3. Decoding | |||
| skipping to change at page 17, line 27 ¶ | skipping to change at page 17, line 27 ¶ | |||
| 5.2.4. Point addition | 5.2.4. Point addition | |||
| For point addition, the following method is recommended. A point | For point addition, the following method is recommended. A point | |||
| (x,y) is represented in projective coordinates (X, Y, Z), with x = X/ | (x,y) is represented in projective coordinates (X, Y, Z), with x = X/ | |||
| Z, y = Y/Z. | Z, y = Y/Z. | |||
| The neutral point is (0,1), or equivalently in projective coordinates | The neutral point is (0,1), or equivalently in projective coordinates | |||
| (0, Z, Z) for any nonzero Z. | (0, Z, Z) for any nonzero Z. | |||
| The following formulas for adding two points, (x3,y3) = | The following formulas for adding two points, (x3,y3) = | |||
| (x1,y1)+(x2,y2) on untwisted edwards curve (i.e. a=1) with non-square | (x1,y1)+(x2,y2) on untwisted Edwards curve (i.e. a=1) with non-square | |||
| d are described in [Faster-ECC] section 4 and in [EFD-ADD]. They are | d are described in [Faster-ECC] section 4 and in [EFD-ADD]. They are | |||
| complete, i.e., they work for any pair of valid input points. | complete, i.e., they work for any pair of valid input points. | |||
| A = Z1*Z2 | A = Z1*Z2 | |||
| B = A^2 | B = A^2 | |||
| C = X1*X2 | C = X1*X2 | |||
| D = Y1*Y2 | D = Y1*Y2 | |||
| E = d*C*D | E = d*C*D | |||
| F = B-E | F = B-E | |||
| G = B+E | G = B+E | |||
| H = (X1+Y1)*(X2+Y2) | H = (X1+Y1)*(X2+Y2) | |||
| X3 = A*F*(H-C-D) | X3 = A*F*(H-C-D) | |||
| Y3 = A*G*(D-C) | Y3 = A*G*(D-C) | |||
| Z3 = F*G | Z3 = F*G | |||
| Again, similarly as with the other curve, doubling formulas can be | Again, similarly as with the other curve, doubling formulas can be | |||
| obtained by substituting equal points, turning four multiplies into | obtained by substituting equal points, turning four multiplications | |||
| squarings. However, this is not even nearly optimal, the following | into squares. However, this is not even nearly optimal, the | |||
| formulas described in [Faster-ECC] section 4 and in [EFD-DBL] save | following formulas described in [Faster-ECC] section 4 and in | |||
| multiple multiplications. | [EFD-DBL] save multiple multiplications. | |||
| B = (X1+Y1)^2 | B = (X1+Y1)^2 | |||
| C = X1^2 | C = X1^2 | |||
| D = Y1^2 | D = Y1^2 | |||
| E = C+D | E = C+D | |||
| H = Z1^2 | H = Z1^2 | |||
| J = E-2*H | J = E-2*H | |||
| X3 = (B-E)*J | X3 = (B-E)*J | |||
| Y3 = E*(C-D) | Y3 = E*(C-D) | |||
| Z3 = E*J | Z3 = E*J | |||
| skipping to change at page 41, line 11 ¶ | skipping to change at page 41, line 11 ¶ | |||
| Contexts can be used to separate uses of the protocol between | Contexts can be used to separate uses of the protocol between | |||
| different protocols (which is very hard to reliably do otherwise) and | different protocols (which is very hard to reliably do otherwise) and | |||
| between different uses within the same protocol. However, the | between different uses within the same protocol. However, the | |||
| following SHOULD be kept in mind when using this facility: | following SHOULD be kept in mind when using this facility: | |||
| The context SHOULD be a constant string specified by the protocol | The context SHOULD be a constant string specified by the protocol | |||
| using it. It SHOULD NOT incorporate variable elements from the | using it. It SHOULD NOT incorporate variable elements from the | |||
| message itself. | message itself. | |||
| Contexts SHOULD NOT be used oppurtunistically, as that kind of use | Contexts SHOULD NOT be used opportunistically, as that kind of use | |||
| is very error-prone. If contexts are used, one SHOULD require all | is very error-prone. If contexts are used, one SHOULD require all | |||
| signature schemes avaiable for use in that purpose support | signature schemes available for use in that purpose support | |||
| contexts. | contexts. | |||
| Contexts are an extra input, which percolates out of APIs, as | Contexts are an extra input, which percolates out of APIs, as | |||
| such, even if signature scheme supports contexts, those may not be | such, even if signature scheme supports contexts, those may not be | |||
| available for use. This problem is compounded by the fact that | available for use. This problem is compounded by the fact that | |||
| many times the application is not invoking the signing and | many times the application is not invoking the signing and | |||
| verification functions directly, but via some other protocol. | verification functions directly, but via some other protocol. | |||
| 10.4. Signature malleability | 10.4. Signature malleability | |||
| Some systems assume signatures are not malleabile: That is, given a | Some systems assume signatures are not malleable: That is, given a | |||
| valid signature for some message under some key, the attacker can't | valid signature for some message under some key, the attacker can't | |||
| produce another valid signature for the same message and key. | produce another valid signature for the same message and key. | |||
| Ed25519 and Ed448 signatures are not malleable due to the | Ed25519 and Ed448 signatures are not malleable due to the | |||
| verification check that decoded S is smaller than l. Without this | verification check that decoded S is smaller than l. Without this | |||
| check, one can add multiple of l into scalar part and still pass | check, one can add multiple of l into scalar part and still pass | |||
| signature verification, resulting in malleabile signatures. | signature verification, resulting in malleable signatures. | |||
| 10.5. Choice of signature primitive | 10.5. Choice of signature primitive | |||
| The Ed25519 and Ed25519ph have nominal strength of 128 bits, whereas | The Ed25519 and Ed25519ph have nominal strength of 128 bits, whereas | |||
| Ed448 and Ed448ph have strength of 224. While the lower strength is | Ed448 and Ed448ph have strength of 224. While the lower strength is | |||
| sufficient for the foreseeable future, the higher level brings some | sufficient for the foreseeable future, the higher level brings some | |||
| defense against possible future cryptographic advances. Both are | defense against possible future cryptographic advances. Both are | |||
| demolished by quantum computers just about the same. | demolished by quantum computers just about the same. | |||
| The Ed25519ph and Ed448ph variants are prehashed. This is mainly | The Ed25519ph and Ed448ph variants are prehashed. This is mainly | |||
| useful for interoperation with legacy APIs, since in most of the | useful for inter-operation with legacy APIs, since in most of the | |||
| cases, either the amount of data signed is not large, or the protocol | cases, either the amount of data signed is not large, or the protocol | |||
| is in position to do digesting in ways better than just prehashing | is in position to do digesting in ways better than just prehashing | |||
| (e.g. tree hashing or splitting the data). The prehashing also | (e.g. tree hashing or splitting the data). The prehashing also | |||
| makes the functions greatly more vulnerable to weaknesses in hash | makes the functions greatly more vulnerable to weaknesses in hash | |||
| functions used. These variants SHOULD NOT be used. | functions used. These variants SHOULD NOT be used. | |||
| Ed25519ctx and Ed448 have contexts. However, this is balanced by the | Ed25519ctx and Ed448 have contexts. However, this is balanced by the | |||
| problems noted in section about contexts. | problems noted in section about contexts. | |||
| On implementation front, Ed25519 is widely implemented, and has many | On implementation front, Ed25519 is widely implemented, and has many | |||
| skipping to change at page 42, line 51 ¶ | skipping to change at page 42, line 51 ¶ | |||
| Finalize) verification interface is prone to misuse | Finalize) verification interface is prone to misuse | |||
| It is a bad idea to modify Ed25519 or Ed448 signing to be able to | It is a bad idea to modify Ed25519 or Ed448 signing to be able to | |||
| create valid Ed25519/Ed448 signatures using IUF interface with only | create valid Ed25519/Ed448 signatures using IUF interface with only | |||
| constant buffering. Pretty much any error in such would cause | constant buffering. Pretty much any error in such would cause | |||
| catastrophic security failure. | catastrophic security failure. | |||
| 10.8. Multiplication by cofactor in verification | 10.8. Multiplication by cofactor in verification | |||
| The given verification formulas for both Ed25519 and Ed448 multiply | The given verification formulas for both Ed25519 and Ed448 multiply | |||
| points by the cofactor. While this is not strictly necressary for | points by the cofactor. While this is not strictly necessary for | |||
| security (in fact, any signature that meets the non-multiplied | security (in fact, any signature that meets the non-multiplied | |||
| equation will satisfy the multiplied one), in some applications it is | equation will satisfy the multiplied one), in some applications it is | |||
| undesirable for implementations to disagree about exact set of valid | undesirable for implementations to disagree about exact set of valid | |||
| signatures. Such disagreements could open up e.g. fingerprinting | signatures. Such disagreements could open up e.g. fingerprinting | |||
| attacks. | attacks. | |||
| 10.9. Use of SHAKE256 as hash function | 10.9. Use of SHAKE256 as hash function | |||
| Ed448 uses SHAKE256 as hash function, even if SHAKE256 is | Ed448 uses SHAKE256 as hash function, even if SHAKE256 is | |||
| specifically defined not to be a hash function. | specifically defined not to be a hash function. | |||
| The first potentially troublesome property is that shorter outputs | The first potentially troublesome property is that shorter outputs | |||
| are prefixes of longer ones. This is acceptable because output | are prefixes of longer ones. This is acceptable because output | |||
| lengths are fixed. | lengths are fixed. | |||
| The second potentially torublesome property is failing to meet | The second potentially troublesome property is failing to meet | |||
| standard hash security notions (especially with preimages). However, | standard hash security notions (especially with preimages). However, | |||
| the estimated 256-bit security level against collisions and preimages | the estimated 256-bit security level against collisions and preimages | |||
| is sufficient to pair with 224-bit level elliptic curve. | is sufficient to pair with 224-bit level elliptic curve. | |||
| 11. References | 11. References | |||
| 11.1. Normative References | 11.1. Normative References | |||
| [RFC4634] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms | [RFC4634] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms | |||
| (SHA and HMAC-SHA)", RFC 4634, DOI 10.17487/RFC4634, July | (SHA and HMAC-SHA)", RFC 4634, DOI 10.17487/RFC4634, July | |||
| End of changes. 17 change blocks. | ||||
| 22 lines changed or deleted | 22 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||