Monthly Archives: January 2017

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

Computer Cipher Solving – Lesson 7: cross-reduction

Last September I wrote a series of blog posts on computer cipher solving. They continue to get quite a few views, so it seems to be a popular topic. Today I’m resuming the topic by discussing cross-reduction of word patterns. This method has been used for centuries with simple substitution ciphers and it is still useful today for several types of ACA ciphers. Clearly it can be done without computers, but it is simple to program and a great time-saver. Often it’s the only way to break some tough ciphers. Don’t confuse this usage with cross-reduction in mathematics, which is a method to reduce fractions. The idea is to use the patterns of one word to reduce the possible solutions of a second word and vice versa.

The basic concept is simple. Take two ciphertext words enciphered with the same key, preferably long words, and compare the patterns to produce combinations of possible words that fit both patterns. It’s easier to understand by looking at an example. Headlines puzzles contain simple substitution ciphers, but they are often very short and have uncommon words such as proper nouns so usual methods like hill-climbing may not work. Consider this ciphertext from a recent ACA Headlines puzzle: EA’I NG THJLUZI IGIAHN AWBA’I MBCG. My hillclimber had no luck with it, but cross-reduction solved it easily.

Begin by reading through a word list and identifying all words with same pattern as THJLUZI, which is to say, all 7-letter words with no repeated letters. That sounds like a large list, but you can reduce its size by considering that Headlines puzzles use K3 alphabets to encipher. No, that’s not Kindergarten – 3rd grade. That K3 as used here: http://www.cryptogram.org/resources/cipher-guidelines/. Click on Keywords to get an explanation. The significance is that if a letter stands for itself in a K3 substitution, then all the letters must stand for themselves. In effect, the entire plaintext would be showing. Since it isn’t, that means none of the letters of the words stands for itself. That means you can eliminate all words beginning with T, having H as the second letter, etc. Next do the same thing with the word IGIAHN. Here, the 1st and 3rd letters are the same, so your list will probably be somewhat shorter. These lists may be saved in arrays or in files. Finally, you compare the two lists word by word to produce pairs of words such that there are no conflicts. That means the 2nd letter of word 1 must be the same as the 5th letter of word 2, the last letter of word 1 must be the same as the 1st letter of word 2, and so on.

The easiest way to do this with programming is to write a pattern function, one that produces ABACDEF for IGIAHN, etc. When you test every word pair (word1 and word2) from your lists all you have to do is ask if the pattern(word1+word2) = pattern(THJLUZI +IGIAHN). If it does, then display it or save that pair as a possible solution. My program produced about 200 pairs that fit the pattern. That didn’t appear to help much at first, especially since several combos seemed like plausible phrases from a newspaper headline (e.g. AEROBIC CYCLES). But notice that two words in the ciphertext end with an apostrophe I. That strongly suggests that I stands for plaintext S. Looking through my lists, there was only one word there that looked possible for the 2nd word: SYSTEM. The combos included DEVIOUS SYSTEM and LEPROUS SYSTEM, but it wasn’t hard to spot NERVOUS SYSTEM as the most likely candidate, and that proved to be correct. The solution is “IT’S MY NERVOUS SYSTEM THAT’S LAZY”. This method works best when you can find two words that have many common letters; if they’re adjacent, too, that’s even better, but not necessary. Needless to say, it only works if both words are in your word lists. When I get no solutions this way, I sometimes drop the final letter of one of the words in case it’s an inflected form (e.g. plural or past tense) and try again hoping the base word will be in the list.

This method will work with Key Phrase ciphers, too, even though that doesn’t use simple substitution. You just have to write a different comparison routine. Of course it works with Xenocrypts as long as you have good word lists for the language.

 

Venomous by Christie Wilcox

Venomous: How Earth's Deadliest Creatures Mastered BiochemistryVenomous: How Earth’s Deadliest Creatures Mastered Biochemistry by Christie Wilcox
My rating: 5 of 5 stars

