Subject: [IPsec] I-D Action: draft-fluhrer-qr-ikev2-02.txt

From: [email-masked]
Date: Thu, 04 Aug 2016 20:45:43 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the IP Security Maintenance and Extensions of the IETF.

        Title           : Postquantum Preshared Keys for IKEv2
        Authors         : Scott Fluhrer
                          David McGrew
                          Panos Kampanakis
	Filename        : draft-fluhrer-qr-ikev2-02.txt
	Pages           : 12
	Date            : 2016-08-04

Abstract:
   This document describes an extension of IKEv2 to allow it to be
   resistant to a Quantum Computer, by using preshared keys

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-fluhrer-qr-ikev2/

There's also a htmlized version available at:
https://tools.ietf.org/html/draft-fluhrer-qr-ikev2-02

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-fluhrer-qr-ikev2-02

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 5 Aug 2016 10:49:25 +0300

Scott et al.,

It's not great to include a list of algorithms in a particular document, 
because it will quickly grow stale. I suggest to add something like:

The preference of specific algorithms in IKE will likely change over 
time. Please consult [rfc4307bis] or its follow-on document for guidance 
on which algorithms are preferred and which need to be avoided.

Thanks,
	Yaron

-------- Forwarded Message --------
Subject: [IPsec] I-D Action: draft-fluhrer-qr-ikev2-02.txt
Date: Thu, 04 Aug 2016 20:45:43 -0700
From: [email-masked]
To: [email-masked]
CC: [email-masked]

A New Internet-Draft is available from the on-line Internet-Drafts 
directories.
This draft is a work item of the IP Security Maintenance and Extensions 
of the IETF.

Abstract:

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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 5 Aug 2016 12:54:57 +0000

> -----Original Message-----
> From: IPsec [mailto:[email-masked]] On Behalf Of Yaron Sheffer
> Sent: Friday, August 05, 2016 3:49 AM
> To: [email-masked]
> Subject: [IPsec] Fwd: I-D Action: draft-fluhrer-qr-ikev2-02.txt
> 
> Scott et al.,
> 
> It's not great to include a list of algorithms in a particular document, because
> it will quickly grow stale. I suggest to add something like:
> 
> The preference of specific algorithms in IKE will likely change over time.
> Please consult [rfc4307bis] or its follow-on document for guidance on which
> algorithms are preferred and which need to be avoided.

The point of listing algorithms here is to list which ones are Quantum Safe, and which are not, as that may not be obvious to an implementor.  Pointing them to 4307bis isn't helpful, as it doesn't mention which ones are Quantum Safe.

Now, this draft is still fairly early (pending the discussion of requirements); it is quite unlikely that it will be accepted as-is.  I agree that this might not be the ultimate right spot for it; we might (say) amend 4307bis to explicitly state which algorithm is QR or not (and also state that any RFC that defines future algorithms will include their expected Quantum Resistance in the security considerations).  However, until we have a landing spot for such information, I can't think of any place better than this draft.

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 5 Aug 2016 18:23:29 +0300

On 05/08/16 15:54, Scott Fluhrer (sfluhrer) wrote:
>
>> -----Original Message----- From: IPsec
>> [mailto:[email-masked]] On Behalf Of Yaron Sheffer Sent:
>> Friday, August 05, 2016 3:49 AM To: [email-masked] Subject: [IPsec]
>> Fwd: I-D Action: draft-fluhrer-qr-ikev2-02.txt
>>
>> Scott et al.,
>>
>> It's not great to include a list of algorithms in a particular
>> document, because it will quickly grow stale. I suggest to add
>> something like:
>>
>> The preference of specific algorithms in IKE will likely change
>> over time. Please consult [rfc4307bis] or its follow-on document
>> for guidance on which algorithms are preferred and which need to be
>> avoided.
>
> The point of listing algorithms here is to list which ones are
> Quantum Safe, and which are not, as that may not be obvious to an
> implementor.  Pointing them to 4307bis isn't helpful, as it doesn't
> mention which ones are Quantum Safe.
>

My point was that nominally QR-resistant algorithms might still get
broken and be deprecated in 4307bis or maybe the next "bis". I guess my 
proposed text didn't make the point clearly enough.

