Subject: [openpgp] German BSI, PQC for OpenPGP in Thunderbird,

From: Kai Engert <[email-masked]>
Date: Thu, 24 Jun 2021 15:52:06 +0200

Hello,

I'd like to make you aware of a project call by the German BSI (a 
federal agency for IT security), which was brought to my attention.

I've posted some information on it on the Thunderbird planning mailing 
list, see the following thread, which has multiple messages from me:

https://thunderbird.topicbox.com/groups/planning/T5abbf135db2f3c1c/the-german-bsi-intends-to-sponsor-pqc-improvements-for-openpgp-in-thunderbird

In my understanding they intend to pay a contractor for a wide set of 
tasks to bring PQC to Thunderbird, including the work to standardize the 
use of PQC with OpenPGP, including implementations for RNP, Botan, GnuPG 
and libgcrypt.

It seems the BSI has already made a suggestion that they want to require 
the use of CRYSTALS-Kyber and -Dilithium.

Is that a reasonable choice?

Does it make sense to define a limitation to these methods at this point 
of time?

Thanks
Kai

---

From: "Derek Atkins" <[email-masked]>
Date: Thu, 24 Jun 2021 10:39:59 -0400

Hi Kai,

My only concern at this point in time would be the question of what PQC
methods to include?  Right now there are still way too many choices, and
there is an expectation that NIST will reduce those choices over the next
2ish years.  So does it pay to do the work now, or perhaps wait a bit for
Round 3 to finish, before we potentially add methods?

-derek

On Thu, June 24, 2021 9:52 am, Kai Engert wrote:
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 24 Jun 2021 11:40:21 -0400

Thanks for the heads up about this, Kai!

> use of PQC with OpenPGP, including implementations for RNP, Botan, GnuPG 

I appreciate your providing an English summary of the call for
contractors.  I'm glad that the BSI is interested in this topic -- i am
too, though i share Derek's concerns about whether standardization is
premature given the state of PQ cryptanalysis.  I'm a little surprised
to see the BSI simultaneously proposing standardization of PQ schemes in
OpenPGP *and* advocating for implementation of a specific scheme.  I'd
expect the standardization to involve selecting which PQ scheme(s) seem
reasonable for the context, rather than pre-determining the scheme for
use.

If we can get the crypto refresh done relatively soon, it would be a
great way to demonstrate that we are ready as a community to figure out
how to get PQ mechanisms mixed into OpenPGP.  And, as the thread from
earlier this week discussed, one of the ways that we're likely to see
proposals for PQC to work would be to have multi-key combinations -- so
that we don't introduce a relatively new algorithm that makes things
weaker than the established traditional asymmetric crypto; this
requires some nuance and planning that are not part of the simple
"crypto refresh" mandate we have right now.

I'd welcome the BSI to send their own members (and/or delegates) to the
WG to talk about their goals and plans, but i'd hope it wouldn't
interfere with the current chartered work.

          --dkg

---

From: Kai Engert <[email-masked]>
Date: Thu, 24 Jun 2021 18:04:53 +0200

On 24.06.21 17:40, Daniel Kahn Gillmor wrote:
> ... I'm a little surprised
> use. ...

The call mentions that the NIST standardization isn't done, so 
apparently they intend to follow the NIST recommendations.

They also say, the project's cryptographic design should consider 
crypto-agility and hybrid solutions. They describe a hybrid solution as 
a conbination of a PQ method with a classic asymmetric method.

Maybe this means they're asking for a solution that implements the 
specific CRYSTALS-* method, but in addition be prepared for alternative 
algorithms as well?

I found that in section 1.3 of document 02
(Vergabeunterlagen/02 - P480 - Leistungsbeschreibung - Offenes Verfahren 
v1.0.pdf)
from https://www.evergabe-online.de/tenderdocuments.html?1&id=397181

