TOC 
Secure Shell Working GroupD. Stebila
Internet-DraftUniversity of Waterloo
Intended status: Standards TrackJ. Green
Expires: April 4, 2009October 01, 2008


Elliptic-Curve Algorithm Integration in the Secure Shell Transport Layer
draft-green-secsh-ecc-03

Status of this Memo

By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on April 4, 2009.

Abstract

This document describes algorithms based on Elliptic Curve Cryptography (ECC) for use within the Secure Shell (SSH) transport protocol. In particular, it specifies: Elliptic Curve Diffie-Hellman (ECDH) key agreement, Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement and Elliptic Curve Digital Signature Algorithm (ECDSA) for use in the SSH Transport Layer protocol.



Table of Contents

1.  Introduction
2.  Notation
3.  ECC Public Key Algorithm
    3.1.  Key Format
        3.1.1.  Signature Algorithm
        3.1.2.  Signature Encoding
4.  ECDH Key Exchange
5.  ECMQV Key Exchange
6.  IANA Considerations
    6.1.  Elliptic Curve Domain Parameter Identifiers
    6.2.  ECC Public Key Algorithm (ecdsa-sha2)
        6.2.1.  Elliptic Curve Digital Signature Algorithm
    6.3.  ECDH Key Exchange Method Names (ecdh-sha2-*)
    6.4.  ECMQV Key Exchange and Verification Method Name (ecmqv-sha2)
7.  Key Exchange Messages
    7.1.  ECDH Message Numbers
    7.2.  ECMQV Message Numbers
8.  Security Considerations
9.  Named Elliptic Curve Domain Parameters
    9.1.  Required and Recommended Curves
    9.2.  SEC Equivalent NIST Curves and Encoded OIDs
10.  References
    10.1.  Normative References
    10.2.  Informative References
Appendix A.  Acknowledgements
§  Authors' Addresses
§  Intellectual Property and Copyright Statements




 TOC 

1.  Introduction

Due to its inclusion in NSA's Suite B and its small key sizes elliptic curve cryptography (ECC) is becoming a widely utilized and attractive public-key cryptosystem.

In the interest of adding Suite B algorithms to SSH this document adds three ECC Suite B algorithms to the Secure Shell arsenal: Elliptic Curve Menezes-Qu-Vanstone (ECMQV), Elliptic Curve Diffie-Hellman (ECDH), and Elliptic Curve Digital Signature Algorithm (ECDSA), as well as utilizing the SHA2 family of secure hash algorithms.

Compared to cryptosystems such as RSA, DSA, and DH, ECC variations on these schemes offer equivalent security with smaller key sizes. This is illustrated in the following table, based on Section 5.6.1 of NIST 800-57 [NIST‑800‑57] (National Institute of Standards and Technology, “Recommendation for Key Management - Part 1: General (Revised),” March 2007.), which gives approximate comparable key sizes for symmetric- and asymmetric-key cryptosystems based on the best known algorithms for attacking them. L is field size and N is sub-field size.

SymmetricDiscrete Log (eg. DSA, DH)RSAECC
80 L = 1024 N = 160 1024 160-223
112 L = 2048 N = 256 2048 224-255
128 L = 3072 N = 256 3072 256-383
192 L = 7680 N = 384 7680 384-511
256 L = 15360 N = 512 15360 512+

Implementation of this specification requires familiarity with both SSH [RFC4251] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Protocol Architecture,” January 2006.) [RFC4253] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” January 2006.) [RFC4250] (Lehtinen, S. and C. Lonvick, “The Secure Shell (SSH) Protocol Assigned Numbers,” January 2006.) and ECC [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.) [IEEE1363] (Institute of Electrical and Electronics Engineers, “Standard Specifications for Public Key Cryptography,” 2000.) [ANSI‑X9.63] (American National Standards Institute, “Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography,” January 1999.).

This document is concerned with SSH implementation details; specification of the underlying cryptographic algorithms is left to other standards documents.

Comments on this draft are solicited and should be addressed to Douglas Stebila <douglas@stebila.ca>.



 TOC 

2.  Notation

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

