Subject: [Cfrg] Quantum Computing and Crypto Policies

From: "Dr. Pala" <[email-masked]>
Date: Mon, 11 Apr 2016 10:33:32 -0400

Hi all,

At the CFRG meeting, I have appreciated the presentation about QC in the 
sense that inspired to think about the future in a more practical way 
(although there was probably not much agreement on how to proceed forward).

I have also been following the conversation about the post-quantum 
computing crypto resistance and I am trying to figure out - given what 
we know about possible quantum computing which, as Tim pointed out 
during the meeting, is still very little - what types of policies can be 
implemented today that would allow us to be a bit more resilient to 
attacks in the post quantum-computing environment (i.e., not being taken 
by surprise since deploying of new crypto can take several years in the 
real world despite the algorithm agility we have in current standards). 
I will try to summarize the two main points:

 1. Symmetric crypto is still relatively secure. Using 256bits keys
    (e.g., AES 256) should provide enough confidentiality for the time
    being (this is already a common practice in the industry as the
    overhead compared to 128bits is negligible) - so we are relatively
    safe here.
 2. Given the physical limitations when it comes to be able to have QC
    with high number of qbits, it seems that when it comes to Asymmetric
    crypto, ECDSA (given the limited number of bits and the
    impossibility to extend the number of bits without defining new
    curves) is the weakest choice compared to RSA with very long keys
    (e.g., 8K or 16K bits keys or even bigger...).

In other words, given this scenario and setting aside considerations 
about signature sizes (although, we have seen an increase in computing 
resources in terms of processing power, bandwidth, and storage it seems 
that signature size is a big concern - AFAIK, mostly driven by IoT and 
similar environments - even more than 10yrs ago! and many WGs are using 
the size argument over the security argument in their specifications and 
suggestions), the more flexible and forward-secure choice would be to 
start using "oversized" RSA keys for asymmetric and for symmetric we can 
keep using AES 256 with relative confidence (assuming, as I said, that 
no new quantum-specific algorithms are discovered...)

Does this summarizes the current situation? Are these (very simplistic) 
considerations correct? Anybody disagree with these statements? Why?

Cheers,
Max

-- 
Massimiliano Pala, PhD
Director at OpenCA Labs
twitter: @openca

---

From: "Grigory Marshalko" <[email-masked]>
Date: Mon, 11 Apr 2016 20:48:39 +0000

Not only described issues.
Two recent papers also address the post-quantum security of block cipher modes and MACs.
http://arxiv.org/pdf/1602.05973.pdf (http://arxiv.org/pdf/1602.05973.pdf)
https://eprint.iacr.org/2016/197.pdf (https://eprint.iacr.org/2016/197.pdf)
Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru

11 апреля 2016 г., 17:33, "Dr. Pala"  написал:
Hi all,

At the CFRG meeting, I have appreciated the presentation about QC in the sense that inspired to think about the future in a more practical way (although there was probably not much agreement on how to proceed forward).

I have also been following the conversation about the post-quantum computing crypto resistance and I am trying to figure out - given what we know about possible quantum computing which, as Tim pointed out during the meeting, is still very little - what types of policies can be implemented today that would allow us to be a bit more resilient to attacks in the post quantum-computing environment (i.e., not being taken by surprise since deploying of new crypto can take several years in the real world despite the algorithm agility we have in current standards). I will try to summarize the two main points:
	* Symmetric crypto is still relatively secure. Using 256bits keys (e.g., AES 256) should provide enough confidentiality for the time being (this is already a common practice in the industry as the overhead compared to 128bits is negligible) - so we are relatively safe here.
	* Given the physical limitations when it comes to be able to have QC with high number of qbits, it seems that when it comes to Asymmetric crypto, ECDSA (given the limited number of bits and the impossibility to extend the number of bits without defining new curves) is the weakest choice compared to RSA with very long keys (e.g., 8K or 16K bits keys or even bigger...).
	In other words, given this scenario and setting aside considerations about signature sizes (although, we have seen an increase in computing resources in terms of processing power, bandwidth, and storage it seems that signature size is a big concern - AFAIK, mostly driven by IoT and similar environments - even more than 10yrs ago! and many WGs are using the size argument over the security argument in their specifications and suggestions), the more flexible and forward-secure choice would be to start using "oversized" RSA keys for asymmetric and for symmetric we can keep using AES 256 with relative confidence (assuming, as I said, that no new quantum-specific algorithms are discovered...)

	Does this summarizes the current situation? Are these (very simplistic) considerations correct? Anybody disagree with these statements? Why?

	Cheers,
