Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

From: Russ Housley <[email-masked]>
Date: Wed, 27 Jan 2016 10:38:54 -0500

NSA has posted some more information about their previous guidance:

https://www.iad.gov/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/cnsa-suite-and-quantum-computing-faq.cfm

Russ

On Aug 14, 2015, at 5:08 PM, Russ Housley wrote:

> See https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml
> 
> This guidance suggests mitigation against a yet-to-be-invented quantum computer that will be able to attack existing cryptographic algorithms.
> 
> I am posting this here because some CFRG participants may be interested in developing ways to add quantum-resistance existing key establishment techniques.
> 
> Russ

---

From: Tony Rutkowski <[email-masked]>
Date: Wed, 27 Jan 2016 11:13:03 -0500

Hi Russ,

Good pointers.  Folks might also be interested in
the the ongoing related standards efforts at the
ETSI QSC (Quantum-Safe Cryptography) TC.
https://portal.etsi.org/tb.aspx?tbid=836&SubTB=836
There is also the reference site on Quantum Key
Distribution and the related pointers to
workshops.
http://www.etsi.org/technologies-clusters/technologies/quantum-key-distribution

Like many others - having watched the passing
scene here for several decades, this is a forever
evolving competition among a relatively small
set of interested parties that provides potential
uses for increasing faster and cheaper processing
cycles as cannon fodder for battle.

Having helped the ILPF get started 20 years ago
- which was modeled after the IETF to nurture
the PKI industry - with disappointing takeup,
the only observation is that getting industry
or ordinary people to care is the challenge.

cheers,
--tony

On 2016-01-27 10:38 AM, Russ Housley wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 27 Jan 2016 11:54:55 -0500

> https://www.iad.gov/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/cnsa-suite-and-quantum-computing-faq.cfm

You can't get there using Chrome due to the SHA-1 certificate in the path.

One thing I did notice is that the commercial suite now specifies RSA
3072 or larger. Which might as well be 'stop using RSA'. Sure
commercial CAs can support RSA up to 4096 but I don't see the point,
the ECC is better.

The near term priority has to be a transition to ECC. And in IETF
terms that is going to mean Curve 448. And since that is faster and
stronger than P384, it should be the curve we can all standardize on.

On the QC stuff. Of course we have to start looking at that now. But I
think we need to look at the problem on two separate tracks:

1) Find a public key algorithm that resists QC using Shorr's algorithm.
2) Find a mechanism that makes symmetric key feasible in place of public.

My gut feel is that any public key algorithm is likely to be
vulnerable to QC. But even if my intestinal argument is wrong, we have
no way to predict how fast QC hardware will advance. This isn't being
governed by Moore's law. And any machine doesn't need to meet
commercial QA standards to destroy the WebPKI. A machine that works
once for a few hours and then needs a rebuild would be plenty
dangerous enough in the wrong hands.

So I am going to be working on path 2. And the way to make that viable
is to convert the WebPKI from being a single ended authentication
mechanism to being dual ended.

So the first step in that process is to develop an infrastructure that
makes client side public keys easy to use. No, makes using the
computer easier and gives client side keys as a side effect. My scheme
to do that is the Mathematical Mesh. That is what I released last week
and I am currently editing a demo video to show what it looks like.

Second step for the Mesh will be adding the proxy re-encryption
techniques that Matt Blaze invented twenty years ago and haven't been
recognized properly. It is a very powerful technique. Like digital
signatures.

I don't know how they might be used eventually. But one of the things
I want to do with the Mesh is to provide a mechanism that provides for
secure distribution of Kerberos style tickets in case of future need.
Then you folk can try to work out how we might use them in the future.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 27 Jan 2016 19:35:30 +0200

> You can't get there using Chrome due to the SHA-1 certificate in the path.

Actually, looks like unknown root than SHA-1.

> commercial CAs can support RSA up to 4096 but I don't see the point,