The data types boolean, uint32, uint64, string, and mpint are to be interpreted in this document as described in [RFC4251] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Protocol Architecture,” January 2006.).

The size of a set of elliptic curve domain parameters on a prime curve is defined as the number of bits in the binary representation of the field order, commonly denoted p. Size on a characteristic-2 curve is defined as the number of bits in the binary representation of the field, commonly denoted m. A set of elliptic curve domain parameters defines a group of order n generated by a base point P.



 TOC 

3.  ECC Public Key Algorithm

The ECC public key algorithm is defined by its key format, corresponding signature algorithm ECDSA, signature encoding and algorithm identifiers.

This section defines the "ecdsa-sha2" public key format and corresponding signature format.



 TOC 

3.1.  Key Format

The "ecdsa-sha2" key format has the following encoding:

   string    "ecdsa-sha2"
   byte[n]   ecc_key_blob

The ecc_key_blob value has the following specific encoding:

   string     [identifier]
   string     Q

The string [identifier] is the identifier of the elliptic curve domain parameters. The format of this string is specified in Section 6.1 (Elliptic Curve Domain Parameter Identifiers). Information on the required and recommended sets of elliptic curve domain parameters for use with this algorithm can be found in Section 9 (Named Elliptic Curve Domain Parameters).

Q is the public key encoded from an elliptic curve point into an octet string as defined in Section 2.3.3 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.).

The algorithm for ECC key generation can be found in Section 3.2 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). Given some elliptic curve domain parameters, an ECC key pair can be generated containing a private key, an integer d, and a public key, an elliptic curve point Q.



 TOC 

3.1.1.  Signature Algorithm

Signing and verifying is done using the Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is specified in [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.) and in [ANSI‑X9.62] (American National Standards Institute, “Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” 1998.). The message hashing algorithm must be from the SHA2 family of hash functions [RFC4634] (Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” July 2006.) and is chosen according to the curve size as specified in Section 6.2.1 (Elliptic Curve Digital Signature Algorithm).



 TOC 

3.1.2.  Signature Encoding

Signatures are encoded as follows:

   string     "ecdsa-sha2"
   string     ecdsa_signature_blob

The ecdsa_signature_blob value has the following specific encoding:

   mpint      r
   mpint      s

The integers r and s are the output of the ECDSA algorithm.

The width of the integer fields is determined by the curve being used. Note that the integers r and s are integers modulo the order of the curve, which is may be larger than the size of the finite field. Thus, the integers r and s are encoding as octet strings each of length ciel(log[2](n)/8) using Section 2.3.7 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.), where n is the order of the elliptic curve group.



 TOC 

4.  ECDH Key Exchange

The Elliptic Curve Diffie-Hellman (ECDH) key exchange method generates a shared secret from an ephemeral elliptic curve local private key and remote public key. This key exchange method provides explicit server authentication as defined in [RFC4253] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” January 2006.) using a signature on the exchange hash.

The primitive used for shared key generation is ECDH with cofactor multiplication, the full specification of which can be found in Section 3.3.2 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). The algorithm for key pair generation can be found in Section 3.2 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.).

The family of key exchange method names defined for use with this key exchange can be found in Section 6.3 (ECDH Key Exchange Method Names (ecdh-sha2-*)). Algorithm negotiation chooses the public key algorithm to be used for signing and the method name of the key exchange. The method name of the key exchange chosen determines the elliptic curve domain parameters and hash function to be used in the remainder of this section.

Information on the required and recommended elliptic curve domain parameters for use with this method can be found in Section 9 (Named Elliptic Curve Domain Parameters).

All elliptic curve public keys MUST be validated after they are received. An example of a validation algorithm can be found in A.16.10 of [IEEE1363] (Institute of Electrical and Electronics Engineers, “Standard Specifications for Public Key Cryptography,” 2000.). If a key fails validation the key exchange MUST fail.

The elliptic curve public keys (points) that must be transmitted are encoded into octet strings before they are transmitted. The transformation between elliptic curve points and octet strings is specified in Section 2.3 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). The output of shared key generation is a field element xp. The ssh framework requires that the shared key be an integer. The conversion between a field element and an integer is specified in Section 2.3.9 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.).

