Subject: [lamps] PKIX and related RFCs - definition of Key Packages

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 16 Jun 2021 20:53:24 +0000

I confess that until now I never bothered actually looking with a critical eye at RFC 5958, 5208, 5915 and such – because the apps that presumably use them to interoperate, were already written by somebody else and (sorta ;) working.

Now, as I’m looking at extending those definitions to Post-Quantum algorithms and parameters, I’m seeing what appears weird to me.

A lot of the ASN.1 definitions seem to describe how to package private keys. Considering that interoperability in the majority of cases is about applications communicating “over the wire” using S/MIME, CMS, TLS or IKE key exchange, etc. – the predominant need appears to be exchanging public (not private) keys?

Yet the definitions invest in the details of the private keys, leaving the public key as “BIT STRING OPTIONAL”. Why is it so?

IMHO, first – PublicKey should be OCTET STRING (probably not OPTIONAL), probably CONTAINING {}. Then, each specific IETF-accepted algorithm should have its own definition of how to serialize its public key, maybe wrapping the result into an OCTET STRING (usually this is done to allow parser that doesn’t understand the format, to skip this field)… 

Is it too late to rectify? And if I’m missing something, could you enlighten me please? Am I barking at the wrong tree altogether? If so, where is the public key serialization described, if not here? And why not here?

Thank you! And apologies for the exhibited ignorance.

Here are some examples of what I’m talking about:

ECPrivateKey ::= SEQUENCE {

     version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),

     privateKey     OCTET STRING,

     parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,

     publicKey  [1] BIT STRING OPTIONAL

   }

OneAsymmetricKey ::= SEQUENCE {

     version                   Version,

     privateKeyAlgorithm       PrivateKeyAlgorithmIdentifier,

     privateKey                PrivateKey,

     attributes            [0] Attributes OPTIONAL,

     ...,

     [[2: publicKey        [1] PublicKey OPTIONAL ]],

     ...

   }

PublicKey ::= BIT STRING

                     -- Content varies based on type of key. The

                     -- algorithm identifier dictates the format of

                     -- the key.

--

Regards,

Uri Blumenthal                              Voice: (781) 981-1638 

Secure Resilient Systems and Technologies   Cell:  (339) 223-5363

MIT Lincoln Laboratory                      

244 Wood Street, Lexington, MA  02420-9108      

Web:     https://www.ll.mit.edu/biographies/uri-blumenthal

Root CA: https://www.ll.mit.edu/llrca2.pem

There are two ways to design a system. One is to make is 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: Peter Gutmann <[email-masked]>
Date: Thu, 17 Jun 2021 06:19:51 +0000

Blumenthal, Uri - 0553 - MITLL <[email-masked]> writes:

>Yet the definitions invest in the details of the private keys, leaving the
>public key as “BIT STRING OPTIONAL”. Why is it so?

Cargo cult protocol design.  Back in the late 1980s someone decided that holes
containing keys had to be BIT STRINGs.  So today, thirty-plus years later,
holes containing keys are still (mostly) BIT STRINGs even though what's
present in the hole is always an OCTET STRING.

>A lot of the ASN.1 definitions seem to describe how to package private keys.
>Considering that interoperability in the majority of cases is about
>applications communicating “over the wire” using S/MIME, CMS, TLS or IKE key
>exchange, etc. – the predominant need appears to be exchanging public (not
>private) keys?

More cargo cult protocol design.  PKCS #8 specified the format for RSA private
keys but nothing else, for the simple reason that there was nothing else at
the time.  Then when people needed to store something other than RSA keys they
invented their own formats extending PKCS #8, principally led by OpenSSL (who
had the most need for it) but occasionally other vendors as well, whoever got
the most mindshare first.  The issue was resolved by PKCS #15 which specified
a general format for public and private keys, but everyone ignored that and
invented their own new format for each new public-key algorithm.

As a result, when you write an RFC specifying the format for public keys for
algorithm X for, for example, S/MIME, you also need to specify the private-key
format even though it has nothing to do with S/MIME.  Rot bilong kago.

