security of Felix cipher

Question

I just find this pencil and paper cipher 'Felix' on this site and I want to know how secure it is?

Answer 1

Cipher details

Cipher type

The Felix cipher can be broken down into two algorithms: a substitution cipher and a permutation of the character pairs. We obtain the substitution if we read the number pairs in figure 3.3 vertically rather than horizontally. Since the permutation is fixed, it has no cryptographic value. Therefore, we'll only analyze the substitution cipher.

Block size

The substitution cipher has the property that each pair of characters in the ciphertext depends solely on the corresponding pair of characters in the plaintext. This means that the cipher's block size is two characters ($\log(36^2)\approx10.3$ bits).

Mode of operation

The cipher transforms each pair of characters in the exact same way, i.e., the mode of operation is Electronic Codebook (ECB).

Key size

You can construct a total of $36!$ different keys (tables), but the symbols assigned to each row and the corresponding column are arbitrary, as long as they match. Therefore, we can reorder the numbers $1,2,3,4,5,6$ assigned in any possible way – or swap the rows $i$ and $j$ and then the columns $i$ and $j$ – to obtain equivalent key.

This means that the effective key size is $\log(\frac{36!}{6!})\approx128.6$ bits.

Weaknesses

ECB mode

An immediate problem is that a given character pairs always gets transformed into the same character pair.

If part of the plaintext is known (e.g., it begins with $HELLO$), you already know which character pairs of the ciphertext correspond to $HE$ and $LL$ in the plaintext.

Involution

The substitution cipher is an involution, meaning that encryption and decryption are the exact same function.

In our example, the ciphertext corresponding to the plaintext $LL$ is $T8$. That means that the ciphertext corresponding to the plaintext $T8$ is $LL$.

Fixed points

The substitution cipher has an unusual number of fixed points (characters pairs that get transformed into the same character pairs).

The character pair $\alpha\beta$ is a fixed point if and only if the column of $\alpha$ coincides with the row of $\beta$. That means that for every $\alpha$, there are 6 $\beta$ such that $\alpha\beta$ is a fixed point, giving a total of 216 fixed points, which is $\frac{1}{6}$ of all possible character pairs.

Since it's easy to determine which character pairs in the ciphertext are not fixed points (if the language is known), this might be enough to guess parts of the plaintext.

Small block size

Due to the small block size, a trivial chosen-plaintext attack is possible.

It is sufficient to get the plaintext $AA\ AB\ AC\ \dots BA\ BB\ BC\ \dots$ encrypted to be able to decrypt any ciphertext. Reconstructing the key table is unnecessary.

Known-plaintext attack

A known-plaintext attack may be possible due to the following weaknesses of the cipher:

• Every known pair of different characters gives away some information about the key.

  For example, $KN$ gets transformed into $7H$. That means that $K$ and $7$ share a row and $N$ and $H$ share a column.

  If the character pair is a fixed point (e.g., $OW$ gets transformed into $OW$), as discussed previously, we can infer that the column of $O$ coincides with the row of $W$.

• Inverted character pairs give away more information on the plaintext.

  For example, $RE$ gets transformed into $2S$, while $ER$ gets transformed into $FA$. That means that the characters $2$ and $F$ (and the characters $S$ and $A$ as well) are diagonally opposed, i.e., one's row coincides with the other's column.

• Repeating letters give away even more information on the key.

  For example, $LL$ gets transformed into $T8$. That means that both $T$ and $8$ lie on the key's diagonal.

Since every bit of known plaintext weakens the key a little, a computer can test all possible keys until finding one that decrypts the ciphertext correctly, given that sufficient plaintext is known.

Let's say somebody sends you the message whose corresponding ciphertext using the key from your example is as following:

HE LL OI LL SE CU RE KN OW LE DG EI SP OW ER
HE T8 AW T8 2T CU 2S 7H OW HP DG FO XT OW FA

We learn that the following is true:

On the diagonal:                          T,8
Characters that share a row:              A,O   E,F   H,L,T   K,7   R,S,X,2
Characters that share a column:           A,R   E,P,S,T   H,N   I,O,W   L,8
Column of the first is row of the second: C,U   D,G   H,E   O,W
Diagonally opposed:                       A,S   F,2

Because of equivalent keys, we can fix the position of $T$ and $8$ anywhere on the diagonal. This determines the position of $L$ (row of $T$, column of $8$), the row of $H$ (we can fix the column) and the column of $N$ (2 possible locations, since we can fix the row if it isn't the column of $H$), which in turn determines the location of $E$ (row determined by $H$, column by $T$).

$F$ lies on the same row as $E$. Since $F$ and $2$ are diagonally opposed from each other, $F$ can't lie on the diagonal and $F$'s location will determine the location of $2$. Since $S$ lies on the row of $2$ and the column of $T$, the location of $F$ will also determine the location of $S$ and $A$ (diagonally opposed) and $R$ (row of $S$, column of $A$).

• If $E$ and $N$ lie on the same row, we can fix the column of $F$.

• Otherwise, $E$ may lie on the column of $8$, on the column that coincides with the row of $N$ or on any other of the remaining two columns (we can fix it). But if $F$ lied on the column of $8$, $2$ and $S$ would lie on the row of $8$ and, therefore, $S$ would be diagonally opposed from $L$. Since this isn't true, the are 2 possible locations for $F$, $2$, $S$, $A$ and $R$.

So far, we have only 3 different partial keys:

$$ \left.\begin{array}{ccccccc} &\alpha&\beta&\gamma&\delta&\varepsilon&\zeta\\\alpha&T&L&H&A\\\beta&&8\\\gamma&E&N&&F\\\delta&S&&2&R\\\varepsilon\\\zeta& \end{array}\right| \left|\begin{array}{ccccccc} &\alpha&\beta&\gamma&\delta&\varepsilon&\zeta\\\alpha&T&L&H&A\\\beta&&8\\\gamma&E&&&F\\\delta&S&N&2&R\\\varepsilon\\\zeta& \end{array}\right| \left|\begin{array}{ccccccc} &\alpha&\beta&\gamma&\delta&\varepsilon&\zeta\\\alpha&T&L&H&&A\\\beta&&8\\\gamma&E&&&&F\\\delta&&N\\\varepsilon&S&&2&&R\\\zeta& \end{array}\right. $$

Since $A$ is diagonally opposed from $S$ which lies on the same column as $T$, $A$ and $O$ lie on the same row as $T$. This determines the position of $O$ in the first two cases and leaves 2 possible locations for $O$ in the last. Since $W$ lies on the same column as $O$ and $W$'s row coincides with the column of $O$, this determines the location of $W$. This leaves us with only 4 different partial keys so far.

In the second partial key, there are 2 different possible locations for $X$; in the remaining 3 partial keys, there are 3. This leaves us with 11 different partial keys so far.

Continuing this procedure, there are 3 different locations for $P$ and 4 for $I$. This distributes 20 characters (all used characters except for $C$, $D$, $G$, $K$, $U$ and $7$) in $132$ manners.

This leaves 16 possible locations for $K$ (all remaining ones), up to 5 for $7$ (row of $K$), 14 for $C$, up to 6 for $U$, 12 for $D$ and up to 6 for $G$, giving a total of less than $483\,840$ possible manners to distribute those remaining 6 characters. Note that this number would get much smaller if we knew a little more plaintext.

This gives a total of less than $63\,866\,880$ different manners of distributing all used characters¹, meaning that a brute-force attack on all those possible keys only needs to try less than $2^{26}$ keys. Computers do this in no time.

Note that we achieved this attack with only 13 different character pairs, i.e., $\log(36^{26})\approx134.4$ bits of plaintext, which only slightly more than the effective key size.

Chosen-plaintext attack

Using the same ideas as in the known-plaintext attack, it is possible to perform a chosen-plaintext attack with negligible work and encrypting not more than 35 character pairs ($\log(36^{70})\approx361.9$ bits of plaintext) and possibly only 29 character pairs ($\log(36^{58})\approx299.9$ bits of plaintext).

The ciphertext corresponding to, e.g., $AA$ ($TR$ in our example) completely determines the location of $A$ in function of $T$'s and $R$'s position on the diagonal.

Thus, encrypting $AA\ BB\ CC\ \dots\ 88$ (35 character pairs) is sufficient to reconstruct the key table ($9$'s position is the only remaining one). If we already know that the character $\alpha$ lies on the diagonal, encrypting $\alpha\alpha$ is unnecessary. If the characters of the diagonal are known before any associated pair is encrypted, we'll have encrypted only 29 character pairs.

Due to equivalent keys, the elements of the diagonal can be fixed at will and reconstructing the table is straightforward.

---

¹ The location of unused characters doesn't affect decryption. If they are used in a future message, it's sufficient to try all $10! = 3\,628\,800 < 2^{22}$ possible permutations.

Answer 2

As the page explains, the cipher it describes is a simple variant of the bifid cipher, with the alphabet extended from the traditional 25 to 36 letters. As such, most techniques for breaking the bifid cipher ought to be more or less directly applicable to it.

The bifid cipher is nowadays mainly used for crypto puzzles. Like most classical ciphers, it is not a secure way to encrypt long messages, especially not against an adversary with access to computers and modern statistical cryptanalysis techniques. For an example of what kind of attacks are possible, see e.g. the paper "Automated Ciphertext-Only Cryptanalysis of the Bifid Cipher" by Machiavelo and Reis (2006). I found the concluding remarks from that paper appropriate enough to quote here:

"The method here presented, and its implementation as a computer program, permits to crack in an acceptable time any sufficiently large cryptogram, provided that the language of origin is know. It is not, because it essentially uses heavy statistical analysis, a system to solve small cryptographic puzzles such as those for which the Bifid cipher is currently used: for recreational purposes. 'Typographical' ciphers such as this simply do not have good security properties when used for large messages. If modified to better resist this kind of attacks, they become too cumbersome to be used 'by hand'."

(Ps. Anyone familiar with crypto jargon is likely to cringe at the repeated misuse of the word "crib" on the page you linked to. Properly, the word refers to a piece of known or suspected plaintext used as an aid in cryptanalysis, and dates back to Bletchley Park during WWII. What the Felix cipher page calls a "crib" is better known as a Polybius square, and has no apparent connection to the established meaning of the term.)