Internet X.509 Public Key Infrastructure: Algorithm Identifiers for Dilithium
draft-ietf-lamps-dilithium-certificates-01

LAMPS WG                                                      J. Massimo
Internet-Draft                                             P. Kampanakis
Intended status: Standards Track                                     AWS
Expires: 10 August 2023                                        S. Turner
                                                                   sn3rd
                                                           B. Westerbaan
                                                              Cloudflare
                                                         6 February 2023

  Internet X.509 Public Key Infrastructure: Algorithm Identifiers for
                               Dilithium
               draft-ietf-lamps-dilithium-certificates-01

Abstract

   Digital signatures are used within X.509 certificates, Certificate
   Revocation Lists (CRLs), and to sign messages.  This document
   describes the conventions for using Dilithium quantum-resistant
   signatures in Internet X.509 certificates and certificate revocation
   lists.  The conventions for the associated post-quantum signatures,
   subject public keys, and private key are also described.

Note

   [EDNOTE: This draft is not expected to be finalized before the NIST
   PQC Project has standardized PQ algorithms.  After NIST has
   standardized its first algorithms, this document will replace TBD,
   with the appropriate algorithms and parameters before proceeding to
   ratification.  The algorithm Dilithium (version 3.1 2021-02-08) has
   been added as an example in this draft, to provide a more detailed
   illustration of the content - it by no means indicates its inclusion
   in the final version.  This specification will use object identifiers
   for the new algorithms that are assigned by NIST, and will use
   placeholders until these are released.]

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

Massimo, et al.          Expires 10 August 2023                 [Page 1]
Internet-Draft         Dilithium for Certificates          February 2023

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

   This Internet-Draft will expire on 10 August 2023.

Copyright Notice

   Copyright (c) 2023 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
     1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
   2.  Identifiers . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Dilithium Signatures in PKIX  . . . . . . . . . . . . . . . .   4
   4.  Dilithium Public Keys in PKIX . . . . . . . . . . . . . . . .   5
   5.  Key Usage Bits  . . . . . . . . . . . . . . . . . . . . . . .   8
   6.  Dilithium Private Keys  . . . . . . . . . . . . . . . . . . .   8
   7.  ASN.1 Module  . . . . . . . . . . . . . . . . . . . . . . . .   9
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  11
   9.  Security Considerations . . . . . . . . . . . . . . . . . . .  11
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  13
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  13
     10.2.  Informative References . . . . . . . . . . . . . . . . .  13
   Appendix A.  Acknowledgements . . . . . . . . . . . . . . . . . .  14
   Appendix B.  Security Strengths . . . . . . . . . . . . . . . . .  14
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  15

1.  Introduction

   Dilithium is a quantum-resistant digital signature scheme
   standardized by the US National Institute of Standards and Technology
   (NIST) PQC project [NIST-PQC].  This document specifies the use of
   the Dilithium algorithm in Public Key Infrastructure X.509 (PKIX)
   certificates and Certificate Revocation Lists (CRLs) at three
   security levels: Dilithium2, Dilithium3, and Dilithium5, using object

Massimo, et al.          Expires 10 August 2023                 [Page 2]
Internet-Draft         Dilithium for Certificates          February 2023

   identifiers assigned by NIST

   This specification includes conventions for the signatureAlgorithm,
   signatureValue, signature, and subjectPublicKeyInfo fields within
   Internet X.509 certificates and CRLs [RFC5280], like [RFC3279] did
   for classic cryptography and [RFC5480] did for elliptic curve
   cryptography.  It describes the encoding of digital signatures and
   public keys generated with quantum-resistant signature algorithm
   Dilithium.

1.1.  Requirements Language

   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.

2.  Identifiers

   This specification uses placeholders for object identifiers until the
   identifiers for the new algorithms are assigned by NIST.

   The AlgorithmIdentifier type, which is included herein for
   convenience, is defined as follows:

      AlgorithmIdentifier  ::=  SEQUENCE  {
          algorithm   OBJECT IDENTIFIER,
          parameters  ANY DEFINED BY algorithm OPTIONAL
      }

      |  NOTE: The above syntax is from [RFC5280] and matches the
      |  version used therein, i.e., the 1988 ASN.1 syntax.  See
      |  [RFC5912] for ASN.1 copmatible with the 2015 ASN.1 syntax.

   The fields in AlgorithmIdentifier have the following meanings:

   *  algorithm identifies the cryptographic algorithm with an object
      identifier.

   *  parameters, which are optional, are the associated parameters for
      the algorithm identifier in the algorithm field.

   The OIDs are:

      id-dilithiumTBD OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)
               country(16) us(840) organization(1) gov(101) csor(3)
               nistAlgorithm(4) sigAlgs(3) TBD }

Massimo, et al.          Expires 10 August 2023                 [Page 3]
Internet-Draft         Dilithium for Certificates          February 2023

      id-dilithiumTBD OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)
               country(16) us(840) organization(1) gov(101) csor(3)
               nistAlgorithm(4) sigAlgs(3) TBD }

      id-dilithiumTBD OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)
               country(16) us(840) organization(1) gov(101) csor(3)
               nistAlgorithm(4) sigAlgs(3) TBD }

   The contents of the parameters component for each algorithm are
   absent.

3.  Dilithium Signatures in PKIX

   Dilithium is a digital signature scheme built upon the Fiat-Shamir-
   with-aborts framework [Fiat-Shamir].  The security is based upon the
   hardness of lattice problems over module lattices [Dilithium].
   Dilithium provides three parameter sets for the security categories
   2, 3 and 5.

   Signatures are used in a number of different ASN.1 structures.  As
   shown in the ASN.1 representation from [RFC5280] below, in an X.509
   certificate, a signature is encoded with an algorithm identifier in
   the signatureAlgorithm attribute and a signatureValue attribute that
   contains the actual signature.

      Certificate  ::=  SEQUENCE  {
         tbsCertificate       TBSCertificate,
         signatureAlgorithm   AlgorithmIdentifier,
         signatureValue       BIT STRING  }

   Signatures are also used in the CRL list ASN.1 representation from
   [RFC5280] below.  In a X.509 CRL, a signature is encoded with an
   algorithm identifier in the signatureAlgorithm attribute and a
   signatureValue attribute that contains the actual signature.

      CertificateList  ::=  SEQUENCE  {
         tbsCertificate       TBSCertList,
         signatureAlgorithm   AlgorithmIdentifier,
         signatureValue       BIT STRING  }

   The identifiers defined in Section 2 can be used as the
   AlgorithmIdentifier in the signatureAlgorithm field in the sequence
   Certificate/CertificateList and the signature field in the sequence
   TBSCertificate/TBSCertList in certificates CRLs, respectively,
   [RFC5280].  The parameters of these signature algorithms are absent,
   as explained in Section 2.

Massimo, et al.          Expires 10 August 2023                 [Page 4]
Internet-Draft         Dilithium for Certificates          February 2023

   The signatureValue field contains the corresponding Dilithium
   signature computed upon the ASN.1 DER encoded tbsCertificate
   [RFC5280].

   Conforming Certification Authority (CA) implementations MUST specify
   the algorithms explicitly by using the OIDs specified in Section 2
   when encoding Dilithium signatures in certificates and CRLs.
   Conforming client implementations that process certificates and CRLs
   using Dilithium MUST recognize the corresponding OIDs.  Encoding
   rules for Dilithium signature values are specified Section 2.

   When the id-dilithiumTBD identifier appears in the algorithm field as
   an AlgorithmIdentifier, the encoding MUST omit the parameters field.
   That is, the AlgorithmIdentifier SHALL be a SEQUENCE of one
   component, the OID id-dilithiumTBD.

4.  Dilithium Public Keys in PKIX

   In the X.509 certificate, the subjectPublicKeyInfo field has the
   SubjectPublicKeyInfo type, which has the following ASN.1 syntax:

     SubjectPublicKeyInfo  ::=  SEQUENCE  {
         algorithm         AlgorithmIdentifier,
         subjectPublicKey  BIT STRING
     }

   The fields in SubjectPublicKeyInfo have the following meanings:

   *  algorithm is the algorithm identifier and parameters for the
      public key (see above).

   *  subjectPublicKey contains the byte stream of the public key.  The
      algorithms defined in this document always encode the public key
      as TODO.

   The public parameters for Dilithium are based upon a polynomial ring
   R_q for prime q.  A (k*l) public matrix A is produced, consisting of
   polynomials whose coefficients are sampled uniformly at random from
   the integers modulo q.  This sampling is performed by expanding a
   nonce (rho) using an XOF.

   The Dilithium public key MUST be encoded using the ASN.1 type
   DilithiumPublicKey:

     DilithiumPublicKey ::= OCTET STRING

