Computer cipher solving – Lesson 8: Brute Force

Brute force as a concept is as simple as it gets. Write a program that decrypts a cipher type given the ciphertext and key, then decrypt it using every possible key. The key is usually a word or a sequence of letters or numbers, or in the case of transposition types, a route or pattern. Try every every possible key and save the ones that produce the best plaintext. You need a method of identifying the correct solution, but that’s covered in earlier lessons.

Some purist hobbyists disdain brute force as a solution method, at least for recreational purposes. It’s true that once you have the program written, using it becomes a cut-and-paste exercise and deprives you of the task/fun of solving the cipher. However, some of the ciphers solved this way are tedious and not very fun to solve anyway, and the fun comes from writing the program and watching it work. In addition, there always seem to be some small variations that require modifying or debugging your program. You don’t realize how many assumptions you’ve made when you wrote your program until you run the program and it fails. Maybe your word list doesn’t include the keyword, or that word may be a phrase. Maybe the period length doesn’t fall within your program’s range. Maybe you haven’t allocated enough stack size for a cipher of that length. You get the idea.

What may be useful for me to do here is provide you a method of determining whether a brute force attack is practical for a given cipher type. What it normally boils down to is the size of the keyspace. Simple substitution ciphers like Aristocrats, Patristocrats, and Xenocrypts (using the terminology of the American Cryptogram Association or ACA), are simple to solve with other methods but are not susceptible to brute force, at least not on my computer. Let’s forget the NSA. That’s because brute force would require approximately 26! trials, which is about 4×1026. That number would be less if the number of different letters is less than 26 or if ACA rules are followed and no letter stands for itself, but it’s unimaginably large. At the other extreme, the ACA’s Pollux uses only about 19,000 possible different keys, which a desktop PC can handle in less than a second. Of course, what’s practical depends on how long you’re willing to wait for an answer. If you can let your computer run for hours or even days on a problem, then more types become practical, but my chart below assumes the answer is needed within an hour or two. Of course the time to try each key varies by ciphertype and how efficient your decryption engine is, the length of the ciphertext, etc., but I’ve provided a chart showing the approximate keyspace size and whether it’s practical on a standard PC using a compiled language like C++ or in my case, Delphi. Bear in mind that brute force may not be the best approach for all these types, nor does the fact a type doesn’t appear mean it isn’t solvable by a computer method or even by brute force. Keyspace numbers should be considered approximate for several reasons, e.g. some different keys may produce the same result, some might produce plaintext for the ciphertext, etc. I can say that I have brute force programs that will solve all these types. For some, whether brute force is practical depends on the period or other factor N, as indicated in the chart.

Ciphertype (ACA rules) Keyspace Practical
Amsco (period N) N!x2 N<13
Baconian (N different characters in ct) 2N Yes
Bazeries 1,000,000 Yes
Columnar (Period N) N! N<13
Grille (N rows/columns) 4(n^2)/4 Yes
Homophonic 390,625 Yes
Morbit 3,628,800 Yes
Nihilist Transposition (N rows/columns) N! N<13
Pollux ~19000 Yes
Polybius (Playfair, Bifid, etc. 1-word key) ~4,000,000 Yes
Ragbaby (1-word key) ~80000 Yes
Railfence/Redefence (N rows) N*N! N<12
Route (48 routes, N diff. rectangles) N*2304 Yes
Sequence Transposition (primer given) 3,628,800 Yes
Swagman (N-digit key) (N*(N-1))! N<8

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.