object formats in NIST PQC standards

[Falko Strenzke]

I have the following question to NIST: What are the input/output formats of public keys, ciphertexts and signatures that can be expected in the NIST PQC standards? What I mean is the general distinction between

• (A) opaque binary blobs (as they are currently used by the reference implementations)
• (B) a somewhat structured format,
  • (i) e.g. defining the keys as lists of elements (such as pk = (A, t) in case of Dilithium public keys) without providing an encompassing encoding
  • (ii) defining such lists/sequences of elements with some kind of encompassing encoding (e.g. length encoding of some kind)

The background of this question is that we observed that in the LAMPS PQC drafts for the hash-based schemes an ASN.1 encoding is prescribed for the internal structuring of public keys and signatures. See our posts on the LAMPS mailing list for what is our concern here.

- Falko

--

MTG AG
Dr. Falko Strenzke
Executive System Architect

Phone: +49 6151 8000 24
E-Mail: falko.s...@mtg.de
Web: mtg.de


MTG Exhibitions – See you in 2023

---

MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde

This email may contain confidential and/or privileged information. If you are not the correct recipient or have received this email in error,
please inform the sender immediately and delete this email. Unauthorised copying or distribution of this email is not permitted.

Data protection information: Privacy policy

[Markku-Juhani O. Saarinen]

On Tuesday, April 25, 2023 at 10:25:06 AM UTC+1 Falko Strenzke wrote:

I have the following question to NIST: What are the input/output formats of public keys, ciphertexts and signatures that can be expected in the NIST PQC standards? What I mean is the general distinction between

• (A) opaque binary blobs (as they are currently used by the reference implementations)
• (B) a somewhat structured format,
  • (i) e.g. defining the keys as lists of elements (such as pk = (A, t) in case of Dilithium public keys) without providing an encompassing encoding
  • (ii) defining such lists/sequences of elements with some kind of encompassing encoding (e.g. length encoding of some kind)

The background of this question is that we observed that in the LAMPS PQC drafts for the hash-based schemes an ASN.1 encoding is prescribed for the internal structuring of public keys and signatures. See our posts on the LAMPS mailing list for what is our concern here.

Hi Falko & All,

Some hash-based I-D's may have this, and there were even some early proposals of doing (B) on Kyber and Dilithium too. I personally hope we should have gotten over this issue at IETF already; Clearly, the (B) option is significantly more difficult to implement for PQC schemes as one needs to externally convert the ASN.1 encodings into the standard implementation formats for use. One also loses at least a few bytes in certificate size to the redundant ASN.1 encoding.

Hence the IETF industry working group for PQC certificates and keys basically uses the (A) option for public keys and signatures. These blobs are wrapped inside X.509 ASN.1 structures as-is, at least for Kyber and Dilithium. Many other things (such as the OIDs) and higher-level ASN.1 are still subject to change, but this aspect should remain. There has been interoperability testing between about 10 vendors/implementations with certificates of this type in IETF Hackathons: https://github.com/IETF-Hackathon/pqc-certificates 

A further reminder that (A) formats are not just about reference implementations (and important KAT testing etc); at least Kyber and Dilithium specifications themselves contain public key serialization formats of type (A), and the algorithms also use them internally (in Fujisaki-Okamoto and BUFF features, respectfully). So, in addition to all of the interoperability and implementation trouble, the (B) option ASN.1 re-serialization may sacrifice the technical security properties that FO and BUFF provide. At least it would necessitate the unnecessary hurdle to prove that the implemented ASN.1 public key transformations are one-to-one to the standard internal format public keys.

Cheers,

-markku

[Perlner, Ray A. (Fed)]

Hi Falko

 

Our (NIST’s) current plan is to encode signatures, ciphertexts, and public keys as byte strings. I think this is closest to (A) from your list.

 

-Ray Perlner

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/88002f84-4f6a-b2cd-9614-fc709c6a9942%40mtg.de.

[Mike Ounsworth]

Thanks for asking this question Falko.

 

 

Ray,

 

Within the IETF we have the “uni-qsckeys” drafts floating around which provide encodings for the PQC finalists.

 

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

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

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

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

 

Quoting one of their abstracts:

 

Abstract