Basically the FAQ makes the argument there that there is no point
at transitioning now to ECC only to transition to PQC (the document
talks about QRC) later.
 
> 2) Find a mechanism that makes symmetric key feasible in place of public.

The problem is that symmetric keys are rarely feasible due to
asymptotically worse scalability (asymmetric tend to scale as O(N)
while symmetric tends to scale as O(N^2).

> dangerous enough in the wrong hands.

There actually are existing public-key (all main categories, encryption,
signature and key agreement) algorithms not _known_ to be vulernable
to QC.

Regarding advances to QC hardware, it is mostly about amount of fully
coupled qbits (AFAIK, the public records are currenty on order of half
dozen or so). If you have too few, your QC is useless for attack, but
if you have enough, you can totally destroy any algorithm that doesn't
resist QC.

The algorithms that resist QC can't be broken with any reasonable
amount of qbits (without finding a way to break the cipher, which can
happen).

Unfortunately, the currently known PQC algorithms tend to suffer
from many serious problems, like (the combination varies):

- Large public keys
- Large signatures/encryptions
- Lack of analysis
- Slowness
- Lack of DH-style key agreement.

-Ilari

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 27 Jan 2016 18:05:51 +0000

On 1/27/16, 12:35 , "Cfrg on behalf of Ilari Liusvaara"
<[email-masked] on behalf of [email-masked]> wrote:

>>https://www.iad.gov/iad/library/ia-guidance/ia-solutions-for-classified/a
>>lgorithm-guidance/cnsa-suite-and-quantum-computing-faq.cfm
>> 

Kerberos was facing this problem three decades ago. I personally think
their solution was fine.

You have to have a trusted 3rd party, be it PKI or Kerberos-like KDC. The
difference is in how secure this 3rd party needs to be, and which failures
cause what implications. But at the high level, the concept is the same:
you either trust KDC to give you a shared key for you and your peer, or
you trust CA to swear to you that the PK your peer gave you truly belongs
to your peer.

( 1. Yes I understand the difference in convenience/usability between
symmetric and asymmetric. 2. While in theory the “symmetric” problem is
O(N^2), clearly not everybody needs/wants to talk to everybody else. So in
practice it is not THAT bad. It really boils down to trust model, IMHO.)

>- Lack of DH-style key agreement.

Add one more: being patented (the story of RSA and ECC about to repeat
itself :).

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 27 Jan 2016 14:00:31 -0500

> Kerberos was facing this problem three decades ago. I personally think

Exactly, which was why I said Kerberos tickets.

Doing Kerberos at Web scale would be horrendous and you don't get non
repudiable signatures. It would not be fun at all. But if people told
me today that QC was broken and gave me access to the necessary
resources, we could deploy a kerberos type scheme in 12 months.

The problem is that there would be no way to bootstrap the
authentication system. Which is why it makes sense to use PKI while we
can trust it.

>>- Lack of DH-style key agreement.

And there is a real possibility that there is a faster attack than Shorr.

Thing is, finding a trapdoor in a one way function is exactly the sort
of thing I would expect a quantum computer to be able to do due to the
nature of the beast. Shorr is only one attack.

> Add one more: being patented (the story of RSA and ECC about to repeat

That might not be a problem in practice. It takes us 20 years to get
used to new algorithms and comfy with them.

---

From: James Cloos <[email-masked]>
Date: Wed, 27 Jan 2016 16:37:30 -0500

>>>>> "RH" == Russ Housley <[email-masked]> writes:

RH> NSA has posted some more information about their previous guidance:
RH> https://www.iad.gov/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/cnsa-suite-and-quantum-computing-faq.cfm

So, first invalid issuer for www.iad.gov's cert, and then if one ignores
that the [Get File] link returns:

  The service is unavailable

So what does this stupidly posted file say?

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Bill Cox <[email-masked]>
Date: Wed, 27 Jan 2016 14:02:11 -0800

> signature and key agreement) algorithms not _known_ to be vulernable

The public-key algorithm that finally convinced me that we can have
provably secure public key crypto is the original Merkel Puzzle
<https://en.wikipedia.org/wiki/Merkle%27s_Puzzles> key exchange, which
looks obviously quantum-resistant to me.

Even better, we can feel good about hash based signatures
<https://www.imperialviolet.org/2013/07/18/hashsig.html>.  It is easy to
see that breaking this system is roughly the same as the difficulty of
finding hash collisions in a strong cryptography hash function, which is
generally believed to be quantum resistant (it had better be!).  Then
there's LWE based key exchange
<https://en.wikipedia.org/wiki/Learning_with_errors>.  The probability
based argument for distinguishing encrypted data from random looks good to
me, though I am not convinced that the problem of directly reversing the
public key is quantum resistant.  Do we know if this is the case?

I'm reading about Ring Learning-With-Errors
<https://www.imperialviolet.org/2015/12/24/rlwe.html>.  My initial gut
reaction is "Danger, Will Robinson!"  The public key does not act as a
random function of the secret.  There are strong correlations between
public keys when the secret keys are only slightly different.  Also, the
probabilistic argument used in LWE security analysis does not apply to this
particular R-LWE key exchange algorithm.  However, I have not finished
reading the papers covering the security...

Bill

---

From: Watson Ladd <[email-masked]>
Date: Wed, 27 Jan 2016 14:27:44 -0800

On Jan 27, 2016 1:38 PM, "James Cloos" <[email-masked]> wrote:
> RH>
> So what does this stupidly posted file say?

Given the multidecade military acquisition cycle, the NSA is beginning to
think about post-quantum algorithms, and doesn't feel that switching all
their currently deployed solutions by the previously announced deadline
will be cost effective for them.

Remember, the B-52 will have served for almost century when finally
retired. Most people have far shorter upgrade cycles then the 50 years the
NSA is discussing.

---

From: Richard Outerbridge <[email-masked]>
Date: Wed, 27 Jan 2016 17:53:27 -0500

> On 2016-01-27 (27), at 17:27:44, Watson Ladd <[email-masked]> wrote:
> [….]
> 
> Given the multidecade military acquisition cycle, the NSA is beginning to think about post-quantum algorithms, and doesn't feel that switching all their currently deployed solutions by the previously announced deadline will be cost effective for them.
> 
> Remember, the B-52 will have served for almost century when finally retired. Most people have far shorter upgrade cycles then the 50 years the NSA is discussing.
> 
More or less  The Soviet Fialka system was in trusted service from ~1951 until ~1971, so more like ~25 years.
__outer

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 27 Jan 2016 18:15:29 -0500

8

> Kerberos was facing this problem three decades ago. I personally think

This is a bit misleading, as what is the bootstrap for the identity 
(principal) to the KDC?  A TLS protected session?  Same problem with the 
one IBE solution I have looked at.  Looks good until you look at its 
bootstrap.

Showing up at a Univ admissions desk may work to some extent, but does 
not work in a sensor network.  There are solutions that use some 
short-range RF for admissions control, but I have seen that abused in 
the field.

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 27 Jan 2016 15:17:12 -0800

> On Jan 27, 2016, at 2:02 PM, Bill Cox <[email-masked]> wrote:
> 
> On Wed, Jan 27, 2016 at 9:35 AM, Ilari Liusvaara <[email-masked] <mailto:[email-masked]>> wrote:
> > [Phillip Hallam-Baker wrote:]
> The public-key algorithm that finally convinced me that we can have provably secure public key crypto is the original Merkel Puzzle <https://en.wikipedia.org/wiki/Merkle%27s_Puzzles> key exchange, which looks obviously quantum-resistant to me.

Merkel puzzles aren’t even classical-resistant.  O(mn) time simply isn’t enough, given that you have to send omega(m log n) bytes, and given that the parties might be limited in computation, bandwidth or power.  Also, Grover’s algorithm for quantum brute-force would erode that quadratic complexity somewhat, though probably not all the way because it has caveats.  In a straightforward implementation Grover’s would reduce the time from O(mn) to at most O(msqrt(n)), but maybe you could defend against this by using a memory-intensive hash function.

> Even better, we can feel good about hash based signatures <https://www.imperialviolet.org/2013/07/18/hashsig.html>.

Yes.  Unfortunately these are stateful and/or quite large, but they are conservatively believed to be quantum resistant.

> It is easy to see that breaking this system is roughly the same as the difficulty of finding hash collisions in a strong cryptography hash function, which is generally believed to be quantum resistant (it had better be!).

To break the signature itself, you need to find preimages and not collisions.  There’s still the question of how to hash the message, but hopefully the overall signature scheme could force target-collisions instead of just collisions.

> Then there's LWE based key exchange <https://en.wikipedia.org/wiki/Learning_with_errors>.  The probability based argument for distinguishing encrypted data from random looks good to me, though I am not convinced that the problem of directly reversing the public key is quantum resistant.  Do we know if this is the case?

At least some lattice and LWE schemes have quantum reductions from standard problems, but we don’t know if the standard lattice/LWE problems themselves are quantum-hard.

> I'm reading about Ring Learning-With-Errors <https://www.imperialviolet.org/2015/12/24/rlwe.html>.  My initial gut reaction is "Danger, Will Robinson!"  The public key does not act as a random function of the secret.  There are strong correlations between public keys when the secret keys are only slightly different.  Also, the probabilistic argument used in LWE security analysis does not apply to this particular R-LWE key exchange algorithm.  However, I have not finished reading the papers covering the security...
> 
> Bill

I think most cryptographers have very limited confidence in RLWE’s security, though the known attacks on practical systems are the same as classical LWE.  RLWE’s advantage is that it is relatively bandwidth-efficient for a post-quantum scheme, so that we could (in theory) deploy it today alongside ECDH.  Then you’d have to break both ECDH and RLWE to get the key.  Roughly the same thing is true for NTRU and its variants.

Cheers,
— Mike

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 27 Jan 2016 22:25:49 -0500 (EST)

> authentication system. Which is why it makes sense to use PKI while we

A few people have been proposing to use PKI to make cross-realm Kerberos
"just work" recently, but there hasn't been enough manpower in kitten to
actually put things together.  We'd be happy to have more eyes on, e.g.,
draft-williams-kitten-krb5-pkcross or draft-vanrein-dnstxt-krb1 (or other
potential proposals).

There is also the question of what the realm topology would look like --
in other contexts there was talk of a central "clearinghouse" realm that
would share keys with anyone that asked, leaving trust decisions to the
end parties.  But that is not the only possible model...

-Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 27 Jan 2016 22:25:49 -0500 (EST)

-Ben

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 28 Jan 2016 10:16:17 +0000

> end parties.  But that is not the only possible model...

That topic ("realm topology"), including who trusts whom for what,
might be a fine thing for a small group of folks to try sketch out in
case we needed such. The content might be initial attempts to answer
the question "what if we had to use Kerberos everywhere we now use
(EC)DH or RSA key transport, what'd that look like at Internet scale?"
That work might identify bits of work that could be taken up by the
IETF kitten WG later on.

As CFRG is considering post-quantum stuff, that'd fit well here think,
if someone wanted to take a stab at it. (Sorry, I don't have time to
help with that right now.)

Cheers,
S.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 28 Jan 2016 10:04:28 -0500

> help with that right now.)

