[Cryptography] quantum computers & crypto

Ray Dillinger bear at sonic.net
Mon Nov 8 16:00:22 EST 2021



On 11/8/21 5:42 PM, Jerry Leichter 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?
I can't think of a very strong argument that Triple AES, applied one
block at a time, would _necessarily_ be stronger than AES.  It is very
likely to be.  Almost certain to be.  It would be very surprising if it
weren't.  But I remember the 'Double DES' superencryption proposal and
how certain that seemed and how very surprising was the analysis that
proved it wasn't.

My goto example of 'more isn't always better' is shuffling a card deck. 
Shuffling is understood as randomizing the order of the cards.  So you
may decide that 'shuffle(n)' to shuffle the cards n times is a good
randomization algorithm. 

But if you do 52 perfect shuffles in a row you bring the deck back into
its original order.  No matter what (n) you use, it will never be 'more
secure' than some (n) less than 52.  The so-called 'perfect shuffle' is
actually fairly lousy considered as a randomization algorithm, but you
see the point.

... that said ...

Here is a construction of Triple AES that I'd approve without
reservation but it would require quadrupling (to 512 bits or 64 bytes)
the block size.

In quasi-standard notation it would be


AES3(K123,P)=AES(K3(Shuffle(AES(K2(Shuffle(AES(K1,P))))))

Shuffle(ABCD EFGH IJKL MNOP)=(AEIM BFJN CGKO DHLP)

For P = 512 bit block of plaintext (= 4 AES blocks)
For AES3 key K123 = cat(AES key1, AES key2, AES key3)
For 'shuffle' defined on 512-bit blocks of 32-bit words (presented here
in AES-block sized groups)

I'd believe in the security of this particular formulation of AES3
specifically because it breaks the block boundaries and in doing so
makes me not worry about the kind of 'diminishing returns' seen in some
cases where the same cipher is applied multiple times to the same
block.  These are also the block boundaries that known analytic methods
rely on - and while there are still block boundaries they are much
further apart.  AES is believed to achieve full diffusion (or close
enough to be undetectable) over its 64-bit block length.  With the
'shuffle' operation mixing material from the 512-bit block into
AES-block size chunks, AES is enabled to perform complete diffusion. 
And if there are any 'interference'



So it still isn't a mathematical proof of security, but it would
transform my personal trust in getting the full benefit of the
additional operations from 'very confident' to 'I'd bet my life on it'
levels of certainty.
> 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.
Trivial indeed.  If breaking a 40-bit key has become trivial, imagine
the ease of breaking a negative-40 bit key! Although overhead means it
can't actually be completed in negative time.
> 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.
Very true.  Lots of crypto operations are happening on machinery where a
whole lot of other things are happening at the same time.  And
'speculative execution' is a window across process boundaries that's
hard to close without severely compromising the CPU's performance.  If
the amount of side channel leakage that's feasible within the runtime of
a given crypto application (or operation) remains far less than key
length, the security of that application is improved.

    Bear



More information about the cryptography mailing list