• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

S box replaced by linear function in DES.

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
dreamer.ande
Just Arrived
Just Arrived


Joined: 01 Sep 2009
Posts: 0


Offline

PostPosted: Tue Sep 01, 2009 9:33 pm    Post subject: S box replaced by linear function in DES. Reply with quote

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

C_i = R_{i-0} || R_{i-0} XOR K_{i-1} XOR L_{i-0}
Back to top
View user's profile Send private message
jk_the_cjer
Forum Fanatic
Forum Fanatic


Joined: 05 Oct 2004
Posts: 16777215


Offline

PostPosted: Thu Sep 03, 2009 9:25 am    Post subject: Reply with quote

I'll take stab:

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.
Back to top
View user's profile Send private message
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
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

Community Area

Log in | Register