Massimo, et al.          Expires 10 August 2023                 [Page 5]
Internet-Draft         Dilithium for Certificates          February 2023

   where DilithiumPublicKey is a concatenation of rho and t1.  Here, rho
   is the nonce used to seed the XOF to produce the matrix A, and t1 is
   a vector encoded in 320*k bytes where k is the rank of the vector
   over the polynomial ring R_q.  These parameters MUST be encoded as a
   single OCTET STRING.  The size required to hold a DilithiumPublicKey
   public key element is therefore 32+320*k bytes.

   The id-dilithiumTBD identifier defined in Section 2 MUST be used as
   the algorithm field in the SubjectPublicKeyInfo sequence [RFC5280] to
   identify a Dilithium public key.

   The Dilithium public key (a concatenation of rho and t1 that is an
   OCTET STRING) is mapped to a subjectPublicKey (a value of type BIT
   STRING) as follows: the most significant bit of the OCTET STRING
   value becomes the most significant bit of the BIT STRING value, and
   so on; the least significant bit of the OCTET STRING becomes the
   least significant bit of the BIT STRING.

   The following is an example of a Dilithium3 public key encoded using
   the textual encoding defined in [RFC7468].

Massimo, et al.          Expires 10 August 2023                 [Page 6]
Internet-Draft         Dilithium for Certificates          February 2023

   -----BEGIN PUBLIC KEY-----
   MIIHtDANBgsrBgEEAQKCCwcGBQOCB6EAFyP2dnbMELz5lkTFG7YvOdqVF5km835e
   UHXNaynmIrWHeKMla2gHZTCAwgLWIr9RAh1K11KRvFf+HYMs3ykOrd4xQ2vgLsjP
   jU0bup+rgRK5gvm3Z37rm2jAXDzJNxeM5lEDTklz9BQwOdQGm1rI/MXeMGssnOG4
   a9QvNPERdcG7VpTAEEevuTWmOeiKK3+kNCpoMRZr4WkgeInRyVUZXUvbYKkbm1Yj
   2Mn2ZhgqFW4M1IJwq3LPDCAXZU9R0dTQCt9Ns04HQHNylARZya6TdW+F2k+pfZ3U
   BRGbdI0MbVkOxqgRTfdWLlcXCfPn9/qdbz2K18QKdEuBBtPdZxiwTePDS6XvXjEp
   KZg9bukd7Yxqhg+DPGQp+yQLW4H3lkOkq6mCNW2z86OVnja7xHYL8vAU8xDZ9IeL
   oAIJm37X+qLOMIrT7qJE6zx2k+cJBnxBMSErEmOGOHb+dMvZyn8O77EyOSJS5pyn
   70quzO8k+VieM8jc7ZJan3NUeC7F3Os45uAJzEa1ssKwMx+f4Dtz8GkSjjwCIdFA
   fp6MNzek90lPKqJuxL37NGDB9scH6nLQOKpikaYkBYxD/huNtAe/e9MEHFlD1/Uz
   bSWTN2qQ4UmdV7iJKtIvesDrzx7D6v5EUh9QGdt4D3dNI7NvdyOGrQXwMz8M1EOB
   RX7QbAySLAkpGtpjcqkyiW0nOmslMtgI1JPM0bSzx1DuIaWjG/jf6HKpu2Ev2UlN
   pYs8cMoFeHmJpzGUkGlFwE+nGysZOx708p98yDRrQyY/Fw6Qg1xzFle14CTqW86h
   sD4K0scryDnETg3ZXpwhfQncYfxBbnIIyvxn2AnyGjy6h2r0b1SC8xzxWP7tGaSX
   0H4sdGPvv1AIc6id4VhtrKZgau7JK24c4lqun3WgmZH3+/wyDeyf+Zrb8/DPK3N3
   ZI4R+xkZDzSkuFWLh5om8MykaFT6TNmc5Hc1kO039tgz0vqXpsQHir+EiFPbugEp
   JLoxmoCgdxy9RLvDkSjnDwyI4Hg1djp9nRhpTVjvMdoIw6dSyO11ilEwppm+dNIn
   Gxd6iO7yaE2tJ6UjIc+7tuKoZkzmsO6p4hN8VKhzXcVjnRr6xox4sD5u3esqtJly
   9lsMU0qZnqJU4jbBS3SQloj3m8pl4cdf/j6ZHNiAAnfX6hhUGZDetTEv7MICeSW0
   b77XO5i4udTcYQtLvdo7mmyzG/N8NNR1T9pw89GYJ1maJhC2JyYx3Qwedppk0xac
   BwWednYgQMMNEUKmAGoZxytTHtFfPhGQ4s7gZ6zw2CTiqAEGLfGj6lrwuBgXXAn+
   S8B7UwF4b4ReCpwdYO1N5AyWXAax5T67H5a/5VkiX8zT5lX6+/bAqT8waLIImE3Q
   bEK74kOgQvULbzLzVjqJYPiAF8RwPIWRxH8ocOAM+NG0pREiEgDlO0xrcW26PeIo
   pGEsxOfiZRq1CLIRFn2FyczJQ8xFwC7fWio3q91+RGr+hzgBE69HuT8C/Z/pBT/x
   Im+D4lM1l++Xyn1RAoHyfnZy+nQK9i4hZ3eGyvpYfjfNGN5S+cBHY7/pKcr/EFaE
   WgN97C4eTLD/SDxCoS9K25XEVFECHNfgY5NS3sfizlVrQqRIecoSLUhyqswlXYF8
   xgi58ZRh0oCGv6/4oyNROhwBi/aJYL0RRSYd5ZuARcs/aZ+QhdMOkprdzZSh4wDX
   n3Vw1Rm1GAJEDVEojLoFtpWroe4YdsFHDmkJodZl3PHZIOuwHRr8YsqcHwuXM5nW
   iGZRw+PoJP6gri+ev62U0jW5k7t7v35aF4ccBhwg4AVT2odFnj72hwD6df29LMIa
   Zebj4iagOADfdVJhNUis9YseJwJtmlCJqUAB/6BQsCqeleD9LldTMutN/mq67DSe
   z33nzBeLs0PnhtYiX2z3yjw4s+6/c4Q0o+fikm4t23A1Px8sDi72yplLRl67L6L8
   I4zXOW4eA9PFQFndAhDblmceVOoCmRuncXte56/8trdyGepF7+tm+79zKXeDkVkf
   XmyHbcipFPHg00EUDgt2Wovq63obQXHP9f1KWon8YGOmW5MJbBNWiu83RZvwX7YW
   6Z+STzC7aMzmQECmKEuiW1Zx6kcZnXFYDrlEiyit+lCiUyjqVbEJb3GJnOJM7Lmj
   WEhutG6MSdJFuP/LHc0xxjxrQeG776skEujPcIt+kWqYXpdKTthWbfiuqCKbs+Qa
   cGz3tRhyH2urDZC0LuZHF15AyQmSmRP4FcC9aMn6q4alx/+LUZwGvrjb4xJNAtqC
   aapC8vTyNxKBJhawlkSewVoI3c7ra0WKYJ7YGaHct1VeH9u47a7pu/hYC1dAPWd8
   kajqEv2JJyWk0rrCi5OzrIfxE9Bl9C4nFWCPsd61qGLmi7u+1MrdN3k6dk6TG/y5
   Qkn9iw7wFyoaq6p6RFtFFPnAJJDiHEMp/ZFfY9Rxquvb4EK6FjAHAtKejzEMte4x
   zXK4C4pBZTy+RTMvu7j0CGVlKRgSyj05LX2c22NY6YB1ZSoe9r8NFeRSOQ0ojHBf
   afbiN3jcuOA/nB1MHq6ll/VpLR9NIAJyC4Xh+isdDK4JIXesSD9iNA5CIVXMUlE4
   x5AXF2HOm4o=
   -----END PUBLIC KEY-----

