PQ KEM method names per draft iteration

[csosto-pk]

Hi folks,

Some collaborators are trying to interop our PQ SSH key exchange in NIST NCCOE's PQ Migration effort. As we are working through this, we will all try to interop with the ecdh-nistp256-kyber-512-sha256. It is supported in OQS OpenSSH and wolfSSH, which is great.

Now there is one concern about backwards compatibility. Someone that implements the method name ecdh-nistp256-kyber-512-sha256 today may have interop issues in a couple of years when Kyber has been slightly tweaked or something in the method has been tweaked in the draft and the peer implements the latest version. That is a concern for any RFC draft which changes over time.

To prevent such problems we could introduce a temporary identifier that basically creates a snapshot of the method in time. For example, we could rename ecdh-nistp256-kyber-512-sha256 to method name ecdh-nistp256-kyber-512r3-sha256-d00. That basically means the method is specific to the time it was implemented (Kyber-512 round 3 the way draft -00 explained the method). In the next change which breaks compatibility for that method, its name will change to something like ecdh-nistp256-kyber-512r4-sha256-d01 or something like that. So, old clients that were not upgraded would not be able to negotiate ecdh-nistp256-kyber-512r3-sha256-d00 any more and they would still interop using classical methods. When the RFC is ratified, the final standardized name would be ecdh-nistp256-kyber-512-sha256

I know this is not something we have done for TLS 1.3 group names, or SSH methods. But have you given it any thought? Would it be too much overhead to rename the method every time something underlying (KEM algorithm, or implementation detail) changes?

[baentsch]

Would it be too much overhead to rename the method every time something underlying (KEM algorithm, or implementation detail) changes?

Simple answer probably is "No": Speaking for the arguably equivalent TLS group names that I'm more familiar with, it surely would be possible to map them to specific liboqs versions (carrying specific Kyber versions); it's "just software" after all and "there's no problem in CS that cannot be solved by another level of indirection".

But I see the following implications/questions affecting any software where different algorithm versions are lifted to/exposed at "user level":

• Each user is made acutely aware that this is not a reliable/durable piece of software/cryptography the moment they configure it and thus might refrain from deploying it until finally standardized. This arguably would be goodness (stopping people considering things "final" that are not) so I'd find it good if every implementation at this point in time were using the name ecdh-nistp256-kyber-512-sha256-draft in your example.
• Bigger issue: Which entity defines "the need" for a name change -- and to which specific name? For example, what exactly constitutes "-d01"? A new hash over the KATs? Who maintains this name/KAT table? Why should the name change if a non-KAT-changing implementation change occurs? If done separately by each project, the (interop) problem would not be solved. If done by some "registrar", how far away is that from a real standardization?
• Practically, (sample) code / downstream integrations would need to be constantly upgraded as some PQ algorithm detail changes if that is encoded in a (configurable) name. I'm not sure everyone would appreciate this. It would be good and fair to require a name change once a standard has been finalized, but doing this more often I find problematic from a "practical acceptance" perspective (and more cumbersome than just replacing an outdated library -- which actually can happen automatically).

So, old clients that were not upgraded would not be able to negotiate ecdh-nistp256-kyber-512r3-sha256-d00 any more and they would still interop using classical methods.

This I find very risky: Is the suggestion that although PQ has been configured, the client shall silently fall back to classic crypto because of an algorithm version mismatch? Wouldn't it be more advisable to have users experience a real error (due to client and server not being able to interop via PQ due to actually different algorithms being used) such as to trigger a check of code/library version and a suitable upgrade?

In sum, I'd personally try to refrain from creating PQ "legacy software" (defined as code that can keep working in a future it wasn't written for) from the get-go, but rather standardize things more quickly. I do agree, though, that using names without some "draft" moniker can mislead users into thinking PQ is already as stable as classic crypto.

[csosto-pk]

Hi Michael @baentsch ,

Thx for the feedback.

Bigger issue: Which entity defines "the need" for a name change -- and to which specific name?

The way I think it should work is that every time you are making a compatibility breaking change, that is where you change the identifier. For example, if you change the combiner (in SSH the draft has option 1, 2a, 2b and 2c), or if there is a new Kyber Round 4 version. One example for TLS 1.3 is when the IETF draft switched from using the length of the key_share before the key/ciphertext itself. A later version of the draft removed the length, and that would trigger a new group identifier to negotiate.

The IETF draft should be responsible for incrementing this value imo. I mean for TLS 1.3, right now OQS OpenSSL is the source of truth, so OQS OpenSSL would be defining new identifiers for TLS 1.3 until the draft started defining them. But generally speaking, the IETF draft should be changing the identifiers per iteration (in the end only the final one is added in the IANA registry of course).

Practically, (sample) code / downstream integrations would need to be constantly upgraded as some PQ algorithm detail changes if that is encoded in a (configurable) name. I'm not sure everyone would appreciate this.