(And as a general note, a lot of the WTF?!!? stuff in PKIX is explainable
through cargo cult protocol design, it's not just these two).

Peter.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 13:06:50 +0000

> I think the short answer is that public keys are usually exchanged by sending certificates.

I'm not sure I understand - private keys usually are not exchanged at all, and yet there's a whole bunch of ASN.1 stuff describing them.

> Raw public keys that are not associated with an identity can lead to subtle security
> vulnerabilities (Mallory swaps Mallory's public key for Alice's without Bob noticing). 

This is supposed to be not about what good a standalone public key is - but about how to represent and encode that public key in an interoperable way. Whether such encoding makes sense outside of any context is a totally different question, which to me seems irrelevant to the main one - how to encode a public key that is not a simple big integer.

> Sorry to be the bearer of bad news, but you may be headed for a serious encounter
> with X.509, e.g., via RFC 5280.

That is indeed bad news, but on the other hand - a good start. __

>    present in the hole is always an OCTET STRING.

Excellent. That means there's no hidden wisdom in there, and I can (and will) in my design revert this to what Common Sense suggests: an OCTET STRING CONTAINING the specific format/encoding structure that a specific algorithm (e.g., lattice-based) would require for ensuring an app can correctly decode it in an interoperable way.

>    >  .  .  . [though]  .  .  . the predominant need appears to be exchanging public
>    > (not private) keys?
>
>    the time.  .  .  .

Hmm... What would happen if in a new document I choose not to specify private-key format...? 
Given the fact that it's (practically) never present on the wire, and compliance/interoperability for its implementation cannot be tested?

>    through cargo cult protocol design, it's not just these two).

I see. Thank you very much for explaining - unfortunately, it makes a lot of sense. ☹

On the other hand, it seems to mean that (due to this lack of definitions) there's nothing to be backward-compatible with, so one can (finally, hopefully, maybe) do it right...

Thanks!

---

From: Russ Housley <[email-masked]>
Date: Thu, 17 Jun 2021 09:50:45 -0400

> I'm not sure I understand - private keys usually are not exchanged at all, and yet there's a whole bunch of ASN.1 stuff describing them.

Yes, this is needed.  For example, PKCS#12 can be used to move a private key from one device to another.

Russ

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 17 Jun 2021 17:36:15 +0300

On Thu, Jun 17, 2021 at 01:06:50PM +0000, Blumenthal, Uri - 0553 - MITLL wrote:
> 
> This is supposed to be not about what good a standalone public key is
> - but about how to represent and encode that public key in an
> interoperable way. Whether such encoding makes sense outside of any
> context is a totally different question, which to me seems irrelevant
> to the main one - how to encode a public key that is not a simple big
> integer.

Looks like they are even simpler octet strings. :-> Tho there does not
seem to be an operation that takes in private key an pulls public key
out of that.

I took a look at a finalist PQC KEM (Kyber) and a finalist PQC signature
(Dilithium). Seems like everything that is meant to be stored or
transported is an octet string. This includes public keys and private
keys.

Here is what Kyber API looks like (per each variant):

- generate_key() -> (public_key:octets, private_key:octets)
- encapsulate(public_key:octets) -> (ciphertext:octets, shared_sec:octets)
- decapsulate(private_key:octets,ciphertext:octets) -> shared_sec:octets

And Dilithium API (per SSA variant):

- generate_key() -> (public_key:octets, private_key:octets)
- sign(private_key:octets,message:octets) -> signature:octets
- verify(public_key:octets,message:octets,signature:octets) -> ok:boolean

I think this is representative of other KEMs and signatures in NISTPQC.

And furthermore for Kyber/Dilithium, per variant the lengths of all
outputs are fixed:

Variant:	sk:	pk:	ct/sig:		ss:
Kyber512	1632	800	768		32
Kyber768	2400	1184	1088		32
Kyber1024	3168	1568	1568		32
Dilithium2	2528	1312	2420		N/A
Dilithium3	4000	1952	3293		N/A
Dilithium5	4864	2592	4595		N/A

sk => Secret key (bytes)
pk => Public key (bytes)
ct => Ciphertext (bytes)
sig => Signature (bytes)
ss => Shared secret (bytes)

(I think there are some variants of Falcon that have variable signature
size; however it is still always integral number of octets, and taken/
returned as an octet string.)

-Ilari

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 15:09:54 +0000

On 6/17/21, 10:37, "Ilari Liusvaara" <[email-masked]> wrote:
>    > .  .  .  how to encode a public key that is not a simple big integer.
>
>    Looks like they are even simpler octet strings. :-> 

Yes - the question is now to *unwrap* those keys from simple octet string in an architecture-independent way.

>    transported is an octet string. This includes public keys and private

Yes. My question is: if I create that OCTET STRING with one app on a 32-bit Big-Endian machine, and attempt to decode it with a different app (i.e., not the same source base) on a 64-bit Little-Endian machine - would it work correctly?

>  I think this is representative of other KEMs and signatures in NISTPQC.

Yes it is, caveat - answers to my question.

>    returned as an octet string.)

All variants of Falcon that I know of produce variable-size signature, but that's not my concern. 

To repeat myself, my concern is how to create (and unwrap) those octet strings in an interoperable across architectures and platforms way. And whether defining the appropriate encoding (e.g., maybe defining how a vector of integers is encoded into a SEQUENCE that would be contained in that OCTET STRING) would help this.

TNX

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 17 Jun 2021 18:40:31 +0300

On Thu, Jun 17, 2021 at 03:09:54PM +0000, Blumenthal, Uri - 0553 - MITLL wrote:
> 
> Yes. My question is: if I create that OCTET STRING with one app on a
> 32-bit Big-Endian machine, and attempt to decode it with a different
> app (i.e., not the same source base) on a 64-bit Little-Endian machine
> - would it work correctly?

Yes, it will work correctly (modulo bugs and intentional
incompatbilities). After all, definition of octet string is string over
alphabet consisting of integers [0,255]. This definition is independent
of bitness and endianess of platform. Nor do octet strings have bit-
endianess ("octet strings" that do are actually bit strings).

It is not like such algorithms are a new class: Ed25519/Ed448 has defined
public and private key encodings, and that always uses octet strings for
all things meant to be stored or transported.

And if algorithm has octet string input/output, any nontrivial encoding
is increased complexity on code that is ill-equipped to handle such
complexity. So trying to expand the thing in any way is very bad idea.
Not to mention that the built-in encodings used are often optimized for
size (sometimes to the last byte), so any nontrivial encoding also
bloats the data (and even if it is not optimize to the last byte, ASN.1
overhead would eat any savings).

-Ilari

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Thu, 17 Jun 2021 16:51:23 +0100

> endianess ("octet strings" that do are actually bit strings).
Hi,

Yeah, I don't see problems with this.