Specification of the message numbers SSH_MSG_KEX_ECDH_INIT and SSH_MSG_KEX_ECDH_REPLY are found in Section 7 (Key Exchange Messages).

The following is an overview of the key exchange process:

   Client                                                Server
   ------                                                ------
   Generate ephemeral key pair.
   SSH_MSG_KEX_ECDH_INIT  -------------->

                                   Verify received key is valid.
                                    Generate ephemeral key pair.
                                          Compute shared secret.
                                Generate and sign exchange hash.
                          <------------- SSH_MSG_KEX_ECDH_REPLY

   Verify received key is valid.
   *Verify host key belongs to server.
   Compute shared secret.
   Generate exchange hash.
   Verify server's signature.

*It is recommended that the client verify that the host key sent is the server's host key (Using certificates or a local database). The client is allowed to accept the host key without verification, but doing so will render the protocol insecure against active attacks.

This is implemented using the following messages.

The client sends:

   byte       SSH_MSG_KEX_ECDH_INIT
   string     client's ephemeral public key octet string

The server responds with:

   byte       SSH_MSG_KEX_ECDH_REPLY
   string     server's public host key and/or certificates
   string     server's ephemeral public key octet string
   string     the signature on the exchange hash

The exchange hash H is computed as the hash of the concatenation of the following.

   string     client's version string (CR and NL excluded)
   string     server's version string (CR and NL excluded)
   string     payload of the client's SSH_MSG_KEXINIT
   string     payload of the server's SSH_MSG_KEXINIT
   string     server's public host key
   string     client's ephemeral public key octet string
   string     server's ephemeral public key octet string
   mpint      shared secret


 TOC 

5.  ECMQV Key Exchange

The Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key exchange algorithm generates a shared secret from two local elliptic curve key pairs and two remote public keys. This key exchange method provides implicit server authentication as defined in [RFC4253] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” January 2006.).

The key exchange method name defined for use with this key exchange is "ecmqv-sha2". This method name gives a hashing algorithm that is to be used for the HMAC below. Future RFCs may define new method names specifying new hash algorithms for use with ECMQV. More information about the method name and HMAC can be found in Section 6.4 (ECMQV Key Exchange and Verification Method Name (ecmqv-sha2)).

In general the ECMQV key exchange is performed using the ephemeral and long term key pair of both the client and server, a total of 4 keys. Within the framework of SSH the client does not have a long term key pair that needs to be authenticated. Therefore we generate an ephemeral key and use that as both the clients keys. This is more efficient than using two different ephemeral keys and does not adversely affect security (it is analogous to the one-pass protocol in Section 6.1 of [LMQSV98] (Law, L., Menezes, A., Qu, M., Solinas, J., and S. Vanstone, “An Efficient Protocol for Authenticated Key Agreement,” August 1998.)).

A full description of the ECMQV primitive can be found in Section 3.4 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). The algorithm for key pair generation can be found in Section 3.2 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.).

During algorithm negotiation with the SSH_MSG_KEXINIT messages the ECMQV key exchange method can only be chosen if a Public Key Algorithm supporting ECC host keys can also be chosen. This is due to the use of implicit server authentication in this key exchange method. This case is handled the same way that key exchange methods requiring encryption/signature capable public key algorithms are handled in Section 7.1 of [RFC4253] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” January 2006.). If ECMQV key exchange is chosen then the Public Key Algorithm supporting ECC host keys MUST also be chosen.

ECMQV requires that all the keys used to generate a shared secret are generated over the same elliptic curve domain parameters. Since the host key is used in the generation of the shared secret, allowing for implicit server authentication, the domain parameters associated with the host key are used throughout this section.

All elliptic curve public keys MUST be validated after they are received. An example of a validation algorithm can be found in A.16.10 of [IEEE1363] (Institute of Electrical and Electronics Engineers, “Standard Specifications for Public Key Cryptography,” 2000.). If a key fails validation the key exchange MUST fail.

The elliptic curve public keys (points) that must be transmitted are encoded into octet strings before they are transmitted. The transformation between elliptic curve points and octet strings is specified in Section 2.3 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). The output of shared key generation is a field element xp. The ssh framework requires that the shared key be an integer. The conversion between a field element and an integer is specified in Section 2.3.9 of [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.).