> Now, this draft is still fairly early (pending the discussion of
> requirements); it is quite unlikely that it will be accepted as-is.
> I agree that this might not be the ultimate right spot for it; we
> might (say) amend 4307bis to explicitly state which algorithm is QR
> or not (and also state that any RFC that defines future algorithms
> will include their expected Quantum Resistance in the security
> considerations).  However, until we have a landing spot for such
> information, I can't think of any place better than this draft.

The trick to that is to add a new column to the IANA table
https://www.iana.org/assignments/ikev2-parameters/ikev2-parameters.xhtml#ikev2-parameters-5

>
>>
>> Thanks, Yaron
>>
>>
>> -------- Forwarded Message -------- Subject: [IPsec] I-D Action:
>> draft-fluhrer-qr-ikev2-02.txt Date: Thu, 04 Aug 2016 20:45:43
>> -0700 From: [email-masked] To: [email-masked] CC:
>> [email-masked]
>>
>>
>> directories. This draft is a work item of the IP Security
>> Maintenance and Extensions of the IETF.
>>
>> Title           : Postquantum Preshared Keys for IKEv2 Authors
>> : Scott Fluhrer David McGrew Panos Kampanakis Filename        :
>> draft-fluhrer-qr-ikev2-02.txt Pages           : 12 Date
>> : 2016-08-04
>>
>> Abstract: This document describes an extension of IKEv2 to allow it
>> to be resistant to a Quantum Computer, by using preshared keys
>>
>>
>> Please note that it may take a couple of minutes from the time of
>> submission until the htmlized version and diff are available at
>> tools.ietf.org.
>>
>> _______________________________________________ IPsec mailing list
>> [email-masked] https://www.ietf.org/mailman/listinfo/ipsec
>>
>> _______________________________________________ IPsec mailing list
>> [email-masked] https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Paul Hoffman" <[email-masked]>
Date: Fri, 05 Aug 2016 08:42:17 -0700

> https://www.iana.org/assignments/ikev2-parameters/ikev2-parameters.xhtml#ikev2-parameters-5

That's the first of two tricks: the second is getting agreement about 
the rules for the values in that column. It seems like there is still 
disagreement in the crypto community about how susceptible different 
algorithms and modes are to quantum.

--Paul Hoffman

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 8 Aug 2016 16:15:01 +0300

> algorithms and modes are to quantum.

As an IANA expert, I am not that happy adding yet another column to
that table. The ESP/IKEv2 reference columns already seem to make
enough confusion for people :-)

Also I think it is bad idea to list which ciphers are quantum
computing safe, as I have no idea whether RC5 or Blowfish are really
in that category, even when they do have long keys...

It might be better to list ciphers which we consider not to be safe,
i.e., explictly note that PRF_AES128_XCBC and PRF_AES128_CMAC are
using 128-bit keys so they might be vulnerable. (Btw it is
PRF_AES128_CMAC, not PRF_AES_CBC).

Also this is something we might want to add to the rfc4307bis provided
we can agree on the text before it goes forward. I.e. I do not think
the RFC4307bis should wait for the text, as we can add it the QR
document also, but if we can agree on that now, then we can add this
kind of warning to rfc4307bis too. That text could be something like
this:

   Quantum computers might able to perform Grover's algorithm; that
   effectively halves the size of a symmetric key. Because of this, to
   provide 128-bit security even when we have quantum computers, the
   symmetric algorithm keys needs to have least 256 bits of entropy.

Btw, both PRF_AES128_XCBC and PRF_AES128_CMAC do use 128-bit keys
always, they cannot use longer keys, so the text saying "even though
they can use larger keys" is wrong, as those versions cannot use
longer keys.
-- 
[email-masked]

---

From: Paul Wouters <[email-masked]>
Date: Mon, 8 Aug 2016 09:41:36 -0400 (EDT)

>   symmetric algorithm keys needs to have least 256 bits of entropy.

Actually, this is a very good reason to bumo the keysizes from 128 to
256. Currently in 7321bis and 4307bis, 128 is MUST and 256 is SHOULD. I
have asked before if we should make 256 MUST and 128 MUST-.

