Subject: [IPsec] Modp-12288 and Modp-16384

From: Tero Kivinen <[email-masked]>
Date: Tue, 17 Jul 2018 18:15:52 +0300

When we greated RFC3526 [1] in 2003 we included 1536, 2048, 3072,
4096, 6144, and 8192 bit modp groups. I did also create 12288 and
16384 bit modp groups [2], but we did not include those as we assumed
they would be too slow for normal use.

Now sometimes there is requirement to align all security parameters
with AES-256 also (because AES-128 is not enough if someone gets
quantum computers some day). 

SP800-57 part 1 rev 4 [3] has table 2 that says:

Security  Symmetric     FCC               IFC           ECC
Strength  key           (e.g. DSA,        (e.g.,        (e.g., 
          algorithms    D-H)              RSA)          ECDSA)
<=80      2TDEA         L=1024, N=160     k=1024        f=160-233
112       3TDEA         L=2048, N=224     k=2048        f=224-255
128       AES-128       L=3072, N=256     k=3072        f=256-383
192       AES-192       L=7680, N=384     k=7680        f=384-511
256       AES-256       L=15360, N=512    k=15360       f=512+

Meaning that we do not have any MODP groups with IANA numbers that
would match AES-256. For vendor to add elliptic curve support to
simply be able to mark that tick mark saying we do support AES-256 is
bit much. Adding 16384 bit MODP group is much faster and easier, and
nobody does not need to use it (I think the recommended group in NIST
documents is still the 2048 bit group).

NIST SP 800-56A Rev 3 [4] aligns with this and says that MODP-8192 is
for less than 200 bits of security, i.e., not enough for AES-256.

In the SP 800-56B rev2 draft [5], there is formula in Appendix D,
which allows you to calculate the strength for different bit lengths
and if you plug in the 15360 you get 264 bits. To get 256 bits of
maximum strength the nBits needs to be between 14446-14993. 15000
would already give you 264, i.e., the same than 15360 gives. 15360 is
of course 1024*15 so it is nice round number in binary.

If you plug in 12288 to that formula you get strength of 240 and 16384
gives you 272.

Checking old performance numbers I can see that in 2008 the speed of
6144 group was same as 16384 is with current machines, which most
likely matched what 2048 or 3072 bit group speed was in 2003 (i.e.
about half a second per full Diffie-Hellman).

So my question is do other people think it would be useful to allocate
IANA numbers for the 12288 and 16384 bit MODP groups?

You can of course use private numbers, but I myself think it would be
good idea to have IANA numbers for those groups too, just in case
someone wants interoperability with them at some point. Also we do not
yet know how quantum computers are going to do for different
algorithms, i.e., whether P-521 is harder or easier than MODP 16384.

[1] https://datatracker.ietf.org/doc/rfc3526/
[2] https://kivinen.iki.fi/primes/
[3] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf
[4] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf
[5] https://csrc.nist.gov/CSRC/media/Publications/sp/800-56b/rev-2/draft/documents/sp800-56Br2-draft.pdf
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 17 Jul 2018 11:26:10 -0400

Hi,

my concern is that these MODP groups will have public keys of  1.5-2 Kb in
size,
so it can make using them problematic in real world due to fragmentation
issues...

Regards,
Valery.