The following is an overview of the key exchange process:

   Client                                                Server
   ------                                                ------
   Generate ephemeral key pair.
   SSH_MSG_KEX_ECMQV_INIT ------------->

                                   Verify received key is valid.
                                    Generate ephemeral key pair.
                                          Compute shared secret.
                             Generate exchange hash and compute
                           HMAC over it using the shared secret.
                          <------------- SSH_MSG_KEX_ECDH_REPLY

   Verify received keys are valid.
   *Verify host key belongs to server.
   Compute shared secret.
   Verify HMAC.

*It is recommended that the client verify that the host key sent is the server's host key (Using certificates or a local database). The client is allowed to accept the host key without verification, but doing so will render the protocol insecure against active attacks.

The specification of the message numbers SSH_MSG_ECMQV_INIT and SSH_MSG_ECMQV_REPLY can be found in Section 7 (Key Exchange Messages).

This key exchange algorithm is implemented with the following messages.

The client sends:

   byte       SSH_MSG_ECMQV_INIT
   string     client's ephemeral public key octet string

The server sends:

   byte       SSH_MSG_ECMQV_REPLY
   string     server's public host key octet string
   string     server's ephemeral public key octet string
   string     HMAC tag computed on H using the shared secret

The hash H is formed by applying the algorithm HASH on a concatenation of the following:

   string     client's version string (CR and NL excluded)
   string     server's version string (CR and NL excluded)
   string     payload of the client's SSH_MSG_KEXINIT
   string     payload of the server's SSH_MSG_KEXINIT
   string     client's ephemeral public key octet
   string     server's public host key octet
   string     server's ephemeral public key octet
   mpint      shared secret


 TOC 

6.  IANA Considerations

This document defines a new family of key exchange method names, a new key exchange method name, and a new public key algorithm name in the SSH name registry. These additions to the SSH name space will have to be approved the IANA.



 TOC 

6.1.  Elliptic Curve Domain Parameter Identifiers

This section specifies identifiers encoding named elliptic curve domain parameters. These identifiers are used in this document to identify the curve used in the ECC public key format, the ECDSA signature blob, and the ECDH method name.

An elliptic curve domain parameter identifier is the Base64 encoding of the MD5 hash [RFC1321] (Rivest, R., “The MD5 Message-Digest Algorithm,” April 1992.) of the ASN.1 Distinguished Encoding Rules (DER) encoding [ASN1] (International Telecommunications Union, “Abstract Syntax Notation One (ASN.1): Specification of basic notation,” July 2002.) of the ASN.1 Object Identifier (OID) of the named curve domain parameters that are associated with the server's ECC host keys. Every identifier is precisely 24 characters in length. Base64 encoding is described in Section 6.8 of [RFC2045] (Freed, N. and N. Borenstein, “Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies,” November 1996.). A list of the required and recommended curves, their OIDs, and the encoding of their identifiers can be found in Section 9 (Named Elliptic Curve Domain Parameters).

For example: the identifier for the sect163k1 elliptic curve domain parameters would be "4MHB+NBt3AlaSRQ7MnB4cg==".



 TOC 

6.2.  ECC Public Key Algorithm (ecdsa-sha2)

The ECC Public Key Algorithm is specified by the public key format identifier "ecdsa-sha2".



 TOC 

6.2.1.  Elliptic Curve Digital Signature Algorithm

The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified for use with the ECC Public Key Algorithm.

The hashing algorithm defined by this family of method names is the SHA2 family of hashing algorithms [RFC4634] (Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” July 2006.). The algorithm from the SHA2 family that will be used is chosen based on the size of the named curve specified in the public key:

Curve SizeHash Algorithm
b <= 256 SHA-256
256 < b <= 384 SHA-384
384 < b SHA-512



 TOC 

6.3.  ECDH Key Exchange Method Names (ecdh-sha2-*)

The Elliptic Curve Diffie-Hellman key exchange is defined by a family of method names. Each method name is the concatenation of the string "ecdh-sha2" with the elliptic curve domain parameter identifier as defined in Section Section 6.1 (Elliptic Curve Domain Parameter Identifiers). A list of the required and recommended curves and their OIDs can be found in Section 9 (Named Elliptic Curve Domain Parameters).