Current text has:

   [1] - This requirement level is for 128-bit keys. 256-bit keys are at
         SHOULD.  192-bit keys can safely be ignored.  [IoT] - This
                requirement is for interoperability with IoT.

    IPsec sessions may have very long life time, and carry multiple
    packets, so there is a need to move 256-bit keys in the long term.
    For that purpose requirement level is for 128 bit keys and 256 bit
    keys are at SHOULD (when applicable).  In that sense 256 bit keys
    status has been raised from MAY in RFC7321 to SHOULD.

Is there anyone who disagrees with making 128 MUST- and 256 MUST ?

Paul

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 9 Aug 2016 12:44:07 +0000

> From: Tero Kivinen [mailto:[email-masked]]
> Sent: Monday, August 08, 2016 9:15 AM
> To: Paul Hoffman
> Cc: Yaron Sheffer; [email-masked]; Scott Fluhrer (sfluhrer)
> Subject: Re: [IPsec] I-D Action: draft-fluhrer-qr-ikev2-02.txt
> 
> Paul Hoffman writes:
> > > https://www.iana.org/assignments/ikev2-parameters/ikev2-
> parameters.x
> > > html#ikev2-parameters-5
> >
> As an IANA expert, I am not that happy adding yet another column to that
> table. The ESP/IKEv2 reference columns already seem to make enough
> confusion for people :-)

On the other hand, we need to give people some guidance somehow...

> 
> Also I think it is bad idea to list which ciphers are quantum computing safe, as
> I have no idea whether RC5 or Blowfish are really in that category, even
> when they do have long keys...

There's no known Quantum attack against either (assuming long keys), and so they're in the same category as AES-256.

> 
> It might be better to list ciphers which we consider not to be safe, i.e.,
> explictly note that PRF_AES128_XCBC and PRF_AES128_CMAC are using 128-
> bit keys so they might be vulnerable. (Btw it is PRF_AES128_CMAC, not
> PRF_AES_CBC).

That makes a lot of sense; ultimately, we don't really know which ones are strong against Quantum Computers (then again, we really don't know which ones are strong against conventional computers using undiscovered attacks :-); we do know some are likely weak.

> 
> Also this is something we might want to add to the rfc4307bis provided we
> can agree on the text before it goes forward. I.e. I do not think the
> RFC4307bis should wait for the text, as we can add it the QR document also,
> but if we can agree on that now, then we can add this kind of warning to
> rfc4307bis too. That text could be something like
> this:
> 
> always, they cannot use longer keys, so the text saying "even though they
> can use larger keys" is wrong, as those versions cannot use longer keys.

Actually, if you look through the definitions of the transforms that IANA points to, RFC4434 and RFC4615, the transform can take as input a "key" longer than 128 bits.  Yes, if you look inside the definition of the transform, you see that they transform the arbitrary-length "key" into a 128 bit one; people quite often don't look into the innards of their crypto (nor should they have to).

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 9 Aug 2016 16:07:27 +0300

Scott Fluhrer (sfluhrer) writes:
> Actually, if you look through the definitions of the transforms that
> IANA points to, RFC4434 and RFC4615, the transform can take as input
> a "key" longer than 128 bits.  Yes, if you look inside the
> definition of the transform, you see that they transform the
> arbitrary-length "key" into a 128 bit one; people quite often don't
> look into the innards of their crypto (nor should they have to). 

Yes, as PRF they can take arbitrary long keys, but the AES is always
using 128-bit keys. So both of those are true in a way. For encryption
algorithms you can use the key length attribute to specify key length
for the AES, but for the PRF or INTEG you cannot, instead they use
fixed length key for AES.

The original version of the AES-XCBC-PRF-128 specified in the RFC3664
did require the exactly 128-bit key for the PRF use also, but this
caused problems as in IKEv2 we want to use PRF on the nonces, and the
shared secret, thus requiring them to be 128-bits caused problems.
Because of this RFC4434 was done so that it allows arbitrary sized
keying material but the PRF still has security of 128-bit...

I.e. the prehashing done to feed the PRF key to the AES is just to
allow any sized material, and using longer PRF key does not increase
the security.

So at least separate the "PRF key" and "AES key" in the text, so it is
clear which text we are refering.
-- 
[email-masked]

---

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 09 Aug 2016 09:15:47 -0700

On 9 Aug 2016, at 5:44, Scott Fluhrer (sfluhrer) wrote:

>> that