For PQC: The NIST API and test vector requirement, fortunately, has helped
with that. Since the PQC standardization effort started in 2016, all
supplied reference and optimized implementations had to comply with a
single set of test vectors, supplied by the design teams. The test vectors
are octet strings. Many of us use those for compliance testing of new and
old implementations.

The better algorithms are very specific about encodings, but if in doubt I
just go to the test vectors to check. So we already have a multitude of
interoperable implementations (hardware implementations, different
languages, embedded, SIMD, etc).

My expectation is that (with a few improvements) a similar test vector
system will be eventually be used for high-level CAVP/ACVT (FIPS 140-3)
testing of NIST algorithm implementations. There is no ASN.1 in the
encoding or decoding of keys, ciphertexts, or signatures, etc.

As it is, those byte strings go directly even into hardware modules. We
view pk/sk/ct/sig octet strings as well defined in the context of a
specific PQC parameter set. Note that PQC parameter sets are very specific
and discrete, a bit like elliptic curve groups (not "sliders" like the RSA
keys). So I personally hope IETF wouldn't go into unwrapping those octet
strings too much, just assign OIDs to the "blobs", or at least give an
option to use blobs.

There are some wrinkles that will no doubt be ironed out in the
standardization process; for example, the 16-bit elements in FrodoKEM
private keys in test vectors are little-endian while public values are in
network byte order. Furthermore, the algorithms that utilize NTT may want
to store some private key material in the "NTT Domain" rather than as
normal mod q integer vectors. One particular NTT representation may not be
ideal for implementation on another platform. But this aspect of private
key encoding is similar to "CRT" values for RSA private keys.

Uri:

> To repeat myself, my concern is how to create (and unwrap) those octet
> strings in an interoperable across architectures and platforms way. And
> whether defining the appropriate encoding (e.g., maybe defining how a
> vector of integers is encoded into a SEQUENCE that would be contained in
> that OCTET STRING) would help this.
>

I doubt that unwrapping PQC octet strings into vectors of integers is
particularly helpful. As you know, the implementations compress bit fields
and secrets in very specific ways that can be interpreted only in the
context of that algorithm. Kyber field elements are 13 bits, for example,
and some algorithms use quite complex encoding schemes. This unwrapping
would directly make testing more difficult.

Some additional notes on testing:

- A detached signature format needs to be explicitly defined in addition to
the "signed envelope" format from NIST. However, I hope that this is a byte
string too.

- The algorithms fail in very specific ways. A good test vector set needs
to include malformed signatures, ciphertexts, public keys.

- The minimalistic NIST PQC API required that the decapsulation and
signature operation can be completed without access to the public key (with
a private key only). This led to the situation where the public key is
often fully contained in the private key ( A Fujisaki-Okamoto CCA
decapsulation requires re-encryption and hence a public key, of course ).
If specified with an API that also has access to the public key for private
key operations, the private key can be made smaller in some cases as this
redundancy is removed.

- Furthermore, the major algorithms (Falcon, Kyber, Dilithium, NTRU, SIKE,
FrodoKEM, McEliece) can be fairly easily be transformed into deterministic
versions where relatively short seed keys are used for key generation,
signature, decapsulation operations. This helps with testing of course, as
I can record those seeds along with NIST test vectors.

- The origin of this feature is a bit amusing; short-seed determinism was
not explicitly stated to be desirable (in the original call for algorithms
) but the "fake reference RBG" supplied by NIST was just horrendously slow
due to a programming oversight (a full AES-256 key schedule for each
CTR_DRBG output block) so many teams decided to only take a minimal seed
amount from that RNG and expand it with a good SHAKE implementation
themselves. This gave a very large advantage in benchmarking (as some
implementations spent 90% of cycles in the NIST RNG code).

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <[email-masked]> PQShield, Oxford UK.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 16:01:53 +0000

On 6/17/21, 11:42, "Ilari Liusvaara" <[email-masked]> wrote:
>    > My question is: if I create that OCTET STRING with one app on a

I don't think I made my question clear. I know that byte strings are the same - but since the integers that are encoded into that string have different representations on different platforms, my worry is recovering/re-interpreting the values into the correct (and different) representation.

>    complexity. So trying to expand the thing in any way is very bad idea.

Understood.

>    overhead would eat any savings).

I disagree here. ASN.1 is a descriptive format that is translated into various binary encodings.
While DER (traditionally used for certs, etc.) is indeed "verbose", other formats such as PER or OER are quite compact, and optimize not only to the byte but to the bit level.

---

From: Russ Housley <[email-masked]>
Date: Thu, 17 Jun 2021 12:16:25 -0400

> I don't think I made my question clear. I know that byte strings are the same - but since the integers that are encoded into that string have different representations on different platforms, my wo…

This has not been a major source of interoperability issues.  RSA uses integers, and the conversion to octets is specified in PKCS#1.  That approach has worked regardless of endian differences.

Russ

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 16:43:27 +0000

For PQC: The NIST API and test vector requirement, fortunately, has helped with that. Since the PQC standardization effort started in 2016, all supplied reference and optimized implementations had to comply with a single set of test vectors, supplied by the design teams. The test vectors are octet strings. Many of us use those for compliance testing of new and old implementations.

The better algorithms are very specific about encodings, but if in doubt I just go to the test vectors to check. So we already have a multitude of interoperable implementations (hardware implementations, different languages, embedded, SIMD, etc). 