> When we greated RFC3526 [1] in 2003 we included 1536, 2048, 3072, 4096,
> 6144, and 8192 bit modp groups. I did also create 12288 and
> 16384 bit modp groups [2], but we did not include those as we assumed they
> would be too slow for normal use.
> 
> Now sometimes there is requirement to align all security parameters with
> AES-256 also (because AES-128 is not enough if someone gets quantum
> computers some day).
> 
> would match AES-256. For vendor to add elliptic curve support to simply be
> able to mark that tick mark saying we do support AES-256 is bit much.
Adding
> 16384 bit MODP group is much faster and easier, and nobody does not need
> to use it (I think the recommended group in NIST documents is still the
2048
> bit group).
> 
> NIST SP 800-56A Rev 3 [4] aligns with this and says that MODP-8192 is for
less
> than 200 bits of security, i.e., not enough for AES-256.
> 
> In the SP 800-56B rev2 draft [5], there is formula in Appendix D, which
allows
> you to calculate the strength for different bit lengths and if you plug in
the
> 15360 you get 264 bits. To get 256 bits of maximum strength the nBits
needs
> to be between 14446-14993. 15000 would already give you 264, i.e., the
same
> than 15360 gives. 15360 is of course 1024*15 so it is nice round number in
> binary.
> 
gives
> you 272.
> 6144 group was same as 16384 is with current machines, which most likely
> matched what 2048 or 3072 bit group speed was in 2003 (i.e.
IANA
> numbers for the 12288 and 16384 bit MODP groups?
> 
> You can of course use private numbers, but I myself think it would be good
> idea to have IANA numbers for those groups too, just in case someone wants
> interoperability with them at some point. Also we do not yet know how
> quantum computers are going to do for different algorithms, i.e., whether
P-
> 521 is harder or easier than MODP 16384.
> 
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 17 Jul 2018 15:27:36 +0000

If the requirement for AES-256 is to handle the scenario "someone gets a quantum computer", then in that scenario, there is no realistic DH group size that is secure.

Hence, I personally see no point in allocating IANA numbers for the larger than 8k MODP groups.  The only scenario I can think of where they might be useful would be one where all of the following apply:

	- We believe that there's an adversary that can perform significantly more than circa 2**128 computations'
	- We are not concerned with adversaries with a Quantum Computer
	- For some reason, we don't want to use ECDH.

> -----Original Message-----
> From: IPsec <[email-masked]> On Behalf Of Tero Kivinen
> Sent: Tuesday, July 17, 2018 11:16 AM
> To: [email-masked]
> Subject: [IPsec] Modp-12288 and Modp-16384
> 
> able to mark that tick mark saying we do support AES-256 is bit much. Adding
> to use it (I think the recommended group in NIST documents is still the 2048
> bit group).
> 
> NIST SP 800-56A Rev 3 [4] aligns with this and says that MODP-8192 is for less
> In the SP 800-56B rev2 draft [5], there is formula in Appendix D, which allows
> you to calculate the strength for different bit lengths and if you plug in the
> 15360 you get 264 bits. To get 256 bits of maximum strength the nBits needs
> to be between 14446-14993. 15000 would already give you 264, i.e., the same
> If you plug in 12288 to that formula you get strength of 240 and 16384 gives
> you 272.
> 
> So my question is do other people think it would be useful to allocate IANA
> idea to have IANA numbers for those groups too, just in case someone
> wants interoperability with them at some point. Also we do not yet know
> how quantum computers are going to do for different algorithms, i.e.,
> whether P-521 is harder or easier than MODP 16384.
>

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 17 Jul 2018 23:36:40 +0300

Valery Smyslov writes:
> my concern is that these MODP groups will have public keys of 1.5-2
> Kb in size, so it can make using them problematic in real world due
> to fragmentation issues...

In most of those cases the uses are not really road warriors or
similar setups, but more in a line of SGW between two offices, and the
network can often be required to behave properly. I.e., if your
companies ISP drops all fragments, better switch to another ISP or
complain to ISP and require them to fix the issue. This is very
different than normal cases where there is no point of trying to get
big udp packets through the hotel captive portal, or nat etc.

We were mostly able to get IKE work with certificates and so even
before IKE fragmentation with similar packet sizes, and we do have
text in section 2 of the RFC7296 which says that implementation SHOULD
work with 3000 octets long packets:

   All IKEv2 implementations MUST be able to send, receive, and process
   IKE messages that are up to 1280 octets long, and they SHOULD be able
   to send, receive, and process messages that are up to 3000 octets
   long.  

This of course does not mean that long packets work through your
network, but in SGW <-> SGW setting that can quite often be taken care
of. IKEv2 implementations themselves should still work with such
packets if the network work.
-- 
[email-masked]

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 18 Jul 2018 00:17:06 +0300

Scott Fluhrer (sfluhrer) writes:
> If the requirement for AES-256 is to handle the scenario "someone
> gets a quantum computer", then in that scenario, there is no
> realistic DH group size that is secure.

That we do not know until we know what those quantum computers can
really do... I have not seen anybody saying how many qbits you need to
break MODP-2048. Most of the things I have seen talks about factoring
RSA, and even then they do not provide numbers.

draft-hoffman-c2pq also says that we might have machines breaking
AES-128 before than we have machines that can break Diffie-Hellman,
i.e., it is most likely easier to make machine running Grover's
algorithm than machine running Shor's algorithm. 

> Hence, I personally see no point in allocating IANA numbers for the
> larger than 8k MODP groups. The only scenario I can think of where
> they might be useful would be one where all of the following apply:
> 
> 	- We believe that there's an adversary that can perform
> 	  significantly more than circa 2**128 computations' 

Or cases where customer requires your product to include support
256-bits of security level. Perhaps they read from the paper that 128
bits is too little if someone gets quantum computer and thats why
256-bit security is what you need. I.e., there is no real security
reason for that, just to be able to tick check box saying "support
security level of 256-bits".

To provide that you need AES-256, and SHA2-512 for symmetric parts,
and then either P-521 or MODP-15360 for Diffie-Hellman. If you do not
have ECDH in your implementation it is much easier to add just
MODP-16384 in configuration especially as the main reason is to tick
that check box.
-- 
[email-masked]

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 18 Jul 2018 14:55:27 +0000

Answering to give some info about what we know about the likely capabilities of Quantum Computers.

> From: Tero Kivinen <[email-masked]>
> Sent: Tuesday, July 17, 2018 5:17 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>
> Cc: [email-masked]
> Subject: RE: [IPsec] Modp-12288 and Modp-16384
> 
> > If the requirement for AES-256 is to handle the scenario "someone gets
> > a quantum computer", then in that scenario, there is no realistic DH
> > group size that is secure.
> 
> break MODP-2048.

It's about twice as many as you need to factor a 2048 bit composite; so about 4k (logical) qubits.

> Most of the things I have seen talks about factoring RSA,
> and even then they do not provide numbers.

How about https://arxiv.org/abs/quant-ph/0205095 - to factor an n bit number, you can do it with circa 2n qubits.

If you want other references, we have https://arxiv.org/abs/1611.07995  and https://arxiv.org/pdf/1706.07884.pdf both with similar results.  We also have https://arxiv.org/abs/quant-ph/0601097 which suggests a way with 1.5n qubits; however that paper makes some assumptions about errors that might not be true.

Of course, these papers are focusing in on minimizing the number of qubits; it's quite possible a trade-off that increases the number of qubits, while decreasing the number of (say) T gates, would be advantageous; we don't know enough about the relative costs to know.

> AES-128 before than we have machines that can break Diffie-Hellman, i.e., it
> is most likely easier to make machine running Grover's algorithm than
> machine running Shor's algorithm.

That work totally ignores the amount of time we're talking about with O(2**64) computations (and parallelization is less helpful than usual; Grover's becomes less efficient the more we parallelize it).

Also, the interesting algorithms in Quantum Chemical modelling are significantly different from Grover's.  It's possible that there are some proposed protein folding problems that would use Grover's...

---

From: <[email-masked]>
Date: Wed, 18 Jul 2018 15:03:17 +0000

> On Jul 18, 2018, at 10:55 AM, Scott Fluhrer (sfluhrer) <sfluhrer=[email-masked]> wrote:
> 

That, times a factor for error correction.  I've seen various opionions on how large that factor is; one estimate was 100 if not higher.  An interesting question is whether coherence across half a million qubits is achievable.

	paul

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 18 Jul 2018 15:22:49 +0000

