Composite ML-DSA Signatures for SSH
draft-sun-ssh-composite-sigs-01

sshm                                                              S. Sun
Internet-Draft                                                 L. Prabel
Intended status: Standards Track                                  Huawei
Expires: 5 January 2026                                      4 July 2025

                  Composite ML-DSA Signatures for SSH
                    draft-sun-ssh-composite-sigs-01

Abstract

   This document describes the use of PQ/T composite signatures for the
   Secure Shell (SSH) protocol.  The composite signatures described
   combine ML-DSA as the post-quantum part and the elliptic curve
   signature schemes ECDSA, Ed25519 and Ed448 as the traditional part.

About This Document

   This note is to be removed before publishing as an RFC.

   The latest revision of this draft can be found at
   https://example.com/LATEST.  Status information for this document may
   be found at https://datatracker.ietf.org/doc/draft-sun-ssh-composite-
   sigs/.

   Discussion of this document takes place on the Secure Shell
   Maintenance (sshm) Working Group mailing list (mailto:ssh@ietf.org),
   which is archived at https://mailarchive.ietf.org/arch/browse/ssh/.
   Subscribe at https://www.ietf.org/mailman/listinfo/ssh/.

   Source for this draft and an issue tracker can be found at
   https://github.com/USER/REPO.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   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."

Sun & Prabel             Expires 5 January 2026                 [Page 1]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   This Internet-Draft will expire on 5 January 2026.

Copyright Notice

   Copyright (c) 2025 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   3
   3.  Composite Algorithms  . . . . . . . . . . . . . . . . . . . .   3
     3.1.  Composite Key Generation  . . . . . . . . . . . . . . . .   3
     3.2.  Composite Sign  . . . . . . . . . . . . . . . . . . . . .   4
     3.3.  Composite Verify  . . . . . . . . . . . . . . . . . . . .   5
   4.  Public Key Algorithm  . . . . . . . . . . . . . . . . . . . .   5
   5.  Public Key Format . . . . . . . . . . . . . . . . . . . . . .   7
   6.  Signature Format  . . . . . . . . . . . . . . . . . . . . . .   8
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  10
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  11
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  11
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  12
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  12
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  12

1.  Introduction

   The development of quantum computers has raised concern towards
   traditional asymmetric cryptographic algorithms.  A Cryptographically
   Relevant Quantum Computer (CRQC) will break RSA and elliptic curve
   signature schemes.  There is a need to migrate to quantum-resistant
   signature schemes.

   Recently, NIST publised the ML-DSA [FIPS204] algorithm, which is a
   post-quantum signature scheme.  However, when using relatively new
   cryptographic schemes, the lack of maturing time makes people worry.
   Many hybrid solutions are thus proposed, which combine a traditional
   algorithm with a post-quantum algorithm.

Sun & Prabel             Expires 5 January 2026                 [Page 2]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   [FIPS204] defines both pure ML-DSA and pre-hash ML-DSA.  This
   document only uses pure ML-DSA.

   This document describes how to combine ML-DSA with the elliptic curve
   signature schemes ECDSA, Ed25519 and Ed448 for authentication in the
   SSH [RFC4251] protocol.

2.  Conventions and Definitions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

   This document is consistent with the terminology for hybrid
   signatures defined in [I-D.draft-ietf-pquip-pqt-hybrid-terminology].

   The key and signature formats follows the notation introduced in
   [RFC4251], Section 3, and the string data type format follows the
   notation from [RFC4251], Section 5.

3.  Composite Algorithms

   A composite algorithm has one post-quantum algorithm, and one
   traditional algorithm.

3.1.  Composite Key Generation

   Composite public and private keys are generated by calling the key
   generation functions of the two component algorithms and
   concatenating the keys in an order given by the registered composite
   algorithm.

   For the composite algorithms described in this document, the Key
   Generation process is as follows:

   (pk_1, sk_1) <- ML-DSA.KeyGen()
   (pk_2, sk_2) <- ECCSigAlg.KeyGen()

   Composite Public Key <- SerializePublicKey(pk_1, pk_2)
   Composite Private Key <- SerializePrivateKey(sk_1, sk_2)

   It makes use of the serialization routines from
   [I-D.draft-ietf-lamps-pq-composite-sigs] to obtain the byte string
   encodings of the composite public and private keys.