I don’t read a lot of non-fiction, but I do enjoy a good science book. Wilcox has managed to turn a serious subject into a fun read and still impart the science subject matter in considerable detail. I enjoy learning something new, and almost every page held a fascinating nugget. I had no idea platypi, worms, and shrews were venomous. I didn’t know the difference between venom and poison. I didn’t realize how many different types of chemical attack were contained in the various venoms. All this and much more awaits you in this well-written exploration of our deadliest animal neighbors’ biochemistry.

The book is full of anecdotes, many lived by the author herself, depicting the bad luck, bravery, or idiocy (depending on your point of view) of those who have been bitten or stung, voluntarily or otherwise, by some of these creatures. She also recounts the efforts by clinicians and researchers to find ways of protecting humans from the effects of venom, and, perhaps more importantly, how to use venom to treat various diseases that afflict us. She does this with a scientist’s attention to detail and source citations. She provides an enormous lexicon of scientific terms. As a writer of murder mysteries, this book has filled my head with ideas (ah yes, “The Adventure of the Speckled Band” – it’s been done).

View all my reviews

Hide and Seek by Gary Slinkard

This delightful paean to geocaching will warm the heart of any geocacher. Gary’s boyish ebullience and complete devotion to geocaching are evident throughout the book. There is probably not much new for the seasoned geocacher, but the book covers a wide variety of geocaching-related topics, such as various resources on the web and elsewhere, how to negotiate with a non-geocaching spouse, what hazards to watch for while geocaching, and so forth. I’ve been geocaching since 2002 and I’d never heard of WVTim and his gadget caches until I read this book, so I think you’ll find plenty of nuggets to hold your interest even if you’re an old-timer.

For newbies and those who have never geocached but are curious about it, this is an excellent place to learn about geocaching or to broaden your knowledge and gain more enjoyment from the sport. Geocaching is much more than “using billion dollar satellites to find Tupperware in the woods” as the familiar slam goes. This book will show you why.

The author is not a seasoned writer, as he admits early in the book, and it shows. If you’re the type who cannot abide a split infinitive you’ll have trouble with this book, but I can only say that I just wish the average geocache page was as well-written. There’s an extensive glossary of geocaching terms at the end. The book can thus be a good reference resource for geocachers. Such terms are usually explained in the text as well, but at times they may be used before the explanation occurs, so if you come across such terms just jump to the back. The definitions are generally full explanations. There are also dozens of web links in the end notes so you can explore particular topics more fully. I like the inclusion of many photographs in the book, as well.

By way of full disclosure, the author mentions my own Cliff Knowles Mysteries in this book, a fact I didn’t know when I bought the book.

The Innovators by Walter Isaacson

The Innovators: How a Group of  Hackers, Geniuses and Geeks Created the Digital RevolutionThe Innovators: How a Group of Hackers, Geniuses and Geeks Created the Digital Revolution by Walter Isaacson
My rating: 4-1/2 of 5 stars

Isaacson has accomplished an impressive feat in summarizing 70 years of progress in the field of computing and the Internet. The 500+ pages may not seem like a summary, but he rarely spends more time than necessary on a topic. His central thesis is that innovators are most successful when collaborating with others. The brilliant idea man needs the practical manager to convert that idea into a useful product. He seems to agree with those who say that for most of even all of the great 20th and 21st century digital innovations, there were no inventors in the conventional sense, only people who contributed to bringing about such a thing. Every great innovation was incremental in nature and even the increments were collaborative processes.

Whether you agree with this thesis, you can enjoy his clear and concise well-researched account of each of the steps that led to the digital age we have. I was astounded at how many separate “inventions” have occurred in this time span, nearly all of which I have lived through. A look at the chapter titles will make clear what an incredible journey it has been: The computer, Programming, the Transistor, Microchips, Video games, the Internet, the Personal Computer, software, Online, The Web. Within each of these broad chapters there are a dozen or more key individuals who helped to bring about the concept and the reality listed in the chapter heading. The only major innovation he has omitted in my opinion is the cell phone/smart phone. I think this book must have gone to press just before the popularity of smart phones exploded.