For example: The method name for ECDH key exchange with ephemeral keys generated on the sect409k1 curve would be "ecdh-sha2-m/FtSAmrV4j/Wy6RVUaK7A==".

The hashing algorithm defined by this family of method names is the SHA2 family of hashing algorithms [RFC4634] (Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” July 2006.). The hashing algorithm is defined in the method name to allow room for other algorithms to be defined in future documents. The algorithm from the SHA2 family that will be used is chosen based on the size of the named curve specified in the method name according to the table in Section Section 6.2.1 (Elliptic Curve Digital Signature Algorithm).

The concatenation of any so encoded ASN.1 OID specifying a set of elliptic curve domain parameters with "ecdh-sha2-" is implicitly registered under this specification.



 TOC 

6.4.  ECMQV Key Exchange and Verification Method Name (ecmqv-sha2)

The Elliptic Curve Menezes-Qu-Vanstone key exchange is defined by the method name "ecmqv-sha2". Unlike the ECDH key exchange method, ECMQV relies on a public key algorithm that uses ECC keys: it does not need a family of method names because the curve information can be gained from the public key algorithm.

The hashing and message authentication code algorithms are defined by the method name to allow room for other algorithms to be defined for use with ECMQV in future documents.

The hashing algorithm defined by this method name is the SHA2 family of hashing algorithms [RFC4634] (Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” July 2006.). The algorithm from the SHA2 family that will be used is chosen based on the size of the named curve specified for use with ECMQV by the chosen public key algorithm according to the table in Section Section 6.2.1 (Elliptic Curve Digital Signature Algorithm).

The keyed-hash message authentication code that is used to identify the server and verify communications is based on the hash chosen above. The information on implementing the HMAC based on the chosen hash algorithm can be found in [RFC4634] (Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” July 2006.).



 TOC 

7.  Key Exchange Messages

The message numbers 30-49 are key exchange-specific and in a private namespace defined in [RFC4250] (Lehtinen, S. and C. Lonvick, “The Secure Shell (SSH) Protocol Assigned Numbers,” January 2006.) that may be redefined by any key exchange method [RFC4253] (Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” January 2006.) without being granted IANA permission.

The following message numbers have been defined in this document:



 TOC 

7.1.  ECDH Message Numbers

   #define SSH_MSG_KEX_ECDH_INIT                30
   #define SSH_MSG_KEX_ECDH_REPLY               31


 TOC 

7.2.  ECMQV Message Numbers

   #define SSH_MSG_ECMQV_INIT                   30
   #define SSH_MSG_ECMQV_REPLY                  31


 TOC 

8.  Security Considerations

The Elliptic Curve Diffie-Hellman key agreement algorithm is defined in [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.), [IEEE1363] (Institute of Electrical and Electronics Engineers, “Standard Specifications for Public Key Cryptography,” 2000.) and [ANSI‑X9.63] (American National Standards Institute, “Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography,” January 1999.). The appropriate security considerations of those documents apply.

The Elliptic Curve Menezes-Qu-Vanstone key agreement algorithm is defined in [SEC1] (Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” September 2000.). The security considerations raised in that document also apply. A more detailed discussion of security considerations can be found in Section 4.7 of the Guide to Elliptic Curve Cryptography [HMV04] (Hankerson, D., Menezes, A., and S. Vanstone, “Guide to Elliptic Curve Cryptography,” 2004.).

The server's host key is used in the ECMQV key exchange algorithm. This means that the strength of the server's ECC host key determines the strength of the ECMQV key exchange algorithm. This should be taken into consideration when generating ECC keys for a server.

The methods defined in Section Section 6 (IANA Considerations) rely on the SHA2 family of hashing functions as defined in [FIPS‑180‑2] (National Institute of Standards and Technology, “Secure Hash Standard,” August 2002.). The appropriate security considerations of that document apply.

The hashing algorithms defined for use with ECDH and ECMQV are defined by their method names so that if security problems are found with the SHA2 family of hashing algorithms or more secure hashing algorithms become the standard then future documents can extend this document to include new hashing algorithms by defining new method names.

