[Pqc-forum] Key Establishment for PQC algorithms
Moody, Dustin (Fed)
One important application is using public-key cryptography to securely establish a key to be used for symmetric encryption. NIST intends to standardize one or more schemes that enable semantically secure encryption or key encapsulation with respect to adaptive chosen ciphertext attack (IND-CCA2), for general use. This security definition is substantially similar to what we had in our original draft Call.
As a result of comments received, we are adding another option. While chosen ciphertext security is necessary for many existing applications, it is possible to implement a purely ephemeral key exchange protocol in such a way that only passive security is required from the encryption or KEM primitive. For these applications, NIST will consider standardizing an encryption or KEM scheme which provides semantic security with respect to chosen plaintext attack (IND-CPA).
As the KEM and public key encryption functionalities can generally be interconverted, unless the submitter specifies otherwise, NIST will apply standard conversion techniques to convert between schemes if necessary.
We would like your feedback.
Does this approach seem sound?
What (if any) changes would you suggest?
Dustin Moody
NIST
Markku-Juhani Olavi Saarinen
It would be disappointing if functionally Diffie-Hellman - type
Post-Quantum key exchange algorithms are no longer be solicited for
standardization by NIST. The proposed KEM is functionally equivalent
to public key encryption in the eyes of cryptographic engineers such
as myself anyway; using public key encryption for something other than
to encrypt secret key material for symmetric encryption and/or
authentication is not generally a good idea.
Especially hybrid schemes incorporating ECDH and some Post-Quantum
scheme offer a highly attractive and cost-effective way of ``future
proofing'' current cryptographic communication systems against future
attacks (i.e. an adversary intercepting and recording a session now
and breaking it when quantum computers become available). Here session
authentication may still be based on current PKI mechanisms as active
attacks requiring quantum computation are not seen as a current
threat.
In [1] Craig Costello and Patrick Longa introduce the ``Open Quantum
Safe'' project which has the goal of developing and testing such
algorithms ( https://openquantumsafe.org/ ). Proposals like ``New
Hope'' [2] have gained early traction, having already been
incorporated by Google in their BoringSSL library and Chrome Canary
browser. Also Microsoft has apparently made its this type of key
exchange their initial priority, with a stream of publications
focusing on Supersingular Isogeny Diffie-Hellman (SIDH) [3].
Cheers,
- markku
[1] Douglas Stebila and Michele Mosca, "Post-Quantum Key Exchange for
the Internet and the Open Quantum Safe Project". From SAC 2016 Invited
Talk. http://eprint.iacr.org/2016/1017.pdf
[2] Erdem Alkim, L?o Ducas, Thomas P?ppelmann, and Peter Schwabe.
"Post-quantum key exchange ? a new hope.". USENIX SECURITY 2016.
https://eprint.iacr.org/2015/1092.pdf
[3] Craig Costello, Patrick Longa, and Michael Naehrig, "Efficient
algorithms for supersingular isogeny Diffie-Hellman." CRYPTO 2016.
https://eprint.iacr.org/2016/413.pdf
Dr. Markku-Juhani O. Saarinen <mjos at iki.fi>
On Fri, Oct 28, 2016 at 7:27 PM, Moody, Dustin (Fed)
<dustin.moody at nist.gov> wrote:
> NIST received several comments regarding our request for a key-exchange
> algorithm. As a result, we are clarifying what exactly we are looking for.
> In our revised call, instead of using the term key-exchange we will be
> asking for Key Encapsulation Mechanisms (KEMs). While the term KEM has been
> widely used in academic literature, previous NIST publications have tended
> to describe KEMs using the term ?key agreement? (also known as key
> exchange). KEM schemes consist of algorithms for key generation,
> encapsulation, and decapsulation.
>
> One important application is using public-key cryptography to securely
> establish a key to be used for symmetric encryption. NIST intends to
> standardize one or more schemes that enable semantically secure encryption
> or key encapsulation with respect to adaptive chosen ciphertext attack
> (IND-CCA2), for general use. This security definition is substantially
> similar to what we had in our original draft Call.
>
> As a result of comments received, we are adding another option. While
> chosen ciphertext security is necessary for many existing applications, it
> is possible to implement a purely ephemeral key exchange protocol in such a
> way that only passive security is required from the encryption or KEM
> primitive. For these applications, NIST will consider standardizing an
> encryption or KEM scheme which provides semantic security with respect to
> chosen plaintext attack (IND-CPA).
>
> As the KEM and public key encryption functionalities can generally be
> interconverted, unless the submitter specifies otherwise, NIST will apply
> standard conversion techniques to convert between schemes if necessary.
>
> We would like your feedback.
>
> Does this approach seem sound?
>
> What (if any) changes would you suggest?
>
>
>
> Dustin Moody
>
> NIST
>
>
>
>
> _______________________________________________
> pqc-forum mailing list
> pqc-...@list.nist.gov
> (_internal_name)s
>
Moody, Dustin (Fed)
We are certainly aware of the Open Quantum Safe project, and we believe that (aside from re-naming variables) that the API we are suggesting for KEMs is along the same lines as their key exchange API.
Dustin
Stebila, Douglas
Douglas
Markku-Juhani Olavi Saarinen
The initial NIST KEM API description was perhaps little too terse for me.
I am assuming that the appropriate mapping for key exchange purposes
would be as follows (looking at:
https://github.com/open-quantum-safe/liboqs/blob/master/src/kex/kex.h
)
Function: alice_0() = crypto_kem_keygenerate()
alice_priv = sk
alice_msg = pk
Function: bob() = crypto_kem_encapsulate()
alice_msg = pk
bob_msg = ct
key = ss
Function: alice1() = crypto_kem_decapsulate()
bob_msg = ct
alice_priv = sk
key = ss
Cheers,
- markku
Dr. Markku-Juhani O. Saarinen <mjos at iki.fi>
Christopher J Peikert
Summary: interactive key-exchange (KEX) protocols and (unidirectional)
key encapsulation mechanisms (KEM) are completely different beasts,
each with their own particular use cases and incomparable security
requirements. So NIST certainly should not conflate the two or treat
them interchangeably. Instead, it should request proposals for both
kinds of objects, being clear about which security properties they are
expected to satisfy.
Details:
While it is possible to *syntactically* (at an API level) convert some
KEX protocols to KEMs and vice versa, the *security properties*
usually asked of these objects are very different. I say "some KEX
protocols" because others can involve a combination of long-lived and
ephemeral keys/messages, and are ill-fit to the KEM model.
For KEX protocols, a long line of important works has established some
very subtle attack models and strong security requirements, e.g.,
Bellare-Rogaway, Canetti-Krawczyk, etc. These capture desirable
security properties like forward secrecy, one-sided or mutual
authentication, key confirmation, etc. etc. Many such properties --
especially forward secrecy -- are by now considered non-negotiable by
many (if not most) theorists and practitioners alike.
By contrast, basic security properties like IND-CCA2 for KEMs may not,
or do not, provide the above-mentioned properties in a KEX context.
For example, in typical usage a KEM public key is long lived
("static"), and therefore provides no forward security. One can of
course generate a new KEM keypair every time a new pairwise key is
needed, but then one needs an additional mechanism to ensure that the
new public key is authentic, etc. etc. So one still has to design a
good KEX protocol around the KEM to get the requisite security
properties. And in the end, it may be that a CCA2-secure KEM was
unnecessary in the first place.
In addition, the real-world efficiency profiles of one kind of object
may change significantly when it is converted to the other. E.g., a
KEX might do additional work that is unnecessary for obtaining just
IND-CCA2 security, while a KEM might have slow key generation that is
acceptable for rare use, but too slow to be run every time a new
pairwise key is needed.
There is also precedent for treating KEX and KEM differently: NIST
SP800 56A (revision 2) separately defines interactive "Key Agreement
Schemes" (aka KEX) and non-interactive "Key Transport Schemes" (aka
KEM).
In conclusion, I do not believe it makes sense to treat KEX and KEM as
interchangeable, or to force them into the same API. What was the
rationale for this change? Those (like me) who thought that the
initial request for a KEX was plainly a good idea may have seen no
reason to speak up for its virtues, nor raised the drawbacks of using
a KEM for KEX purposes, since that was not part of NIST's initial
plans.
Sincerely yours in cryptography,
Chris Peikert
On Fri, Oct 28, 2016 at 11:27 AM, Moody, Dustin (Fed)
<dustin.moody at nist.gov> wrote:
> NIST received several comments regarding our request for a key-exchange
> algorithm. As a result, we are clarifying what exactly we are looking for.
> In our revised call, instead of using the term key-exchange we will be
> asking for Key Encapsulation Mechanisms (KEMs). While the term KEM has been
> widely used in academic literature, previous NIST publications have tended
> to describe KEMs using the term ?key agreement? (also known as key
> exchange). KEM schemes consist of algorithms for key generation,
> encapsulation, and decapsulation.
>
> One important application is using public-key cryptography to securely
> establish a key to be used for symmetric encryption. NIST intends to
> standardize one or more schemes that enable semantically secure encryption
> or key encapsulation with respect to adaptive chosen ciphertext attack
> (IND-CCA2), for general use. This security definition is substantially
> similar to what we had in our original draft Call.
>
> As a result of comments received, we are adding another option. While
> chosen ciphertext security is necessary for many existing applications, it
> is possible to implement a purely ephemeral key exchange protocol in such a
> way that only passive security is required from the encryption or KEM
> primitive. For these applications, NIST will consider standardizing an
> encryption or KEM scheme which provides semantic security with respect to
> chosen plaintext attack (IND-CPA).
>
> As the KEM and public key encryption functionalities can generally be
> interconverted, unless the submitter specifies otherwise, NIST will apply
> standard conversion techniques to convert between schemes if necessary.
>
> We would like your feedback.
>
> Does this approach seem sound?
>
> What (if any) changes would you suggest?
>
>
>
> Dustin Moody
>
> NIST
>
>
>
>
D. J. Bernstein
> Those (like me) who thought that the initial request for a KEX was
> plainly a good idea may have seen no reason to speak up for its
> virtues, nor raised the drawbacks of using a KEM for KEX purposes,
> since that was not part of NIST's initial plans.
In Section 4.A.2 "Security Model for Encryption/Key-Establishment" of
the initial call, NIST explicitly stated that it intends to standardize
one or more schemes that enable "semantically secure encryption" with
respect to adaptive chosen ciphertext attack. (This property is
generally denoted IND-CCA2 security in academic literature.)
The above security model should be taken as a statement of what NIST
will consider to be a relevant attack. Submitted schemes for
encryption and key exchange will be evaluated based on how well they
appear to provide this property, when used as specified by the
submitter.
NIST also clearly stated that each submission needs implementations that
"shall adhere to the provided API". The API for "Key Establishment" had
the same basic data-flow restrictions as a KEM: for example, there's no
obvious way to express HMQV within this API.
It seems reasonably clear that, starting from this baseline, NIST is now
making three types of improvements:
* Clarifying the functionality and security requirements: for
example, trying to avoid ambiguous "key exchange" terminology.
* Simplifying the API: for example, removing an irrelevant split of
encapsulation into two steps.
* Allowing additional targets of interest: for example, recognizing
that IND-CCA2 is overkill in the TLS/SIGMA context.
If the goal is to ask NIST to consider adding further "key exchange"
targets, then it seems to me that the right approach is to
* clearly say what those targets actually are,
* give illustrative examples of why they're useful, and
* argue that the benefits of further targets outweigh the costs.
Objecting to imaginary failures in the process---for example, bringing
up the cost of generating ephemeral keys as if NIST hadn't addressed
precisely this issue in Section 4.A.5, or claiming that NIST's original
draft allowed any imaginable type of "key exchange" and that NIST is
somehow retreating from this---is clearly not the right approach.
---Dan
Perlner, Ray (Fed)
Thanks,
Ray Perlner
Q: NIST provided APIs and security definitions for Public Key encryption, KEM, and digital signature. Why are other functionalities not included?
A: NIST is looking primarily to replace quantum-vulnerable schemes with functionalities that are widely used, have widely agreed upon security and correctness definitions in academic literature, and for which there appear to be a range of promising approaches for designing a postquantum replacement. NIST considered a number of other functionalities, but did not provide explicit support for them, since it did not feel they met the above criteria as well as encryption, KEM, and signature. In many cases, NIST expects that schemes providing some of these functionalities may be submitted as a special case or an extension of one of the functionalities we explicitly asked for. In such a case, any additional functionality would be considered an advantage as noted in section 4.C.1 of our Call. Two particular functionalities NIST considered were authenticated key exchange (AKE), and a drop in replacement for Diffie-Hellman.
Diffie-Hellman is an extremely widely used primitive, and has a number of potentially useful special features, such as asynchronous key exchange, and secure key use profiles ranging from static-static to ephemeral-ephemeral. However, NIST believes that in its most widely used applications, such as those requiring forward secrecy, Diffie-Hellman can be replaced by any secure KEM with an efficient key generation algorithm. The additional features of Diffie-Hellman may be useful in some applications, but there is no widely accepted security definition, of which NIST is aware, that captures everything one might want from a Diffie-Hellman replacement. Additionally, some plausibly important security properties of Diffie-Hellman, such as a secure, static-static key exchange, appear difficult to meet in the postquantum setting. NIST therefore recommends that schemes sharing some or all of the desirable features of Diffie-Hellman be submitted as KEMs, while documenting any additional!
functionality.
AKE is also a widely used functionality. However, NIST would consider it a protocol rather than a scheme. This is an important distinction, because most widely used AKE protocols are constructed by combining simpler primitives, like digital signature, public key encryption, and KEM schemes. NIST wants to leave open the possibility that standards for these schemes may come from different submitters. Additionally, the security definitions for AKE are significantly more complicated and contentious than those for the functionalities NIST is explicitly asking for in its call for proposals. NIST recognizes that there are some AKE functionalities, in particular implicitly authenticated key exchange (IAKE), that cannot easily be constructed from simpler components. While it is less natural to treat IAKE schemes as an extension of the KEM framework, than it is for Diffie-Hellman-like primitives, NIST does believe that it can be done in most cases. For example, a significant part of t!
he functionality of a 2-message IAKE protocol could be demonstrated by treating the initiator's public authentication key as part of a KEM public key, and the responder's public authentication key as part of the KEM ciphertext.
Markku-Juhani Olavi Saarinen
Ray Perlner wrote:
"NIST believes that in its most widely used applications, such as
those requiring forward secrecy, Diffie-Hellman can be replaced by any
secure KEM with an efficient key generation algorithm."
Perhaps NIST can provide pointers that back up this argument, as it
does not seem trivial to me. The security model for KEMs I've seen
does not let the adversary choose the public and private keys, which
is the case with "KEM as a KEX".
EXAMPLE. A classical man-in-the-middle attack on Diffie-Hellman (as
used in TLS, IPSec, etc) would use a small subgroup public value (in
KEM terminology, public key) such as 1 or -1, which of course forces
the shared secret into the same subgroup. In this way the MITM can
force both parties to use a shared secret that he also can guess,
thereby defeating mutual authentication measures. The countermeasure
is to always check the group order (of the public parameter provided
by other party) before agreeing on a key.
In case of KEMs, such as those based on factoring, this countermeasure
would be equivalent to checking whether or not the public key (i.e.
modulus) is "weak" during the encapsulation operation, and similiarly
if ciphertext is "weak" in decapsulation. In encapsulation such
checking of n (i.e. of prime powers etc) seems related to the
factoring problem itself. I don't think that current factoring-based
KEMs perform such checking as the security proofs assume that the
adversary has no access to the secret key (certainly cannot choose
it).
Cheers,
- markku
Dr. Markku-Juhani O. Saarinen <mjos at iki.fi>
On Fri, Nov 4, 2016 at 10:17 PM, Perlner, Ray (Fed)
<ray.perlner at nist.gov> wrote:
> We've been working on a FAQ entry regarding additional key exchange functionalities beyond KEM, and some of us thought it might address some of the concerns that have been expressed on the forum regarding our current plan. Please comment.
>
> Thanks,
> Ray Perlner
>
>
> Q: NIST provided APIs and security definitions for Public Key encryption, KEM, and digital signature. Why are other functionalities not included?
>
> A: NIST is looking primarily to replace quantum-vulnerable schemes with functionalities that are widely used, have widely agreed upon security and correctness definitions in academic literature, and for which there appear to be a range of promising approaches for designing a postquantum replacement. NIST considered a number of other functionalities, but did not provide explicit support for them, since it did not feel they met the above criteria as well as encryption, KEM, and signature. In many cases, NIST expects that schemes providing some of these functionalities may be submitted as a special case or an extension of one of the functionalities we explicitly asked for. In such a case, any additional functionality would be considered an advantage as noted in section 4.C.1 of our Call. Two particular functionalities NIST considered were authenticated key exchange (AKE), and a drop in replacement for Diffie-Hellman.
>
> Diffie-Hellman is an extremely widely used primitive, and has a number of potentially useful special features, such as asynchronous key exchange, and secure key use profiles ranging from static-static to ephemeral-ephemeral. However, NIST believes that in its most widely used applications, such as those requiring forward secrecy, Diffie-Hellman can be replaced by any secure KEM with an efficient key generation algorithm. The additional features of Diffie-Hellman may be useful in some applications, but there is no widely accepted security definition, of which NIST is aware, that captures everything one might want from a Diffie-Hellman replacement. Additionally, some plausibly important security properties of Diffie-Hellman, such as a secure, static-static key exchange, appear difficult to meet in the postquantum setting. NIST therefore recommends that schemes sharing some or all of the desirable features of Diffie-Hellman be submitted as KEMs, while documenting any addition!
al!
> functionality.
>
> AKE is also a widely used functionality. However, NIST would consider it a protocol rather than a scheme. This is an important distinction, because most widely used AKE protocols are constructed by combining simpler primitives, like digital signature, public key encryption, and KEM schemes. NIST wants to leave open the possibility that standards for these schemes may come from different submitters. Additionally, the security definitions for AKE are significantly more complicated and contentious than those for the functionalities NIST is explicitly asking for in its call for proposals. NIST recognizes that there are some AKE functionalities, in particular implicitly authenticated key exchange (IAKE), that cannot easily be constructed from simpler components. While it is less natural to treat IAKE schemes as an extension of the KEM framework, than it is for Diffie-Hellman-like primitives, NIST does believe that it can be done in most cases. For example, a significant part of!
t!
> he functionality of a 2-message IAKE protocol could be demonstrated by treating the initiator's public authentication key as part of a KEM public key, and the responder's public authentication key as part of the KEM ciphertext.
>
D. J. Bernstein
> EXAMPLE. A classical man-in-the-middle attack on Diffie-Hellman (as
> used in TLS, IPSec, etc) would use a small subgroup public value (in
> KEM terminology, public key) such as 1 or -1, which of course forces
> the shared secret into the same subgroup. In this way the MITM can
> force both parties to use a shared secret that he also can guess,
> thereby defeating mutual authentication measures.
For server authentication: The server signs the transcript. The client
verifies the signature. The client now knows that the server has seen
exactly the messages that the client sent, and sent exactly the messages
that the client received, so there's no man in the middle.
For client authentication: The client signs the transcript, etc.
This works with any single-message KEM that's secure against passive
attacks. It relies on a secure signature system, and on an explicit
model of the protocol as a transcript that can be provided as input to
the signature system.
Instead of using transcription to delay signatures, one can simply sign
each message, and verify each signature before acting upon the message.
This has the advantage of eliminating all opportunities for the attacker
to feed forgeries to the client's KEM decryption code. But even a single
signature isn't cheap, especially post-quantum, and protocols often have
several messages before they've agreed on an authenticated-cipher key.
> The countermeasure is to always check the group order (of the public
> parameter provided by other party) before agreeing on a key.
This type of checking is something that TLS has historically tried to do
to compensate for _not_ signing the whole transcript. People thought
that having the server sign a few critical pieces would allow the client
to trust everything. But this turns out to be awfully hard to get right.
I prefer a different style of protocol design where the server's
long-term key is a KEM key (typically a DH key, but this will probably
change post-quantum) rather than a signature key:
* The client simply uses the KEM to transport a session key to the
server, and then accepts only messages that are authenticated under
the session key.
* For client authentication, the server similarly sends something to
a long-term client KEM key.
* For key erasure, the client or server sends a short-term KEM key,
and the server or client uses that to transport a new sesssion key.
Of course this relies on multiple-message security for the KEM, but it
avoids the need for a separate signature system, and it avoids the cost
of signatures. (Post-quantum signatures seem more expensive than KEMs.)
It eliminates forgeries very quickly, just like having each message
immediately signed by the server and verified by the client.
---Dan
Garcia Morchon O, Oscar
looking at your (I)AKE suggestion below, we have tried to fit an (implicitly) authenticated key exchange under the draft API -- described in a previous email -- to demonstrate a 2-message IAKE protocol between an initiator an a responder.
The first message would be the IAKE initiator public key sent by the initiator to the responder. This public-key could be certified to belong to the owner using a public-key or ID-based infrastructure.
Preparation of second message by the responder relies on crypto_kem_encapsulate ():
int crypto_kem_encapsulate(
const unsigned char *pk,
unsigned char *ct,
unsigned char *ss
)
Here, *pk would point to the IAKE initiator public key, but we would also need to pass (concatenate) the IAKE responder private key used for authentication. *ss is the encapsulated key. Output *c would concatenate the responder public key and the encrypted message (and signature).
The second message is output *ct. The receiver of the message (the initiator) processes it by means of crypto_kem_decapsulate ():
int crypto_kem_decapsulate(
const unsigned char *ct,
const unsigned char *sk,
unsigned char *ss
)
Here *ct is the received message, and *sk points to the initiator private key. *ss is the received shared key once the signature has been verified.
In this example, combining the responder public key with the initiator private key as a parameter seems to be the only way to use the KEM API to achieve IAKE. Is this how you would suggest to structure a 2-message IAKE submission?
Kind regards, Oscar.
-----Original Message-----
From: pqc-forum-bounces at nist.gov [mailto:pqc-forum-bounces at nist.gov] On Behalf Of Perlner, Ray (Fed)
Sent: Friday, November 04, 2016 2:17 PM
To: pqc-forum
Subject: Re: [Pqc-forum] Key Establishment for PQC algorithms
Thanks,
Ray Perlner
_______________________________________________
pqc-forum mailing list
pqc-...@list.nist.gov
(_internal_name)s
________________________________
The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.
John Mattsson
algorithms. I think getting a standardized PQC key exchange with forward
secrecy is utterly important. But I do not think no disqualifying is
enough, I would like to see commitment from NIST to standardize at least
two PQC key exchange mechanisms:
- At least one PQC half-roundtrip key encapsulation protocol for use in
stateless protocols such as S/MIME, JOSE etc. typically used for secure
messaging such as email.
- At least one key exchange protocol with forward secrecy for use in
stateful protocols such as TLS, IPsec, SSH etc.
At a minimum NIST should clearly state what they intend to standardize so
that other SDOs can avoid overlap/fill in gaps.
John
On 2016-10-28, 19:24, "pqc-forum-bounces at nist.gov on behalf of Moody,
Dustin (Fed)" <pqc-forum-bounces at nist.gov on behalf of
Alperin-Sheriff, Jacob (Fed)
NIST?s focus in this project is not to standardize full-fledged key exchange protocols, per se, or to specify any specific protocols in which those algorithms we standardize are suitable for use, but rather to standardize the underlying algorithms, although we are certainly considering ease of integration into currently existing protocols as a significant factor in terms of which algorithms we eventually standardize. If any of the algorithms submitted can be naturally formulated as Diffie-Hellman style exchange algorithms, we also expect to take that into consideration as a potential positive factor in terms of our choice, but as most candidate post-quantum key exchange algorithms that have been proposed so far do not seem to fit well as a ?drop-in? Diffie-Hellman replacement, we did not specify such a category of submissions explicitly, to avoid the possibility of facing limited submissions.
However, I believe we are going to be addressing your concerns in the final call for proposals. In particular, we are distinguishing between KEM schemes using ephemeral keys (thus providing forward secrecy and corresponding with the second category you?ve mentioned) and KEMs and public key encryption schemes using static keys (which appears to align well with the first category you?ve mentioned).
Our final call for proposals (as well as our FAQ) will provide a clear and more detailed description of what we expect in our submissions and what we intend to standardize.
Thanks.
-Jacob Alperin-Sheriff