Do we? Who is "we"? Why is "our" guidance any better than what they get 
from their own experts, particularly if "our" guidance gets ossified in 
an IANA registry or RFCs that are updated slowly?

>> computing safe, as
> There's no known Quantum attack against either (assuming long keys), 
> and so they're in the same category as AES-256.

That would be better stated as "There's currently no known..."

>> i.e.,
> That makes a lot of sense; ultimately, we don't really know which ones 
> are strong against Quantum Computers (then again, we really don't know 
> which ones are strong against conventional computers using 
> undiscovered attacks :-); we do know some are likely weak.

Exactly.

--Paul Hoffman

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 11 Aug 2016 09:12:30 +0300

Hi, 

> an IANA registry or RFCs that are updated slowly?

Instead of listing QR-secure (or insecure) symmetric algorithms
it's probably better to give some generic advice of selecting
symmetric crypto in presense of Quantum Computers.

For example (I stole the text from http://www.pqcrypto.eu.org/docs/initial-recommendations.pdf):

Symmetric systems are usually not affected by Shor's algorithm, but they are affected by
Grover's algorithm. Under Grover's attack, the best security a key of length n can offer is
2^(n/2), so AES-128 offers only 2^64 post-quantum security. This document recommends 
using algorithms with 256-bit keys to achieve 2^128 post-quantum security.

Exactly.

> --Paul Hoffman

Regards,
Valery.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 11 Aug 2016 13:50:14 +0000

> From: Valery Smyslov [mailto:[email-masked]]
> Sent: Thursday, August 11, 2016 2:13 AM
> To: Paul Hoffman; Scott Fluhrer (sfluhrer)
> Cc: [email-masked]
> > Do we? Who is "we"? Why is "our" guidance any better than what they
> > get from their own experts, particularly if "our" guidance gets
> > ossified in an IANA registry or RFCs that are updated slowly?
> 
> Instead of listing QR-secure (or insecure) symmetric algorithms it's probably
> better to give some generic advice of selecting symmetric crypto in presense
> of Quantum Computers.
> 
> Symmetric systems are usually not affected by Shor's algorithm, but they are
> affected by Grover's algorithm. Under Grover's attack, the best security a
> key of length n can offer is 2^(n/2), so AES-128 offers only 2^64 post-
> quantum security. This document recommends using algorithms with 256-bit
> keys to achieve 2^128 post-quantum security.

I'll steal this text in the next version (along with a note that, while the PRFs PRF_AES128_XCBC and PRF_AES128_CMAC do accept keys larger than 128 bits, they internally convert them to 128 bit values, and hence should be considered as 128 bit algorithms).

---

From: Paul Wouters <[email-masked]>
Date: Tue, 23 Aug 2016 13:55:10 -0400 (EDT)

On Mon, 8 Aug 2016, Paul Wouters wrote:

I haven't heard any objection to making 128 bit key sizes MUST- and
256 bit key sizes MUST. Answers that agree or disagree would be good
to hear.

Paul

---

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 23 Aug 2016 11:32:51 -0700

On 23 Aug 2016, at 10:55, Paul Wouters wrote:

> 256 bit key sizes MUST.

You can hear one now.

> Answers that agree or disagree would be good
> to hear.

The proposed change is based on the existence of quantum computers that 
have a sufficient number of properly-interacting qbits. We have 
literally no idea if those computers will ever exist. All current data 
indicates that we will see the progressing of "sufficient number" and 
"properly-interacting" and be able to increase key sizes well ahead of 
widespread use of quantum computers.

--Paul Hoffman

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 23 Aug 2016 15:12:34 -0400

Paul,

> widespread use of quantum computers.

Just to play devil's advocate here, are you implying that we'll see a
5-10-year lead time on quantum computer development sufficiently in order
to spend those 5-10 years:
1) having this discussion again,
2) revving the documents
3) getting the revved documents through the process
4) getting the revved documents published
5) getting the revved documents implemented
6) getting that new implementation into the field, and (most importantly)
7) getting the OLD hardware decommissioned?

