Lucifer's substitution

September 10, 2010

As part of my analytical paper I’m writing for my application to Sarah Lawrence College, I’m performing cryptanalysis on a Lucifer variant. More specifically, I’m attacking the variant described in US Patent 3,796,830. This cipher is a SP-network that consists of three steps per round: addition, substitution and permutation. I initially focused on finding linearity in the S-Boxes, and almost immediately found something rather quizzical. The following is a pictorial hardware description of the S-Box:


A brief description: The S-Box provides 4 bits of output and takes 4 bits of input, along with a control signal (KS). The picture is fairly self explanatory–T0 is the first output bit, T1 is the second output bit, et cetera. The output is either a 0, 1, the value of KS, or its inversion.

However, if you calculate the given outputs for every input, you’ll notice something strange–the S-Box is a non-injective surjection. At first I was greatly surprised by this until I received confirmation of my doubts on FreeNode’s ##crypto. Usually S-Boxes are bijective by nature, so that you can invert them (and the encryption process). However, since multiple inputs map to the same output, information is lost. If this is not covered elsewhere in the cipher, I am hesitant to say this is a fatal flaw. But surely this is not the case, and I hope it is simply some form of error on my part.