Max

	-- Massimiliano Pala, PhD Director at OpenCA Labs twitter: @openca

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 11 Apr 2016 21:02:02 +0000

These papers assume a very obscure attack model; where the attacker can generate a plaintext that is a superposition of several possible values, and have the device generate a ciphertext that is a superposition of the encryption of the various values.

We assume that within a Quantum Computer, we somehow maintain coherence of the various quantum states; however this attack model asks that this coherency is not disrupted when the queries leave the Quantum Computer.  Realistically, it is hard to see how this could be implemented over a network.  Quantum Superposition is quite delicate; in fact, the main problem we have in building a Quantum Computer is how to maintain coherence over a nontrivial period of time – it would appear to be unlikely that the device under attack would be helpful enough to the attacker to go through that effort.

Now, for totally public operations (hashing, public key encryption, signature verification, whitebox cryptography), these sorts of attacks are plausible (because someone with a Quantum Computer can perform them entirely within the Quantum Computer, and so go through the effort of maintaining coherence over the entire operation).  However, for attacking devices on the internet, well, it’s less interesting.

From: Cfrg [mailto:[email-masked]] On Behalf Of Grigory Marshalko
Sent: Monday, April 11, 2016 4:49 PM
To: Dr. Pala; [email-masked]
Subject: Re: [Cfrg] [MASSMAIL] Quantum Computing and Crypto Policies

Not only described issues.
Two recent papers also address the post-quantum security of block cipher modes and MACs.
http://arxiv.org/pdf/1602.05973.pdf
https://eprint.iacr.org/2016/197.pdf
Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru<http://www.tc26.ru>

11 апреля 2016 г., 17:33, "Dr. Pala" <[email-masked]<mailto:[email-masked]%3e>> написал:
Hi all,

  1.  Symmetric crypto is still relatively secure. Using 256bits keys (e.g., AES 256) should provide enough confidentiality for the time being (this is already a common practice in the industry as the overhead compared to 128bits is negligible) - so we are relatively safe here.
  2.  Given the physical limitations when it comes to be able to have QC with high number of qbits, it seems that when it comes to Asymmetric crypto, ECDSA (given the limited number of bits and the impossibility to extend the number of bits without defining new curves) is the weakest choice compared to RSA with very long keys (e.g., 8K or 16K bits keys or even bigger...).

Cheers,
Max

--

Massimiliano Pala, PhD

Director at OpenCA Labs

twitter: @openca

---

From: David McGrew <[email-masked]>
Date: Mon, 11 Apr 2016 17:35:27 -0400

Hi Scott and Grigory,

> On Apr 11, 2016, at 5:02 PM, Scott Fluhrer (sfluhrer) <[email-masked]> wrote:
> 
> These papers assume a very obscure attack model; where the attacker can generate a plaintext that is a superposition of several possible values, and have the device generate a ciphertext that is a superposition of the encryption of the various values. <> <>
>  

thanks for bringing these works into the discussion.  To add some more detail and emphasis to Scott’s point: the attack model in these works does not correspond to any current use of cryptography.  From http://arxiv.org/pdf/1602.05973.pdf <http://arxiv.org/pdf/1602.05973.pdf>:  "We consider here a much stronger model [than the quantum random oracle] in which, in addition to local quantum operations, an adversary is granted an access to a possibly remote cryptographic oracle in superposition of the inputs, and obtains the corresponding superposition of outputs.”   In other words, the results show that if you use a quantum computer to implement your secret-key crypto scheme, and then you let the attacker use your quantum computer, you can expect your scheme to be broken (if it is on the list of schemes they can attack).   

While this is a very interesting research result, the attack model is far from any current or anticipated use of secret-key cryptography, and thus it would be wrong to attempt to use these results to inform us in what sort of algorithms we should be using on the Internet.   

best

David 