Maybe it would be necessary for applications to ask for clarification. 
(As noted in the other posts to the Thunderbird planning list, all 
questions need to be asked in German via the BSI project site. And in 
order to ask questions, it seems necessary to register as an interested 
party for the project.

Kai

---

From: Michael Richardson <[email-masked]>
Date: Thu, 24 Jun 2021 12:31:05 -0400

Derek Atkins <[email-masked]> wrote:
    > methods to include?  Right now there are still way too many choices,
    > and there is an expectation that NIST will reduce those choices over
    > the next 2ish years.  So does it pay to do the work now, or perhaps
    > wait a bit for Round 3 to finish, before we potentially add methods?

Reading Kai's email, my impression was that the point of the German effort is
to figure out (sooner) what changes might be needed to Thunderbird, and
perhaps, provide NIST with implementation feedback.

So, that's why they want to do the work now.

    >> tasks to bring PQC to Thunderbird, including the work to standardize
    >> the use of PQC with OpenPGP, including implementations for RNP, Botan,
    >> GnuPG and libgcrypt.
    >>
    >> It seems the BSI has already made a suggestion that they want to
    >> require the use of CRYSTALS-Kyber and -Dilithium.
    >>
    >> Does it make sense to define a limitation to these methods at this
    >> point of time?
    >>
    >> Thanks Kai
    >>
    >> _______________________________________________ openpgp mailing list
    >> [email-masked] https://www.ietf.org/mailman/listinfo/openpgp
    >>

    > --
    >        Derek Atkins 617-623-3745 [email-masked] www.ihtfp.com Computer
    > and Internet Security Consultant

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

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Alessandro Barenghi <[email-masked]>
Date: Fri, 25 Jun 2021 09:07:35 +0200

Hello,

> Is that a reasonable choice?

(Disclaimer: I have been involved in the NIST contest with a
submission which made it to the 2nd round. I am
not part of NIST personnel, opinions following are mine only.)

Kyber and Dilithium are two of the finalist algorithms in the current
NIST PQ standardization effort and,
as things stand now, thus potential candidates at the end of this year.
>From the latest update on the contest ([*] , slides 10 and 11) they
are both likely to be chosen as standards.

> Does it make sense to define a limitation to these methods at this point
NIST is planning to announce the choice of the actual winners at the
end of 2021/early 2022 at the latest.
While writing down actual standards will take a bit more, the cut-down
on the algorithms will be significant.
We expect a single  lattice-based KEM and Classic McEliece for
diversity to be selected for KEMs,
and a single lattice based signature to make it in the standard which
will be announced at the end of the year.

NIST also has plans for a fourth stage of the competition, where they
will accept proposals for non-lattice based signatures
and analyze further the current "alternate" candidates.

If the idea is to understand what is the impact of the choices made by
NIST when implementing, it may be a reasonable time to keep thinking
about all the candidates in the NIST PQ standardization process.

An interesting bird's eye view on the sizes of ciphertexts/keypairs
and speed of the current third round candidates is available here[**]
(from slide 100 onwards).

Hope this helps,

Alessandro

[*] https://csrc.nist.gov/CSRC/media/Presentations/status-update-on-the-3rd-round/images-media/session-1-moody-nist-round-3-update.pdf
[**] https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/seminars/oct-2020-gaj-kris-presentation.pdf

---

From: Daniel Huigens <[email-masked]>
Date: Mon, 28 Jun 2021 09:05:27 +0000

Hi all,

For what it's worth, we (ProtonMail) were also planning to create an
experimental implementation of post-quantum crypto in OpenPGP, sometime
this fall - not intending to "create a standard", rather our rationale
was that an experimental implementation could teach us something about
a potential standardization in the future.

That being said, if the WG is ready for this work by then, we are of
course happy to contribute to that work, and collaborate on a potential
standardization while working on an experimental implementation.
Depending on when someone applies to this tender from the BSI, perhaps
they could do the same.

While it's of course up for debate, we had a similar set of algorithms
in mind to use for the experimental implementation (using a hybrid
approach of both post-quantum and classical algorithms). We do think
that it makes more sense to wait for NIST standardization for the final
standardization of PQC in OpenPGP - but even if the set of standardized
algorithms ends up being different, the high-level work might still
teach us something, so we are in principle not opposed to this work.

If someone applies to this tender before the WG is ready for this work,
we would hope / recommend that they take a similar approach as we were
planning, and create an experimental implementation that could inform,
but not define, the final specification. That being said, as soon as
this WG has the bandwidth to work on this, hopefully the person working
on that could join the WG and help draft a specification, and as I said
we would be happy to contribute to that effort as well.

Best regards,
Daniel Huigens

---

From: Werner Koch <[email-masked]>
Date: Mon, 28 Jun 2021 11:50:11 +0200

> we would hope / recommend that they take a similar approach as we were

FWIW, the tender is designed for a timeframe of 3 years with a strict
set of milestones and implementation can't be done before the other work
items have been finished.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Justus Winter <[email-masked]>
Date: Mon, 28 Jun 2021 12:36:17 +0200

> [**] https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/seminars/oct-2020-gaj-kris-presentation.pdf

That is a great pointer.  I think from the perspective of the protocol,
the biggest challenge is that OpenPGP can only express cryptographic
artifacts up to 2^16 bits, or 2^13 bytes.

Even if we assume that artifacts like keys, ciphertexts, signatures are
just comprised of a single component, that only impacts very few KEMs
(HCQ, FrodoKEM, and of course McEliece), of which only McEliece is a 3rd
round finalist.  But, given that all other finalists are based on
structured lattices, and NIST expects to select only one of those,
McEliece may very well be one of the selected algorithms.

It's a different picture for the signature schemes, though, where only
Falcon and Dilithium fit into OpenPGP's MPI envelope, both of which are
3rd round finalists.  The signature schemes seem to all trade off key
size vs. signature size, with only two schemes barely able to fit into
MPIs.  That is a bit disconcerting.  NIST seems to think so too, as they
are interested in more candidates.

I think we should revisit the way we store cryptographic artifacts in
OpenPGP.  Unfortunately, neither SOS nor SBS address the issue of
potentially large PQ artifacts.

Justus

---

From: Kai Engert <[email-masked]>
Date: Mon, 28 Jun 2021 15:52:48 +0200

FYI, Werner's message fails to render in Thunderbird, because of the use 
of an apostrophe character in the MIME boundary.

I've filed the issue here:
https://bugzilla.mozilla.org/show_bug.cgi?id=1718533

Kai

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 28 Jun 2021 10:26:24 -0400

> potentially large PQ artifacts.

As the person who coined "SBS", I want to note that it is *not* intended
to be a design that will work for future algorithms.  It's merely a
handle to describe the particular idiosyncratic structure used in some
cases already for 25519.

While SBS is "MPI-like", we already do have non-MPI-like data structures
stuffed into the "algorithm-specific" parts of some key material: in
particular, the ECC OID is encoded with a single octet length, which
means it cannot be parsed correctly by any implementation that is
ECC-ignorant but blindly expects to extract a series of MPI-like
objects from a public key packet.

For future algorithms (including anything PQ) i'd hope that the future
spec would explicitly declare a distinct data structure for the
algorithm as necessary.  I don't think we need a generic data structure
format given the range of possible requirements.

       --dkg