1357467 - AES-256 preference to help guard against quantum

Status: UNCONFIRMED

(NSS :: Libraries, defect, P3)

Description

[Ruben89]

User Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:53.0) Gecko/20100101 Firefox/53.0
Build ID: 20170418122848

Steps to reproduce:

The Dutch National Cyber Security Center (NCSC) just released guidelines regarding crypto in a post-quantum cryptography world:
https://www.ncsc.nl/binaries/content/documents/ncsc-nl/actueel/factsheets/factsheet-postkwantumcryptografie/1/Factsheet%2BPostkwantumcryptografie.pdf

The factsheet is in Dutch but is based on recommendations written in English which I'll get to in a moment.

They advise the use or preference of AES-256 above AES-128 bit  ciphers, the gist of it being that the use of quantum-computers might seem a distant future but it's not, (encrypted traffic could be captured and stored for decryption using quantum-computers at a later time) and AES-256 is much much more resistant to decryption by quantum-computers.  

This advice is based on the:  "Initial recommendations of long-term secure post-quantum systems" written by "PQCRYPTO" a research project funded by the EU.

The recommendations can be found here:
https://pqcrypto.eu.org/press.html
https://pqcrypto.eu.org/docs/initial-recommendations.pdf

On page. 7 par. 3 of the document the use of AES-256 above AES-128 is recommended:
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
2n/2, so AES-128 offers only 264 post-quantum security. PQCRYPTO recommends thoroughly analyzed ciphers with 256-bit keys to achieve 2128post-quantum security:
•AES-256 [8].
•Salsa20 [3] with a 256-bit key.

"At the moment Firefox (NSS) prefers AES-128 Above AES-256 (note that i've enabled TLS 1.3):
TLS_AES_128_GCM_SHA256 (0x1301)   Forward Secrecy 	128
TLS_CHACHA20_POLY1305_SHA256 (0x1303)   Forward Secrecy 	256
TLS_AES_256_GCM_SHA384 (0x1302)   Forward Secrecy 	256
TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (0xc02b)   Forward Secrecy 	128
TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (0xc02f)   Forward Secrecy 	128
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256 (0xcca9)   Forward Secrecy 	256
TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256 (0xcca8)   Forward Secrecy 	256
TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 (0xc02c)   Forward Secrecy 	256
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (0xc030)   Forward Secrecy 	256
TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA (0xc013)   Forward Secrecy 	128
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA (0xc014)   Forward Secrecy 	256
TLS_DHE_RSA_WITH_AES_128_CBC_SHA (0x33)   Forward Secrecy 	128
TLS_DHE_RSA_WITH_AES_256_CBC_SHA (0x39)   Forward Secrecy 	256
TLS_RSA_WITH_AES_128_CBC_SHA (0x2f) 	128
TLS_RSA_WITH_AES_256_CBC_SHA (0x35) 	256
TLS_RSA_WITH_3DES_EDE_CBC_SHA (0xa)   WEAK"

I think it might be a good idea to get Firefox (NSS) to start preferring AES-256 based ciphers above 128-bit ciphers. 

In other words:
When i visit a website, for instance https://www.bonnieradvocaten.nl (this website has no server cipher preference) the client, Firefox, /  (NSS), prefers AES-128 above AES-256.





Actual results:

AES_128_GCM_SHA256  is used to encrypt traffic between Firefox and https://www.bonnieradvocaten.nl


Expected results:

Firefox should have preferred AES-256 based ciphers (like: AES-256_GCM_SHA384)  so that AES-256 based ciphers are used to encrypt traffic since it is much more resistant to the threat that quantum will pose in the near future.

Comment 1

[Eric Rescorla (:ekr)]

TLS (all versions) uses one of {DH, ECDH, RSA} for key establishment. I am of course willing to be wrong, but my sense is that the general belief is that these will be weaker with respect to quantum computers than AES-128, so until we add some sort of post-quantum key establishment, I'm not sure there's much point in preferring AES-256.

Comment 2

[Ruben89]

