Implement the DES/3DES block cipher

Even though DES is no longer FIPS approved, it is still needed as an implementation for 3DES. As a crypto library we still will want to have an implemenation of every popular cipher anyways.

Follow the FIPS 46-3 standard to implement this and try to use the same naming convention of functions and variables as in 46-3. Also keep similar documentation as is in the standard.

Make sure you are working withing the constraints of the Message structure at the center of the Gestalt Library, i.e. data, iv, digest, etc are strings, and add algorithm to enum in src/lib.h. For your reference here is the current Message struct as of version 0.1:

As of Gestalt v0.2.0, Gestalt has moved from a single include library with a class based front end to a multiple include, function based library. See the v0.2.0 PR for more detail or the changes file.

So when you complete your implementation create a new file under src/des/des.cpp, along with any other files you need to implement DES, and a new header in include/gestalt/des.h where the functions for a user to use DES should be.

Note that you are free to add modes of operation for your DES implementation, but if rather you'd wait till Create general Block Cipher Modes of Operations #7 is complete to get the modes of operation for DES/3DES. This has been implemented, see https://github.com/HLRichardson-Git/Gestalt/pull/12

Testing

Don't forget to write a new tests/desTests.cpp file to test your implementation. I suggest following the AES implementation, of implementation structure (i.e. a DES class, and a DES testing friend class), and unit test structure. It will probably be better to first make a few Known Answer Tests, that you can get from here starting from page 124.

I have begun implementing DES, and I actually have an implementation already here, but I guess I hate myself because I looked at it and thought I can do this better.

I learned about bitset and will try to use it instead of the string I used in the implementation I already made. I hope this will make it better :). We'll see.

I believe I have implemented the key expansion, funnily enough, I think my key expansion test vector was wrong so I was annoyed why it wasn't working for a long time, and now using a proper vector it is passing. Oh the joy of coding.

I've got quite an update. I mentioned in the last comment that I learned about bitset and I wanted to implement the DES key expansion using that instead of how I did it a year ago using strings in the hope that bitset was faster. I have good news in that I did implement it and it was faster! But only by ~1000ns, see the benchmark below:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BM_DES_BITSET              13474 ns        13497 ns        49778
BM_DES_STRING              12802 ns        12556 ns        49778

Not that exciting admittedly.

But remember how I said I probably hate myself. Well, I think we can confirm this now. I then decided to implement the DES key expansion using uint64_t. I guess I thought if I was already in bit manipulation hell, might as well go all the way. I think I accidentally made something good though because here is the benchmark:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BM_DES_BITSET              13700 ns        13602 ns        44800
BM_DES_STRING              12429 ns        12556 ns        56000
BM_DES_UINT64               2356 ns         2344 ns       280000

A lot more impressive! That's about a 6x performance increase, which I am very happy with. If you want to see the three implementations you can see it in src/des.cpp. If you are reading this later, those 3 implementations will not still be in the code so if you want to see it go check out commit 177ef41.

So TLDR; the string implementation I made about a year ago is actually not much slower than a bitset implementation. But a uint64_t implementation is much faster than both.

Note: I do not know why I am putting so much effort into a algorithm that is planned to be deprecated :) send help.

UPDATE! In my latest commit #5f59ecb I added DES encrypt block function.

There is reason for update though, and that is like in my previous rambling I did not go the easy route and use my implementation I made a year ago. I am struggling (successfully) to implement DES using uint64_t because it should be faster, and its not everyday you get to get in the weeds and do bit manipulation so its kinda fun.

Since I benchmarked the previous tests I thought I would go ahead and benchmark the encrypt block function I just implemented:

----------------------------------------------------------------
Benchmark                      Time             CPU   Iterations
----------------------------------------------------------------
BM_DES_ENCRYPT_BLOCK        3355 ns         3299 ns       203636

So about ~3k ns per block. So with my napkin math that's around ~2.5 MB/s, which I am not too unhappy with.

If I had to guess where we could get some more performance out of it, it could be the sboxSubstitution having cache misses somehow, or the logic could be more efficient. Maybe how I implemented the permutations is inefficient. idk, I would need to setup a profiler again to see and I don't think at this moment I care about getting a bit more performance out of it.

Quite an awkward update TBH.

As said in the last update I implemented the encryptBlock for DES, so then implementing a decryptBlock was quite trivial sense you literally just flip the key order. In fact in doing this I noticed a pretty large flaw in the previous encryptRound function I made in that each call split up the halves and recombined them. So removing the function and just doing the logic in encryptBlock now saves us from doing that :). Unfortunately with the current setup of how I benchmark Gestalt I cannot test if this made a tangible improvement (this could be a possible issue to make and work on in the future).

Putting off the awkward update for now, the good news is that Gestalt now supports single DES with ECB and CBC.

Now for the awkward news. Previously in src/modes I made templated functions for ECB and CBC that are used for AES. They were pretty tailored to AES as that was the only block cipher Gestalt supported. So I worked towards extending the functions to support both AES and DES which has its own challenges, and as you may tell in the commit I was not able to use the templated functions. I should be able to in the future if I rework AES a bit. But for now DES ECB and CBC are individually implemented in gestalt/des.h.

Sadly that isn't even the most awkward news... In trying to get the templates to work for both DES and AES I reworked the testing for AES a bit so I could better see encryption then decryption results (where the old testing was a roundtrip). In doing so I found out that my implementation of AES-CBC encryption/decryption was incorrect and not working properly :)))))))))))))))))). I quickly (taking a break after an hour of spamming debug messages) found the issue was xorBlocks in tools/utils.cpp. The problem was that unsigned char indexing works on bytes and the string (which was in hex) indexing works on 4-bit, or hex char. So we were not properly xoring the correct values together.

I wish I could tell you that I found an elegant solution. But at least I found a solution, and that's what counts :). Here is my public L:

In xorBlocks I take the hex string and convert it to an unsigned char bytes vector, which properly formats the string. Great! A bit weird to turn it into a vector, but I already had this hexStringToBytesVec so I just reused it. But now this introduces other problems in the AES CBC template. Being that xorBlocks can only accept hex strings now. With how CBC works we can steal the output of AES encyrptBlock which is already in bytes. But instead of cleanly taking that output, we now have to convert it to hex then back to bytes :))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))). Not great!

But hey, its a solution and its now working!

This is planned to be reworked when I get around to reworking AES to allow me to use the template function with both AES and DES.

HLRichardson-Git / Gestalt

Implement the DES/3DES block cipher #8

Testing