< 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/