I think only the compatibility breaking changes warrant a new identifier. And to be honest, someone would not need to drop the old ones. No one needs to drop support for old identifiers, so that does not break backward compatibility. Only very up-to-date implementations would be negotiating the latest identifiers, older ones could still be functional with older ones.

In sum, I'd personally try to refrain from creating PQ "legacy software" (defined as code that can keep working in a future it wasn't written for) from the get-go, but rather standardize things more quickly.

I understand, and to be honest this has not been done well in the past either. Other RFC drafts have not been using a similar logic.

Let me rephrase my question, and focus on OpenSSH. As we are working through the draft, what if we added an extra identifier? Currently the draft includes SSH method names:

• ecdh-nistp256-kyber-512-sha256 which OQS OpenSSH supports already
• x25519-kyber-512-sha256@amazon.com which OQS OpenSSH does not support yet

What if we made them

• x25519-kyber-512r3-sha256-d05@amazon.com
• ecdh-nistp256-kyber-512r3-sha256-d05 This for now would be exactly the same as `ecdh-nistp256-kyber-512-sha256. It would only would change if the draft ended up changing the combiner or we have Kyber Round 4 etc.

Would OQS OpenSSH be willing to add support for these two in OQS OpenSSH?

[dstebila]

I agree that versioning the names makes sense, and in principle yes we should do that in OQS-OpenSSH. One tricky part is making sure we actually get the version naming correct, but we should be able to figure that out. As the underlying liboqs will only have one version of an algorithm available at a time, we won't be able to have multiple versions available -- e.g., once we migrate liboqs to kyber-512r3, we won't have kyber-512r2 available in the same binary.

[dstebila]

Regarding putting the draft identifier in, how do you plan to deal with increments to the draft that don't affect the actual technical details? For example, if d05 and d06 yield the same protocol, but just the text changes, what should be in the implementation?

• Stay with d05, skip d06
• Increment to d06 and and drop d05
• Have both d05 and d06 but treat them as different (even though we know they're equivalent)
• Have both d05 and d06 and treat them as interoperable

[csosto-pk]

Hi Douglas,

As the underlying liboqs will only have one version of an algorithm available at a time,

Agreed. OQS OpenSSH or any other implementation that is not worried about backwards compatibility would just keep updating the latest method name / identifier and it would just forget about the previous one. You would only support the latest version.

Often drafts put in TBD in the new identifiers when IANA has not assigned them. Basically we do the same thing and just put something in for implementers to implements.

Note that I am mostly focusing on OQS OpenSSH right now. OQS OpenSSL did not have any identifiers in the draft, so pretty much OQS historically defined the test identifiers. And updating them in the very early stages with all the algorithms would be hard. So, I am OK with the TLS 1.3 identifiers. I just want to address the OpenSSH problem now that we have a draft to follow.

Regarding putting the draft identifier in, how do you plan to deal with increments to the draft that don't affect the actual technical details? For example, if d05 and d06 yield the same protocol, but just the text changes, what should be in the implementation?

I think in this case we would skip 06 and stay at 05 . We would just use the 0x only for the next version that makes a compatibility breaking change. To avoid confusion, note that we could do it by just putting in ecdh-nistp256-kyber-512r3-sha256-tmp1, ecdh-nistp256-kyber-512r4-sha256-tmp2 etc if we did not want to tie it to the draft version. Other ways could be possible too.

[dstebila]

Makes sense, sounds good to me.

[csosto-pk]

Sorry, updating this again based on discussions. I think we are in agreement here.

After discussing it, we realized that the names as they are will not overlap in the final ratified version of the draft because there will be no Kyber. NIST will rename it to MLWE-KEM or something like that. Let's say we keep he names as they are in the draft for now

• ecdh-nistp256-kyber-512-sha256 which OQS OpenSSH supports already
• x25519-kyber-512-sha256@amazon.com which OQS OpenSSH does not support yet

Sorry, I take it back. I think I will change the draft to include the versioning even for the first version. That will be ecdh-nistp256-kyber-512r3-sha256-tbd1 and x25519-kyber-512r3-sha256-tbd1. We want to be backwards compatible.

In the next iteration of the draft that breaks backwards compatibility, update the names to follow the new nomenclature ecdh-nistp256-kyber-512r4-sha256-tbd2 and x25519-kyber-512r4-sha256-tbd2 or something like that.

@dstebila , @baentsch , @christianpaquin , we will submit a PR to update the name in OQS OpenSSH to support both ecdh-nistp256-kyber-512r3-sha256-tbd1 and ecdh-nistp256-kyber-512r3-sha256 so you don't break backwards compatibility.

Let us know if you are violently against this, so we don't go through the trouble.

[csosto-pk]

I think this can be closed since we have consensus. I will leave this to the OQS team if they agree.