At this point, all I have time to look at is how we can use the
existing PKI to push out tickets to client endpoints in case of future
need.

Let us imagine that Alice has a shared secret with three distribution
centers run by the likes of Comodo, Symantec, etc. that have been
established in case of future need. There are 5 billion Internet users
and approx 50% have that type of backup plan but no applications are
going to use it at all until the need is proven.

---

From: "A. Huelsing" <[email-masked]>
Date: Thu, 28 Jan 2016 17:47:18 +0100

>> going to use it at all until the need is proven.

I am honestly slightly confused that this is truly considered a possible
solution that needs analysis. A Kerberos-based web-security model would
mean that the trusted third parties can listen to any "secured"
communication between a user and a service. While this would already be
possible in todays Web-PKI setting (which is horrible enough), the new
issue is that no one could ever detect this attack in the new setting.
This would be the de-facto abolishment of Internet privacy.

So you would honestly want to sell privacy just because signatures and
ciphertexts (for public key encryption) would slightly grow when using
post-quantum crypto? (Compared to the increase in size of user data like
an average Webpage over the last years the increase in size for
pq-crypto is really small.)

-- Andreas

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 28 Jan 2016 09:54:45 -0800

Sent from my phone.  Please excuse brevity and typos.

> On Jan 28, 2016, at 08:47, A. Huelsing <[email-masked]> wrote:
> 
> 
> 