> From: IPsec <[email-masked]> On Behalf Of [email-masked]
> Sent: Wednesday, July 18, 2018 11:03 AM
> To: sfluhrer=[email-masked]
> Cc: [email-masked]; [email-masked]
> Subject: Re: [IPsec] Modp-12288 and Modp-16384
> 
> 
> 
> > On Jul 18, 2018, at 10:55 AM, Scott Fluhrer (sfluhrer)
> <sfluhrer=[email-masked]> wrote:
> >
> >> really do... I have not seen anybody saying how many qbits you need
> >> to break MODP-2048.
> >
> >> Most of the things I have seen talks about factoring RSA, and even
> >> then they do not provide numbers.
> >
> > How about https://arxiv.org/abs/quant-ph/0205095 - to factor an n bit
> number, you can do it with circa 2n qubits.
> 
> That, times a factor for error correction.  I've seen various opionions on how
> large that factor is; one estimate was 100 if not higher.

Well, yes, this is logical qubits.  As for how many physical qubits you need to implement a logical one, well, that depends on the error correction logic you use (and that selection depends a great deal on the error rate you get on the physical qubit operations, and various proposed implementations of quantum computing differ quite a bit on their likely error rate).

> An interesting
> question is whether coherence across half a million qubits is achievable.

Actually, that's the point of quantum error correction; you don't need to achieve consistent coherence across all those physical qubits; it suffices if you get coherence across enough of them..

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 18 Jul 2018 18:34:43 +0300

Scott Fluhrer \(sfluhrer\) writes:
> How about https://arxiv.org/abs/quant-ph/0205095 - to factor an n
> bit number, you can do it with circa 2n qubits.
> 
> If you want other references, we have
> https://arxiv.org/abs/1611.07995 and
> https://arxiv.org/pdf/1706.07884.pdf both with similar results. We
> also have https://arxiv.org/abs/quant-ph/0601097 which suggests a
> way with 1.5n qubits; however that paper makes some assumptions
> about errors that might not be true.

It would be good idea to get draft-hoffman-c2pq updated with these
references. 

> Of course, these papers are focusing in on minimizing the number of
> qubits; it's quite possible a trade-off that increases the number of
> qubits, while decreasing the number of (say) T gates, would be
> advantageous; we don't know enough about the relative costs to know.

Yep, and how many bits we need more because of error correcting stuff
etc. 

