Russell Atkinson's Blog, page 83

Computer Cipher Solving – Lesson 9: Determining the type

What kind of cipher is this? How do I find out? I’ve avoided this topic up to now because it is both the most sought after question and the most difficult one to tackle. Determining what kind of cipher you are dealing with is certainly the necessary starting point and often the most frustrating. I wrote a series of columns for The Cryptogram, the magazine published by the American Cryptogram Association (ACA), called Tackling the Unknown. I believe I stopped after 19 articles. If you are an ACA member you can access those. I am not going to republish or even summarize all of those here. They were specific to ACA cipher types and not necessarily all that useful in other contexts, anyway.

The fact is, there is no magic bullet for this. Depending on the source, there is an infinite number of possible cipher types (since some people make up their own system which has never been seen before or since). For most modern computer or communication applications, the ciphers used are unbreakable by us mere mortals so I am restricting this post to the types you are likely to find in various puzzle venues like the ACA or geocaching unknown types or that weird message you found in your great-grandfather’s letters.

Step one is to determine the general class as either code or cipher, and if it’s a cipher, whether it’s substitution or transposition. With a code plaintext words or phrases are substituted by another word, symbol, numbers, or a collection of characters, usually much shorter in length than the original. “Washington, D.C.” might be encoded TSOPN. I’m not going to deal with codes. Ciphers work on individual characters or small groups (e.g. pairs) of characters. They may be substituted by other characters, or just moved around (transposed) or both. That’s what I will deal with here.

A pure transposition cipher is one that rearranges the letters (or other characters such as spaces, numbers, or punctuation). There are many well-known types such as the Route, Railfence, Amsco, Columnar, Double Columnar, Knight’s Tour, Scytale, and Turning Grille, ciphers. Some are (or once were) useful in the real world, but most were not. As long as you know the language and the plaintext is normal, it is usually fairly easy to spot such ciphers because you can see lots of frequent letters like ETAOINS in English. However, I have devised a test for measuring how normal the letter frequencies are which I call the Normor test. If you have text you’d like to test, you can paste it into my cipher test page. Generally transposition types will score less than 100 on that test. There is a link to an article on that page explaining in more detail how to use the test and interpret the results.

If the test indicates it is a transposition type, how do you know which one? I don’t have the time or patience to go into detail, but there are several things to look at, such as the number of letters (a square of an even number, e.g. 64 or 100, might indicate a Grille, a prime number might eliminate a Route, etc.) Look at the history of the source for clues as to types used before, types probably known to the author, etc. If it’s a puzzle, clues as to type are probably there. The best way to diagnose which transposition type it is in my experience is to run it through autosolvers of the various types to see if plaintext emerges. Most transposition types yield rather easily to brute force autosolvers.

For simple substitution types like cryptograms or patristocrats (cryptograms without spaces or punctuation), the Index of Coincidence (IC) will usually identify it as such because the IC will be the same as the original text. My test page also measures the IC. For other types, including ones that mix substitution and transposition, there are various tests, some specific to a particular type. I am not going to go through them all here, but there are resources available. A good website for diagnosing the type is BION’s gadget page. See his various ID tests.

Beyond that, it boils down to using your brain and reading up on the different kinds of ciphers. Some so-called ciphers are actually hoaxes. Others may be too short or too convoluted and unique so as never to be solvable. All you can really do is to keep trying different things and hope you can at least identify the type so you can start solving.

The post Computer Cipher Solving – Lesson 9: Determining the type appeared first on OnWords.

Vengeance in Death by J.D. Robb

This is not a review, just a warning. I pulled this audiobook off the shelf at the library thinking it was a mystery. It’s not. J.D. Robb is the pen name of Nora Roberts, a romance writer. I didn’t make it through the first disk. The excessive and graphic gore was more of a problem than the excessive and graphic sex, but maybe fans of the romance genre go for both. I don’t.

The post Vengeance in Death by J.D. Robb appeared first on OnWords.

The Butcher’s Boy by Thomas Perry

The Butcher’s Boy by Thomas Perry