I had expected this to be rather dry and boring, but it turned out to be anything but. This may perhaps be in part due to the fact I grew up in Silicon Valley. I was working in an IBM warehouse in one of my summer jobs in high school. I learned to operate mainframe computers for a work-study job in college. My first job out of college was operating such machines for a semiconductor company in Silicon Valley (then still known as the Valley of Heart’s Delight). In the 80s I bought an Apple ][e and taught myself Applesoft BASIC. When I switched to a PC I learned DOS and QBASIC, then Pascal and Delphi. I was on the high-tech squad in the FBI office in San Jose dealing with dozens of the high-tech firms mentioned in the book. I was offered – and took – the position of west coast security manager for AOL when that company bought Netscape. I was recruited away from there during the Dot Com Boom by another Internet company then laid off during the Bust. I’ve seen it all unfold before my eyes, but until now I never really had an understanding of who was causing this avalanche of change or why. This book has brought it all into focus and into perspective. If nothing else, it is a heart-warming nostalgia trip.

I listened to this book on CDs. The reader is excellent. I never got tired of his voice nor did he have the slick or smarmy sound of Scott Brick or other well-known readers.

View all my reviews

Our Ignorant Newsies – Len Ramirez edition

Last night Len Ramirez of KPIX news reported on a neighborhood that became completely surrounded by water from the recent flooding, in essence temporarily becoming an island. He described it as “landlocked.” Sorry, Len, that’s the exact opposite of what you meant. Landlocked means completely surrounded by land with no access to navigable water, like, say, Nevada or Mongolia. What you meant was enisled.

Before the Fall by Noah Hawley

Before the FallBefore the Fall by Noah Hawley
My rating: 4½ of 5 stars

A private jet goes down in the water somewhere between Martha’s Vineyard and Teterboro Airport. Scott, a painter and recovering alcoholic, is a last-minute addition to the passenger list, invited by Maggie, the wife of the wealthy news network owner whose company leased the jet. In addition to that executive’s family, other souls on board include their two small children, a money manager under investigation for laundering money for North Korea and others, a former Israeli war hero turned security expert, a pilot, co-pilot, and a beautiful flight attendant. Scott and the 4-year-old son survive in the water. Scott, who was also a standout swimmer in high school, must try to save himself and the boy despite a dislocated shoulder. He begins to swim, towing the boy.

The beginning of this book is riveting. Scott survives, that much we can predict from the opening, but who else does? Why did the plane go down? Weather was fine other than a low fog. The pilots were experienced and the plane had a good safety and maintenance record. We meet Gus, an investigator from the NTSB, and O’Brien, a jerkwad FBI agent. More bodies are found. Relatives come out of the woodwork. The post-truth news hounds descend.

This thriller borders on being great. The middle begins to drag a bit as the life stories of all the characters are brought out in a touch too much detail. The characters begin to take on cliched depictions. The NTSB guy is sympathetic and professional. The FBI guy is arrogant and suspicious. Cunningham, the cable news anchor, a sort of mix of Larry King, Rush Limbaugh, and Bill O’Reilly, is a lie-mongering viper. As we get closer to learning what actually happened, the pace quickens and suspense builds again. The ending does not come as a surpise since there are plenty of clues leading to it along the way, but it satisfies the hungry reader. Although the book is not perfect, it’s a solid four and half stars. I recommend it for those who enjoy thrillers.

View all my reviews

A Will to Die Cliff Knowles Mystery #7

The seventh book in the Cliff Knowles Mysteries series is now for sale on Amazon as both Kindle and paperback. You can also order the paperback at my Cliff Knowles Mysteries site.

San Diego is renowned for its sunny weather and beautiful beaches, but it has its dark side. It is the location of one of the largest mass suicides in American history. Thirty-eight members of the Heaven’s Gate cult left their bodily “vehicles” hoping for their souls to be taken aboard an alien space ship traveling behind the Hale-Bopp comet. Now, decades later, it looks like an offshoot cult is following the same pattern. One of the victims is the sister of private eye Cliff Knowles, a sister he hasn’t seen in years. He has trouble accepting the conclusion of the police that it’s a suicide. His investigation turns into a bittersweet family reunion when he comes to know his disabled niece whom he last saw when she was an infant. He’s determined to see justice done for her sake.