My expectation is that (with a few improvements) a similar test vector system will be eventually be used for high-level CAVP/ACVT (FIPS 140-3) testing of NIST algorithm implementations. There is no ASN.1 in the encoding or decoding of keys, ciphertexts, or signatures, etc. 

In other words, it’s the application’s job to do this right – and therefore, ASN.1 definitions do not need to go inside of those OCTET STRINGs. Right?

As it is, those byte strings go directly even into hardware modules. We view pk/sk/ct/sig octet strings as well defined in the context of a specific PQC parameter set. Note that PQC parameter sets are very specific and discrete, a bit like elliptic curve groups (not "sliders" like the RSA keys). So I personally hope IETF wouldn't go into unwrapping those octet strings too much, just assign OIDs to the "blobs", or at least give an option to use blobs.  .  .  .  I doubt that unwrapping PQC octet strings into vectors of integers is particularly helpful. As you know, the implementations compress bit fields and secrets in very specific ways that can be interpreted only in the context of that algorithm. Kyber field elements are 13 bits, for example, and some algorithms use quite complex encoding schemes. This unwrapping would directly make testing more difficult.

Understood. If it’s counterproductive unwrapping those blobs – it’s simple enough to just assign them the appropriate labels (aka, OIDs) and be done with it. That’s what I’m planning to do then.

- A detached signature format needs to be explicitly defined in addition to the "signed envelope" format from NIST. However, I hope that this is a byte string too.

Yep.

- The algorithms fail in very specific ways. A good test vector set needs to include malformed signatures, ciphertexts, public keys.

;-) Noted.

- The minimalistic NIST PQC API required that the decapsulation and signature operation can be completed without access to the public key (with a private key only). This led to the situation where the public key is often fully contained in the private key ( A Fujisaki-Okamoto CCA decapsulation requires re-encryption and hence a public key, of course ). If specified with an API that also has access to the public key for private key operations, the private key can be made smaller in some cases as this redundancy is removed.

Good point. 

I wonder why it wasn’t brought up with NIST, either on their PQC mailing list, or at the one of the PQC workshops.

- Furthermore, the major algorithms (Falcon, Kyber, Dilithium, NTRU, SIKE, FrodoKEM, McEliece) can be fairly easily be transformed into deterministic versions where relatively short seed keys are used for key generation, signature, decapsulation operations. This helps with testing of course, as I can record those seeds along with NIST test vectors. 

Noted, thanks.

- The origin of this feature is a bit amusing; short-seed determinism was not explicitly stated to be desirable (in the original call for algorithms ) but the "fake reference RBG" supplied by NIST was just horrendously slow due to a programming oversight (a full AES-256 key schedule for each CTR_DRBG output block) so many teams decided to only take a minimal seed amount from that RNG and expand it with a good SHAKE implementation themselves. This gave a very large advantage in benchmarking (as some implementations spent 90% of cycles in the NIST RNG code).

:-)

And thank you very much for an excellent explanation!

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Thu, 17 Jun 2021 21:54:10 +0100

On Thu, Jun 17, 2021 at 5:43 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> In other words, it’s the application’s job to do this right – and
> therefore, ASN.1 definitions do *not* need to go inside of those OCTET
> STRINGs. Right?
>

Hi Uri,

Yep. The way things are for PQC, generic APIs handle { public keys,
signatures, ciphertexts, private keys, .. } as octet strings, and the
interpretation of those bytes is defined in the algorithm specifications
and reference information.

As noted by Ilari, modern elliptic curve point encodings are similarly
stated simply as octet strings, not as pairs of "integers" (See e.g. RFC
7748, Sect 5 or RFC8032, Sect 2.)  Much of this has to do with the security
aspects of input validation; ASN.1 en/decoding is difficult to guarantee to
be constant time, for example. Hence there is a general acceptance that
encoding and decoding of sensitive security parameters is an
algorithm-specific matter and generic mechanisms (like ASN.1) can do more
harm than good.

> option to use blobs.  .  .  .  I doubt that unwrapping PQC octet strings
> into vectors of integers is particularly helpful. As you know, the
> implementations compress bit fields and secrets in very specific ways that
> can be interpreted only in the context of that algorithm. Kyber field
> elements are 13 bits, for example, and some algorithms use quite complex
> encoding schemes. This unwrapping would directly make testing more
> difficult.
>
>
>
> Understood. If it’s counterproductive unwrapping those blobs – it’s simple
> enough to just assign them the appropriate labels (aka, OIDs) and be done
> with it. That’s what I’m planning to do then.
>

Great. In addition to OIDs, the integration into PKI will of course require
a few additional definitions, so labels alone may not be sufficient. They
may still be too generic.

Example: For Dilithium PKI integration, I'd probably define an OID for a
specific randomized hash mechanism (with other hash functions than the
SHAKE used by Dilithium internally) for generating and verifying a
*detached* Dilithium signature, rather than just for "Dilithium".
Integrating Kyber in S/MIME would similarly require specification of how to
turn a KEM into a PKE (via arbitrary AEADs, specified via their OIDs,
probably). So the Kyber OID would refer to that mechanism in addition to
the internal Kyber parameter set and behavioral definitions (i.e. "Kyber"
the KEM).

Cheers,
- markku

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 17 Jun 2021 17:19:34 -0400

I agree with much of Uri's frustration here. My concern is the meta level.
If LAMPS is going to ever close, we have to make sure we are not going to
need something similar in future. Which means that we need to define what
is required to specify a cryptographic algorithm so it is available for use
with IETF protocols.