> That work totally ignores the amount of time we're talking about
> with O(2**64) computations (and parallelization is less helpful than
> usual; Grover's becomes less efficient the more we parallelize it).

Any idea how many computations needs to be done for the shor's
algorithm, i.e., breaking 2048 bit Diffie-Hellman. I have just seen
text saying it is polynominal time, but I have not really seen any
guesses what the actual numbers are going to be. And I understand that
there is also quite big classical computation pre- and post-processing
steps too.

> Also, the interesting algorithms in Quantum Chemical modelling are
> significantly different from Grover's.  It's possible that there are
> some proposed protein folding problems that would use Grover's... 
-- 
[email-masked]

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Wed, 18 Jul 2018 16:08:09 +0000

Hi Tero

I've no issues per se with this, but as per our chat in London, most VPN consumers pick the group with the highest number (of course group24 is more secure than group21, 24 is bigger than 21 ...!)..

Maybe some words of warning around potential performance impact. I’m sure someone somewhere in the world will want this.. 

I feel for the poor vendors support desk "dear customer, I know you enabled group38 (RSA 16384) and now your 5000 device full mesh solution is not converging as quickly as it did before.."..

cheers 

On 17/07/2018, 16:16, "IPsec on behalf of Tero Kivinen" <[email-masked] on behalf of [email-masked]> wrote:

---

From: Yoav Nir <[email-masked]>
Date: Wed, 18 Jul 2018 20:23:26 +0300

> On 18 Jul 2018, at 19:08, Graham Bartlett (grbartle) <grbartle=[email-masked]> wrote:
> 
> Hi Tero
> 

Hasn’t been my experience. Most customers stay with the default. Sophisticated customers compare number of bits. So again 2048-bit group 24 is much better than 521-bit group 21, but nowhere near as good as 8192-bit group 18.

> Maybe some words of warning around potential performance impact. I’m sure someone somewhere in the world will want this.. 

They only need 16384-bit DH if they use 16384-bit RSA, no?

> I feel for the poor vendors support desk "dear customer, I know you enabled group38 (RSA 16384) and now your 5000 device full mesh solution is not converging as quickly as it did before..”..

Publish it and they will come. I once had to tackle a customer request to filter by the RFC 3514 security flag.  As it turns out, this was totally possible with my employer’s firewall product. It just wasn’t a good idea.

Yoav

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 18 Jul 2018 18:27:34 +0000

> Sent: Wednesday, July 18, 2018 11:35 AM
> Cc: [email-masked]; [email-masked]
> > also have https://arxiv.org/abs/quant-ph/0601097 which suggests a way
> > with 1.5n qubits; however that paper makes some assumptions about
> > errors that might not be true.
> 
> Yep, and how many bits we need more because of error correcting stuff etc.

It multiplies it by a factor of N, whose value depends on the quantum error correction algorithm.

In the quantum computing space, they mostly talk about "logical queue bits", that is, they assume that the error correction problem is already solved (unless, of course, they are specifically working on quantum error correction algorithms).

> > That work totally ignores the amount of time we're talking about with
> > O(2**64) computations (and parallelization is less helpful than usual;
> > Grover's becomes less efficient the more we parallelize it).
> 
> Any idea how many computations needs to be done for the shor's algorithm,
> i.e., breaking 2048 bit Diffie-Hellman. I have just seen text saying it is
> polynominal time, but I have not really seen any guesses what the actual
> numbers are going to be.

Very good question; the references I find all essentially say "cubic"; however they don't immediately talk about the constant factor.  I suspect that this constant factor won't be that large; however that most certainly merits further investigation.

> And I understand that there is also quite big
> classical computation pre- and post-processing steps too.

Not really; there is computation needed there, but it is quite straight-forward.

Shor's algorithm gives you a value k where a^x = a^(x+k) mod n; once you have that value k, factoring n is a well understood (and fairly easy) problem, solvable by, say, Miller's algorithm.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 19 Jul 2018 00:00:45 +0300

Hi.

Since my message got lost in the overtime, I’ll say it again here.

AFAIK there is very little usage of anything beyond 4096-bit groups. I don't sense a need for 16K.  Engineering should be about creating what people need (or at least want). 

I haven’t heard anyone say they would like to use 16384-bit DH groups or RSA keys. If they want more “bits” then 2048, they usually go to ECDSA/ECDHE or the CFRG curves.

I don’t feel strongly about this as in “oh my god, this is horrible for the Internet”, but I think this is something we should not do.

Yoav

> On 17 Jul 2018, at 18:15, Tero Kivinen <[email-masked]> wrote:
>

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 19 Jul 2018 01:24:22 +0300

> Since my message got lost in the overtime, I’ll say it again here.

Btw, I copied your comment from jabber to the minutes, as it should
have been releayed, but as our jabber relay was on the microphone, it
got skipped...
-- 
[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Wed, 18 Jul 2018 21:24:18 -0400

Valery Smyslov <[email-masked]> wrote:
    > my concern is that these MODP groups will have public keys of  1.5-2 Kb
    > in size,

I think, what you mean you say, is that thanks to these MODP groups, we can
more effectively test interoperability of fragmentation handling :-)

-- 
]               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: Fri, 27 Jul 2018 18:51:35 +0000

> From: Scott Fluhrer (sfluhrer)
> > guesses what the actual numbers are going to be.
> 
> Very good question; the references I find all essentially say "cubic"; however
> they don't immediately talk about the constant factor.  I suspect that this
> constant factor won't be that large; however that most certainly merits
> further investigation.

Ok, I went through the literature, and while the short answer is "it's complex", I do have some partial answers, including what I believe is a defensible time estimate.

I went through a number of academic papers, and came to the conclusion that factoring 2kbit numbers on a Quantum Computer with circa 4700 qubits available could reasonably be done in time circa 8 billion times the time taken by a single quantum gate (details on how I came to that conclusion are listed below); increasing the size of the numbers to 16k would increase the attack time by a factor of perhaps 60 to 100.

The other factor to address is the actual gate speed.  One result is http://www.nature.com/articles/nature25737 which gives a high fidelity (but not error corrected) gate speed of 1.6usec (using trapped ion qubits).  Adding error correction logic to that would add some overhead, if we take the guess that it slows things down by a factor of 10 (which is the approximate speed of the original Shor error correction code), then that gives us an error corrected speed of 16usec (or 60k gate operations per second).

Combining those two results would give an estimate of less than 2 days to factor a 2k integer.  As for computing a discrete log for a 16k modulus (which is what the original discussion was about), a somewhat larger quantum computer (circa 250k qubit) that ran at the same speed would take several months to compute the discrete log.

Of course, this time estimate is based on current published literature; this is quite an active field, and future work (especially in the realm of gate speed) could easily shrink these numbers significantly.

As a side note, if we look at the time it would take Grover's algorithm to break AES-128, we have https://www.researchgate.net/publication/287249961_Applying_Grover%27s_algorithm_to_AES_quantum_resource_estimates where they estimate a time of 1.16 2^81 = 2.8E24 circuit depth, or about 300 trillion times longer than our estimate for factoring a 2k integer.  Now, this isn't quite an apples-to-apples comparison (for one, with Grover's, you could do some parallelism with independent Quantum Computers, however that costs more in terms of parallel units than you'd naively expect); however the fact remains that Grover's algorithm appears to be vastly more expensive than Shor's.  The only thing in favor of Grover's is that attacking AES-128 would take circa 1000 qubits (same paper), while factoring a 2k integer could be done with about 4 times more.

Also, while I did go through a number of papers, I cannot pretend that I did anything close to a full literature search.  If someone spots a relevant result that I missed (or one that I misinterpreted, or two results that I combined incorrectly), please correct me.

Further details on my assumptions and the research:

For one, I assumed that what we care about is "time taken", not "number of operations performed"; that is, our quantum hardware is able to perform some level of parallelism for independent operations; the Quantum Computing literature refers to this as the "Circuit Depth" (as opposed to "Circuit Size", which is the number of gate operations performed).

In addition, the vast majority of the computation is done performing the modular exponentiation; the other quantum operation, the quantum Fourier transform, is comparatively inexpensive (ref: https://arxiv.org/abs/quant-ph/0006004 ); the other operations are the classical pre- and post-computations, which are also comparatively cheap.

The most aggressive result I found for performing the modular exponentiation is https://arxiv.org/abs/1207.0511 ; this gives us a concrete result of 2000 n^2 operations (where n is the size of the modulus in bits).  This result is quadratic (meaning that doubling the modulus size only increases the attack time by a factor of 4); however, it is a comparatively expensive alternative (requiring about 9n qubits), and for 2k modulii, it would appear we can actually do better.  It does show that going to, say, a 16k modulus might not give us as much security as we would have hoped.

In the other extreme (how few resources do we need), there are a number of papers examining that, in particular, how we can solve the problem while minimizing the number of qubits used.  The results I cited earlier were all from this stream of research.  These results use 2n+epsilon qubits, where epsilon may be as small as 1.  Unfortunately, they use algorithms such as ripple addition, which is just as slow in the quantum realm as it is in the classical.  This algorithms result in a Shor's implementation that takes time cn^3 for some c; if we hit a hard bound on the number of qubits we can afford, that appears to be the best we can do.  Unfortunately, none of the papers I've seen actually give a concrete value for 'c'; on the other hand, we can do better anyways.

As an intermediate result, I did find https://pdfs.semanticscholar.org/a1dc/59b51794cf9737a7985da38a7230db89740a.pdf , which shows how to do moderately fast addition (they claim 30 log n circuit depth) using 3n/log n additional qubits (these are referred to as "ancillary" in the literature).  My opinion is that if you need to factor a 2048 bit number, then having 4700 qubits isn't that much more difficult than having 4100, and the additional 600 qubits allows you to speed up your computation by over an order of magnitude, which is likely to make it worth it.  If we take this adder, and use it to replace the serial adder within https://arxiv.org/abs/1611.07995, this would give you an implementation of Shor's algorithm with a depth of approximately 180 n^2 log n).  If this estimate is right, for a 2048 bit modulus, this would give us a depth of about 8 billion, which is approximately the same as the more aggressive implementation, but using far fewer qubits.

In addition, I referred to a 'gate time'; actually, there are a number of different types of quantum gates, including some that have no classical analogue, and it is certainly reasonable to expect them to take different amounts of time.  On the other hand, according to https://arxiv.org/abs/1202.5872, the speed difference is not drastic, most of the papers ignore this difference (the AES paper is the only one I could find that doesn't), and so I ignored this difference as well.

Note on the discrete log problem: I previously stated that you would need approximately double the number of qubits required to factor a modulus of the same size, and the time would approximately remain the same.  Digging further into this, it appears that the time might increase somewhat (but less than a factor of 2); that's because for factoring, you select a value 'a' and compute a^b (for entangled values of b); it turns out that using a=2 will yield a factorization (various strategies to select p and q in a manner to frustrate Shor with a=2 turn out not to work), and can (depending on the algorithm) make it more efficient.  Against the discrete log, you compute both g^b and h^b, where h is the value you're taking the discrete log of; this is a large value, and so the optimization you could take advantage of during factorization isn't available.  On the other hand, this doesn't increase the amount of time drastically.

Also, again, all the qubit numbers I quoted were "logical qubits", that is, qubits that have error correction logic applied.  Each "logical qubit" is made up of a number of "physical qubits"; the exact number depends on the quantum error correction algorithm used.

> 
> > And I understand that there is also quite big classical computation
> > pre- and post-processing steps too.
> 
> Shor's algorithm gives you a value k where a^x = a^(x+k) mod n; once you
> have that value k, factoring n is a well understood (and fairly easy) problem,
> solvable by, say, Miller's algorithm.
>

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 30 Jul 2018 11:04:47 +0300

Thanks Scott, it was extremely helpful.

So, as far as I understand, it is not feasible for QC to break 2K or larger MODP groups in real time
(say in few seconds), and this restriction seems hard to overcome (at least with our current understanding).

What about ECDH groups? Can you estimate how long would it take for QC to break Ed448 or 521-bit groups?

Regards,
Valery.

> Ok, I went through the literature, and while the short answer is "it's complex", I do have some partial answers,
> including what I believe is a defensible time estimate.
> 
> I went through a number of academic papers, and came to the conclusion that factoring 2kbit numbers on a
> Quantum Computer with circa 4700 qubits available could reasonably be done in time circa 8 billion times the
> time taken by a single quantum gate (details on how I came to that conclusion are listed below); increasing
> the size of the numbers to 16k would increase the attack time by a factor of perhaps 60 to 100.
> 
> The other factor to address is the actual gate speed.  One result is
> http://www.nature.com/articles/nature25737 which gives a high fidelity (but not error corrected) gate speed
> of 1.6usec (using trapped ion qubits).  Adding error correction logic to that would add some overhead, if we
> take the guess that it slows things down by a factor of 10 (which is the approximate speed of the original Shor
> error correction code), then that gives us an error corrected speed of 16usec (or 60k gate operations per
> second).
> 
> Combining those two results would give an estimate of less than 2 days to factor a 2k integer.  As for
> computing a discrete log for a 16k modulus (which is what the original discussion was about), a somewhat
> larger quantum computer (circa 250k qubit) that ran at the same speed would take several months to
> compute the discrete log.
> 
> Of course, this time estimate is based on current published literature; this is quite an active field, and future
> work (especially in the realm of gate speed) could easily shrink these numbers significantly.
> 
> As a side note, if we look at the time it would take Grover's algorithm to break AES-128, we have
> https://www.researchgate.net/publication/287249961_Applying_Grover%27s_algorithm_to_AES_quantum_
> resource_estimates where they estimate a time of 1.16 2^81 = 2.8E24 circuit depth, or about 300 trillion
> times longer than our estimate for factoring a 2k integer.  Now, this isn't quite an apples-to-apples
> comparison (for one, with Grover's, you could do some parallelism with independent Quantum Computers,
> however that costs more in terms of parallel units than you'd naively expect); however the fact remains that
> Grover's algorithm appears to be vastly more expensive than Shor's.  The only thing in favor of Grover's is that
> attacking AES-128 would take circa 1000 qubits (same paper), while factoring a 2k integer could be done with
> about 4 times more.
> 
> Also, while I did go through a number of papers, I cannot pretend that I did anything close to a full literature
> search.  If someone spots a relevant result that I missed (or one that I misinterpreted, or two results that I
> combined incorrectly), please correct me.
> 
> 
> For one, I assumed that what we care about is "time taken", not "number of operations performed"; that is,
> our quantum hardware is able to perform some level of parallelism for independent operations; the Quantum
> Computing literature refers to this as the "Circuit Depth" (as opposed to "Circuit Size", which is the number of
> gate operations performed).
> 
> In addition, the vast majority of the computation is done performing the modular exponentiation; the other
> quantum operation, the quantum Fourier transform, is comparatively inexpensive (ref:
> https://arxiv.org/abs/quant-ph/0006004 ); the other operations are the classical pre- and post-computations,
> which are also comparatively cheap.
> 
> The most aggressive result I found for performing the modular exponentiation is
> https://arxiv.org/abs/1207.0511 ; this gives us a concrete result of 2000 n^2 operations (where n is the size
> of the modulus in bits).  This result is quadratic (meaning that doubling the modulus size only increases the
> attack time by a factor of 4); however, it is a comparatively expensive alternative (requiring about 9n qubits),
> and for 2k modulii, it would appear we can actually do better.  It does show that going to, say, a 16k modulus
> might not give us as much security as we would have hoped.
> 
> In the other extreme (how few resources do we need), there are a number of papers examining that, in
> particular, how we can solve the problem while minimizing the number of qubits used.  The results I cited
> earlier were all from this stream of research.  These results use 2n+epsilon qubits, where epsilon may be as
> small as 1.  Unfortunately, they use algorithms such as ripple addition, which is just as slow in the quantum
> realm as it is in the classical.  This algorithms result in a Shor's implementation that takes time cn^3 for some
> c; if we hit a hard bound on the number of qubits we can afford, that appears to be the best we can do.
> Unfortunately, none of the papers I've seen actually give a concrete value for 'c'; on the other hand, we can do
> better anyways.
> 
> As an intermediate result, I did find
> https://pdfs.semanticscholar.org/a1dc/59b51794cf9737a7985da38a7230db89740a.pdf , which shows how
> to do moderately fast addition (they claim 30 log n circuit depth) using 3n/log n additional qubits (these are
> referred to as "ancillary" in the literature).  My opinion is that if you need to factor a 2048 bit number, then
> having 4700 qubits isn't that much more difficult than having 4100, and the additional 600 qubits allows you
> to speed up your computation by over an order of magnitude, which is likely to make it worth it.  If we take
> this adder, and use it to replace the serial adder within https://arxiv.org/abs/1611.07995, this would give you
> an implementation of Shor's algorithm with a depth of approximately 180 n^2 log n).  If this estimate is right,
> for a 2048 bit modulus, this would give us a depth of about 8 billion, which is approximately the same as the
> more aggressive implementation, but using far fewer qubits.
> 
> In addition, I referred to a 'gate time'; actually, there are a number of different types of quantum gates,
> including some that have no classical analogue, and it is certainly reasonable to expect them to take different
> amounts of time.  On the other hand, according to https://arxiv.org/abs/1202.5872, the speed difference is
> not drastic, most of the papers ignore this difference (the AES paper is the only one I could find that doesn't),
> and so I ignored this difference as well.
> 
> Note on the discrete log problem: I previously stated that you would need approximately double the number
> of qubits required to factor a modulus of the same size, and the time would approximately remain the same.
> Digging further into this, it appears that the time might increase somewhat (but less than a factor of 2); that's
> because for factoring, you select a value 'a' and compute a^b (for entangled values of b); it turns out that
> using a=2 will yield a factorization (various strategies to select p and q in a manner to frustrate Shor with a=2
> turn out not to work), and can (depending on the algorithm) make it more efficient.  Against the discrete log,
> you compute both g^b and h^b, where h is the value you're taking the discrete log of; this is a large value, and
> so the optimization you could take advantage of during factorization isn't available.  On the other hand, this
> doesn't increase the amount of time drastically.
> 
> Also, again, all the qubit numbers I quoted were "logical qubits", that is, qubits that have error correction logic
> applied.  Each "logical qubit" is made up of a number of "physical qubits"; the exact number depends on the
> quantum error correction algorithm used.
> 
> >

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 30 Jul 2018 14:46:29 +0000

> From: Valery Smyslov <[email-masked]>
> Sent: Monday, July 30, 2018 4:05 AM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>; 'Tero Kivinen'
> <[email-masked]>
> So, as far as I understand, it is not feasible for QC to break 2K or larger MODP
> groups in real time (say in few seconds), and this restriction seems hard to
> overcome (at least with our current understanding).

Note that this estimates were based on currently published results; it is extremely likely that these will be improved on, and it would be difficult to guess by how much.

It would appear that the speed of a Quantum Gate would need to increase by perhaps a factor of 1000 (along with some algorithm improvements) in order to make breaking MODP in real time feasible; I would personally be uncomfortable in making the implausibility of this to be a security assumption.

> break Ed448 or 521-bit groups?

Well, I didn't see any papers talking about a Quantum attack of ECDH.  However, based on what I've seen:

- The DLOG approach of performing two parallel modular exponentiations would certainly appear to be applicable to ECC; hence the time would essentially be bounded by twice the time taken to perform a point multiplication (note: we assume that the two point multiplies are done in parallel; the twice mentioned is the amount of data that Shor's algorithm needs to do its QFFT).

- From the previous results, we should be able to perform an n-bit modular multiply in 90n log n gate delays time (log is base 2).

- Constant time ECC algorithms would appear to translate directly into the Quantum realm; these take circa 10 modular multiplies (and some modular adds/subtracts, but they're cheap) per bit of the multiplier; however if we allow parallel multiplies (which uses a few more qubits), we might be able to manage with as few as 3 modular multiplies (or might not; in Quantum Computing, all operations need to be invertible, and the parallel multiplies might make this difficult; if we can't get to this level of parallelism, this estimate might be off by a factor of 2).  We also have to do a modular inversion at the end (as the QFFT algorithm at the end will need equivalent points to have the same bit pattern).

- Adding everything together (and assuming we can go with the full parallel multiply option), we get  around 600 n^2 log n gate delays (where I'm using n to mean both the characteristic of the field and the curve group size; they're close enough that the difference doesn't matter for this crude estimate).

With n=448, we get circa 1 billion, a fraction of the time we estimated to break RSA-2048, with our 60,000 gate operations per second, that's about 5 hours.  If we count Qubits, it would appear that ECC also uses considerably fewer; however coming up with an exact number is nontrivial (the parallel multiples may share sources, and so some additional ancillary qubits may be needed)

So, with this rather crude (and off-the-cuff) analysis, ECC looks to be noticeably weaker against a Quantum Computer.  Of course, this is a such a crude estimate, it's not clear if it ought to be used to make any real security decisions...

> > > > algorithm, i.e., breaking 2048 bit Diffie-Hellman. I have just
> > > > seen text saying it is polynominal time, but I have not really
> > > > seen any guesses what the actual numbers are going to be.
> > >
> > > Very good question; the references I find all essentially say
> > > "cubic"; however they don't immediately talk about the constant
> > > factor.  I suspect that this constant factor won't be that large;
> > > however that most certainly merits further investigation.
> >
> > Ok, I went through the literature, and while the short answer is "it's
> > complex", I do have some partial answers, including what I believe is a
> defensible time estimate.
> >
> > I went through a number of academic papers, and came to the conclusion
> > that factoring 2kbit numbers on a Quantum Computer with circa 4700
> > qubits available could reasonably be done in time circa 8 billion
> > times the time taken by a single quantum gate (details on how I came to
> that conclusion are listed below); increasing the size of the numbers to 16k
> would increase the attack time by a factor of perhaps 60 to 100.
> >
> > http://www.nature.com/articles/nature25737 which gives a high fidelity
> > (but not error corrected) gate speed of 1.6usec (using trapped ion
> > qubits).  Adding error correction logic to that would add some
> > overhead, if we take the guess that it slows things down by a factor
> > of 10 (which is the approximate speed of the original Shor error correction
> code), then that gives us an error corrected speed of 16usec (or 60k gate
> operations per second).
> >
> > Combining those two results would give an estimate of less than 2 days
> > to factor a 2k integer.  As for computing a discrete log for a 16k
> > modulus (which is what the original discussion was about), a somewhat
> > larger quantum computer (circa 250k qubit) that ran at the same speed
> would take several months to compute the discrete log.
> >
> > Of course, this time estimate is based on current published
> > literature; this is quite an active field, and future work (especially in the
> realm of gate speed) could easily shrink these numbers significantly.
> >
> https://www.researchgate.net/publication/287249961_Applying_Grover%27
> s
> > _algorithm_to_AES_quantum_ resource_estimates where they estimate a
> > time of 1.16 2^81 = 2.8E24 circuit depth, or about 300 trillion times
> > longer than our estimate for factoring a 2k integer.  Now, this isn't
> > quite an apples-to-apples comparison (for one, with Grover's, you
> > could do some parallelism with independent Quantum Computers,
> however
> > that costs more in terms of parallel units than you'd naively expect);
> > however the fact remains that Grover's algorithm appears to be vastly
> > more expensive than Shor's.  The only thing in favor of Grover's is that
> attacking AES-128 would take circa 1000 qubits (same paper), while factoring
> a 2k integer could be done with about 4 times more.
> >
> > Also, while I did go through a number of papers, I cannot pretend that
> > I did anything close to a full literature search.  If someone spots a
> > relevant result that I missed (or one that I misinterpreted, or two results
> that I combined incorrectly), please correct me.
> >
> >
> > For one, I assumed that what we care about is "time taken", not
> > "number of operations performed"; that is, our quantum hardware is
> > able to perform some level of parallelism for independent operations;
> > the Quantum Computing literature refers to this as the "Circuit Depth" (as
> opposed to "Circuit Size", which is the number of gate operations
> performed).
> >
> > In addition, the vast majority of the computation is done performing
> > the modular exponentiation; the other quantum operation, the quantum
> Fourier transform, is comparatively inexpensive (ref:
> > https://arxiv.org/abs/quant-ph/0006004 ); the other operations are the
> > classical pre- and post-computations, which are also comparatively cheap.
> >
> > https://arxiv.org/abs/1207.0511 ; this gives us a concrete result of
> > 2000 n^2 operations (where n is the size of the modulus in bits).
> > This result is quadratic (meaning that doubling the modulus size only
> > increases the attack time by a factor of 4); however, it is a
> > comparatively expensive alternative (requiring about 9n qubits), and for 2k
> modulii, it would appear we can actually do better.  It does show that going
> to, say, a 16k modulus might not give us as much security as we would have
> hoped.
> >
> > In the other extreme (how few resources do we need), there are a
> > number of papers examining that, in particular, how we can solve the
> > problem while minimizing the number of qubits used.  The results I
> > cited earlier were all from this stream of research.  These results
> > use 2n+epsilon qubits, where epsilon may be as small as 1.
> > Unfortunately, they use algorithms such as ripple addition, which is just as
> slow in the quantum realm as it is in the classical.  This algorithms result in a
> Shor's implementation that takes time cn^3 for some c; if we hit a hard
> bound on the number of qubits we can afford, that appears to be the best
> we can do.
> > Unfortunately, none of the papers I've seen actually give a concrete
> > value for 'c'; on the other hand, we can do better anyways.
> >
> https://pdfs.semanticscholar.org/a1dc/59b51794cf9737a7985da38a7230db89
> > 740a.pdf , which shows how to do moderately fast addition (they claim
> > 30 log n circuit depth) using 3n/log n additional qubits (these are
> > referred to as "ancillary" in the literature).  My opinion is that if
> > you need to factor a 2048 bit number, then having 4700 qubits isn't
> > that much more difficult than having 4100, and the additional 600
> > qubits allows you to speed up your computation by over an order of
> > magnitude, which is likely to make it worth it.  If we take this
> > adder, and use it to replace the serial adder within
> https://arxiv.org/abs/1611.07995, this would give you an implementation of
> Shor's algorithm with a depth of approximately 180 n^2 log n).  If this
> estimate is right, for a 2048 bit modulus, this would give us a depth of about 8
> billion, which is approximately the same as the more aggressive
> implementation, but using far fewer qubits.
> >
> > In addition, I referred to a 'gate time'; actually, there are a number
> > of different types of quantum gates, including some that have no
> > classical analogue, and it is certainly reasonable to expect them to
> > take different amounts of time.  On the other hand, according to
> > https://arxiv.org/abs/1202.5872, the speed difference is not drastic, most
> of the papers ignore this difference (the AES paper is the only one I could
> find that doesn't), and so I ignored this difference as well.
> >
> > Note on the discrete log problem: I previously stated that you would
> > need approximately double the number of qubits required to factor a
> modulus of the same size, and the time would approximately remain the
> same.
> > Digging further into this, it appears that the time might increase
> > somewhat (but less than a factor of 2); that's because for factoring,
> > you select a value 'a' and compute a^b (for entangled values of b); it
> > turns out that using a=2 will yield a factorization (various
> > strategies to select p and q in a manner to frustrate Shor with a=2
> > turn out not to work), and can (depending on the algorithm) make it
> > more efficient.  Against the discrete log, you compute both g^b and h^b,
> where h is the value you're taking the discrete log of; this is a large value, and
> so the optimization you could take advantage of during factorization isn't
> available.  On the other hand, this doesn't increase the amount of time
> drastically.
> >
> > Also, again, all the qubit numbers I quoted were "logical qubits",
> > that is, qubits that have error correction logic applied.  Each
> > "logical qubit" is made up of a number of "physical qubits"; the exact
> number depends on the quantum error correction algorithm used.
> >
> > >
> > > Not really; there is computation needed there, but it is quite
> > > straight- forward.
> > >
> > > Shor's algorithm gives you a value k where a^x = a^(x+k) mod n; once
> > > you have that value k, factoring n is a well understood (and fairly
> > > easy) problem, solvable by, say, Miller's algorithm.
> > >
> >

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 30 Jul 2018 18:20:18 +0000

Sigh, a rather major correction here...

> Sent: Monday, July 30, 2018 10:46 AM
> To: 'Valery Smyslov' <[email-masked]>; 'Tero Kivinen'
> <[email-masked]>

Oops, my analysis of ECC is broken, and should be disregarded.

One major problem is my blithe assertion that:

> - Constant time ECC algorithms would appear to translate directly into the
> Quantum realm

Nope; they rely on operations that are easy in the classical realm, but don't directly translate into the Quantum.  For one, they do operations such as:

    u := u^2 mod p

A classical computer has no problem with this, however a Quantum Computer is forbidden from doing that exact operation.  The problem is that all computations done by a Quantum Computer (other than the measurement operation, which this is not) must be invertible.  However, with this operation, if the final u value is '1', we have no idea if the original 'u' value was either 1 or p-1; hence it's not invertbile, and so we cannot do it.

The standard Quantum Computing way to express this is something like:

   (u, v) := (u, v + (u^2 mod p))

for some reasonable meaning of '+', possibly xor, possibly modular addition.  However, just cutting/pasting this into the standard ECC algorithms would chew up massive numbers of ancillary qubits, and so that's not an option.  One probably could restructure the ECC computations to avoid these problems (uncomputing the ancillary qubits so they can be used in later iterations), however I cannot guess how expensive that would be.

Sorry for the wrong answer I gave earlier.

---

From: Dan Brown <[email-masked]>
Date: Mon, 30 Jul 2018 18:37:46 +0000

For ECC v QC, see also

‎https://ia.cr/2017/598

  Original Message
From: Scott Fluhrer (sfluhrer)
Sent: Monday, July 30, 2018 2:20 PM
To: Valery Smyslov; 'Tero Kivinen'
Cc: [email-masked]; [email-masked]
Subject: Re: [IPsec] Modp-12288 and Modp-16384

    u := u^2 mod p

---

From: <[email-masked]>
Date: Mon, 30 Jul 2018 18:52:28 +0000

Interesting item in the abstract:  "... using a quantum circuit of at most 448.n^3.log2(n)+4090.n^3 Toffoli gates."  In the past I've seen mention of qubit counts but not gate counts.  While the gate count isn't exponential, it's nevertheless formidable.  For 1000 bit inputs it translates to several teragates.  How tight is that upper bound?

Are the numbers for RSA or discrete log (conventional Diffie-Hellman) similar?  If so, does that translate into "quantum computers are not a practical issue"?

	paul

> On Jul 30, 2018, at 2:37 PM, Dan Brown <[email-masked]> wrote:
> 
> For ECC v QC, see also
> 
> ‎https://ia.cr/2017/598

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 30 Jul 2018 20:26:01 +0000

> From: [email-masked] <[email-masked]>
> Sent: Monday, July 30, 2018 2:52 PM
> To: [email-masked]
> Cc: Scott Fluhrer (sfluhrer) <[email-masked]>; [email-masked];
> [email-masked]; [email-masked]; [email-masked]
> Interesting item in the abstract:  "... using a quantum circuit of at most
> 448.n^3.log2(n)+4090.n^3 Toffoli gates."  In the past I've seen mention of
> qubit counts but not gate counts.  While the gate count isn't exponential, it's
> nevertheless formidable.  For 1000 bit inputs it translates to several
> teragates.  How tight is that upper bound?

I believe that is a misleading statistic.

What that is a measure of is "if we implement the circuit as a huge combinatorial circuit, how many individual quantum gates will we need?"

It's misleading because, in practice, we'd never implement things that way.  Instead, we'd devise ways where the same physical  Tofolli gate is used multiple times during the computation (analogous to how, on a classical computer, we reuse the same addition and multiplication circuit repeatedly when performing a series of operations).

Now, in the Quantum realm, this problem turns out to be a bit different than in the classical realm; however I believe that is a problem that can be solved (and, indeed, needs to be solved for Quantum Computing to be realistic)