Massimo, et al.          Expires 10 August 2023                 [Page 7]
Internet-Draft         Dilithium for Certificates          February 2023

   Conforming CA implementations MUST specify the X.509 public key
   algorithm explicitly by using the OIDs specified in Section 2 when
   using Dilithium public keys in certificates and CRLs.  Conforming
   client implementations that process Dilithium public keys when
   processing certificates and CRLs MUST recognize the corresponding
   OIDs.

5.  Key Usage Bits

   The intended application for the key is indicated in the keyUsage
   certificate extension; see Section 4.2.1.3 of [RFC5280].  If the
   keyUsage extension is present in a certificate that indicates id-
   dilithiumTBD in the SubjectPublicKeyInfo, then the at least one of
   following MUST be present:

     digitalSignature; or
     nonRepudiation; or
     keyCertSign; or
     cRLSign.

   Requirements about the keyUsage extension bits defined in [RFC5280]
   still apply.

6.  Dilithium Private Keys

   EDNOTE: this section is still under construction as we discuss the
   best way to formulate the private key with the wider working group.

   A Dilithium private key is encoded as DilithiumPrivateKey in the
   privateKey field as an OCTET STRING.  Dilithium public keys are
   optionally distributed in the publicKey field of the
   DilithiumPrivateKey structure.  This follows the OneAsymmetricKey
   syntax.

   The ASN.1 encoding for a Dilithium private key is as follows:

     DilithiumPrivateKey ::= SEQUENCE {
         version                  Version,
         privateKeyAlgorithm      PrivateKeyAlgorithmIdentifier,
         privateKey               OCTET STRING,
         publicKey                [1] DilithiumPublicKey OPTIONAL
     }