(In reply to Eric Rescorla (:ekr) from comment #1)
> TLS (all versions) uses one of {DH, ECDH, RSA} for key establishment. I am
> of course willing to be wrong, but my sense is that the general belief is
> that these will be weaker with respect to quantum computers than AES-128, so
> until we add some sort of post-quantum key establishment, I'm not sure
> there's much point in preferring AES-256.

Shor's algorithm is indeed thought to be able to defeat (EC)DH, RSA and ECDSA, but i don't disagree with the advise the Dutch NCSC (part of the Ministry of Security and Justice) put out. You have to start somewhere when defending against quantum.

Comment 3

[Eric Rescorla (:ekr)]

I'm not seeing your reasoning here. If the key establishment isn't secure against quantum, QC then AES-256 doesn't do any good.

Comment 4

[Ruben89]

(In reply to Eric Rescorla (:ekr) from comment #3)
> I'm not seeing your reasoning here. If the key establishment isn't secure
> against quantum, QC then AES-256 doesn't do any good.

My reasoning - or rather the reasoning of the researchers of PQCRYPTO and by extension the NCSC's - is that switching preference to AES-256 based ciphers will at least mitigate one attack vector (that of breaking AES). 

Of course if the RSA, ECDSA, (EC)DH(E) key isn't secure against quantum that's another area where defenses need to be shored up (if I'm not mistaken Google is trying with CECPQ1) but that doesn't mean that measures that can be put into place today should be held off until fully quantum resistant key's / ciphers are developed.

Comment 5

[Eric Rescorla (:ekr)]

I don't think I agree with this. The cost of the attack is dictated by the weakest piece of the system. As long as the weakest piece is the asymmetric piece, then I'm not really seeing the point of strengthening the symmetric piece. Of course, if you have some argument that the symmetric piece is weakest....

Comment 6

[Ruben89]

(In reply to Eric Rescorla (:ekr) from comment #5)
> I don't think I agree with this. The cost of the attack is dictated by the
> weakest piece of the system. As long as the weakest piece is the asymmetric
> piece, then I'm not really seeing the point of strengthening the symmetric
> piece. Of course, if you have some argument that the symmetric piece is
> weakest....

At this moment, in all honesty, I don't. 
My understanding is that the Grover's algorithm that breaks AES is effective against AES-128 but is very, very slow when used against AES-256, whereas Shor's algorithm is able to effectively break (EC)DH(E).

I'll do some more reading into this topic, but as it stands i still think 'switching' to prefer AES-256 is a good idea, since we have to start somewhere to help defend current encryption against QC.

Comment 7

[Ruben89]

I'm having a hard time finding solid info about the speed of Shor's VS Grover's Algorithm and breaking aes-128 vs breaking (private)keys.  According tot the Dutch "Center for Mathematics and Computer Science" (CWI):

Shor’s algorithm (1994) factors an n-bit integer in roughly
n2 elementary quantum gates. This is 
- exponential speed-up over best known classical algo
- breaks a lot of public-key cryptography

Grover’s algorithm (1996) searches a size-N search
space in∼√N time
- quadratic speed-up over classical
- widely applicable

(Source:)
http://homepages.cwi.nl/~rdewolf/warsaw2short.pdf

Comment 8

[Robert Relyea]

Eric,

So there is some benefit for going to 256 bit AES. Even though EC, RSA, DH, and DSA are all vulnerable to quantum algorithms, there will be a ramp up. Smaller key sizes will fall first because quantum is an all or nothing proposition (either you have enough bits to solve the whole problem or you get no speed up from the quantum computer). Unlike classical computers where you can do the same problem on smaller versions, just slower, a quantum computer needs to be 'big enough'.

I'm not sure how many quBits you need to solve AES 128 keys, but I'm pretty sure it's smaller than the number of bits needed to solve RSA 8K, for instance, probably more than EC p256. (Gover's algorithm uses the same basic Fourier analysis as Shor's, so it likely requires the smae number of quBits for the same classical bits).

Upshot: There is some benefit in that we are practically quantum resistant for longer with AES-256 than with AES-128.

Comment 9

[Ruben89]

Eric,

I'm curious as to how Mozilla is moving forward with this bug, taking into account the information that Robert has provided.

Comment 10

[Eric Rescorla (:ekr)]

The preferences for these algorithms are in NSS, so it's not solely a Mozilla decision. With that said, given that the algorithms are ultimately the server's choice, I don't believe that any change to NSS is merited.

Comment 11

[Ruben89]

Alright I'll leave it at this then, thanks for you're help.

Comment 13

[u677327]

Attachment: Symmetric

Comment 14

[u677327]

Attachment: Asymmetric

Comment 15

[u677327]

The belief that quantum computers will break {DH, ECDH, RSA} before AES128 only applies to ECDH. Breaking AES128 requires ~3,000 qubits (AES256 is ~7,000) compared to the 8,192 qubits required to break RSA 4096 or DH 4096.

Preferring AES256 does provide more quantum resistance.

Comment 16

[Masatoshi Kimura [:emk]]

NSS added SSL_CipherSuiteOrderSet so that Mozilla can customize the order.