[Cryptography] quantum computers & crypto

[Arnold Reinhold]

On Nov 8, 2021, at 12:42 PM, Jerry Leichter <leichter at lrw.com> wrote:
> 
>>> [Suggestions for ciphers with longer keys]
>> Why not just use Triple AES26, ala Triple DES?  E_AES256_k1 -> D_AES256_k2 -> E_AES256_k1 ?  Voila (albeit @1/3 the throughput), 512 bits!
>> 
>> Or even Triple AES256 with three different keys, Ek1 -> Dk2 -> Ek3 for 768 bits?
> Keep in mind that all that we know with any degree of certainty about 3-DES is that it's no weaker than DES-X (XOR'ing a single 64-bit extra key before and after DES itself) - and we know that DES-X is "pretty strong" *against brute force attack."  This was one of Phillip Rogaway's earliest results in concrete security.
> 
> So, sure, maybe Triple AES256 is really significantly strong than AES256 - and maybe it's exactly as strong as "AES256-X," which would be stronger against a brute-force attack that is out of even conceptual reach even with quantum techniques.
> 
> BTW, there's actually a completely different reason for considering systems with *much* larger keys.  Keys concentrate vulnerabilities:  Leaking 128 bits out of a document almost never reveals anything of significance.  (Oh, sure, sometimes the really relevant number is something like a price, and it's contained in just a few bytes.  But that's unusual.)  On the other hand, leaking 128 bits of key material can be a disaster, as it can serve to unlock a huge amount of material.
> 
> Now consider side-channel attacks.  Often, they work but have very low data rates.  Very old papers on them would point out that you can't entirely eliminate them, but if you can force their data rates low enough - say, a bit an hour - well, how much damage can they do?  At a bit an hour, of course, in a week you can leak enough bits of a 128-bit key to make a search for the rest trivial.
> 
> Today, we're seeing tons of clever side channel attacks, particularly of late within shared CPU's, and closing them completely is proving very difficult and a performance killer.
> 
> Now, if a key were 10Kbits long, and you in fact needed all of them ... a side channel attack might be somewhat more difficult.
>                                                        — Jerry
> 

Here is another way to look at using an approved XOF to schedule AES. If you are already using a hash to extract entropy/unpredictability from a bit string, such as the output from a public key agreement, why condense it into a 256-bit key and then expand those 256 bits with a different algorithm to provide a 1,920-bit round key array when an XOF hash could provide the 1,920 bits directly. That would avoid providing a relatively easy point of attack for the Grover search algorithm and it would also make side channel attacks harder. 

The entropy/unpredictability is defused in the original input string, it gets defused into the hash internal state and its defused in the round keys. Why make it explicit? 

All the brute force QC attacks seem to be based on Grover. Maybe Grover will never be practical on 256-bit searches, but why facilitate that? I don’t know enough QM to evaluate the interesting claims and counterclaims of QC attack feasibility in this thread, but I have been following the computer industry since the vacuum tube era and I would never underestimate the progress that can happen in the next 30 years. 

My only question is what possible criteria, besides speed, are there which the standard AES key schedule algorithm meets that SHA 3 Shake is not already certified to meet? 

Arnold Reinhold