Massimo, et al.          Expires 10 August 2023                 [Page 8]
Internet-Draft         Dilithium for Certificates          February 2023

   A fully populated Dilithium private key consists of 6 parameters.
   The size necessary to hold all private key elements is
   32+32+32+32*[(k+l)*ceiling(log(2*eta+1))+13*k] bytes.  The
   description of k, l, and eta as well as public key and secret key
   sizes for security levels 2, 3, and 5 can be found in Figure 1 of the
   Appendix.

7.  ASN.1 Module

   This section includes the ASN.1 module for the Dilithium signature
   algorithm.  This module does not come from any previously existing
   RFC.  This module references [RFC5912].

Massimo, et al.          Expires 10 August 2023                 [Page 9]
Internet-Draft         Dilithium for Certificates          February 2023

   [ EDNOTE: Add ASN.1 here ]

     PKIX1-PQ-Algorithms { iso(1) identified-organization(3) dod(6)
        internet(1) security(5) mechanisms(5) pkix(7) id-mod(0)
        id-mod-pkix1-PQ-algorithms(X) }

     DEFINITIONS EXPLICIT TAGS ::=

     BEGIN

     -- EXPORTS ALL;

     IMPORTS

     -- FROM RFC 5912

     PUBLIC-KEY, SIGNATURE-ALGORITHM, DIGEST-ALGORITHM, SMIME-CAPS
     FROM AlgorithmInformation-2009
       { iso(1) identified-organization(3) dod(6) internet(1)
         security(5) mechanisms(5) pkix(7) id-mod(0)
         id-mod-algorithmInformation-02(58) }

     --
     -- Public Key (pk-) Algorithms
     --
     PublicKeys PUBLIC-KEY ::= {
       -- This expands PublicKeys from RFC 5912
       pk-dilithiumTBD |
       pk-TBD-TBD,
       ...
     }

     -- The hashAlgorithm is mda-shake256
     -- The XOF seed rho is 32 bytes
     -- The vector t1 is 320*k bytes
     -- These are encoded as a single string
     pk-dilithiumTBD PUBLIC-KEY ::= {
       IDENTIFIER id-dilithiumTBD
       KEY DilithiumPublicKey
       PARAMS ARE absent
       CERT-KEY-USAGE { nonRepudiation, digitalSignature,
                       keyCertSign, cRLSign }
       PRIVATE-KEY DilithiumPrivateKey
     }

     END

Massimo, et al.          Expires 10 August 2023                [Page 10]
Internet-Draft         Dilithium for Certificates          February 2023

8.  IANA Considerations

   Extensions in certificates and CRLs are identified using object
   Identifiers (OIDs).  The creation and delegation of these arcs is to
   be determined.

   IANA is requested to register the id-mod-pkix1-PQ-algorithms OID for
   the ASN.1 module identifier found in Section 5 in the "SMI Security
   for PKIX Module Identifier" registry.

