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

From: Russ Housley <[email-masked]>
Date: Fri, 14 Aug 2015 17:08:46 -0400

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: Andy Lutomirski <[email-masked]>
Date: Fri, 14 Aug 2015 14:29:42 -0700

> I am posting this here because some CFRG participants may be interested in developing ways to add quantum-resistance existing key establishment techniques.

I don't like some of these recommendations.

(Disclaimer: I really did study quantum crypto.  OTOH, I didn't check
my work here very carefully.)

AES: Use 256 bit keys to protect up to TOP SECRET

That's not enough.  If you attack N ciphertexts at once, then any
trial key has probability 2^256/N of matching one.  Grover search
finds a match in ~sqrt(2^256/N) tries (there's factor of 4 or so in
there, but that doesn't matter much).  This isn't a comfortable margin
as N approaches, say, 2^64.  I think people should use at least
384-bit symmetric keys to defend against this type of attack.

ECDH: Use Curve P-384 to protect up to TOP SECRET.

If you're worried about smallish quantum computers, just use big RSA
moduli.  The attack complexity is more or less the same for ECC and
RSA, but RSA at least requires a bigger computer to store the thing in
memory.

--Andy

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 14 Aug 2015 14:41:58 -0700

> On Aug 14, 2015, at 2:29 PM, Andy Lutomirski <[email-masked]> wrote:
> 

But Grover only square-roots the time required, right?  Not the space?  So if you have 2^32 quantum computers and 2^64 plaintexts, you still need to run them for 2^80 cycles, right?  That sounds like 50 year protection to me…

— Mike

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 14 Aug 2015 14:46:17 -0700

> But Grover only square-roots the time required, right?  Not the space?  So if you have 2^32 quantum computers and 2^64 plaintexts, you still need to run them for 2^80 cycles, right?  That sounds li…

It square roots the number of queries.  The standard Grover algorithm
is serial, but I wouldn't be surprised if there were some way to get
at least a bit of parallelism out of it.  But yeah, without some kind
of parallelization, the actual running time might still be excessive.
I don't think space matters too much, though -- you can just ask "does
AES_k(0) hash to something such-and-such".

--Andy

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 14 Aug 2015 16:43:59 -0700

> On Aug 14, 2015, at 2:46 PM, Andy Lutomirski <[email-masked]> wrote:
> 
> On Fri, Aug 14, 2015 at 2:41 PM, Michael Hamburg <[email-masked] <mailto:[email-masked]>> wrote:
>> 

I should have said area rather than space, though it’s not obvious that
"hashing to something such-and-such” gives free compression of the
2^64 preimages.

I was curious if anyone on this list knows of a parallel Grover, but

http://arxiv.org/abs/quant-ph/9711070 <http://arxiv.org/abs/quant-ph/9711070>

claims to show that it is impossible.

— Mike

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 14 Aug 2015 17:12:12 -0700

On Aug 14, 2015 4:44 PM, "Michael Hamburg" <[email-masked]> wrote:
>>>>> 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.
>>> But Grover only square-roots the time required, right?  Not the space?
So if you have 2^32 quantum computers and 2^64 plaintexts, you still need
to run them for 2^80 cycles, right?  That sounds like 50 year protection to
me…
> "hashing to something such-and-such” gives free compression of the

Hmm, I was thinking about it wrong.  A classical machine can check
membership in a set quickly -- just implement a hash table in memory.
Multiple threads can share the memory.  A quantum machine has a bit more
trouble, since you have to activate all memory cells for each query.

So maybe area * time is still pretty bad.

> http://arxiv.org/abs/quant-ph/9711070
>

I'll have to read that.

--Andy

---

From: "Mehmet Adalier (Antara Teknik)" <[email-masked]>
Date: Sat, 15 Aug 2015 00:23:38 +0000 (UTC)

my understanding is that the paper claims that attempting to parallelize Grover on a single quantum computer does not provide benefits.
however, the paper describes that the search space can be divided into sub-searches and each sub-search executed independently, in parallel, on multiple systems (i.e. a cluster of quantum computers) --which should deliver linear scale.
    "This shows that to get a certain success probability we can gain only a factor of√S in T by using S oracles, but this is essentially the same performance as Sindependent Grover searches, each working on one Sthof the total search space. "
   so entities that could afford a (yet-to-be-invented) cluster of quantum computers could do the search in parallel
mehmet
      From: Andy Lutomirski <[email-masked]>
 To: Mike Hamburg <[email-masked]> 
Cc: Russ Housley <[email-masked]>; [email-masked] 
 Sent: Friday, August 14, 2015 5:12 PM
 Subject: Re: [Cfrg] New guidance from NSA on cryptographic algorithms

On Aug 14, 2015 4:44 PM, "Michael Hamburg" <[email-masked]> wrote:
> 2^64 preimages.Hmm, I was thinking about it wrong.  A classical machine can check membership in a set quickly -- just implement a hash table in memory.  Multiple threads can share the memory.  A quantum machine has a bit more trouble, since you have to activate all memory cells for each query.So maybe area * time is still pretty bad.>

--Andy> — Mike

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 15 Aug 2015 20:36:08 +0100

> establishment techniques.

After CFRG have finished the meat of the work on new curves
(can we have that *soon*, pretty please?) then I think it'd
be interesting to know if there were a consensus amongst
qualified CFRG folks as to what, if anything, the IETF might
want to do about quantum computer attacks on crypto.

In the meantime, I very much hope that we (IETF or CFRG) do
not simply blindly follow the advice of any one nation-state
on this, or any, cryptographic topic. While governments may
have the best expertise on this topic, and while they also do
undoubtedly have many fine people honestly working to improve
Internet security and privacy, we do also know that some parts
of the exact same organisations that could provide expert advice
here have been credibly reported to be working to undermine
Internet security and privacy. At this point it would arguably
be irresponsible to simply take what any such organisation says
on trust.

So I think the right thing is to factor this in, but to carefully
consider what if anything to do and when and to (at least try)
get a good bit more input than just this. I would prefer that
we end up with a well considered approach to handling this even
if that risked say another year's worth of data being at risk of
being deciphered if the relevant machines do get built in a few
more years. While that doesn't sound so good, I think it'd be
worse to rush to upgrade now and then find out that we made the
wrong upgrade. For example, an ineffective upgrade here could
result in less interoperability and hence more cleartext, or more
ciphertext that's at risk from a quantum computer.

But please first finish the work on new curves!

S.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 16 Aug 2015 09:20:12 -0700

> want to do about quantum computer attacks on crypto.

Notice that we've already had proposals for PQ algorithms in TLS,
starting in the 1990's with NTRU. However, many proposals like ring
LWE have a very murky cryptanalytic picture. It's more reasonable to
wait for something like NESSIE or additional funding for research into
post-quantum cryptography to bear fruit. I don't see anything in the
NSA statement that makes it sound like they are going to come up with
proposals within a year or so from them, but rather start working on
processes like the AES process.

Of course we don't need to change protocols. All proposals will meet
standard security definitions for already existing primitives. The
challenge comes with ensuring that this is enough for security: it
hasn't been.

> ciphertext that's at risk from a quantum computer.

If introducing new ciphers reduces interoperability, that's a failure.
But it's entirely dependent on how the transition is handled. Our
stated preference to permit many configurations from a smorgasbord
with the only basic ingredient being utterly unpalatable should be
reversed. Instead there should be few suites, with the MTI strong.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 17 Aug 2015 11:28:31 +0000

Andy Lutomirski <[email-masked]> writes:

>That's not enough.  If you attack N ciphertexts at once, then any trial key
>has probability 2^256/N of matching one.  Grover search finds a match in
>~sqrt(2^256/N) tries (there's factor of 4 or so in there, but that doesn't
>matter much).  This isn't a comfortable margin as N approaches, say, 2^64.  I
>think people should use at least 384-bit symmetric keys to defend against this
>type of attack.

... and then the attackers use an evil maid attack, or your data is leaked by
a whistleblower, or given to Hillary Clinton, and suddenly all your numerology
was for naught.

(It doesn't matter how much numerology you apply because if your data gets out
it'll be by some means other than an attack on the crypto.  All you need is
good-enough crypto, which we have plenty of, and then you need to look at all
the other sources of compromise and address those, which few people are doing
because they're all too busy arguing over how many key bits can fit on the end
of a pin).

Peter.

---

From: Alyssa Rowan <[email-masked]>
Date: Tue, 18 Aug 2015 07:19:04 +0100

On 2015-08-16 17:20, Watson Ladd wrote:

> It's more reasonable to wait for something like NESSIE or
> additional funding for research into post-quantum cryptography to
> bear fruit. I don't see anything in the NSA statement that makes it
> sound like they are going to come up with proposals within a year
> or so from them, but rather start working on processes like the AES
> process.

Agreed. Divining intention behind an intelligence agency's actions is
fraught with difficulty. I agree, we should not let any such national
agency's stance affect our work securing the internet in any way:
after all, it could be disinformation.

That caveat aside, it doesn't read like panic to me: just planning.

Why they seem happy with RSA-3072 (was that ever in Suite B?) and less
happy with P-256, I'm not sure: and after some thought, that's what
makes me kind of doubt it's for technical reasons.

If it's anything like the position over here, it may just have more to
do with organisational processes like classification destratification.
They haven't been asked to deliver two different "levels" for S & TS
anymore, so they're simply keeping the "big" one and sticking with it.
As for PQ, they are tasked with 50 year protection and don't have a
crystal ball, and they are extremely conservative.

Our "big" level sounds like it's going to have more margin than
theirs; and PQ is already interesting for the future. Let's keep on
course.

- -- 
/akr

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 18 Aug 2015 17:25:00 -0700

On Mon, Aug 17, 2015 at 11:19 PM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

I suspect it's about the size of the quantum computer needed to break
it.  Unless there's an optimization I don't know of, you need a
quantum register big enough to hold a group element, and you also need
a quantum register big enough to store a number approximately the size
of the order of the group.  That's considerably more qubits for
RSA-3072 than for P-256.  (Remember, there's no index calculus here --
Shor's algorithm doesn't really care about the details of the group as
long as it's Abelian, so bigger is harder.)

--Andy

---

From: Yoav Nir <[email-masked]>
Date: Tue, 25 Aug 2015 13:46:10 +0300

> On Aug 18, 2015, at 9:19 AM, Alyssa Rowan <[email-masked]> wrote:
> 

Sure, but plenty of big deployers (government agencies and large companies all over the world) take this particular agency’s recommendations very seriously, so implementers (such as me) will probably have to implement whatever they recommend anyway, and they have enough clout that they will get identifiers for TLS and IPsec. Not that that’s a bad thing.

> That caveat aside, it doesn't read like panic to me: just planning.

Sure. They work on a 10-year cycle. They float this information now, then they (or more likely - NIST) will hold a workshop and ask for comments. Then people will suggest stuff (“no, you shouldn’t use RSA or P-384. you should recommend NTRU”). Then they’ll have more workshops and process comments. Then they will have a draft proposal, and another round of comments. Then they’ll have a final recommendation and a draft testing specification. Then there will be another round of comments on the testing specification. So that is at least 4 years. Then the USG would want to require all agencies to only buy compliant software or hardware, but they can’t do that unless there are at least two certified vendors. So that takes another year. Finally they USG requires all agencies to only buy compliant products, but there are budget concerns and replacement cycles. So it takes another 5 years until all the equipment is replaced or upgraded.

Bottom line, they can’t wait for someone to show a QC that breaks 64-bit ciphers in 10 seconds before starting to work on this. As soon as they deem the risk of something being available 10 years from now to be sufficiently high to justify the expense, they have to start working on this.

Yoav