Otdfbt

Background:

Quite a long time ago (somewhere 1998) I thought I was really clever and invented my own encryption/decryption code. Looking through old code I rediscovered my old algorithm. (No, it was never used in any production environment.)

I'm wondering what type of encryption my naive self invented back then. I'm guessing it is a polyalphabetic substitution cipher, but I'm not really sure?

My Questions:

• What type of algorithm is this?


• How weak is it against modern day cryptanalysis and what methods would be used to break it?

What the code below does:

The algorithm encrypts and decrypts based on a set 64 alphabets. Each alphabet consists of the same 64 characters in random order; each character is included exactly once per alphabet. This set of alphabets is effectively the key for the algorithm.

To start, the plaintext is base64 encoded. Then each individual character, in the base64 encoded plaintext, is substituted by a character from one of the alphabets. The first characters is (always) picked form the first alphabet, for subsequent characters the alphabet is selected based on the index-number of the substituted value of the character preceding it. So, it 'encrypts' one character at the time and, if one character in the ciphertext changes, the decryption will (most likely) be garbled from that point on.

The code also adds base64 style padding to the ciphertext, in an attempt to be 'even more secure' by passing of the ciphertext like regular base64 encoded data.

The Algorithm:

Encryption is being carried out over letters from a 64-element alphabet in the following mode:

$$C_0=F_0(P_0)quad C_i=F_C_i-1(P_i)$$

Where $F:mathbb Z_64times mathbb Z_64tomathbb Z_64$ represents 64 different, random, fixed permutations forming the key.

_{Reference PHP-Code can be found in the revision history.}

What type of algorithm is this?

The best capturing for this algorithm that I can see would be as "mode of operation for a tweakable block cipher" with the tweakable block cipher being the one that has keyspace size $(64!)^64approx 2^18943$ and in its current representation uses (at least) $64^2cdot 6=24576$ bits for key representation. The tweak size is 64 as is the message and ciphertext space. Key decoding then works by partitioning the key into 64 equal-sized strings and then using each string to identify one permutation over 64 elements. Encryption works by selecting the permutation indicated in the tweak and applying it.

Using the notation $E^textTweak_textKey(textPlaintextLetter)$ the mode is then $$C_0=E_K^0(P_0)quad C_i=E^C_i-1_K(P_i)$$ for a given plaintext sequence $P_i$ and the corresponding ciphertext sequence $C_i$ and the key $K$.

How weak is it against modern day cryptanalysis and what methods would be used to break it?

This construction has four main problems for modern cryptography:

1. Ridiculous keysize (for symmetric cryptography). It takes 2.3kB to represent the key, normally our keys use 32 bytes which is plenty (because you can't search $2^256$ fully).


2. Small block size. This is a problem in and of itself as an attacker can just build a dictionary of the input-output pairs by making a sufficient number of block cipher queries (this is part of the reason why modern block ciphers use 128 instead of 6 bit blocks).


3. Deterministic Encryption. The given encryption scheme cannot be CPA secure, because it is deterministic. That is an attacker can recognize whether two encryptions yield the same value. Even worse, this scheme has the same issue as CBC (the best one could hope for in online deterministic encryption), namely it leaks prefixes. If I encrypt abcde and then encrypt abcgh under the same key, the attacker can see that the messages were equal up to abc.


4. Lack of authentication. In theory one could think about fixing the previous point by forcing $P_0$ to be a random value (that's what CBC does). In this case this construction might be secure against CPA attackers. But of course it still isn't secure against the most standard adversary model in modern cryptography: CCA secure, that is attackers who also get to ask for decryptions (with one exception input). To break CCA security when given a challenge ciphertext of one of two possible plaintexts an attacker would simply change the last ciphertext letter and ask for the decryption and use the first few letters to determine what plaintext was encrypted.

_{Also if you don't understand something in this answer, please just ask (in the comments) and don't be frightened if you think "it should be obvious" or something like that.}

This scheme reminds be of the Jefferson Wheel Cipher. Variants were actually used in the military so at one point the general idea was 'secure'.

If I understand it right, the presented construct seems weaker however and suffers a Know Plaintext Attack.

If I know P0, C0 and the algorithm then I can deduce one entry of the F0 alphabet. With 64 or so messages, I can get the full first alphabet. Given sufficient text, I can use the same idea to deduce all of the scrambled alphabets.

With these old style ciphers, it is interesting to consider if a cipher text only attack is possible. If we know that the language is US English then we can do a frequency count on the first letter of the cipher text. Based on that we can deduce some of the entries in F0. With sufficient cipher text, all of the most common letters could be pinpointed in all of the alphabets. At that point, the full set of alphabets could be unraveled with further frequency analysis and human deduction.

Working through the weakness of an older cipher is a great way to learn about modern cryptography. While there have been some big jumps, ciphers have mostly evolved against new and stronger attacks.