Note that adding an algorithm to a registry does not mean it is approved
for use by a particular protocol.

CMS serves a much wider audience than S/MIME. PKIX, a wider audience than
either the WebPKI or PKI in general. Same for JOSE, XML Signature and
Encryption, etc. etc.

So I conclude that one of the exit criteria for LAMPS should be a
document describing the list of things that need to be specified so that an
algorithm can be used in various specific IETF protocols and conversely,
what applications using the IETF maintained IANA registries can expect.

I do not want to get into discussions of why the decisions of some
working group ten years ago on algorithm requirements should bind some
other group doing something different today. HTTP is not based on MIME but
it uses the same IANA registry. That is the correct approach in my view.

Going forward, I see no reason why it should be necessary to specify
separate identifiers for the use of a particular algorithm in every
different application protocol. The ASN.1 world is going to need OIDs for
quite some time and the JOSE world is going to be needing text based
labels. The XML world consumes URIs but there is no reason we couldn't
specify a URN prefix to the JOSE labels and use that to avoid further
maintenance issues.

TLS and IPSEC both operate at a layer that is sufficiently deep that we
should just let them do their own thing. And PEM probably isn't much of a
concern going forward.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 22:00:37 +0000

Yep. The way things are for PQC, generic APIs handle { public keys, signatures, ciphertexts, private keys, .. } as octet strings, and the interpretation of those bytes is defined in the algorithm specifications and reference information.

Good, thanks!

If it’s counterproductive unwrapping those blobs – it’s simple enough to just assign them the appropriate labels (aka, OIDs) and be done with it. That’s what I’m planning to do then.

Great. In addition to OIDs, the integration into PKI will of course require a few additional definitions, so labels alone may not be sufficient. They may still be too generic.

.  .  .  .  .

Example: For Dilithium PKI integration, I'd probably define an OID for a specific randomized hash mechanism (with other hash functions than the SHAKE used by Dilithium internally) for generating and verifying a detached Dilithium signature, rather than just for "Dilithium". Integrating Kyber in S/MIME would similarly require  .  .  .  .  .

Oh yes – I intend for those OIDs to identify very specific (unambiguous) cases, including everything you outlined above, so that the OCTET STRING that follows can be interpreted and processed unambiguously.

TNX

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Jun 2021 22:06:59 +0000

Thank you, and I concur.

--

Regards,

Uri

                                                                                                                                     -  C. A. R. Hoare

From: Spasm <[email-masked]> on behalf of Phillip Hallam-Baker <[email-masked]>
Date: Thursday, June 17, 2021 at 17:20
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: [lamps] META Re: [saag] PKIX and related RFCs - definition of Key Packages

I agree with much of Uri's frustration here. My concern is the meta level. If LAMPS is going to ever close, we have to make sure we are not going to need something similar in future. Which means that we need to define what is required to specify a cryptographic algorithm so it is available for use with IETF protocols.

Note that adding an algorithm to a registry does not mean it is approved for use by a particular protocol. 

CMS serves a much wider audience than S/MIME. PKIX, a wider audience than either the WebPKI or PKI in general. Same for JOSE, XML Signature and Encryption, etc. etc.

So I conclude that one of the exit criteria for LAMPS should be a document describing the list of things that need to be specified so that an algorithm can be used in various specific IETF protocols and conversely, what applications using the IETF maintained IANA registries can expect.

I do not want to get into discussions of why the decisions of some working group ten years ago on algorithm requirements should bind some other group doing something different today. HTTP is not based on MIME but it uses the same IANA registry. That is the correct approach in my view.

Going forward, I see no reason why it should be necessary to specify separate identifiers for the use of a particular algorithm in every different application protocol. The ASN.1 world is going to need OIDs for quite some time and the JOSE world is going to be needing text based labels. The XML world consumes URIs but there is no reason we couldn't specify a URN prefix to the JOSE labels and use that to avoid further maintenance issues.

TLS and IPSEC both operate at a layer that is sufficiently deep that we should just let them do their own thing. And PEM probably isn't much of a concern going forward.

---

From: Sean Turner <[email-masked]>
Date: Mon, 21 Jun 2021 11:49:56 -0400

-saag

> On Jun 16, 2021, at 16:53, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> 

Uri,

In ECPrivateKey, publicKey is OPTIONAL because that’s the way it was defined in the SECG specifications (see c.4 of SEC1). The text in c.4 leads me to believe the entire structure was created to support providing CA-generated keys to the EE. If the CA creates the keys and generates a certificate, there is no need to return the raw public key in the structure; you can get the public key from the certificate.

In OneAsymmetricKey, I followed the same pattern.

As far as identifying the PublicKey serialization, why can’t you use the algorithm identifier?

spt

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 23 Jun 2021 10:15:59 -0400

