|
Dear colleagues: Please find below my comments on IETF draft document draft-igoe-secsh-x509v3-06.txt, which is currently in Last Call. Best regards, Rene == [comments - descriptive] 1. Facilitating ECDSA verification speed-ups: I suggest a change in the method for generating ECDSA signatures that facilitates the optional use of alternative methods for verification of ECDSA signatures, either alone or when combined with the key computation step in a key agreement scheme. In the former case, speed-ups of the incremental cost of ECDSA signature verification are possible of roughly 1.4x when compared to the traditional method; in the latter case, the corresponding speed-up is roughly 2.3x both when using ECDH and ECMQV, as specified with SSH. Moreover, this also facilitates other acceleration techniques, such as batch verification in the context of certificate chains. The suggested change has no impact on standardized formats or security and can be carried out either "after the fact" (by any party) or as part of the signing process. Sole goal is that signers would facilitate verifiers to reap computational benefits, if they choose to implement those (after all, embracing speed-ups is optional). The change with generating ECDSA signatures is aimed at making the mapping r -> R, where R is the ephemeral public key of the signer, a 1-1 mapping (with traditional ECDSA, this is a 1-2 mapping, since both R and -R map to the same signature component r). This is realized, e.g., by changing the sign of signature component s if the point R has an odd valued y-coordinate (here, one uses that h(m)=s*k - d*r (mod n) = (-s)*(-k) - d* r (mod n)). This can be done as post-processing step by any party, without requiring access to the private key (simply recompute R':=(1/s)(eG + rQ), where e:=h(m) and flip the sign of signature component s if (R')y is odd) or by the signer, as part of the ECDSA signature generation procedure. The intention of this *tiny* change is to facilitate people who wish to exploit ECC speed-ups to always be able to do so, without being faced to ambiguity in the r --> R operation. For those who do not wish to implement this, they can of course just keep their verification code implementation. The speed-ups are always facilitated if ECDSA signature generation includes the statement: if Ry is odd, then (r,s):=(r,-s) fi. So, the change is a tiny one-line change :). My proposed edits only describe the above tiny mechanism for facilitating the speed-ups and do *not* describe the speed-ups themselves (after all, we target people who are okay to facilitate the speed-ups, but do not necessarily wish to use these themselves). In my mind, this little edit would present a nice opportunity to facilitate the realization of some recent ECC efficiency improvements in practice (as I also suggested during the saag meeting at IETF-78). The potential speed-ups to incremental ECDSA verification are huge, so I hope we can all work towards a world where these have the potential to actually be used. 2. Other comments: Section 4, 3rd last Para: It could make sense to implement the hash over a canonical representation of the byte string over the air. This allows, e.g., changing the representation of the ECC public key (compressed, uncompressed, etc.) to one's liking during transmission, without impacting the computation of the hash value and, thereby, the signature. Best regards, Rene == [suggested textual changes] Section 3.4:, l.. -1/-3: Original text: The
integers r and s are the output of the ECDSA algorithm. 3.1.2 of [RFC5656]. Suggested replacement text: (change indicated in yellow - in case email supports this) The integers r and s are the output of the ECDSA algorithm, subject to the following post-processing step:
When the ephemeral public key R:=(x1,y1):=kG that is generated during the ECDSA signature generation algorithm has an odd valued y-coordinate y1,the ECDSA signature component s SHALL be changed towards the integer –s (modulo n), where n is the prime order of the cyclic subgroup of the elliptic curve in question; it shall not be changed otherwise.
Note 1 (security) - This post-processing step does not affect the validity of the resulting ECDSA signature, since an ECDSA signature is valid irrespective the “sign” of signature component s.
Note 2 (compatibility) – This post-processing operation only depends on publicly available information and, since it does not require access to the private key, can be executed by any party, not just the signer. In particular, this step may be realized as a post-processing operation, without loss of security properties or deviation from standardized ECDSA signature formats. This allows putting already generated ECDSA certificates into the stipulated format after their original creation, without the need to rely on the party that originally generated the ECDSA signature (such as a Certificate Authority) and without changes to standardized ECDSA formats. Of course, this post-processing may be executed by the original signer as well, who may have the benefit of already having access to the ephemeral signing key R:=kG and, therefore, does not have to reconstruct this key from public information to perform this post-processing step – a simple bit comparison operation is all that is required. It is important to note that, functionally, these two approaches are the same (thus, not impacting “FIPS”-ability).
Note 3 (rationale) – In practice, the above-mentioned mechanism for the generation of ECDSA signatures allows a verifier to uniquely reconstruct the ephemeral key R:=kG that was purportedly used during ECDSA signature generation from the ECDSA signature component r alone, without requiring any side information. (With traditional ECDSA, this reconstruction is generally a 1-to-2 mapping, since both R and –R map to the same signature component r.) Unique recovery of the ephemeral key R from r allows a verifier to express the computationally most expensive step of ECDSA signature verification as that of solving an elliptic curve equation, thereby allowing the optional use of accelerated verification techniques for ECDSA signatures that exploit this fact, such as those described in [Eurocrypt1998, SAC2005, SAC2010].
The details of the acceleration techniques referenced above are explicitly outside scope of this document. However, the post-processing step for generation of ECDSA signatures described above and that facilitates the unique reconstruction of ephemeral key R from signature component r, as well as the procedure for reconstructing R from r are.
The post-processing operation above can be viewed as implementing the modified ECDSA signature scheme with output (R,s) as described in [SAC2005] or as implementing the ECES scheme with [McGrew-2009], so as to allow unique conversion between and ECDSA signature (r,s)and a modified signature (R,s) in practice.
Note 4 (reconstruction algorithm) - For completeness, we describe the procedure for reconstructing the ephemeral key R:=kG from signature component r here. We restrict ourselves to elliptic curves with prime order and that are defined over a prime field. The corresponding reconstruction procedure for curves defined over a binary extension field is similar. For these curves, by Hasse’s theorem, the order n of the curve is approximately equal to the order p of the underlying prime field. We distinguish two cases. If the elliptic curve has order n>p, the ephemeral key R:=(x1,y1) has as x-coordinate the value x1:=r and as y-coordinate the unique value y1 such (x1,y1) is a point on the curve and such that y1 is an even integer. If the elliptic curve has order n<p, the ephemeral key R:=(x1,y1) has as x-coordinate one of the values r or r+n and, for any such potential x-coordinate x1, as y-coordinate the unique value y1 such that (x1,y1) is a point on the curve and such that y1 is an even integer. While this procedure may in theory give rise to two (rather than one) reconstructed points R, in practice the x-coordinate x1:=r+n is virtually always outside the integer interval [0,p-1] and therefore does not need to be checked, thus resulting in at most one, rather than two, reconstructed values R (as was the case with n>p).
This signature format is the same as for ecdsa-sha2-* signatures in Section 3.1.2 of [RFC5656]. Section 7.2 (Informative references): Add the following informative references: [SAC2005]
A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, S.A. Vanstone, "Accelerated Verification
of ECDSA Signatures," in Proceedings of Selected Areas in Cryptography -
SAC2005, B. Preneel, S. Tavares, Eds., Lecture Notes in Computer Science, Vol.
3897, pp. 307-318, New York: Springer, 2006.
[Eurocrypt1998] M. Bellare, J.A. Garay, T. Rabin, ‘Fast Batch Verification for Modular Exponentiation and Digital Signatures,’ in Proceedings of Advances in Cryptology - EUROCRYPT'98, K. Nyberg, Ed., Lecture Notes in Computer Science, Vol. 1403, pp. 236-250, New York: Springer-Verlag, 1998. [McGrew] D. McGrew, "Fundamental Elliptic Curve Cryptography Algorithms," Internet Engineering Task Force, draft-mcgew-fundamentals-ecc-01, October 26, 2009.
[SAC2010] R. Struik, "Batch Verifications
Revisited – Combining Key Computations and Signature Verifications," to
appear in Proceedings of Selected Areas in Cryptography - SAC2010, Waterloo,
ON, August 12-13, 2010.
-- email: rstruik.ext@xxxxxxxxx Skype: rstruik cell: +1 (647) 867-5658 USA Google voice: +1 (415) 690-7363 |
_______________________________________________ Ietf mailing list Ietf@xxxxxxxx https://www.ietf.org/mailman/listinfo/ietf