Well, it turns out that my own hand cipher is incredibly weak. When I initially started designing it, using a chessboard felt a lot like an S-box lookup. There has been a great deal of research into S-boxes since the release of DES, and many ciphers today use them. What plagued me from day one, and I should have listened to my own intuition, is my chessboard key remains static throughout the entire operation. Unlike the Solitaire Cipher, by Bruce Schneier, where the cards in the deck are dynamically changing all the time. To get an idea of S-boxes, check out this AES animation (flash), which I think describes AES very well.
With ciphers, you need an ingredient of non-linearity in the system. Otherwise, your cipher can fall victim to linear cryptanalysis. Initially, I had thought, incorrectly I might add, that by using the ciphertext as the starting direction of the bishop's walk, I was introducing the non-linearity that I needed. Turns out this isn't the case. Let's use my board from my initial announcement, and the trivial example of "AAAAAAAAAAAAAAA" as my plaintext. Here's my board:
As per the algorithm, the bishop starts in "a1", which is valued at "38". Converted to binary, this gives us "100110", which means his travel is "SW" (no move), "NE", then finally "SW". He's back in the corner from which he started. Okay. No problem. Let's continue with the cipher then. Let's setup our worksheet. The character "A" as the value of "0", so my plaintext is:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +38 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 38
Now we take our ciphertext, 38, and use this as the start of our next bishop walk. As you can immediately see, we have a problem. He stays stuck in the corner, and we get the following result:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38
Our ciphertext is thus "mmmmm mmmmm mmmmm". While this may not seem like a practical example, it draws up a very real problem: this cipher is subject to a chosen plaintext attack. And, despite my best efforts to ensure that there are no repeated rounds in the cipher, here's a trivial example that shows they still exist. As such, the cipher is terribly linear.
The BIG PROBLEM with this cipher, and one that was hanging over my head the entire time I was designing it, is that the board key remains static. However, all is not over. Ultimately, the board is just an 8x8 matrix. As such, we should be able to do some matrix operations, such as multiplicitive inverses, exclusive OR, addition, subtraction, and so forth. This might be a major problem when writing the board down on a piece of paper, but this is trivial for a calculator, such as the HP-48 to do. But then we lose the allure of using a pure hand cipher, as we begin relying on computing tools to manage the internal state of the system. At this point, why not just use a typical computer, and use a cipher that has been tried and true, such as AES?
I must admit that I was sloppy when designing the cipher. I didn't take my abstract algebra and linear algebra into account. I should have looked at the math when initially designing it. Peter Maxwell, on the Cryptography Discussion mailing list, pointed out the following:
If you view the moving-the-bishop as an s-box lookup, and apply it to itself three times (composition), you end up with another s-box of the same size, lets call it S. Given S doesn't change, things should be rather easy indeed. If your cipher is then roughly akin to C[n] = P[n] + S[ C[n-1] ] with all operations taken modulo 2^6 the problem should now be a little more obvious.
Indeed. Basically, the cipher is weak due to two inherent problems with the system:
- The internal state of the system is static.
- The cipher does not contain a non-linear component.
I really want to use a chessboard for a cipher. I think it would be a fantastic tool that you could basically hide in plain sight. But, given the initial design of this cipher, and how weak it really is, it just doesn't work. The drunken bishop may make pretty ASCII art pictures for SSH server keys, but when in comes to cryptography, it's had just too much wine to be practical.
I'll hang this one up as a learning exercise, and move on. Designing hand ciphers is much more difficult than I had initially thought.
{ 1 } Comments