I think it would be a good 5 years just to get through step 6, let alone
getting to step 7.  I suspect step 7 is yet another 5-10 years beyond step
6 (and I feel like I'm being generous).

So if we assume that quantum computers WILL, eventually, have a sufficient
number of properly-interacting qbits, then the question is when do we
think that will occur, and when do we need to start the process to update
such that we get to step 7 before the quantum computers arrive?

(I take it from your email that you disagree with this assumption, which
is fine, but I believe this is the assumption from which these all occur)

Also note that MTI does not imply MTU/MTD.  (Use/Deploy).  But I know you
knew that.

> --Paul Hoffman

-derek

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

---

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 23 Aug 2016 12:28:55 -0700

> 7) getting the OLD hardware decommissioned?

No, not at all. PaulW's proposal is *not* about adding a new algorithm, 
it is changing the recommendation status for the algorithms. Both 
algorithms will be in the deployed systems. So the 5-10 years lead time 
is getting users to change their configs. If we can't get them to change 
them in 10 years, we probably can't get them to change them ever. It is 
operator's responsibility to maintain their configurations, not ours to 
be the configuration police. Note that this thread is split off from the 
QR thread.

--PaulH

---

From: Yoav Nir <[email-masked]>
Date: Tue, 23 Aug 2016 22:35:32 +0300

> On 23 Aug 2016, at 9:32 PM, Paul Hoffman <[email-masked]> wrote:
> 
> The proposed change is based on the existence of quantum computers that have a sufficient number of properly-interacting qbits. We have literally no idea if those computers will ever exist. All current data indicates that we will see the progressing of "sufficient number" and "properly-interacting" and be able to increase key sizes well ahead of widespread use of quantum computers.

Perhaps, but those quantum computers will be able to decrypt the traffic we are sending now where the key is only 128-bit long.

The vast majority of implementations support both 128-bit and 256-bit keys for AES. When the day arrives that we feel it’s time to take the performance hit and more to 256-bit AES, all of us will merely have to reconfigure existing deployments. My company’s implementation has supported AES-256 since 2001, and I’m sure others are similar. But those outliers who support only one key length (presumably 128) will impede everyone’s transition to 256-bits. 

So I’m sympathetic to Paul W’s idea to make 256-bit a MUST. I don’t think it’s reasonable to release a product in 2016 that only supports 128-bit AES. I’m not saying anything about what the defaults should be and what configuration advice should be, but requiring support for 256-bit as a precaution seems prudent. 

I’m less sympathetic to reducing AES-128 to MUST-. This algorithm with that key length is the most common, most widely deployed for IKE, IPsec, TLS, and SSH. It’s by far the most commonly deployed. Our focus in these documents in interoperability, so this needs to be a MUST. As you’ve said, we don’t know if quantum computers are going to become practical in our lifetimes. Without them, AES-256 offers little advantage. I don’t think we should be signalling that AES-128 is on its way out.

Yoav

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 23 Aug 2016 15:43:40 -0400

Paul,

> be the configuration police. Note that this thread is split off from the

I apologize for jumping in, but my reading doesn't match your statement. 
My reading was Paul proposing to change the Implementation Level of
AES-256 from SHOULD to MUST.  That implied subtext is that some devices
may not currently implement AES-256 (even though they SHOULD) and he wants
to ensure that, if/when a quantum computer comes into existence then all
that is requires *IS* a configuration change to move deployment to
AES-256.

I definitely agree that the goal should be that only a configuration
change should be required to ensure AES-256 gets used.

-derek

---

From: "Paul Hoffman" <[email-masked]>
Date: Tue, 23 Aug 2016 12:53:54 -0700

On 23 Aug 2016, at 12:43, Derek Atkins wrote:

> AES-256 from SHOULD to MUST.

Ah! If you're right, then I agree with that part of his proposal.

> That implied subtext is that some devices

That sounds fine.

I may have misunderstood his proposal because he also wanted to demote 
AES-128 from MUST to MUST-. I object on the grounds that we have no idea 
if there will quantum-capable computers that can erode AES-128 in the 
foreseeable future, and that even if a dedicated adversary could weaken 
AES-128 to say 80 bits of strength, that we would want to say to all 
developers "don't implement this".

--PaulH

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 23 Aug 2016 16:00:11 -0400

On Tue, August 23, 2016 3:53 pm, Paul Hoffman wrote:
[snip]
> developers "don't implement this".

