# DES hardware implementation of substitution lookup table [ ReWorked ]

I'm a crypto enthusiastic and student of cryptography. I'm developing a project with other students titled "A hardware implementation of a DES cryptography for educational purposes", our idea was to make a simple version of DES encryption in a piece of hardware to help students that are learning cryptography understand better how this complex encryption method is implemented in hardware.

First, we started the system with an input of 8 bits to simplify the complexity and save space. Them, we created all the parts of DES cryptosystem (Initial Permutation, Feistel, XOR, Final Permutation).

Here is a image of our main system:

One of the important parts of the system is the Feistel Function. The Feistel part were divided in 4 parts, Expansion, Mixing, Substitution, Permutation. Each of these parts are implemented as following:

The expansion CI just take the bits and duplicate them putting the new bit in the adjacent output, this CI receive 4 bits of the right part of the input and outputs 8 bits. Mixing just take the first bit of the output of expansion and XOR with the first bit of the key(8 bits) and so on... the output is 8 bits. Now we have the most important part and the part that I personally think we're missing something. The Substitution in witch is the S-Box, this CI has an 8 bits input and these 8 bits are divided in two parts(because we developed only 4 bits S-Boxes) these parts enter the S-Box and the S-Box output is of 2 bits, when you see the S-boxes of DES, all of them uses a lookup table, we've the idea of using the Karnaught map for implementing this table.

Our table :

And here is where we stopped, because we implemented all of this and had fail results like this:

The S-Box works like a lookup table on software but the system does not work, is there any specific way that these look up tables are created ? We couldn't see any pattern in the outputs of the table, do you guys have any material to help us ? I feel like this is the last thing to work on.

• Please note that there is no need to post several comments. If you want to add or modify something, simply click the edit link. For your convenience, I have deleted your three comments after adding them (including the linked images) to your post with an “edit”. The rest is up to you… if you have any questions, our help center will surely provide the information you need. And if it doesn’t, ask in our chatroom. Thanks – e-sushi Aug 17 '15 at 5:02
• What does this have to do with the Digital Encryption Standard? – user1430 Aug 17 '15 at 7:06
• Do you even read Bro? – andremonteiro Aug 28 '15 at 21:02

A simple way to think of the S-boxes of DES when it comes to a hardware implementation is: 8 independent ROM ICs, each with 6 address input lines and 4 data out lines. In an educational physical implementation with retro standard ICs, two such ROMs fit a 4 kiB EPROM (a 2732). Some actual software implementations of DES do group S-boxes two by two in order to reduce the number of table lookups.

Another way is: 8 times, 4 independent boolean functions of the same 6 input bits; for a total of 32 independent boolean functions of 6 input bits out of 48 input bits (which themselves come from the key, with a wiring dependent on the round and if we are enciphering or deciphering). It is well known how to build any boolean function of 6 input bits (e.g. using Karnaugh maps), hence in principle build these 32 boolean functions. However Karnaugh maps do not yield efficient/compact circuits in the case of DES S-boxes.

There is little exploitable regularity in the DES S-box functions. The most striking one is that each line of numbers of the spec of the S-box values (FIPS 46-3 appendix 1) is a permutation of $\{0\dots15\}$. It follows that we can model each of the 32 boolean functions by: 4 functions of 4 input bits (coding columns on that spec) set for precisely 8 out of 16 combination of these 4 inputs, followed by selection of the appropriate of the 4 results of these 4 functions according to 2 other input bits (coding line in the S-box). This translates into a trivial systematic construction of the functions using NAND gates with at most 8 inputs, of depth 3 (including input inverters) plus the final 1-out-of-4 multiplexer stage. Using this structure, it is very easy to fit two S-boxes in a generic PAL with 12 inputs plus internal feedback and 10 outputs, at least 8 of which having at least 8 input terms. The once-popular PALCE22V10 is ample.

The problem of minimizing the complexity of these 32 functions, including considering that they are evaluated together and some work can be shared among the 4 functions belonging to the same S-box, has been extensively studied; for example by Matthew Kwan: Reducing the Gate Count of Bitslice DES, 2000, eprint 2000/051; however he is focusing on 2-input gates and considers XOR of unity cost, which is fine for software, but hardware has different constraints.

As for "how to build the substitution as hardware", it should be easy if you know any of the hardware description language (eg. VHDL or Verilog). Simply write the Sboxes of DES, then the synthesis software will handle the rest. You can also "synthesis" by hand, although that may take a lot of effect.

Still, I'm not sure if this is what you are looking for. Your post says "thought of a very simple DES circuit of 8 bits". It looks like you have designed a simplified version of DES for teaching. However, your post didn't give the description of your simplified DES; only provided some implementation schemes. If you have altered the Sbox of DES to 8-4 (like your picture above), then implement it like that is fine?

• Thank you for replying! We're really appreciated! "Simply write the Sboxes of DES, then the synthesis software will handle the rest. You can also "synthesis" by hand, although that may take a lot of effect. " That's the problem, we want to do all by hand, including the synthesis. :( – andremonteiro Aug 18 '15 at 1:21
• The Sbox is actually a vectorial boolean function. Take DES's Sbox for instance, it can be represented as 4 6-inputs boolean functions. The Sbox table gives the truth tables of those boolean functions. You can compute their ANF(Algebraic normal form), and implement them as their ANF(with XOR and AND gates) . However, this is not an efficient way to implement the Sboxes. That's why we often leave it for synthesis software. Researchers do this by hand when they are looking the best(or most efficient) implementation, which I believe is off your topic here? – gs478516846 Aug 19 '15 at 3:17
• Thank you soo much, I'm implementing a new concept with XOR and AND gates, Like you said! Let's see if it works. – andremonteiro Aug 26 '15 at 19:44
• Unfortunately it didn't work. We've build an lookup table with hardware trough Karnaugh, the system works this way: we've 8 bit input and 4 bit output, first we split in two halves them we put them as the input of the first S-Box ( Our S-Boxes Works only with 4 bits input ). The S-Box works like a lookup table on software but the system does not work, is there any way that these look up tables are created ? We couldn't see any pattern, do you guys have any material to help us ? I feel like this is the last thing to work on. Thanks! – andremonteiro Aug 27 '15 at 22:49
• You should really check fgrieu‘s answer, which gives almost everything you need for the implementation of DES's Sbox. However, I'm still not sure your problem is really about the how to imeplement DES's Sbox. You can implement a Sbox with its ANF, Karnaugh map optimized form, synthesis software optimized form or expert optimized form(e.g. BitSlice version in fgrieu's answer). Some forms are more efficient(low-area,low latency) than others; but they should all "work", if you indeed, get them right. In this sence, I really doubts that changing to other forms will solve your problem. – gs478516846 Aug 28 '15 at 15:02