Sun & Prabel             Expires 5 January 2026                 [Page 3]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   ECCSigAlg is an elliptic curve signature scheme, i.e., ECDSA, Ed25519
   or Ed448.

3.2.  Composite Sign

   A composite signature's value MUST include two signature components
   and MUST be in the same order as the components from the
   corresponding signing key.

   For the composite algorithms described in this document, the
   signature process of a message M follows Section 4.2.1 of
   [I-D.draft-ietf-lamps-pq-composite-sigs], with an empty application
   context string:

   M' <- Prefix || Domain || 0x00 || r || PH(M)

   sig_1 <- ML-DSA.Sign(sk_1, M', ctx=Domain)
   sig_2 <- ECCSigAlgo.Sign(sk_2, M')

   Composite Signature <- SerializeSignatureValue(r, sig_1, sig_2)

   It makes use of the serialization routines from
   [I-D.draft-ietf-lamps-pq-composite-sigs] to obtain the byte string
   encodings of the composite signature.

   A signature randomizer r is used to prevent specific attacks unique
   to composite signature schemes.  More details can be found in
   [I-D.draft-ietf-lamps-pq-composite-sigs].

   The prefix "Prefix" string is defined as in
   [I-D.draft-ietf-lamps-pq-composite-sigs] as the byte encoding of the
   string "CompositeAlgorithmSignatures2025", which in hex is
   436F6D706F73697465416C676F726974686D5369676E61747572657332303235.  It
   can be used by a traditional verifier to detect if the composite
   signature has been stripped apart.

   The domain separator "Domain" is defined in the same way as
   [I-D.draft-ietf-lamps-pq-composite-sigs] as the DER encoding of the
   OID of the specific composite algorithm.  The specific values can be
   found in Table 1.

Sun & Prabel             Expires 5 January 2026                 [Page 4]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

      +=======================+====================================+
      | Key Format identifier | Domain Separator (in Hex encoding) |
      +=======================+====================================+
      | ssh-mldsa44-es256     | 060B6086480186FA6B50090103         |
      +-----------------------+------------------------------------+
      | ssh-mldsa65-es256     | 060B6086480186FA6B50090108         |
      +-----------------------+------------------------------------+
      | ssh-mldsa87-es384     | 060B6086480186FA6B5009010C         |
      +-----------------------+------------------------------------+
      | ssh-mldsa44-ed25519   | 060B6086480186FA6B50090102         |
      +-----------------------+------------------------------------+
      | ssh-mldsa65-ed25519   | 060B6086480186FA6B5009010B         |
      +-----------------------+------------------------------------+
      | ssh-mldsa87-ed448     | 060B6086480186FA6B5009010E         |
      +-----------------------+------------------------------------+

                   Table 1: Composite Domain Separators

3.3.  Composite Verify

   The Verify algorithm MUST validate a signature only if all component
   signatures are successfully validated.

   (pk_1, pk_2) <- DeserializePublicKey(pk)
   (r, sig_1, sig_2) <- DeserializeSignatureValue(sig)

   M' <- Prefix || Domain || 0x00 || r || PH(M)

   if not ML-DSA.Verify(pk_1, M', ctx=Domain)
       output "Invalid signature"
   if not ECCSigAlgo.Verify(pk_2, M')
       output "Invalid signature"
   if all succeeded, then
       output "Valid signature"

   It makes use of the serialization routines from
   [I-D.draft-ietf-lamps-pq-composite-sigs] to obtain the component
   public keys, the randomizer r, and the component signatures.

4.  Public Key Algorithm

   This section gives the concrete composite signature algorithms and
   their component algorithms.  Their usage within SSH follows
   Section 6.6 of [RFC4253].

   The following table defines a list of algorithms associated with
   specific PQ/T combinations.

Sun & Prabel             Expires 5 January 2026                 [Page 5]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   +=================+===========+===========+========+================+
   | Key Format      | First     | Second    | Pre-   | Description    |
   | Identifier      | Algorithm | Algorithm | Hash   |                |
   +=================+===========+===========+========+================+
   | ssh-            | ML-DSA-44 | ecdsa-    | id-    | Composite      |
   | mldsa44-es256   |           | with-     | sha256 | Signature      |
   |                 |           | SHA256    |        | with ML-       |
   |                 |           | with      |        | DSA-44 and     |
   |                 |           | secp256r1 |        | ECDSA using    |
   |                 |           |           |        | P-256 curve    |
   |                 |           |           |        | and SHA-256    |
   +-----------------+-----------+-----------+--------+----------------+
   | ssh-            | ML-DSA-65 | ecdsa-    | id-    | Composite      |
   | mldsa65-es256   |           | with-     | sha512 | Signature      |
   |                 |           | SHA256    |        | with ML-       |
   |                 |           | with      |        | DSA-65 and     |
   |                 |           | secp256r1 |        | ECDSA using    |
   |                 |           |           |        | P-256 curve    |
   |                 |           |           |        | and SHA-256    |
   +-----------------+-----------+-----------+--------+----------------+
   | ssh-            | ML-DSA-87 | ecdsa-    | id-    | Composite      |
   | mldsa87-es384   |           | with-     | sha512 | Signature      |
   |                 |           | SHA384    |        | with ML-       |
   |                 |           | with      |        | DSA-87 and     |
   |                 |           | secp384r1 |        | ECDSA using    |
   |                 |           |           |        | P-384 curve    |
   |                 |           |           |        | and SHA-384    |
   +-----------------+-----------+-----------+--------+----------------+
   | ssh-            | ML-DSA-44 | Ed25519   | id-    | Composite      |
   | mldsa44-ed25519 |           |           | sha512 | Signature      |
   |                 |           |           |        | with ML-       |
   |                 |           |           |        | DSA-44 and     |
   |                 |           |           |        | Ed25519 and    |
   |                 |           |           |        | SHA-512        |
   +-----------------+-----------+-----------+--------+----------------+
   | ssh-            | ML-DSA-65 | Ed25519   | id-    | Composite      |
   | mldsa65-ed25519 |           |           | sha512 | Signature      |
   |                 |           |           |        | with ML-       |
   |                 |           |           |        | DSA-65 and     |
   |                 |           |           |        | Ed25519 and    |
   |                 |           |           |        | SHA-512        |
   +-----------------+-----------+-----------+--------+----------------+
   | ssh-            | ML-DSA-87 | Ed448     | id-    | Composite      |
   | mldsa87-ed448   |           |           | sha512 | Signature      |
   |                 |           |           |        | with ML-       |
   |                 |           |           |        | DSA-87 and     |
   |                 |           |           |        | Ed448 and      |
   |                 |           |           |        | SHA-512        |

Sun & Prabel             Expires 5 January 2026                 [Page 6]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   +-----------------+-----------+-----------+--------+----------------+

           Table 2: Composite ML-DSA Signature Algorithms for SSH

5.  Public Key Format

   The key format for all parameter sets defined in this document
   follows the encoding pattern from [RFC4253], Section 6.6.

   *string* identifier

   *string* key

   The 'identifier' is the key format identifier given in Table 2.

   The 'key' is the composite public key generated as defined in
   Section 3.1.  It is the concatenation of the public keys of the
   component schemes.

   For ML-DSA, the public keys are defined in [FIPS204].

   For ECDSA with curves secp256r1 or secp384r1, the public keys are
   defined in [RFC5656], Section 3.1.  The public key is encoded from an
   elliptic curve point into an octet string as defined in Section 2.3.3
   of [SEC1]; point compression MAY be used.

   For Ed25519 and Ed448, the public keys are defined in [RFC8709],
   Section 6.

   The "ssh-mldsa44-es256" key format has the following encoding:

   *string* ssh-mldsa44-es256

   *string* key

   Here, 'key' is the concatenation of the 1312-octet ML-DSA-44 public
   key and the ECDSA public key using the secp256r1 curve.

   The "ssh-mldsa65-es256" key format has the following encoding:

   *string* ssh-mldsa65-es256

   *string* key

   Here, 'key' is the concatenation of the 1952-octet ML-DSA-65 public
   key and the ECDSA public key using the secp256r1 curve.

   The "ssh-mldsa87-es384" key format has the following encoding:

Sun & Prabel             Expires 5 January 2026                 [Page 7]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   *string* ssh-mldsa87-es384

   *string* key

   Here, 'key' is the concatenation of the 2592-octet ML-DSA-87 public
   key and the ECDSA public key using the secp384r1 curve.

   The "ssh-mldsa44-ed25519" key format has the following encoding:

   *string* ssh-mldsa44-ed25519

   *string* key

   Here, 'key' is the concatenation of the 1312-octet ML-DSA-44 public
   key and the 32-octet Ed25519 public key.

   The "ssh-mldsa65-ed25519" key format has the following encoding:

   *string* ssh-mldsa65-ed25519

   *string* key

   Here, 'key' is the concatenation of the 1952-octet ML-DSA-65 public
   key and the 32-octet Ed25519 public key.

   The "ssh-mldsa87-ed448" key format has the following encoding:

   *string* ssh-mldsa87-ed448

   *string* key

   Here, 'key' is the concatenation of the 2592-octet ML-DSA-87 public
   key and the 57-octet Ed448 public key.

6.  Signature Format

   The signature format for all parameter sets defined in this document
   follows the encoding pattern defined in Section 6.6 of [RFC4253].

   *string* identifier

   *string* signature

   The 'identifier' is the key format identifier given in Section 4.

   The 'signature' is the composite signature generated as defined in
   Section 3.1.  It is the concatenation of a randomizer and the
   signatures of the component schemes.

Sun & Prabel             Expires 5 January 2026                 [Page 8]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   For ML-DSA, the signatures are defined in [FIPS204].

   For ECDSA with curves secp256r1 and secp384r1, the signatures and
   their encodings are defined in [RFC5656], Section 3.1.2.

   For Ed25519 and Ed448, the signature are defined in [RFC8709],
   Section 6.

   The "ssh-mldsa44-es256" signature format has the following encoding:

   *string* ssh-mldsa44-es256

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 2420-octet ML-DSA-44 signature and the ECDSA signature using the
   secp256r1 curve.

   The "ssh-mldsa65-es256" signature format has the following encoding:

   *string* ssh-mldsa65-es256

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 3309-octet ML-DSA-65 signature and the ECDSA signature using the
   secp256r1 curve.

   The "ssh-mldsa87-es384" signature format has the following encoding:

   *string* ssh-mldsa87-es384

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 4627-octet ML-DSA-44 signature and the ECDSA signature using the
   secp384r1 curve.

   The "ssh-mldsa44-ed25519" signature format has the following
   encoding:

   *string* ssh-mldsa44-ed25519

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 2420-octet ML-DSA-44 signature and the 64-octet Ed25519
   signature.

Sun & Prabel             Expires 5 January 2026                 [Page 9]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   The "ssh-mldsa65-ed25519" signature format has the following
   encoding:

   *string* ssh-mldsa65-ed25519

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 3309-octet ML-DSA-44 signature and the 64-octet Ed25519
   signature.

   The "ssh-mldsa87-ed448" signature format has the following encoding:

   *string* ssh-mldsa87-ed448

   *string* signature

   Here, 'signature' is the concatenation of a 32 bytes randomizer and
   the 4627-octet ML-DSA-44 signature and the 114-octet Ed448 signature.

7.  Security Considerations

   The Security Considerations section of [RFC4251] also applies to this
   document.

   The user can refer to [FIPS204] for security issues related to the
   ML-DSA post-quantum component of the composite algorithm and to the
   Security Considerations sections of [RFC5656] and [RFC8709] for the
   traditional component.

   For the specific security issues raising from the use of a hybrid
   composite signature scheme, the user can refer to
   [I-D.draft-ietf-pquip-hybrid-signature-spectrums].

   For more information about hybrid composite signature schemes and the
   different hybrid combinations that appear in this document, the user
   can read [I-D.draft-ietf-lamps-pq-composite-sigs].

8.  IANA Considerations

   IANA is requested to add the following entries to "Public Key
   Algorithm Names" in the "Secure Shell (SSH) Protocol Parameters"
   registry [IANA.SSH]:

Sun & Prabel             Expires 5 January 2026                [Page 10]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

      +===========================+=====================+===========+
      | Public Key Algorithm Name | Key Format          | Reference |
      +===========================+=====================+===========+
      | ssh-mldsa44-es256         | ssh-mldsa44-es256   | THIS-RFC  |
      +---------------------------+---------------------+-----------+
      | ssh-mldsa65-es256         | ssh-mldsa65-es256   | THIS-RFC  |
      +---------------------------+---------------------+-----------+
      | ssh-mldsa87-es384         | ssh-mldsa87-es384   | THIS-RFC  |
      +---------------------------+---------------------+-----------+
      | ssh-mldsa44-ed25519       | ssh-mldsa44-ed25519 | THIS-RFC  |
      +---------------------------+---------------------+-----------+
      | ssh-mldsa65-ed25519       | ssh-mldsa65-ed25519 | THIS-RFC  |
      +---------------------------+---------------------+-----------+
      | ssh-mldsa87-ed448         | ssh-mldsa87-ed448   | THIS-RFC  |
      +---------------------------+---------------------+-----------+

                    Table 3: SSH Public Key Code Points

9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC4251]  Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH)
              Protocol Architecture", RFC 4251, DOI 10.17487/RFC4251,
              January 2006, <https://www.rfc-editor.org/rfc/rfc4251>.

   [RFC4253]  Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH)
              Transport Layer Protocol", RFC 4253, DOI 10.17487/RFC4253,
              January 2006, <https://www.rfc-editor.org/rfc/rfc4253>.

   [RFC5656]  Stebila, D. and J. Green, "Elliptic Curve Algorithm
              Integration in the Secure Shell Transport Layer",
              RFC 5656, DOI 10.17487/RFC5656, December 2009,
              <https://www.rfc-editor.org/rfc/rfc5656>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC8709]  Harris, B. and L. Velvindron, "Ed25519 and Ed448 Public
              Key Algorithms for the Secure Shell (SSH) Protocol",
              RFC 8709, DOI 10.17487/RFC8709, February 2020,
              <https://www.rfc-editor.org/rfc/rfc8709>.

Sun & Prabel             Expires 5 January 2026                [Page 11]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

9.2.  Informative References

   [FIPS204]  National Institute of Standards and Technology (NIST),
              "Module-Lattice-Based Digital Signature Standard", August
              2024,
              <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS204.pdf>.

   [I-D.draft-ietf-lamps-pq-composite-sigs]
              Ounsworth, M., Gray, J., Pala, M., Klaußner, J., and S.
              Fluhrer, "Composite ML-DSA for use in X.509 Public Key
              Infrastructure", Work in Progress, Internet-Draft, draft-
              ietf-lamps-pq-composite-sigs-06, 18 June 2025,
              <https://datatracker.ietf.org/doc/html/draft-ietf-lamps-
              pq-composite-sigs-06>.

   [I-D.draft-ietf-pquip-hybrid-signature-spectrums]
              Bindel, N., Hale, B., Connolly, D., and F. D, "Hybrid
              signature spectrums", Work in Progress, Internet-Draft,
              draft-ietf-pquip-hybrid-signature-spectrums-07, 20 June
              2025, <https://datatracker.ietf.org/doc/html/draft-ietf-
              pquip-hybrid-signature-spectrums-07>.

   [I-D.draft-ietf-pquip-pqt-hybrid-terminology]
              D, F., P, M., and B. Hale, "Terminology for Post-Quantum
              Traditional Hybrid Schemes", Work in Progress, Internet-
              Draft, draft-ietf-pquip-pqt-hybrid-terminology-06, 10
              January 2025, <https://datatracker.ietf.org/doc/html/
              draft-ietf-pquip-pqt-hybrid-terminology-06>.

   [IANA.SSH] "Secure Shell (SSH) Protocol Parameters", n.d.,
              <https://www.iana.org/assignments/ssh-parameters/ssh-
              parameters.xhtml>.

   [SEC1]     Standards for Efficient Cryptography Group, "Elliptic
              Curve Cryptography", May 2009,
              <http://www.secg.org/download/aid-780/sec1-v2.pdf>.

Acknowledgments

   TODO acknowledge.

Authors' Addresses

   Sun Shuzhou
   Huawei
   Email: sunshuzhou@huawei.com

Sun & Prabel             Expires 5 January 2026                [Page 12]
Internet-Draft     Composite ML-DSA Signatures for SSH         July 2025

   Lucas Prabel
   Huawei
   Email: lucas.prabel@huawei.com

Sun & Prabel             Expires 5 January 2026                [Page 13]