Re: To Mok-Kong Shen Re:Variable S-boxes
From: David Eather (eather_at_tpg.com.au)
Date: Fri, 6 Feb 2004 16:38:25 +1000
Opps - silly mistake - the attack suggested won't work with DES (the "data"
collected will all be zero's - not very useful) but needs a cipher where the
sub key is used for whitening - note to self - ensure brain in gear before
"David Eather" <email@example.com> wrote in message
> Hello Mok-Kong Shen, Hello All,
> I support pretty much every underdog (as long as they don't want to kill
> anyone) and any lost cause you can imagine. But your idea for creating
> variable S-boxes has had its run and failed - you need to rethink the
> and try again.
> Tom came up with a working general attack to the idea of variable S-boxes.
> There are variants specific to your particular scheme which was to xor (or
> other wise combine) plain text into the s-box. The simplest attack is
> (assuming DES for example) - xor plaintext into the sboxes so that all
> entries = 0, with DES 64 bit block, 256 bits of Sbox data this takes 4
> encryptions. The next encryption gives you the last left and right round
> subkeys - this is all or nearly all the bits from the master key - so the
> strength of DES goes down from 2**56 to almost nothing. The same approach
> would also work when a more modern cipher is modified - such as Serpent -
> this case you would get the last 128 bit subkey and the subkey gives
> information about bits in other sub keys.
> Your next proposal for starting with an IV was better but still
> Normally the attacker would get to choose the IV. It is no use saying
> is not what he should do - the attacker shouldn't try to break algorithms
> either. In any case the attack above can be used with a random IV to
> extract the final round key and other subkey data in the modified version
> Serpent (with 256 bit key) in about 2**132 to 2**133. This goes a long
> to fully breaking the modified algorithm so it has to be regarded as a
> mistake (the attack I leave for you to work out and there might be a time
> memory trade off possible)
> I strongly suspect that to remain secure the ability to control the
> modification to the S-box must be as difficult as finding the key or it
> won't work.
> Two methods are good for testing new ideas before they go public.
> Write it down - then spend time (until you are literally sick) looking for
> the same idea in other places. No points for re-inventing the wheel, but
> warm fuzzy feeling that you are on the right track.
> Stick it in a draw until you forget the specific details. Then pull it
> and attack it as though someone else had invented it (play devil's
> I think the idea of variable S-boxes by adding plaintext to them as
> proposed, with or without and encrypted IV is dead and this thread should
> quietly pass into history.
> David Eather