9.  Security Considerations

   The Security Considerations section of [RFC5280] applies to this
   specification as well.

   The digital signature scheme defined within this document are modeled
   under existentially unforgeable digital signatures with respect to an
   adaptive chosen message attack (EUF-CMA).  For the purpose of
   estimating security strength, it has been assumed that the attacker
   has access to signatures for no more than 2^{64} chosen messages.

   EDNOTE: Discuss implications of not hash-then-sign.  Implications in
   performance too.

   Within the hash-then-sign paradigm, hash functions are used as a
   domain restrictor over the message to be signed.  By pre-hashing, the
   onus of resistance to existential forgeries becomes heavily reliant
   on the collision-resistance of the hash function in use.  As well as
   this security goal, the hash-then-sign paradigm also has the ability
   to improve performance by reducing the size of signed messages.  As a
   corollary, hashing remains mandatory even for short messages and
   assigns a further computational requirement onto the verifier.  This
   makes the performance of hash-then-sign schemes more consistent, but
   not necessarily more efficient.  Dilithium diverges from the hash-
   then-sign paradigm by hashing the message during the signing
   procedure (at the point in which the challenge polynomial).  However,
   due to the fact that Dilithium signatures may require the signing
   procedure to be repeated several times for a signature to be
   produced, Dilithium implementations can make use of pre-hashing the
   message to prevent rehashing with each attempt.

   EDNOTE: Discuss deterministic vs randomized signing and the impact on
   security.

   Dilithium offers both deterministic and randomized signing.  The
   difference between these two versions of the scheme is a one line
   modification in which the seed is chosen at random (in the randomized
   version) or as a hash of a key together with the message (in the

Massimo, et al.          Expires 10 August 2023                [Page 11]
Internet-Draft         Dilithium for Certificates          February 2023

   deterministic version).  A Hedged signature scheme may be obtained by
   making a modification to the randomized version to include the
   message and key into the seed that generates the the nonce y.  This
   middle ground between a randomized nonce and one tied to the message
   and key could be the solution to mitigiation both nonce-reuse attacks
   in places of poor entropy, as well as mitigate fault attacks that
   rely on differential analysis.

   EDNOTE: Discuss side-channels for Dilithium.

   Dilithium has been designed to provide side-channel resilience by
   eliminating a reliance on Gaussian sampling.  While deliberate design
   decisions such as these can help to deliver a greater ease of secure
   implementation - particularly against side-channel attacks - it does
   not necessarily provide resistance to more powerful attacks such as
   differential power analysis.  Some amount of side-channel leakage has
   been demonstrated in parts of the signing algorithm (specifically the
   bit-unpacking function), from which a demonstration of key recovery
   has been made over a large sample of signatures.  Masking
   countermeasures exist for Dilithium, but come with a performance
   overhead.

   A fundamental security property also associated with digital
   signatures is non-repudiation.  Non-repudiation refers to the
   assurance that the owner of a signature key pair that was capable of
   generating an existing signature corresponding to certain data cannot
   convincingly deny having signed the data.  The digital signature
   scheme Dilithium possess three security properties beyond
   unforgeability, that are associated with non-repudiation.  These are
   exclusive ownership, message-bound signatures, and non-resignability.
   These properties are based tightly on the assumed collision
   resistance of the hash function used (in this case SHAKE-256).
   Exclusive ownership is a property in which a signature sigma uniquely
   determines the public key and message for which it is valid.
   Message-bound signatures is the property that a valid signature
   uniquely determines the message for which it is valid, but not
   necessarily the public key.  Non-resignability is the property in
   which one cannot produce a valid signature under another key given a
   signature sigma for some unknown message m.  These properties are not
   provided by classical signature schemes such as DSA or ECDSA, and
   have led to a variety of attacks such as Duplicate-Signature Key
   Selection (DSKS) attacks , and attacks on the protocols for secure
   routing.  A full discussion of these properties in Dilithium can be
   found at [CDFFJ21].  These properties are dependent, in part, on
   unambiguous public key serialization.  It for this reason the public
   key structure defined in Section 4 is intentionally encoded as a
   single OCTET STRING.

Massimo, et al.          Expires 10 August 2023                [Page 12]
Internet-Draft         Dilithium for Certificates          February 2023

10.  References