This proposal defines key management approaches for the Quantum Safe Cryptographic (QSC) algorithm CRYSTALS-Kyber which has been selected for standardization by the NIST Post Quantum Cryptography (PQC) process. This includes key identification, key serialization, and key compression. The purpose is to provide guidance such that the adoption of quantum safe algorithms is not hampered with the fragmented evolution of necessary key management standards. Early definition of key material standards will help expedite the adoption of new quantum safe algorithms and at the same time as improving interoperability between implementations and minimizing divergence across standards.

 

 

These has been some confusion about whether NIST will provide “official” public key, signature, and ciphertext encodings, or whether 3^rd party standards like this will be necessary. As Falko said, there has been some controversy around these drafts, one of which being that the authors chose an ASN.1-based encoding which is a bit of an odd choice given the number of non-ASN.1-based crypto protocols in existence (like JOSE / COSE).

 

 

So back to the question, Ray, you are confirming that NIST will provide concrete binary encodings in the final PQC algorithm standards, thus making drafts like these obsolete?

 

 

---
Mike Ounsworth
Software Security Architect, Entrust

 

From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Wednesday, April 26, 2023 12:51 PM
To: Falko Strenzke <falko.s...@mtg.de>; pqc-forum <pqc-...@list.nist.gov>
Cc: Evangelos Karatsiolis <evangelos....@mtg.de>

Subject: [EXTERNAL] RE: [pqc-forum] object formats in NIST PQC standards

 

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

---

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB4855CB0CEDB3AA2EF66A4F529C659%40DM6PR09MB4855.namprd09.prod.outlook.com.

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.

[Blumenthal, Uri - 0553 - MITLL]

Ray, I personally think that your (NIST’s) current plan to encode “stuff” as byte strings is the best.

 

IETF would be wise to follow the same approach.

 

TNX

--

V/R,

Uri

 

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

 

 

From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>

Date: Wednesday, April 26, 2023 at 1:51 PM
To: Falko Strenzke <falko.s...@mtg.de>, pqc-forum <pqc-...@list.nist.gov>
Cc: Evangelos Karatsiolis <evangelos....@mtg.de>

Subject: [EXT] RE: [pqc-forum] object formats in NIST PQC standards

Hi Falko Our (NIST’s) current plan is to encode signatures, ciphertexts, and public keys as byte strings. I think this is closest to (A) from your list. -Ray Perlner From: pqc-forum@ list. nist. gov <pqc-forum@ list. nist. gov> On Behalf Of

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender This message came from outside the Laboratory.

ZjQcmQRYFpfptBannerEnd

Hi Falko

 

Our (NIST’s) current plan is to encode signatures, ciphertexts, and public keys as byte strings. I think this is closest to (A) from your list.

 

-Ray Perlner

 

 

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Falko Strenzke
Sent: Tuesday, April 25, 2023 5:25 AM
To: pqc-forum <pqc-...@list.nist.gov>
Cc: Evangelos Karatsiolis <evangelos....@mtg.de>
Subject: [pqc-forum] object formats in NIST PQC standards

 

I have the following question to NIST: What are the input/output formats of public keys, ciphertexts and signatures that can be expected in the NIST PQC standards? What I mean is the general distinction between

·         (A) opaque binary blobs (as they are currently used by the reference implementations)

·         (B) a somewhat structured format,

o    (i) e.g. defining the keys as lists of elements (such as pk = (A, t) in case of Dilithium public keys) without providing an encompassing encoding

o    (ii) defining such lists/sequences of elements with some kind of encompassing encoding (e.g. length encoding of some kind)

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB4855CB0CEDB3AA2EF66A4F529C659%40DM6PR09MB4855.namprd09.prod.outlook.com.

[Markku-Juhani O. Saarinen]

On Wed, Apr 26, 2023 at 7:27 PM Blumenthal, Uri - 0553 - MITLL <u...@ll.mit.edu> wrote:

Ray, I personally think that your (NIST’s) current plan to encode “stuff” as byte strings is the best.

 

IETF would be wise to follow the same approach.

 

Completely agree.

Yet another reminder that the IETF drafts with homebrew ASN.1 encodings were not compatible with the Kyber and Dilithium specifications. Byte strings have always been defined there.