This seems like it would only be useful in the event that PQ public key encryption turns out to be infeasible, or if we can't find a scheme we trust. Remember, we're very confident that hash-based signatures are PQ-secure, but not quite as much about the encryption or key exchange options.

-- Mike

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 28 Jan 2016 18:53:44 +0000

On 28/01/16 16:47, A. Huelsing wrote:
> post-quantum crypto? 

Slightly grow seems somewhat optimistic, but who knows.

Anyway, no - nobody sensible would want to give up the benefits
of asymmetric crypto. However, it could be that we end up with
no choice, if PQ key establishment algorithms do not turn out
usable. I've no idea of the liklihood of that but investigating
how Kerberos-like solutions may look seems to me like a fine
thing to know about, just in case.

And who knows, but maybe there'd be ways to not have the KDCs
involved be operated by big business/big brother. Not that I
can think of any right now;-)

S.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 28 Jan 2016 10:58:39 -0800

> used to new algorithms and comfy with them.

Let's consider the actual history of post quantum schemes. McEliece is
1978, right after Diffie-Hellman. Hash based signatures are from at least
1985 with Lamport. NTRU is early 1990's, and there are many NTRU in X
schemes kicking around from that era.

Most of the questions are about specific ring choices. The key sizes and
performance are knowable quantities, as is the state of analysis. Let's try
actual thinking with actual facts on this issue.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 28 Jan 2016 14:15:10 -0500