10.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/info/rfc2119>.

   [RFC5280]  Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
              Housley, R., and W. Polk, "Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,
              <https://www.rfc-editor.org/info/rfc5280>.

   [RFC5912]  Hoffman, P. and J. Schaad, "New ASN.1 Modules for the
              Public Key Infrastructure Using X.509 (PKIX)", RFC 5912,
              DOI 10.17487/RFC5912, June 2010,
              <https://www.rfc-editor.org/info/rfc5912>.

   [RFC7468]  Josefsson, S. and S. Leonard, "Textual Encodings of PKIX,
              PKCS, and CMS Structures", RFC 7468, DOI 10.17487/RFC7468,
              April 2015, <https://www.rfc-editor.org/info/rfc7468>.

   [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/info/rfc8174>.

10.2.  Informative References

   [CDFFJ21]  Cremers, Cas., Düzlü, S., Fiedler, R., Fischlin, M., and
              C. Janson, "BUFFing signature schemes beyond
              unforgeability and the case of post-quantum signatures",
              In Proceedings of the 42nd IEEE Symposium on Security and
              Privacy, 2021, <https://eprint.iacr.org/2020/1525.pdf>.

   [Dilithium]
              Bai, S., Ducas, L., Lepoint, T., Lyubashevsky, V.,
              Schwabe, P., Seiler, G., and D. Stehlé, "CRYSTALS-
              Dilithium Algorithm Specifications and Supporting
              Documentation", 2021, <https://pq-
              crystals.org/dilithium/data/dilithium-specification-
              round3-20210208.pdf>.

Massimo, et al.          Expires 10 August 2023                [Page 13]
Internet-Draft         Dilithium for Certificates          February 2023

   [Fiat-Shamir]
              Lyubashevsky, V., "Fiat-Shamir with aborts: Applications
              to lattice and factoring-based signatures", International
              Conference on the Theory and Application of Cryptology and
              Information Security, 2009, <https://www.iacr.org/archive/
              asiacrypt2009/59120596/59120596.pdf>.

   [NIST-PQC] National Institute of Standards and Technology (NIST),
              "Post-Quantum Cryptography Project", 20 December 2016,
              <https://csrc.nist.gov/Projects/post-quantum-
              cryptography>.

   [RFC3279]  Bassham, L., Polk, W., and R. Housley, "Algorithms and
              Identifiers for the Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 3279, DOI 10.17487/RFC3279, April
              2002, <https://www.rfc-editor.org/info/rfc3279>.

   [RFC5480]  Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk,
              "Elliptic Curve Cryptography Subject Public Key
              Information", RFC 5480, DOI 10.17487/RFC5480, March 2009,
              <https://www.rfc-editor.org/info/rfc5480>.

Appendix A.  Acknowledgements

   We would like to thank ... for their insightful comments.

Appendix B.  Security Strengths

   Instead of defining the strength of a quantum algorithm in a
   traditional manner using precise estimates of the number of bits of
   security, NIST has instead elected to define a collection of broad
   security strength categories.  Each category is defined by a
   comparatively easy-to-analyze reference primitive that cover a range
   of security strengths offered by existing NIST standards in symmetric
   cryptography, which NIST expects to offer significant resistance to
   quantum cryptanalysis.  These categories describe any attack that
   breaks the relevant security definition that must require
   computational resources comparable to or greater than those required
   for: Level 1 - key search on a block cipher with a 128-bit key (e.g.,
   AES128), Level 2 - collision search on a 256-bit hash function (e.g.,
   SHA256/ SHA3-256), Level 3 - key search on a block cipher with a
   192-bit key (e.g., AES192), Level 4 - collision search on a 384-bit
   hash function (e.g.  SHA384/ SHA3-384), Level 5 - key search on a
   block cipher with a 256-bit key (e.g., AES 256).

Massimo, et al.          Expires 10 August 2023                [Page 14]
Internet-Draft         Dilithium for Certificates          February 2023

   The parameter sets defined for NIST security levels 2, 3 and 5 are
   listed in the Figure 1, along with the resulting signature size,
   public key, and private key sizes in bytes.

   |=======+=======+=====+========+========+========|
   | Level | (k,l) | eta |  Sig.  | Public | Private|
   |       |       |     |  (B)   | Key(B) | Key(B) |
   |=======+=======+=====+========+========+========|
   |   2   | (4,4) |  2  |  2420  |  1312  |  2528  |
   |   3   | (6,5) |  4  |  3293  |  1952  |  4000  |
   |   5   | (8,7) |  2  |  4595  |  2592  |  4864  |
   |=======+=======+=====+========+========+========|

                                  Figure 1

Authors' Addresses

   Jake Massimo
   AWS
   United States of America
   Email: jakemas@amazon.com

   Panos Kampanakis
   AWS
   United States of America
   Email: kpanos@amazon.com

   Sean Turner
   sn3rd
   Email: sean@sn3rd.com

   Bas Westerbaan
   Cloudflare
   Email: bas@westerbaan.name

Massimo, et al.          Expires 10 August 2023                [Page 15]