Re: [lamps] Multiple drafts with PQ algorithm key encodings that are not compatible.

"Kampanakis, Panos" <kpanos@amazon.com> Thu, 29 September 2022 19:19 UTC

Return-Path: <prvs=2641686bf=kpanos@amazon.com>
X-Original-To: spasm@ietfa.amsl.com
Delivered-To: spasm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E5990C14F726 for <spasm@ietfa.amsl.com>; Thu, 29 Sep 2022 12:19:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.174
X-Spam-Level:
X-Spam-Status: No, score=-15.174 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.571, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=amazon.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id X_M4LqNS7prQ for <spasm@ietfa.amsl.com>; Thu, 29 Sep 2022 12:19:54 -0700 (PDT)
Received: from smtp-fw-2101.amazon.com (smtp-fw-2101.amazon.com [72.21.196.25]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 46D5CC14F722 for <spasm@ietf.org>; Thu, 29 Sep 2022 12:19:54 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1664479195; x=1696015195; h=from:to:cc:date:message-id:references:in-reply-to: mime-version:subject; bh=PXKO1DttMYpVHVChbFzxnf5X/OjJtEvvdLB9RlEv5+s=; b=LkwOGXaDxFwyBjSk6VKQ2lzdThbSqACtU9Vua3PYU8Hx2rbIYYX5IoWI IukXMBpNBxBbiHSfUmPWmki74WIKrRuFJ12j1Uf/vUefik48aJptAXq3D NZp1GJpZbL9E+2uGXGP7tEMv6lEf06dxoojz3sYFSljETMACBQIUAeAIQ Y=;
X-IronPort-AV: E=Sophos;i="5.93,356,1654560000"; d="scan'208,217";a="246760581"
Thread-Topic: [lamps] Multiple drafts with PQ algorithm key encodings that are not compatible.
Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-iad-1e-8be8ed69.us-east-1.amazon.com) ([10.43.8.6]) by smtp-border-fw-2101.iad2.amazon.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 29 Sep 2022 19:19:42 +0000
Received: from EX13D12EUC002.ant.amazon.com (iad12-ws-svc-p26-lb9-vlan3.iad.amazon.com [10.40.163.38]) by email-inbound-relay-iad-1e-8be8ed69.us-east-1.amazon.com (Postfix) with ESMTPS id EF192C100F; Thu, 29 Sep 2022 19:19:38 +0000 (UTC)
Received: from EX19D046EUC003.ant.amazon.com (10.252.61.148) by EX13D12EUC002.ant.amazon.com (10.43.164.134) with Microsoft SMTP Server (TLS) id 15.0.1497.38; Thu, 29 Sep 2022 19:19:37 +0000
Received: from EX19D001ANA001.ant.amazon.com (10.37.240.156) by EX19D046EUC003.ant.amazon.com (10.252.61.148) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1118.12; Thu, 29 Sep 2022 19:19:37 +0000
Received: from EX19D001ANA001.ant.amazon.com ([fe80::6054:a5f0:5f79:c120]) by EX19D001ANA001.ant.amazon.com ([fe80::6054:a5f0:5f79:c120%5]) with mapi id 15.02.1118.012; Thu, 29 Sep 2022 19:19:35 +0000
From: "Kampanakis, Panos" <kpanos@amazon.com>
To: "Markku-Juhani O. Saarinen" <mjos@pqshield.com>
CC: "spasm@ietf.org" <spasm@ietf.org>, "Massimo, Jake" <jakemas@amazon.com>, "Panos Kampanakis (pkampana)" <pkampana@cisco.com>, Sean Turner <sean@sn3rd.com>, "bas@westerbaan.name" <bas@westerbaan.name>, "cvvrede@gmail.com" <cvvrede@gmail.com>, "sid@zurich.ibm.com" <sid@zurich.ibm.com>, "bhe@zurich.ibm.com" <bhe@zurich.ibm.com>, "tvi@zurich.ibm.com" <tvi@zurich.ibm.com>, "osb@zurich.ibm.com" <osb@zurich.ibm.com>, "dieter.bong@utimaco.com" <dieter.bong@utimaco.com>, "joppe.bos@nxp.com" <joppe.bos@nxp.com>, John Gray <John.Gray=40entrust.com@dmarc.ietf.org>
Thread-Index: AQHY1DXAtexnd64Tj0WjP+CvhzQahK32x+UA
Date: Thu, 29 Sep 2022 19:19:35 +0000
Message-ID: <3707286a58cc43a8a83773fd80eb6716@amazon.com>
References: <DM6PR11MB25852643FB14014E92A5CFE1EA549@DM6PR11MB2585.namprd11.prod.outlook.com> <CAPwdP4M74afMngjdus_y6SHkuK4cJ_i3GgsQwzF2+sC10kRKdg@mail.gmail.com>
In-Reply-To: <CAPwdP4M74afMngjdus_y6SHkuK4cJ_i3GgsQwzF2+sC10kRKdg@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.136.95.210]
Content-Type: multipart/alternative; boundary="_000_3707286a58cc43a8a83773fd80eb6716amazoncom_"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/y4PwBrg__kjvQmWfsmpzRTdUQr4>
X-Mailman-Approved-At: Thu, 29 Sep 2022 12:22:40 -0700
Subject: Re: [lamps] Multiple drafts with PQ algorithm key encodings that are not compatible.
X-BeenThere: spasm@ietf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: "This is a venue for discussion of doing Some Pkix And SMime \(spasm\) work." <spasm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/spasm>, <mailto:spasm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/spasm/>
List-Post: <mailto:spasm@ietf.org>
List-Help: <mailto:spasm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/spasm>, <mailto:spasm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 29 Sep 2022 19:19:59 -0000

