Re: Last Call: <draft-igoe-secsh-x509v3-06.txt> (X.509v3 Certificates fo

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.
This format is the same as for ecdsa-sha2-* signatures in Section

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(_dot_)ext(_at_)gmail(_dot_)com
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363

_______________________________________________
Ietf mailing list
Ietf(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/ietf