> This seems like it would only be useful in the event that PQ public key encryption turns out to be infeasible, or if we can't find a scheme we trust. Remember, we're very confident that hash-based…

Exactly. It would be considerably less flexible and secure than the
current WebPKI. But it would keep the wheels of commerce turning and
prevent a catastrophic collapse of civilization.

---

From: "Grigory Marshalko" <[email-masked]>
Date: Thu, 28 Jan 2016 20:32:30 +0000

28 января 2016 г., 21:58, "Watson Ladd" <[email-masked]> написал:
> On Jan 27, 2016 11:00 AM, "Phillip Hallam-Baker" <[email-masked]> wrote:
>> 
>>> <[email-masked] on behalf [email-masked]> wrote:
>>> 
> Let's consider the actual history of post quantum schemes. McEliece is 1978, right after
> Diffie-Hellman. Hash based signatures are from at least 1985 with Lamport. NTRU is early 1990's,
> and there are many NTRU in X schemes kicking around from that era.
> 
> Most of the questions are about specific ring choices. The key sizes and performance are knowable
> quantities, as is the state of analysis. Let's try actual thinking with actual facts on this issue.
> 

Yes, the key question is a stable analysis. RSA and EC are used because at some time thier analysis together with researches in number theory have stabilised. This is not true for many of PQ-schemes - their research in an active phase.

It is interesing that with Semaev's results (in case they are confirmed) we can observe a sort of renaissance in ECDLP. So it is a question what would kill modern schemes first: QC or the development of "conventional" analysis.

Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (ТC 26)
www.tc26.ru