This was fixed in the new Dilithium in X.509 draft based on previous comments in this list.

From: Spasm <spasm-bounces@ietf.org> On Behalf Of Markku-Juhani O. Saarinen
Sent: Thursday, September 29, 2022 1:26 PM
To: John Gray <John.Gray=40entrust.com@dmarc.ietf.org>
Cc: pqc@ietf.org; spasm@ietf.org; cfrg@ietf.org; Massimo, Jake <jakemas@amazon.com>; Panos Kampanakis (pkampana) <pkampana@cisco.com>; Sean Turner <sean@sn3rd.com>; bas@westerbaan.name; cvvrede@gmail.com; sid@zurich.ibm.com; bhe@zurich.ibm.com; tvi@zurich.ibm.com; osb@zurich.ibm.com; dieter.bong@utimaco.com; joppe.bos@nxp.com
Subject: RE: [EXTERNAL][lamps] Multiple drafts with PQ algorithm key encodings that are not compatible.


CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.


On Thu, Sep 29, 2022 at 2:51 PM John Gray <John.Gray=40entrust.com@dmarc.ietf.org<mailto:40entrust.com@dmarc.ietf.org>> wrote:
We are doing some interoperability testing with different vendors using the new Dilithium, Falcon and SPHINCS+ algorithms.   We have come across at least two drafts which are trying to specify the ASN.1 encoding formats for these algorithms.   However, the encoding formats are not compatible with each other.   I imagine the authors of these drafts should get together and come up with a common format (I have copied them on this email).   This means we must choose one or the other, or even worse, support multiple formats (which can lead to bugs).   Initially I started more than a year ago using my own encoding format for internal prototyping, but now need to interoperate with others outside of our organization, so a common format is definitely needed at this point.   😊

Indeed it is remarkable that various people have been trying to create "exploded" ASN.1 encodings for Dilithium keys, none of which are compatible with each other, or the actual Dilithium specification, reference implementation, and the test vectors.

Section 5.4 of the specification defines it as a concatenated byte sequence, or as a 32-byte seed value. For ASN.1 these can be naturally expressed as a simple OCTET STRING. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