On Thu, Jun 17, 2021 at 11:51 AM Markku-Juhani O. Saarinen
<[email-masked]> wrote:
>
> On Thu, Jun 17, 2021 at 4:40 PM Ilari Liusvaara <[email-masked]> wrote:
>>
> As it is, those byte strings go directly even into hardware modules. We view pk/sk/ct/sig octet strings as well defined in the context of a specific PQC parameter set. Note that PQC parameter sets are very specific and discrete, a bit like elliptic curve groups (not "sliders" like the RSA keys). So I personally hope IETF wouldn't go into unwrapping those octet strings too much, just assign OIDs to the "blobs", or at least give an option to use blobs.
>
> There are some wrinkles that will no doubt be ironed out in the standardization process; for example, the 16-bit elements in FrodoKEM private keys in test vectors are little-endian while public values are in network byte order. Furthermore, the algorithms that utilize NTT may want to store some private key material in the "NTT Domain" rather than as normal mod q integer vectors. One particular NTT representation may not be ideal for implementation on another platform. But this aspect of private key encoding is similar to "CRT" values for RSA private keys.
>
> Uri:
>>
> I doubt that unwrapping PQC octet strings into vectors of integers is particularly helpful. As you know, the implementations compress bit fields and secrets in very specific ways that can be interpreted only in the context of that algorithm. Kyber field elements are 13 bits, for example, and some algorithms use quite complex encoding schemes. This unwrapping would directly make testing more difficult.
>

OIDs are already showing up in the wild. Botan has some private
assignments at https://botan.randombit.net/handbook/dev_ref/oids.html.

It is reminiscent of Bernstein's x25519 gear. There are multiple OIDs
in the wild that a program must recognize to interoperate.

It would probably be useful to get OID assignments to avoid what
happened with x25519.

Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 23 Jun 2021 10:44:57 -0400

When do we want them - NOW!

I second Jeffrey's request, we have to get OIDs and JOSE tags defined for
PQC algorithms now or else we will have half a dozen different OIDs for the
same algorithm by the time we need to use them.

Of the current finalists, only one, SIKE appears to be compatible with the
Threshold techniques I am using in the Mesh so I will be implementing that
one irregardless of the final NIST choice. I would prefer that either IETF
or the group itself specify an OID etc.

This particular contest is not the same as previous NIST contests because
it may be a decade before these algorithms are being widely used, the
principles behind the algorithms are very new, there are major performance
and functional differences, etc. etc. If I could use more than one of the
proposals, I would probably implement two or more just to stress test the
code.

That said, maybe we should ask the groups to specify their preferred
identifiers as part of their submissions.

On Wed, Jun 23, 2021 at 10:16 AM Jeffrey Walton <[email-masked]> wrote:

> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm
>

---

From: Russ Housley <[email-masked]>
Date: Wed, 23 Jun 2021 11:06:50 -0400

Our charter says that we will use the NIST-assigned OIDs.  Please send the request for OIDs to NIST.

Russ

> On Jun 23, 2021, at 10:44 AM, Phillip Hallam-Baker <[email-masked]> wrote:
> 
> I second Jeffrey's request, we have to get OIDs and JOSE tags defined for PQC algorithms now or else we will have half a dozen different OIDs for the same algorithm by the time we need to use them.
> 
> Of the current finalists, only one, SIKE appears to be compatible with the Threshold techniques I am using in the Mesh so I will be implementing that one irregardless of the final NIST choice. I would prefer that either IETF or the group itself specify an OID etc.
> 
> This particular contest is not the same as previous NIST contests because it may be a decade before these algorithms are being widely used, the principles behind the algorithms are very new, there are major performance and functional differences, etc. etc. If I could use more than one of the proposals, I would probably implement two or more just to stress test the code.
> 
> 
> That said, maybe we should ask the groups to specify their preferred identifiers as part of their submissions.
> 
> 
> 
> On Wed, Jun 23, 2021 at 10:16 AM Jeffrey Walton <[email-masked] <mailto:[email-masked]>> wrote:
> assignments at https://botan.randombit.net/handbook/dev_ref/oids.html <https://botan.randombit.net/handbook/dev_ref/oids.html>.
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 23 Jun 2021 15:36:45 +0000

It was my understanding that the NIST usually follows IANA/IETF regarding OID assignment? If so, it should be easy enough to request and receive the charter correction.

In any case, the NIST is highly unlikely to assign OIDs to pre-selection (e.g., Round 3) candidates. Nor is it likely to assign OIDs to algorithms not selected at the end of Round 3. Other countries may (and probably will) choose different algorithms. 

In short, it appears that OIDs are needed now, the best entity to assign them is IETF/IANA, and this WG is as good a starting place as any.

I’m calling for consensus.

Thanks!

 

 

 

Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 23 Jun 2021 11:46:13 -0400

Since NIST has tweaked algorithms in the past after the close of
competition, they probably can't assign OIDs yet. Also, at one remove, the
'prize' in this competition might be fairly considered to be the assignment
of an OID in the NIST arc.

One peculiarity of such competitions is that after they start, the bulk of
the contestants attention is naturally focused on all the submissions
except their own. Once they have placed their bet, there is little they can
do to improve it. So the way to win is to attempt to knock down rival
claims.

