Railfence Cipher and the frequency analysis attack


by Jerome Bradenbaugh
Courtesy of fravia's pages of reverse engineering
The Railfence cipher is a transposition cipher based on rearranging the order of the plaintext letters according to a rising and falling pattern resembling a railfence. Consider ciphering the message Bulls win by six with a "three-rail" fence. The message would cipher as follows:
b               s                n                                               
    u       l                i               y       s       x   
        l                w               b               i       

Notice the "railfence" created by plotting the letters (and in this case, spaces, too) in this order. From there, strings are created left to right, top to bottom and concatenated to produce the cipher text. The three strings look like this:

bsn 
ul i ysx
lwbi

Finally, concatenating the three strings produces bsn ul i ysxhlwbi. Unlike the other ciphers in this demonstration, the spaces stay in. That's a personal preference. Since letters are simply being rearranged, you can include any or all characters. There's also one other consideration to using the Railfence cipher.

Not only can you specify the number of "rails" (to which the application below refers to as groups), but you can also determine the rail at which you want to start placing the plaintext letters. In the above example the plaintext letters start from the first rail of the fence. That is, b goes in the first rail, u goes in the second, l in the third, and so forth. However, you can start with the second group, putting the b in the second, the u in the third, and so forth. The application below refers to this as displacement.

All the receiving party needs is the number of groups and the displacement, if any. Here's the application. This particular applcation has some validation features, and assigns default values to Groups and Displacement if those validation conditions are not met. The defaults are three groups and zero displacement.

Text:


Groups Displacement    
To cipher enter the plaintext in the text area, select the number of groups and a displacement amount, then choose the Cipher button. It's that easy. This application will handle as much as 8-9K of text. After that, you run the risk of sucking up all your system's resources.

To decipher enter your ciphertext in the textarea, enter the number of groups and the displacement (if any), then choose the Decipher button. Notice that the plaintext has retained its spaces.

This application does some form validation for basic common sense restrictions. For example, you can have at most (message.length - 1) groups, and you must have at least three groups. Could you change this? Sure, but if you have more than (message.length - 1) groups, you'll wind up with the ciphertext in the same order as the plaintext (plus null characters in excess of message.length groups). You could have one or two groups, but one group will again produce identical ciphertext as plaintext, and two groups doesn't produce much of a ciphertext.

The displacement is also restricted to a maximum of ((2 * groups) - 3) places. Consider plaintext with five groups. This application restricts you to a maximum displacement of seven places. After ((2 * groups) - 3), the displacement sequence repeats itself. In this case, a displacement of 0 is the same as a displacement of 8. The same goes for 1 and 9, 2 and 10, 3 and 11, and so forth.

Should you violate the group or displacement restrictions, the applications sets a default(s). The group defaults to 3, the displacement to 0.

The Crack

You can attack this one in several different ways. The amount of possible groups is the difference of the maximum and minimum number of groups. You can generate a that many possible group translations. Then, since displacement also has a limited range (from 0 to ((2 * groups) - 3)), an offset can be applied to each of the possible group translations. In other words, if you have 7 possible groups and 14 (0 - 13) possible offsets, you can decipher the text with a maximum of 98 combinations.

Transposition ciphers such as the railfence cipher have another major weakness: they don't hide letter frequencies at all. What does that mean? Since this is a monoalphabetic cipher (each substituted letter always represents the same plaintext letter), you can check for the frequency each letter appears in the cipher. The most frequently appearing letters of the English language are E-T-A-O-I-N-S-H-R-D-L-U, respectively (See Frequencies of Letters in English Text for more info). You can start the cracking there.

There's always the brute force attack. Since the plaintext has only been rearranged (transposed) and not substituted, rearranging the ciphertext in every possible combination will eventually reveal the plaintext. Of course, the number of permutations rises exponentially. Long messages might make this approach impractical.