"Secret key. The secret key contains ρ, K , tr, s1 , s2 and t0 and is also stored as the
concatenation of the bit-packed representation of these quantities in the given order.
Consequently, a secret key requires 32 + 32 + 32 + 32((k + `) · dlog(2η + 1)e + 13k) bytes.
As mentioned previously, the signer also has the option of simply storing the 32-byte value
ζ and then simply re-deriving all the other elements of the secret key."

The public key is similarly defined. There is no practical advantage of exploding it into individual components -- repacking would always be needed for both signing and signature verification.

Best Regards,
- markku


Dr. Markku-Juhani O. Saarinen
Staff Cryptography Architect
PQShield Ltd



M:             +44 0 7548 620723

E:              mjos@pqshield.com<mailto:mjos@pqshield.com>
W:             www.pqshield.com<http://www.pqshield.com/>



We fully realize the OID values will be changing once official OIDs are registered, (changing those are trivial), but the ASN.1 formats of the public and private keys is kind of important as well…  😊

For example:

The LAMPS group has a specification of Dilithium public keys in this draft:
https://datatracker.ietf.org/doc/draft-massimo-lamps-pq-sig-certificates/


the public key format is this:



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

   DilithiumPublicKey:



     DilithiumPublicKey ::= OCTET STRING



The private key format is this:



     DilithiumPrivateKey ::= SEQUENCE {

         rho         BIT STRING,         - nonce/seed

         K           BIT STRING,         - key/seed

         tr          BIT STRING,         - PRF bytes (CRH in spec.)

         s1          BIT STRING,         - vector l

         s2          BIT STRING,         - vector k

         t0          BIT STRING,         - encoded vector

         PublicKey   IMPLICIT DilithiumPublicKey OPTIONAL

     }



In this draft:
https://datatracker.ietf.org/doc/draft-uni-qsckeys/01/

Dilithium keys have this encoding:




   DilithiumPublicKey ::= SEQUENCE {

       rho         OCTET STRING,

       t1          OCTET STRING

   }





  DilithiumPrivateKey ::= SEQUENCE {

       version     INTEGER {v0(0)}     -- version (round 3)

       nonce       BIT STRING,         -- rho

       key         BIT STRING,         -- key/seed/D

       tr          BIT STRING,         -- PRF bytes (CRH in spec)

       s1          BIT STRING,         -- vector(L)

       s2          BIT STRING,         -- vector(K)

       t0          BIT STRING,

       publicKey  [0] IMPLICIT DilithiumPublicKey OPTIONAL

                                       -- see next section

   }

The draft-uni-qsckeys does not cover SPHINCS+,  it does cover Falcon, but I don’t know of another draft that specifies Falcon.

There are also encodings for Kyber mentioned in two documents that I see.  There is an early   https://datatracker.ietf.org/doc/draft-ietf-lamps-kyber-certificates/  draft which mentions it is up to the document defining Kyber to give more details.    In the draft-uni-qsckeys draft it is more specific.

https://datatracker.ietf.org/doc/draft-uni-qsckeys/01/

   KyberPrivateKey ::= SEQUENCE {
       version     INTEGER {v0(0)}   -- version (round 3)
       s           OCTET STRING,     -- sample s
       publicKey   [0] IMPLICIT KyberPublicKey OPTIONAL,
                                     -- see next section
       hpk         OCTET STRING      -- H(pk)
       nonce       OCTET STRING,     -- z
   }

Partial public key encoding:


KyberPrivateKey ::= SEQUENCE {

       version     INTEGER {v0(0)}   -- version (round 3)

       s           OCTET STRING,     -- EMPTY

       publicKey   [0] IMPLICIT KyberPublicKey OPTIONAL,

                                     -- see next section

       hpk         OCTET STRING      -- EMPTY

       nonce       OCTET STRING,     -- d

   }

Full public key encoding:


   KyberPublicKey ::= SEQUENCE {

       t           OCTET STRING,

       rho         OCTET STRING

   }

Is https://datatracker.ietf.org/doc/draft-uni-qsckeys/01/ meant to become the document that defines the key formats for all the PQ keys that will be standardized?    If not, then it should probably just refer to whatever documents will define the formats so that we can at least agree on one common format for the PQ keys.


Cheers,

John Gray
Entrust
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.
_______________________________________________
Spasm mailing list
Spasm@ietf.org<mailto:Spasm@ietf.org>
https://www.ietf.org/mailman/listinfo/spasm