My rating: 1 of 5 stars

A beautiful DOJ analyst who studies cases looking for professional hit men and a handsome young FBI bomb expert are sent from Washington to investigate a homicide by explosion in Ventura, California, then are sent on to Denver where a U.S. Senator died by curare-poisoned false teeth. Yes, really. If you enjoy books of that sort, you’ll probably enjoy this one, too. I don’t want to be your buzzkill, so if you liked it, that’s fine, just stop reading now.

I found the book so absolutely ludicrous and had to stop at page 80 because I couldn’t take it any more. My regular followers know that I’m a retired FBI agent and mystery book writer (7 novels now) and something of a stickler for verisimilitude. Virtually nothing in this book was even remotely plausible, which is what spoiled it for me. I know it’s fiction, but still. I’ll take this opportunity to educate you on a few real-life facts, as opposed to alternative facts. Do NOT be misled by Michael Connelly’s introduction. He should be ashamed of himself for having written it. He knows real police work as his Harry Bosch novels show.

1. DOJ doesn’t have analysts who look at individual crimes, much less ones who look for killers for hire.

2. Professional killers like the one in the book don’t exist. Sure, mafia and street gangs have killers, but they’re just regular thugs and gang-bangers, low-IQ, not well-paid, and not for hire. The pro for hire like the ones supposedly found in Soldier of Fortune magazine are all undercover cops doing sting operations, or informants hoping to catch someone trying to hire them for a hit job so they can get paid by the cops when they turn in the person trying to hire them.

3. Neither DOJ nor the FBI would send someone from WDC to Ventura to investigate what was believed to be an accident, and certainly not an agent with only four years of experience. The FBI Los Angeles office has a whole team of bomb experts led by people with 15 or 20 years of experience. The FBI probably would investigate a case of this sort as a domestic terrorist matter, but not send someone from back east.

4. Fertilizer bombs do not go off just by having a blasting cap embedded in the fertilizer. You need fuel oil or something similar to make them explosive, like Timothy McVeigh’s Oklahoma City bomb. This “expert” seems to know nothing about explosives.

5. At one point Elizabeth asks the Ventura police chief for a car and driver to take her around because she doesn’t want to interrupt her FBI partner who has their car keys. This almost had me rolling on the floor laughing. If a police chief were even to spare the time to listen to her request, he would respond by saying “You want me to take an officer off patrol to chauffeur you around town when you have your own car?! Get out of here you *%^&$%#!”

6. The various methods of killing by the eponymous hit man are equally ridiculous. They make no sense whatsoever, but I won’t go into all the reasons why as this review would turn into a novel-length diatribe.

The writing is trite and hackneyed. I found later that even my wife had tried it and given up on it early. She had a one-word description: terrible. The author did absolutely no research on anything. How in the world this guy got this first novel published by a major publisher is beyond my comprehension, but somehow he became a big name in the genre. It just goes to show that talent has little to do with it.

View all my reviews

The post The Butcher’s Boy by Thomas Perry appeared first on OnWords.

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


Baconian (N different characters in ct)
2N
Yes


Bazeries
1,000,000
Yes


Columnar (Period N)
N!
N


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


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


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

The post Computer cipher solving – Lesson 8: Brute Force appeared first on OnWords.

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.

 

The post Computer Cipher Solving – Lesson 7: cross-reduction appeared first on OnWords.

Garmin 750T Giveaway on Podcacher

My Garmin 60Cx is having problems ever since the battery leaked inside. So I’m entering Podcacher’s Garmin giveaway contest and you should, too.

The post Garmin 750T Giveaway on Podcacher appeared first on OnWords.

The Netherlands Welcomes Trump

The post The Netherlands Welcomes Trump appeared first on OnWords.

Venomous by Christie Wilcox

Venomous: 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

The post Venomous by Christie Wilcox appeared first on OnWords.

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 post Hide and Seek by Gary Slinkard appeared first on OnWords.

The Innovators by Walter Isaacson

The 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

The post The Innovators by Walter Isaacson appeared first on OnWords.