[Cryptography] quantum computers & crypto

[Natanael]

Den lör 6 nov. 2021 02:39Arnold Reinhold via cryptography <
cryptography at metzdowd.com> skrev:

> [...]
>
> 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?
>

I'm in favor, partially because replacing the key schedule with a XOF
allows one to neatly convert AES into a tweakable block cipher.

Instead of simply caching the AES round keys in between invocations of the
block cipher, you cache the XOF mid-state before it parses the last input
block to the XOF key schedule. The input to it would include both the key
and a tweak value, and the tweak value could for example end with a counter.

So for each new block cipher invocation you can iterate the counter, update
a copy of the cached XOF mid-state to calculate new round keys, and then
process the plaintext/ciphertext with the AES rounds.

(In addition I also want to see wide block ciphers implemented, not just
the standard 128 bit width, but this at least has a chance of being
implemented sometime soon).

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20211107/65c53a88/attachment.htm>