Substitution ciphers amended with cipher block chaining: susceptible to frequency analysis?

Question

I have been studying ways to amend a simple substitution cipher, and one of the toy suggestions was to use CBC in the following way:

1. identify each letter with a number from $0\ldots 25$
2. start with a random IV, i.e. just a random letter
3. add IV to the first letter in the plaintext, modulo 26, and then encrypt according to the old substitution rules

(then continue with CBC in this way, using modulo 26 arithmetic instead of XOR)

The resource then goes on to say that while this clearly can't be cracked by simple frequency analysis on letters, the ciphertext can be split into 26 sets, that is, the letters that follow each ciphertext letter, and then frequency counting can be done. Later on, the author reiterates that by partitioning the message into 26 groups that follow each ciphertext letter, frequency analysis can be done.

I've been trying to figure out what they meant by this. My main problem is trying to interpret the "26 groups that follow each ciphertext letter" part, and I didn't get anywhere with it. (Perhaps they meant grouping sets of 26 adjacent ciphertext letters together, and then modular arithmetic would ensure some repetition somehow? I don't really see how that would work, but I also don't see any other interpretations)

Would greatly appreciate any suggestions!

Answer 1

CBC in this context means that each letter of the ciphertext is used to help encrypt the next letter.

Let's say, making up some numbers, that a certain ciphertext letter is C. The next plaintext letter is T. So to encrypt it, we will add C (or 2) to T, giving V. Then we do the substitution step, which could be anything and happens to be J.

The key observation here is that every time there is a C in the ciphertext, the next letter goes through the same thing. Plus two, substitute. And every time you find a C in the ciphertext, the next letter all Ts go to Js.

The break, then, is to go through the ciphertext looking for Cs. Then you write down all the letters that immediately follow. You get 200 Rs, 160 Js, whatever it is. So you can conclude that after a C, E is probably mapping to R and T is probably mapping to J.

Do the same thing with other letters: everything following Ds, everything following Es, and so on. You'll have 26 different sets of letters to do frequency analysis on. And once you have done them, you'll know the substitution several times over.

Answer 2

Encryption process in CBC mode of your amended cipher is performed as \begin{align} C_1 &= Subs(P_1 + IV \bmod 26)\\ C_i &= Subs(P_i + C_{i-1}\bmod 26),\;\; 1 < i \leq nb, \end{align} where $nb$ is the number of letters.

We access the ciphertext by observing the channel. As a result, we know how each letter is shifted by the previous ciphertext from the chain (the first one is the IV). That is the previous ciphertext determines the shifting by $P_i + C_{i-1}\bmod 26$

Now, there can be at most 26 shiftings by chain the additions. Group the ciphertext into 26 groups according to previous ciphertext values then execute the frequency analysis in each group to break the cipher.