- Section 5.4 (page 20-21) of the Dilithium specification contains "Data layout of keys and signature" -- which is just byte strings. There was never a need for the ASN.1 dissected public key stuff which adds redundant format bytes in the middle of these blobs. The use of the standard public key format in the specification is *required* for correct, interoperable Dilithium implementations as the byte-based public key is hashed with the message when producing and verifying signatures. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

- Ditto for Kyber. The public key is hashed with the ciphertext in the algorithm inthe process create the shared secrets, so valid, interoperable Kyber implementations must use the public key and ciphertext formats contained in the specification. If you look at the definition pseudocode the byte encodings are literally part of the algorithms themselves (Algorithms 4-9). https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

So all NIST has to do is to adopt the byte encodings that Kyber and Dilithium specifications have had all along (of course details and presentation can be improved.) These have been extensively analysed in the PQC standardization process.

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

TNX

--

V/R,

Uri

 

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

 

 

From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Date: Wednesday, April 26, 2023 at 1:51 PM
To: Falko Strenzke <falko.s...@mtg.de>, pqc-forum <pqc-...@list.nist.gov>
Cc: Evangelos Karatsiolis <evangelos....@mtg.de>
Subject: [EXT] RE: [pqc-forum] object formats in NIST PQC standards

Hi Falko Our (NIST’s) curr

Hi Falko

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/BN0P110MB1419AC861D4325769295D89E90659%40BN0P110MB1419.NAMP110.PROD.OUTLOOK.COM.

[Tim Hollebeek]

It’s worth noting that other than one preliminary draft that motivated this discussion, IETF has already been following this approach, and in particular, the LAMPS WG chairs have been advising authors that the opaque binary blob approach is the right approach.  That had even already happened with respect to the draft being called out here, and I’m confident that draft will be modified to be in line with the opaque blob approach before any publication, as I can’t see the LAMPS WG approving anything else.

 

The other related question, which is probably also worth mentioning here as well, is we have also been advising people that cryptographic algorithm OIDs should be in the form of a single OID that says “Do the thing the standard tells you to do” without additional parameters.  E.g. “id-trineutronium-medium” and not something more like “{id-trineutronium rounds=42 effective-security=256 salt=Himalayan bikeshed=purplepolkadots}” This follows the recent trend for most IETF crypto protocols, and we’ve had informal discussions with NIST confirming they also think this is the correct approach.

 

I’m just mentioning it here for wider awareness, and so that if anyone wants to comment on that approach, they can.

 

-Tim

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/BN0P110MB1419AC861D4325769295D89E90659%40BN0P110MB1419.NAMP110.PROD.OUTLOOK.COM.

[Christine Cloostermans]

Hi,

I just wanted to add a motivation note: when writing these I-Ds our main motivation was key compression and the exportability of keys. The authoring companies found many applications where key compression is vital, and with binary blobs it is harder or impossible to distinguish these compressed encodings from the "full key" version. Especially in settings where keys are exportable this can endanger interoperability between applications. 

I understand the concerns listed, and tweaks can always be made to e.g. ensure consistency with NIST specs, but I would note that in previous conversations multiple parties have expressed that the ASN.1 would be useful for this and it would be a waste to throw it out. However we will not continue pushing if this is the consensus, and in that case I would hope the drafts will be useful for something in the future.

Cheers (on behalf of myself),

Christine Cloostermans (-van Vredendaal)

Op do 27 apr 2023 om 22:14 schreef 'Tim Hollebeek' via pqc-forum <pqc-...@list.nist.gov>:

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SJ0PR14MB5489568120BB4992980AD6EE836A9%40SJ0PR14MB5489.namprd14.prod.outlook.com.

[Tony Arcieri]

On Tue, May 2, 2023 at 5:10 AM Christine Cloostermans <cvv...@gmail.com> wrote:

The authoring companies found many applications where key compression is vital, and with binary blobs it is harder or impossible to distinguish these compressed encodings from the "full key" version

The SEC1 Elliptic-Curve-Point-to-Octet-String encoding solved this by using a tag byte to distinguish compressed versus uncompressed encodings, which sidestepped the need to use ASN.1. Though even that's unnecessary, because compressed vs uncompressed could be inferred from the length alone.

--

Tony Arcieri