> http://arxiv.org/pdf/1602.05973.pdf <http://arxiv.org/pdf/1602.05973.pdf>
> https://eprint.iacr.org/2016/197.pdf <https://eprint.iacr.org/2016/197.pdf>
> Regards,
> Grigory Marshalko,
> expert,
> www.tc26.ru <http://www.tc26.ru/>
> 
> 11 апреля 2016 г., 17:33, "Dr. Pala" <[email-masked] <mailto:[email-masked]%3e>> написал:
> Hi all,
> 
> Symmetric crypto is still relatively secure. Using 256bits keys (e.g., AES 256) should provide enough confidentiality for the time being (this is already a common practice in the industry as the overhead compared to 128bits is negligible) - so we are relatively safe here.
> Given the physical limitations when it comes to be able to have QC with high number of qbits, it seems that when it comes to Asymmetric crypto, ECDSA (given the limited number of bits and the impossibility to extend the number of bits without defining new curves) is the weakest choice compared to RSA with very long keys (e.g., 8K or 16K bits keys or even bigger...).
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Grigory Marshalko" <[email-masked]>
Date: Tue, 12 Apr 2016 09:28:10 +0000

Hi David and Scott,

I completely agree with you, nevertheless I suppose It should be usefull at least to keep this pubs in mind as a possible new trend of research

Regards,
Grigory Marshalko,
expert,

12 апреля 2016 г., 00:35, "David McGrew"  написал:
Hi Scott and Grigory,

On Apr 11, 2016, at 5:02 PM, Scott Fluhrer (sfluhrer)  wrote: 
These papers assume a very obscure attack model; where the attacker can generate a plaintext that is a superposition of several possible values, and have the device generate a ciphertext that is a superposition of the encryption of the various values. 
	 We assume that within a Quantum Computer, we somehow maintain coherence of the various quantum states; however this attack model asks that this coherency is not disrupted when the queries leave the Quantum Computer.  Realistically, it is hard to see how this could be implemented over a network.  Quantum Superposition is quite delicate; in fact, the main problem we have in building a Quantum Computer is how to maintain coherence over a nontrivial period of time – it would appear to be unlikely that the device under attack would be helpful enough to the attacker to go through that effort.

	 Now, for totally public operations (hashing, public key encryption, signature verification, whitebox cryptography), these sorts of attacks are plausible (because someone with a Quantum Computer can perform them entirely within the Quantum Computer, and so go through the effort of maintaining coherence over the entire operation).  However, for attacking devices on the internet, well, it’s less interesting.
thanks for bringing these works into the discussion.  To add some more detail and emphasis to Scott’s point: the attack model in these works does not correspond to any current use of cryptography.  From http://arxiv.org/pdf/1602.05973.pdf (http://arxiv.org/pdf/1602.05973.pdf):  "We consider here a much stronger model [than the quantum random oracle] in which, in addition to local quantum operations, an adversary is granted an access to a possibly remote cryptographic oracle in superposition of the inputs, and obtains the corresponding superposition of outputs.”   In other words, the results show that if you use a quantum computer to implement your secret-key crypto scheme, and then you let the attacker use your quantum computer, you can expect your scheme to be broken (if it is on the list of schemes they can attack).   

best

David 

From: Cfrg [mailto:[email-masked] (mailto:[email-masked])] On Behalf Of Grigory Marshalko
Sent: Monday, April 11, 2016 4:49 PM
To: Dr. Pala; [email-masked] (mailto:[email-masked])
Subject: Re: [Cfrg] [MASSMAIL] Quantum Computing and Crypto Policies
Not only described issues.
Two recent papers also address the post-quantum security of block cipher modes and MACs.
http://arxiv.org/pdf/1602.05973.pdf (http://arxiv.org/pdf/1602.05973.pdf)
https://eprint.iacr.org/2016/197.pdf (https://eprint.iacr.org/2016/197.pdf)
Regards,
Grigory Marshalko,
expert,
Technical committee for standardisation "Cryptography and security mechanisms" (TC 26)
www.tc26.ru (http://www.tc26.ru/)

Hi all,

	Cheers,
Max

	-- 

	Massimiliano Pala, PhD

	Director at OpenCA Labs

	twitter: @openca_______________________________________________
Cfrg mailing list
[email-masked] (mailto:[email-masked])
https://www.irtf.org/mailman/listinfo/cfrg (https://www.irtf.org/mailman/listinfo/cfrg)