So maybe asking entrants to specify a pro-tem OID and show them how to
register an arc (if they haven't already) would be sufficient.

That way, we still end up dealing with two OIDs in the end but two is a lot
better than a half dozen.

On Wed, Jun 23, 2021 at 11:37 AM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> It was my understanding that the NIST usually follows IANA/IETF regarding
> OID assignment? If so, it should be easy enough to request and receive the
> charter correction.
>
>
>
> In any case, the NIST is highly unlikely to assign OIDs to pre-selection
> (e.g., Round 3) candidates. Nor is it likely to assign OIDs to algorithms
> *not* selected at the end of Round 3. Other countries may (and probably
> will) choose different algorithms.
>
>
>
> In short, it appears that OIDs are needed now, the best entity to assign
> them is IETF/IANA, and this WG is as good a starting place as any.
>
>
>

---

From: Russ Housley <[email-masked]>
Date: Wed, 23 Jun 2021 11:59:04 -0400

NIST has assigned many OIDs:  https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration

When NIST approves the use of algorithms that were made standards by others, then NIST will use the OIDs that ware already assigned.  The stateful hash-based signatures is one example.

I do not think that the LAMPS WG should get ahead of NIST.  However, we can do a lot of work prior to OID assignment, such as figuring out the information, if any, that needs to be included in parameters.

Russ

> On Jun 23, 2021, at 11:36 AM, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> 
>> On Jun 23, 2021, at 10:44 AM, Phillip Hallam-Baker <[email-masked] <mailto:[email-masked]>> wrote:
>>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 23 Jun 2021 19:23:52 +0000

Understood, thanks.

I do not think that the LAMPS WG should get ahead of NIST.  

As I said, one problem I see with the above is that NIST would only assign OIDs to the algorithms it selects in the end of PQC. By that time, other applications may already use some of the finalists. Also, applications already started experimenting (e.g., see Open Quantum Safe project, and their fork of OpenSSL) – and having “real” OIDs to use would alleviate the need for kludges they currently have to employ.

This is why I think it makes sense for IETF in general, and LAMPS in particular, to assign OIDs for all of the NIST PQC Round 3 finalists. 

Once the NIST picks “the one”, let them re-use the IETF OID or assign a brand new one from their MIB space.

However, we can do a lot of work prior to OID assignment, such as figuring out the information, if any, that needs to be included in parameters.

Yes, let’s do that regardless of whether we decide to assign OIDs here or not.  

Thanks!

Thanks!

 

 

 

Jeff

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Wed, 23 Jun 2021 21:10:06 +0100

On Wed, Jun 23, 2021 at 8:24 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> As I said, one problem I see with the above is that NIST would only assign
> OIDs to the algorithms it selects in the end of PQC. By that time, other
> applications may already use some of the finalists. Also, applications
> already started experimenting (e.g., see Open Quantum Safe project, and
> their fork of OpenSSL) – and having “real” OIDs to use would alleviate the
> need for kludges they currently have to employ.
>
>
>
> This is why I think it makes sense for IETF in general, and LAMPS in
> particular, to assign OIDs for all of the NIST PQC Round 3 finalists.
>

Hi,

Yes, But what would that OID specify exactly? Perhaps this LAMPS would like
to do things like:

1. Specify how to use the PQC algorithms to create *detached signatures*
(not message+signature combinations with a fixed hash and arbitrary
formatting, as used in the NIST competition).
2. Specify how to use general hash functions such as SHA-2 with them (also
not defined by NIST). The obvious, non-randomized way of doing this breaks
their security, and must be avoided. ( Yes, I know that the internal XOFs
are harder to change/specify, but this needs to be discussed in an RFC. )

So after such definitions, the OID could refer to that formatting/padding
method rather than the plain "algorithm".. after all we don't use OIDs that
refer to plain "RSA" covering all of its use cases and PKCS padding methods
either. At least the above two steps would be necessary to integrate PQC
into X.509 PKI framework. Similarly, to use KEMs for some specific purpose,
such as public-key encryption, requires specification for the formatting of
the KEM-DEM/AEAD combination. LAMPS can assign an OID to that specific
formatting + algorithm combination after it is defined.

I don't see the existence of OID numbers for plain algorithms without
versioning as not as a prerequisite for standards definition work but as a
plainly harmful as it leaves many things up for interpretation, even if the
internal parameters are fixed (and PQC algorithms have a lot of security
parameters).

By the way, this is not something that stops me from writing
Internet-Drafts, which I'd see as an useful activity, unlike OIDs for
ambiguous algorithm names. If someone wants an OID for, say,
Falcon-1024-Round3.0, I could probably assign it within a day from our PEN
(IANA has assigned the tree under 1.3.6.1.4.1.54575 to PQShield) .. it's
just a matter of asking for a permission from the design team. Note that
the OID would be for that specific version since I know that Falcon will be
changed soon. Dilithium has already been updated during Round3 -- v3.1 had
substantial functional changes in February (a couple of internal parameters
and a few other things). Hence the current version (
https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
) is not compatible with the one submitted to Round 3 last October.

So, I'd suggest defining a temporary OID yourself or get an OID from the
design teams if you want to use them in applications or Internet Drafts at
this stage. But I see the concrete definition of how PQC algorithms are
used in IETF protocols as an useful step.

Cheers,
- markku

> However, we can do a lot of work prior to OID assignment, such as figuring
> out the information, if any, that needs to be included in parameters.
>
>
>

---

From: Russ Housley <[email-masked]>
Date: Wed, 23 Jun 2021 16:16:08 -0400

Markku and Uri:

I think that LAMPS can do item 1 and item 2 below under the current charter.  However, I thing there would be TBD in the OIDs that could be filled when the competition is finished.  The charter says that the algorithms need to be vetted by NIST or the CFRG.

Russ

> On Jun 23, 2021, at 4:10 PM, Markku-Juhani O. Saarinen <[email-masked]> wrote:
> 
> On Wed, Jun 23, 2021 at 8:24 PM Blumenthal, Uri - 0553 - MITLL <[email-masked] <mailto:[email-masked]>> wrote:
> Yes, But what would that OID specify exactly? Perhaps this LAMPS would like to do things like:
> 
> 1. Specify how to use the PQC algorithms to create detached signatures (not message+signature combinations with a fixed hash and arbitrary formatting, as used in the NIST competition).
> 2. Specify how to use general hash functions such as SHA-2 with them (also not defined by NIST). The obvious, non-randomized way of doing this breaks their security, and must be avoided. ( Yes, I know that the internal XOFs are harder to change/specify, but this needs to be discussed in an RFC. )
> 
> So after such definitions, the OID could refer to that formatting/padding method rather than the plain "algorithm".. after all we don't use OIDs that refer to plain "RSA" covering all of its use cases and PKCS padding methods either. At least the above two steps would be necessary to integrate PQC into X.509 PKI framework. Similarly, to use KEMs for some specific purpose, such as public-key encryption, requires specification for the formatting of the KEM-DEM/AEAD combination. LAMPS can assign an OID to that specific formatting + algorithm combination after it is defined.
> 
> I don't see the existence of OID numbers for plain algorithms without versioning as not as a prerequisite for standards definition work but as a plainly harmful as it leaves many things up for interpretation, even if the internal parameters are fixed (and PQC algorithms have a lot of security parameters). 
> 
> By the way, this is not something that stops me from writing Internet-Drafts, which I'd see as an useful activity, unlike OIDs for ambiguous algorithm names. If someone wants an OID for, say, Falcon-1024-Round3.0, I could probably assign it within a day from our PEN (IANA has assigned the tree under 1.3.6.1.4.1.54575 to PQShield) .. it's just a matter of asking for a permission from the design team. Note that the OID would be for that specific version since I know that Falcon will be changed soon. Dilithium has already been updated during Round3 -- v3.1 had substantial functional changes in February (a couple of internal parameters and a few other things). Hence the current version ( https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf <https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf> ) is not compatible with the one submitted to Round 3 last October. 
> 
> So, I'd suggest defining a temporary OID yourself or get an OID from the design teams if you want to use them in applications or Internet Drafts at this stage. But I see the concrete definition of how PQC algorithms are used in IETF protocols as an useful step.
> 
> Cheers,
> - markku
> 
> Dr. Markku-Juhani O. Saarinen <[email-masked] <mailto:[email-masked]>> PQShield, Oxford UK.
>  
>  
> 
> On Jun 23, 2021, at 11:36 AM, Blumenthal, Uri - 0553 - MITLL <[email-masked] <mailto:[email-masked]>> wrote:
> 
>  
>

---

From: "Markku-Juhani O. Saarinen" <[email-masked]>
Date: Wed, 23 Jun 2021 21:40:32 +0100

On Wed, Jun 23, 2021 at 9:16 PM Russ Housley <[email-masked]> wrote:

> Markku and Uri:
>
> I think that LAMPS can do item 1 and item 2 below under the current
> charter.  However, I thing there would be TBD in the OIDs that could be
> filled when the competition is finished.  The charter says that the
> algorithms need to be vetted by NIST or the CFRG.
>
>
Yeah.. I'd like to add that OIDs from PEN trees would be appropriate only
for Informational RFCs and perhaps for test vectors / interoperability in
the draft stage, not final standards track deliverables. I've used such
private things for hash functions ( RFC 7693 ), and I recall that the
Certificate Transparency OIDs are simply under Google's private PEN tree,
but those RFCs are informational.

Cheers,
- markku

>> As I said, one problem I see with the above is that NIST would only
>> assign OIDs to the algorithms it selects in the end of PQC. By that time,
>> other applications may already use some of the finalists. Also,
>> applications already started experimenting (e.g., see Open Quantum Safe
>> project, and their fork of OpenSSL) – and having “real” OIDs to use would
>> alleviate the need for kludges they currently have to employ.
>>
>>
>>
>> However, we can do a lot of work prior to OID assignment, such as
>> figuring out the information, if any, that needs to be included in
>> parameters.
>>
>>
>>
>> Of the current finalists, only one, SIKE appears to be compatible with
>> the Threshold techniques I am using in the Mesh so I will be implementing
>> that one irregardless of the final NIST choice. I would prefer that either
>> IETF or the group itself specify an OID etc.
>>
>>
>>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 24 Jun 2021 02:46:52 +0000

Markku and Uri:

The main two concerns I have here are:
The NIST will select one algorithm, while implementations may need to interoperate using one of the “not-selected” finalists;
Leaving OIDs as TBD would preclude applications from experimenting and trying to interoperate today.

I’m perfectly OK with vetting the algorithms with CFRG and/or NIST. 

Note: Round 3 finalists have already been “vetted by NIST” – that’s how they got to where they are now. 😉

Thanks!

On Wed, Jun 23, 2021 at 8:24 PM Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:

Hi,

By the way, this is not something that stops me from writing Internet-Drafts, which I'd see as an useful activity, unlike OIDs for ambiguous algorithm names. If someone wants an OID for, say, Falcon-1024-Round3.0, I could probably assign it within a day from our PEN (IANA has assigned the tree under 1.3.6.1.4.1.54575 to PQShield) .. it's just a matter of asking for a permission from the design team. Note that the OID would be for that specific version since I know that Falcon will be changed soon. Dilithium has already been updated during Round3 -- v3.1 had substantial functional changes in February (a couple of internal parameters and a few other things). Hence the current version ( https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) is not compatible with the one submitted to Round 3 last October. 

Cheers,

- markku

 

Thanks!

Thanks!

 

 

 

Jeff