Additionally a good general discussion of the security considerations that must be taken into account when creating an ECC implementation can be found in Section 5 of the Guide to Elliptic Curve Cryptography [HMV04] (Hankerson, D., Menezes, A., and S. Vanstone, “Guide to Elliptic Curve Cryptography,” 2004.).

Since ECDH and ECMQV allow for elliptic curves of arbitrary sizes and thus arbitrary security strength, it is important that the size of elliptic curve be chosen to match the security strength of other elements of the SSH handshake. In particular, host key sizes, hashing algorithms and bulk encryption algorithms must be chosen appropriately. Information regarding estimated equivalence of key sizes is available in [NIST‑800‑57] (National Institute of Standards and Technology, “Recommendation for Key Management - Part 1: General (Revised),” March 2007.). We note in particular that when ECDSA is used as the signature algorithm and ECDH is used as the key exchange method, if curves of different sizes are used, then it is possible that different hash functions from the SHA2 family could be used.



 TOC 

9.  Named Elliptic Curve Domain Parameters

Implementations may support any ASN.1 object identifier (OID) in the ASN.1 object tree that defines a set of elliptic curve domain parameters [ASN1] (International Telecommunications Union, “Abstract Syntax Notation One (ASN.1): Specification of basic notation,” July 2002.).



 TOC 

9.1.  Required and Recommended Curves

Every SSH ECC implementation MUST support the named curves below, these curves are defined in [SEC2] (Standards for Efficient Cryptography Group, “Recommended Elliptic Curve Domain Parameters,” September 2000.). These curves should always be enabled unless specifically disabled by local security policy.

It is RECOMMENDED that SSH ECC implementations also support the following curves.



 TOC 

9.2.  SEC Equivalent NIST Curves and Encoded OIDs

The following table lists common curves by their equivalent SEC and NIST names. The named NIST curves are specified in [NIST‑CURVES] (National Institute of Standards and Technology, “Recommended Elliptic Curves for Federal Government Use,” August 1999.).

SECNIST
sect163k1 nistk163
secp192r1 nistp192
secp224r1 nistp224
sect233k1 nistk233
sect233r1 nistb233
secp256r1 nistp256
sect283k1 nistk283
secp384r1 nistp384
sect409k1 nistk409
sect409r1 nistb409
secp521r1 nistp521
sect571k1 nistk571

The following table lists the above SEC curves, their OID, and the encoding of their OID as appropriate for the identifiers and method names defined in Section Section 6 (IANA Considerations). The encoding is the Base64 encoding of the MD5 hash [RFC1321] (Rivest, R., “The MD5 Message-Digest Algorithm,” April 1992.) of the ASN.1 Distinguished Encoding Rules (DER) encoding [ASN1] (International Telecommunications Union, “Abstract Syntax Notation One (ASN.1): Specification of basic notation,” July 2002.) of the ASN.1 Object Identifier (OID) of the named curve domain parameters that are associated with the ephemeral keys. Base64 encoding is described in Section 6.8 of [RFC2045] (Freed, N. and N. Borenstein, “Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies,” November 1996.).

SECOIDBase64(MD5(DER(OID)))
sect163k1 1.3.132.0.1 4MHB+NBt3AlaSRQ7MnB4cg==
secp192r1 1.2.840.10045.3.1.1 5pPrSUQtIaTjUSt5VZNBjg==
secp224r1 1.3.132.0.33 VqBg4QRPjxx1EXZdV0GdWQ==
sect233k1 1.3.132.0.26 zD/b3hu/71952ArpUG4OjQ==
sect233r1 1.3.132.0.27 qCbG5Cn/jjsZ7nBeR7EnOA==
secp256r1 1.2.840.10045.3.1.7 9UzNcgwTlEnSCECZa7V1mw==
sect283k1 1.3.132.0.16 wiRIU8TKjMZ418sMqlqtvQ==
secp384r1 1.3.132.0.34 qcFQaMAMGhTziMT0z+Tuzw==
sect409k1 1.3.132.0.36 m/FtSAmrV4j/Wy6RVUaK7A==
sect409r1 1.3.132.0.37 D3FefCjYoJ/kfXgAyLddYA==
secp521r1 1.3.132.0.35 h/SsxnLCtRBh7I9ATyeB3A==
sect571k1 1.3.132.0.38 mNVwCXAoS1HGmHpLvBC94w==

