Posted: Tue Sep 01, 2009 9:33 pm Post subject: S box replaced by linear function in DES.
Hi, I search through the web. I know that the core security in DES is provided by the non linear S Box.
I would like to know what really happened when S Box is replaced by linear function? Consider a cipertext attack on such modified DES, why people keep saying that it can be easily cracked? Could someone explain to me in a mathematical way. Consider the cipher being replaced by this modified cipher.
L_0 is the 32 bit of the plain text, R_0 is the next 32 bit of the plain text. || is a function to combine the L and R together such that plain text = L || R
1) You restrict the attacker to a ciphertext-only attack; the most difficult attack-model outside full-on blackbox. This is a bit presumptuous and ignores many of the factors that contribute to cipher security as we know it.
2) First you speak of replacing the S-Box with a linear function. Then you go on to say that the linear function actually combines the left and right halves (XOR's job in DES as i recall). I'm not as much on the up-and-up about DES as some of the folks here, though.
If you replace an S-Box in an SPN (ignoring the DES-factor) with a linear function, you open it up to most modern cryptanalytic techniques. Those sboxes are designed to make linear and differential characteristics hold true as close to 50% of the time as possible. Using a simple linear function instead destroys that resistance.
For example, it may make any input's 1st bit equal to the linear-function's output's 2nd bit 100% of time. By plugging in test cases for the subkey in a previous round, an attacker could test if he "got it right" simply by comparing those bits. This is a very short and simple description of a linear attack, but hopefully it illustrates the point. If you design the linear function so that this simple bit-to-bit relationship doesn't happen, we might find another (like bit1 XOR bit5 = bit6 XOR bit7 XOR bit3). From here, you'd end up literally trying to find a non-linear function that eliminates these weaknesses and would likely end up at our old favorite: the S-Box.
Sorry if this explanation is not math-ish enough, but it comes from my experience (although limited) in writing attack code.
Using linear function likely also leads to more simple algebraic attacks that I haven't fiddled with yet. I suggest taking a simple 1-3 round SPN and plugging in your linear function idea in place of the sbox. Then see what games could be played with a known plaintext-ciphertext pair. I'm willing to bet you'd find some tricks that could recover the key with ease.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum