security of Felix cipher

Question

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

EDIT

From http://web.archive.org/web/20110825142054/http://topcat.hypermart.net/papers/felix.txt

Felix a pencil-and-paper cipher

I. Synopsis

Felix is a `pencil-and-paper cipher' offering relatively good security for causal use. Unlike modern encoding schemes that require, at a minimum, a computer to be of any practical consequence; Felix requires only that you follow three elementary rules (outlined below). If you're curious about cryptology, the Felix cipher is a great place to start. This cipher can typically be understood and applied, even by children, in a handful of minutes. Quite simply that means, its easy to implement for common folks such as you and I. (i)

The Felix cipher is an expanded form of the Bifid cipher originally devised in 1901 by Felix Marie Delastelle. The author of this work respectfully acknowledges Monsieur Delastelle's achievements in the field of cryptology. (ii/iii)

II. The Crib

First, create a crib, by randomly dispersing, all 26 letters of the alphabet, and ten digits from 0-9, throughout: (iv)

   1  2  3  4  5  6
1  8  P  3  D  1  N
2  L  T  4  O  A  H
3  7  K  B  C  5  Z
4  J  U  6  W  G  M
5  X  S  V  I  R  2
6  9  E  Y  0  F  Q

You'll notice each character in the crib is represented by coordinates on the left most column, and top most row. Thus, character 0 (zero), is located in row 6, and column 4. (v)

III. Encoding messages

Working left to right, locate each character from the message (fig 3.1) in the crib, and write out its coordinates vertically (fig 3.2) beneath the message:

fig 3.1:

K N O W L E D G E  I S  P O W E R

fig 3.2:

3 1 2 4 2 6 1 4 6  5 5  1 2 4 6 5  
2 6 4 4 1 2 4 5 2  4 2  2 4 4 2 5

Next, join each digit to the previous digit on the right (fig 3.3), and each row to the previous row above (fig 3.4):

fig 3.3:

31 24 26 14 65 51 24 65
26 44 12 45 24 22 44 25

fig 3.4:

31 24 26 14 65 51 24 65 26 44 12 45 24 22 44 25

The string of numbers produced (fig 3.4), are then read in pairs horizontally working left to right, creating a second sequence of coordinates (fig 3.5), which are next converted back into characters from the crib via their respective coordinates (fig 3.6):

fig 3.5:

31 24 26 14 65 51 24 65 26 44 12 45 24 22 44 25

fig 3.6:

7  O  H  D  F  X  O  F  H  W  P  G  O  T  W  A

The message is now fully encoded, and ready to be delivered. (vi)

IV. Decoding messages

To decode a message, simply reverse the process... Working left to right; convert each character into its corresponding coordinates (fig 4.1), written horizontally (fig 4.2):

fig 4.1:

7  O  H  D  F  X  O  F  H  W  P  G  O  T  W  A

fig 4.2:

31 24 26 14 65 51 24 65 26 44 12 45 24 22 44 25

Next, divide the string of numbers into two equal rows, placing the second row below the first (fig 4.3). Reading the digit in the top row, along with the digit in the bottom row together vertically, use these coordinates to locate the character in the crib and write each character below its corresponding coordinates (fig 4.4):

fig 4.3:

3 1 2 4 2 6 1 4 6  5 5  1 2 4 6 5
2 6 4 4 1 2 4 5 2  4 2  2 4 4 2 5

fig 4.4:

K N O W L E D G E  I S  P O W E R

The message is now fully decoded, and plainly readable.

V. Summary

To encode:

• Convert the plaintext into coordinates vertically
• Join previous digits into a single line
• Horizontally convert coordinates into ciphertext

To decode (simply reverse the process):

• Convert ciphertext into coordinates horizontally
• Split line into two equal parts (2nd half on bottom)
• Vertically convert coordinates back into plaintext

Notes

i. A cipher is a message written in such a way as to conceal its contents. Encoded messages are rendered unreadable. Decoded messages are rendered plainly readable.

ii. Felix Marie Delastelle (1840-1902) was a Frenchman most famous for devising several systems of polygraphic substitution ciphers including the Bifid cipher. Delastelle is unusual for being an amateur cryptographer at a time when significant contributions to the subject were made by professional soldiers, diplomats and academia.

iii. The Felix cipher is based on the Bifid cipher, but reworked with a larger 6x6 crib rather than the more limited 5x5 crib Bifid uses. Whereas the Bifid cipher only referenced 25 characters (typically 'I’ and 'J’ were combined), the Felix cipher uses all 26 letters of the English alphabet, and all ten digits zero to nine.

iv. The crib (excluding coordinates), is a 6x6 grid of 36 characters. Do be sure to create your own private crib when using this cipher. The crib used in this document will have been read by any number of people...

v. Coordinates (always read by row first, then column) are fixed at the left most column, and top most row. The intersection point of a row (horizontal axis), and column (vertical axis), yields a single character from the crib. When labeling coordinates, they need not be digits as shown in this document, however, all labels must unique within row, and within column.

vi. To encode/decode a given message, both the sender and recipient need a copy of the same crib and its coordinates. But remember, NEVER give out the details of the crib to anyone but trusted parties.

About

Copyright 2007 Top Cat/Michael S. Sanders. All rights reserved. This document may be reprinted freely provided no changes are made without the author's consent.

topcat.hypermart.net

eof

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.)