The following sequence of commands can be used on many Unix-type systems to generated the encoding of the OID as above. The command oid below is an OID converter such as [OID.C] (Gartner, M., “OID Converter,” 2006.).

   echo -n ${i} > tmp.oid
   echo -n 0000: > tmp.hex
   oid -i tmp.oid >> tmp.hex
   xxd -r tmp.hex tmp.der
   openssl md5 -binary < tmp.der > tmp.md5
   openssl base64 < tmp.md5 > tmp.b64
   cat tmp.b64


 TOC 

10.  References



 TOC 

10.1. Normative References

[ASN1] International Telecommunications Union, “Abstract Syntax Notation One (ASN.1): Specification of basic notation,”  X.680, July 2002.
[RFC1321] Rivest, R., “The MD5 Message-Digest Algorithm,” RFC 1321, April 1992 (TXT).
[RFC2045] Freed, N. and N. Borenstein, “Multipurpose Internet Mail Extensions (MIME) Part One: Format of Internet Message Bodies,” RFC 2045, November 1996 (TXT).
[RFC2119] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” BCP 14, RFC 2119, March 1997 (TXT, HTML, XML).
[RFC4250] Lehtinen, S. and C. Lonvick, “The Secure Shell (SSH) Protocol Assigned Numbers,” RFC 4250, January 2006 (TXT).
[RFC4251] Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Protocol Architecture,” RFC 4251, January 2006 (TXT).
[RFC4253] Ylonen, T. and C. Lonvick, “The Secure Shell (SSH) Transport Layer Protocol,” RFC 4253, January 2006 (TXT).
[RFC4634] Eastlake, D. and T. Hansen, “US Secure Hash Algorithms (SHA and HMAC-SHA),” RFC 4634, July 2006 (TXT).
[SEC1] Standards for Efficient Cryptography Group, “Elliptic Curve Cryptography,” SEC 1, September 2000 (PDF).
[SEC2] Standards for Efficient Cryptography Group, “Recommended Elliptic Curve Domain Parameters,” SEC 2, September 2000 (PDF).


 TOC 

10.2. Informative References

[ANSI-X9.62] American National Standards Institute, “Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” ANSI X9.62, 1998.
[ANSI-X9.63] American National Standards Institute, “Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography,” ANSI X9.63, January 1999.
[FIPS-180-2] National Institute of Standards and Technology, “Secure Hash Standard,” FIPS 180-2, August 2002.
[HMV04] Hankerson, D., Menezes, A., and S. Vanstone, “Guide to Elliptic Curve Cryptography,” 2004.

Springer, ISBN 038795273X

[IEEE1363] Institute of Electrical and Electronics Engineers, “Standard Specifications for Public Key Cryptography,” IEEE 1363, 2000.
[LMQSV98] Law, L., Menezes, A., Qu, M., Solinas, J., and S. Vanstone, “An Efficient Protocol for Authenticated Key Agreement,” University of Waterloo Technical Report CORR 98-05, August 1998 (PDF).
[NIST-800-57] National Institute of Standards and Technology, “Recommendation for Key Management - Part 1: General (Revised),” NIST Special Publication 800-57, March 2007.
[NIST-CURVES] National Institute of Standards and Technology, “Recommended Elliptic Curves for Federal Government Use,” August 1999.
[OID.C] Gartner, M., “OID Converter,” 2006.


 TOC 

Appendix A.  Acknowledgements

The authors acknowledge helpful comments from Alfred Hines, Russ Housley, Jeffrey Hutzelman, and Rob Lambert.



 TOC 

Authors' Addresses

  Douglas Stebila
  University of Waterloo
  Department of Combinatorics and Optimization
  Waterloo, Ontario N2L 3G1
  Canada
Email:  douglas@stebila.ca
  
  Jon Green


 TOC 

Full Copyright Statement

Intellectual Property