Yeah, I also disagree with the demotion of AES-128 to MUST-.  It's the
most widely deployed now, and when Q-C happens we can turn it off with a
config change and work to remove it at that time.  I also see no reason to
prefer *using* AES-256 today over AES-128, except, perhaps, for 10-30-year
PFS against a potential Q-C that could bring the 128-bit down to 64-bit
security.  But this also assumes an adversary that is recording and
storing all encrypted communications for the next 10-30 years until a Q-C
can be built to break it.

-derek

---

From: Paul Wouters <[email-masked]>
Date: Tue, 23 Aug 2016 16:41:05 -0400 (EDT)

On Tue, 23 Aug 2016, Derek Atkins wrote:

> config change and work to remove it at that time.

I think that is fair, so let me propose the following changes for both
bis documents:

Current:

[1] - This requirement level is for 128-bit keys. 256-bit keys are at
    SHOULD. 192-bit keys can safely be ignored.

New:

[1] - This implementation status covers 128-bit and 256-bit keys. 192-bit
       keys remain at MAY status.

Paul

---

From: Michael Richardson <[email-masked]>
Date: Wed, 24 Aug 2016 01:07:41 -0400

> 7) getting the OLD hardware decommissioned?

Forgive my ignorance here; my BSc in particle physics is ~20 years out of date.
(this %#@*$ internet thing distracted me...)

My understanding is we currently have a small number of qbits
"properly-interacting".  I think that I read an article saying it was 4 or
so, but I just read that we are at 12 qbits in 2006, 28 in 2007 (maybe),
and >1000 in 2015 (maybe).  On the other hand, "2 qubit silicon gate" in 2016.

I believe that we need 128 to interact to break AES-128?

I'm just trying understand how the revolution that will take us from ~12
to 128, won't take us to 256 the following week.

I feel kinda like we are re-arranging the chairs on the titanic here.

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 24 Aug 2016 12:58:38 +0000

> From: Michael Richardson [mailto:[email-masked]]
> Sent: Wednesday, August 24, 2016 1:08 AM
> To: Derek Atkins
> Cc: Paul Hoffman; [email-masked]; Paul Wouters; Tero Kivinen; Scott Fluhrer
> (sfluhrer)
> Subject: Re: [IPsec] 4307bis/7321bis key sizes
> 
> 
> My understanding is we currently have a small number of qbits "properly-
> interacting".  I think that I read an article saying it was 4 or so, but I just read
> that we are at 12 qbits in 2006, 28 in 2007 (maybe), and >1000 in 2015
> (maybe).  On the other hand, "2 qubit silicon gate" in 2016.
> 

Actually, rather more than that; see http://arxiv.org/pdf/1512.04965.pdf for one rather detailed estimate.

However, it doesn't appear that the number of qbits is the limiting factor; instead, it is simply time.  The best known quantum attack against AES is Grover's algorithm; against AES-128, that would take O(2**64) entangled evaluations of AES (where the constant of proportionality is somewhat larger than 1).  In contrast, AES-256 would take O(2**128) such evaluations; we generally agree that performing that many operations is infeasible for any practical attacker, and so we consider AES-256 safe.

Actually, it's even worse than that for the attacker, even for AES-128; Grover's algorithm isn't parallelizable, and so instead of 2**64 operations spread over a large computing cluster, we're talking about 2**64 run on a single thread, and that's far more difficult.  There's no known parallelized approach that's better than dividing up the keyspace into 2**k regions, and running a separate instance of Grovers over each region (using 2**k independent quantum computers); this ends up taking 2**(128-k)/2 time.  If the bound on the number of evaluations a single quantum computer can do is 2**50 (for example, 2**25 evaluations per second for a year), then the attacker will need 2**28 separate quantum computers.

Does this mean that attacking AES-128 is infeasible?  No; there are too many unknowns involved; it should be clear that applying the same argument to AES-256 implies that the attacker has no hope.

> 
> I'm just trying understand how the revolution that will take us from ~12 to
> 128, won't take us to 256 the following week.
> 

No, the debate between AES-128 and AES-256 is more like "AES-128 *might* be quantum secure; AES-256 is (baring some unexpected crypto development) *very* secure"

---

From: Michael Richardson <[email-masked]>
Date: Wed, 24 Aug 2016 18:17:15 -0400

Thank you for the reply, it helps me understand that AES-256 is worthwhile.

-- 
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-                  (Camping this week!)