[Cryptography] quantum computers & crypto

[Arnold Reinhold]

On Sat, 30 Oct 2021 22:03:08 +0000
Ray Dillinger (Bear) wrote (among other things):

> Everything we need to do to get ready to deploy post-QC encryption
> algorithms, is stuff that we arguably needed to do anyway.
> 
> All software with symmetric keys upgraded to handle keys twice as long
> so symmetric crypto can be secure in a post-QC world?? Harmless.? If you
> spot cases where key length doubling has a practical benefit in a non-QC
> world, consider key length tripling instead.


Sound engineering practice calculates what is known and then adds a safety factor. But when dealing with new technology, like QC, it’s hard to know what is prudent and what is homeopathic lasagna. My favorite example is from World War II. The Manhattan Project assigned the production of the new element, plutonium, to E.I Dupont de Nemours, America’s premier chemical company. When the physicists reviewed Dupont’s blueprints for the first production-scale nuclear reactor, they counted up the tubes intended for fuel and control rods and found there were more than they had specified. Asked why, the Dupont engineer explained that Dupont always builds in extra capacity. The physicists patiently explained that the number of tubes had been precisely calculated and therefore no more were needed. The Dupont people replied that their chemists said that all the time, but if the project wanted Dupont to build the reactor, they would do it the Dupont way. The extra tubes would do no harm, so the physicists dropped the argument. 

When the reactor was fired up for its first low-power test, an unforeseen problem was encountered. One of the fission products, xenon-135, strongly absorbed neutrons, poisoning the reaction. The extra tubes allowed corrective measures and the reactor was soon in full operation. (https://www.atomicheritage.org/tour-site/life-hanford)

There has been a tendency in cryptography to keep safety margins small, perhaps a holdover from when processing capability was expensive. For high value applications with long term security requirements, such as financial instruments, it would seem that the balance should be struck at higher safety margins.

One limitation is the lack of any standard  symmetric cipher with keys stronger than 256 bits. For a long time 256 bits seemed to provide a safety margin far beyond what is needed, but the prospect of quantum computers reduces the long term security to an equivalent of 128-bit conventional security. In addition we have seen the security of past ciphers and hashes slowly erode through intricate attacks on their algorithms, so we should never assume their security matches the nominal strength of their key length. Down the road, there is at least a possibility that AI-assisted mathematical analysis might find deeper vulnerabilities. 

I would like to call attention to an alternative: the Rijndael cipher scheduled with Keccak, specifically AES-256 with the AES key schedule replaced by cSHAKE256. This has been proposed in:

   "Towards post-quantum symmetric cryptography,” John Gregory Underhill and Stiepan Aurélien Kovac, and Xenia Bogomolec,  https://eprint.iacr.org/2019/553.pdf

AES consists of two parts: a cipher algorithm that uses an extended key and a key scheduling algorithm that produces the extended key from the primary key, the later ranging in size from 128 to 256 bits. In the case of AES-256, the primary key is 256 bits, while the extended key consists of 15 round keys, each being four 32-bit words (15 is the number of rounds plus one). Underhill, et. al., recommend increasing the AES round count, but I would stick with the standard AES round count so that the cipher part of the AES specification is unchanged.

cSHAKE256 is a variant of Keccak, part of NIST’s SHA-3 family, and is an extendable output function (XOF), a hash function whose output can be specified to any length, possibly with some large limit. (FIPS 202).

The idea is to create a cipher without the 256-bit key restriction, but as close to approved standards as possible. I realize that any deviation from a standard is no longer standard. However the AES 256 standard cleaves neatly into two sections, the key schedule and the 
cipher itself. We are only replacing the key schedule section with an unaltered standard-hash XOF. 

I have been unable to find any suggestion in the literature of any property of the AES key schedule, other than speed, that would not be achieved by the output of a good XOF. Assuming this, the resulting cipher should be no weaker than AES 256 and there is no 256-bit bottleneck. The resulting cipher would be no weaker than AES 256. If the1920-bit round constant array could be attacked directly, AES-256 would share the same vulnerability.  The smallest apparent key bottleneck is the 1600-bit internal state of cSHAKE256. 

One might ask why not just use the output of cSHAKE256 as a stream cipher directly. However to the best of my knowledge cSHAKE256 has never been approved as a cipher. In addition once AES is scheduled using the XOF, it behaves like normal AES, and all the encryption modes, software implementations, and most hardware developed for AES256 can be used as is. 

While cSHAKE256 is slower than the AES key schedule, in many applications AES is preceded by a hash function anyway. In such situations one might as well use cSHAKE256 instead of other hashes. One specific example would be Diffie Hellman key exchange, where the results of the key agreement operation is typically an element in a large finite group, usually 1000 bits or more. There’s no particular reason why one should pass that bit string through a 256 bit bottleneck before initializing AES.

Another use case would be situations where the symmetric key is derived from a pass phrase. NIST SP 800-63b suggest systems allow a minimum of 64-character pass phrases. A random 64 character string consisting of just letters and numbers, without any punctuation or special characters, can have up to 330 bits of entropy. While real world passwords almost never have that much entropy, there’s no reason to throttle that potential entropy down to 256 bits. 

A third use case would be with memory-hard key stretching algorithms such as scrypt, argon2 or balloon. The last step in such algorithms typically forms a hash of all or part of a large memory buffer. By using cSHAKE256 in the last step, one will be directly prepared to initialize the AES cipher, without passing through a 256-bit bottleneck.

If there is a need to quickly shift between multiple, already agreed-upon AES keys, the simple, but fast solution is to store the round constant array for each key. A round key array of 240 bytes is much larger than a 32-byte AES256 key, but memory is very cheap these days, even on small microprocessors. 

While there are many candidates for ciphers with larger keys, the goal here is to stick as close to existing standards as possible. Does anyone know a reason why the AES key schedule cannot be safely replace by a standard XOF?

Arnold Reinhold