# Block cipher linearity (in relation to hill ciphers)

So while I knew hill ciphers were a form of block cipher (I'm assuming all the ones I have solved to date were ECB or something similar), so that got me thinking. Is it possible to use hill ciphers in other modes (ctr, ecb, cbc etc) on a binary alphabet?

• A) Could you provide formula/examples of how it would work?

• B) How would one launch a plain text attack against these?

• C) How would I protect against this attack?

1. CTR. Assuming d is even (for the nonce and counter), and the nonce and counter are d/2

2. CBC.

3. Any other relevant block cipher it could function as

• Why would we need that while it is vulnerable to known-plaintext-attack – kelalaka Sep 20 '19 at 8:29
• @kelalaka just curious. I mean, people try use CBC-MAC to hash and things like that. Normal hill cipher to encrypt, one uses C=E(K*P), would CTR be more akin to C=E(K⊕P)? how would person 2 launch an attack against it and how would person 1 protect against that attack? What about CBC? Are there any other block ciphers that it works for? – Anan Sep 20 '19 at 9:16

Yes, you can convert the Hill Cipher into almost any mode of operation. For simplicity, assume that $$M$$ represent the key matrix and $$P$$ represent the plaintext vector and $$C$$ is the corresponding ciphertext vector with $$C = M\cdot P \pmod{26}$$. For simplicity, we omit the mode 26 for the rest.

• ECB mode: we can assume that Hill cipher is already in ECB mode. As usual, divide the message into the correct matrix size, you also need a padding scheme.
• CBC mode: generate an $$IV$$ which must be unpredictable, however, this is your least concern, as usual, $$C_0 = M\cdot(P_0\oplus IV) \text{ and } C_i = M\cdot(P_0\oplus C_{i-1})$$. You also need a padding scheme.
• CTR mode: $$C=P \oplus [M \cdot (\text{nonce || Counter})]$$. Here one may need to take care of the counter since it is a Matrix. One can consider each cell of the Matrix as a mod 26 counter. No need to padding.

• CMC-MAC: Since you have CBC mode, you have it, now. Remember, in CMC-MAC the IV is all zero.

Note 1: For CBC-MAC we don't need just AES, we can use any secure block cipher.

Note 2: the $$\oplus$$ can generate a number greater than 26. You need to use $$+ \bmod26$$

And a final note: The Hill cipher is vulnerable to known-plaintext attack which means that it is broken! You cannot build a secure mode of operation from a broken cipher!

• Adding null values on the final block or nonsensical input to the initial plain text before the first block would result in valid padding, or are there better more sensible options? How would a slide attack perform against these? – Anan Sep 20 '19 at 10:16
• You can see start from reading padding from Wikipedia – kelalaka Sep 20 '19 at 10:22
• Realized I said that wrong, meant null or nonsensical to the input before the very last block encryption. was reading the sub setting of what you linked on the block cipher mode of operation page – Anan Sep 20 '19 at 10:24
• The padding must be removed from plaintext without an ambiguity. For example, all zero-padding is problematic since in decrypted ciphertext what is plaintext here100000? 1, 10,100,... – kelalaka Sep 20 '19 at 10:35
• so, to make the length retrievable, you simply add a 1 bit followed by 0 bits to fill out the block, and everything before the final 1 is the actual content, as nonsensical may be difficult to retrieve as you don't know when it ends, so say the end of the block is ...0110000110000000, you would simply remove up to and including the end most 1 bit to return the binary character "a" – Anan Sep 20 '19 at 10:52