Starting with a couple text format books from the Gutenburg project, the files were stripped of the legal boilerplate and combined. Then a parser read the file and produced 2991 number matched files of plaintext, random key and ciphertext. Another program ran the hill climber on each file and a third generated a report on how well the hill climber performed with each ciphertext when compared with the original plaintext. I dropped this data into a spreadsheet and extracted some more data.
The average accuracy was 98.6%
greater than 70% solutions 99.93% (only 2 less than 70%)
greater than 95% solutions 93.41% (about 4-6 letters wrong)
greater than 98% solutions 76.43% (only 1 or 2 letters wrong usually JQXZ)
100% exact solutions 55.13%
Further, several scoring file systems were created and the test run again on a smaller sample. In general, the numbers had a variance of +/- about 3 or 4% and scored slightly lower which was attributed to that part of the sample being slightly more difficult or less like normal English. Otherwise, changing to log base 2 log base 1.1, log base 2 squared and even floating point log base 2 had little effect on the accuracy of the hill climber.
Limited trials with reduced randomness produced a slight speed improvement but no significant change in accuracy.
The takeaway here is that a lot of advice and general practice with cryptographic hill climbers is mostly meaningless.
I’ve been writing up some details on my hill climbing experiments that I hope will eventually get published. There are some things I have been finding that may change how crypto hill climbers and similar searches actually work. I still have a lot to do on this, but here are some general observations that tend to go against several things I’ve read.
Randomness: It isn’t what you might think. Virtually every implementation of a hill climber that uses a single key alphabet uses the RND(), rand() or other function built into the whatever programming language might be used. This is used twice to swap two “random” letters. You don’t really need that much randomness and you can get a small speed improvement by using something simpler. One such source is little more than a two instances of a scrambled alphabet. There is also a small speed up just using a less computationally intense random number generator that may be less than perfect.
N-grams: I don’t think anyone expects anything from a basic frequency count so 1-grams are generally unreliable virtually by default. However, there is the potential use as a not so random starting point. Using 2-grams through 5-grams all have potential except, 5-grams may actually be excessively restrictive. As an example, 5-gram scoring is actually worse that 4-gram scoring on the Dorabella Cipher because it never finds a complete decrypt and the partial decrypts are much more limited. My advice here is try, but bigger may not be better for some ciphers with 3-gram and 4-gram scoring being the general purpose sweet spot. If you have a tough cipher try all of them because they each bring something different to the search.
Scoring: Pre-computing is the way to go and eliminate some of the crazy math. Back in the 1990′s I was using partial statistics to detect English. I literally only did about a third of the actual math inside the loop. The reward was eventually an execution time cut in half. I was able to do this because I had a controlled sample. My scoring system is based on ln()^2 or in English, base e logarithm squared. I’m thinking of pushing 5-grams to ln()^3 because I can. Some of these ideas may push the hill climber in a more portable direction where a DLL can hold the scoring arrays for any language or math curve anyone wants to build.
Sorting: If anyone has looked at the posted code for the early versions of my hill climber, they may have noticed a few of the basic sorting algorithms used to step through the letter swaps in an attempt to try a more systematic search rather than totally random. Surprise! It partially works. Pure sort or other sequential stepping patterns cause the hill climber to fail. Add in just enough randomness and the slightly less chaotic patterns actually cut each hill climb in about half with some searches taking less than 676 loops to reach a peak. It is interesting that this even works since the general advice is for totally random.
Shotgun Randomness: I still question the statistical relevance of starting a hill climber with a random alphabet. The cipher alphabet is assumed to already be random relative to any alphabet you want to start with. How is a mixed alphabet any different? Worst case scenario, the second shotgun loop scrambles the current alphabet anyway. Wishful thinking that chaos + chaos = solution? I didn’t even notice a difference when my Fibonacci generator wasn’t getting initialized properly which is what got me really seriously thinking about how much randomness is really needed as noted above.
Corpus: Your corpus and it’s size matters. The one I’ve been using is not really clean. So it includes odds and ends that might get otherwise removed because they are foreign names or places. A recent extension of a few hundred megabytes of text changed how things act. Which implies that maybe clean and perfect isn’t the ideal. Finding the perfect hill climbing corpus to build your scoring files may fall into the category of lofty and near impossible goals.
Solve a 122 year old mystery? Priceless! Actually get credit for it? Near impossible.
I’ve spent way to much time just trying to find someone that would listen and pay attention long enough to see the facts. On the other hand, if it is seen by anyone that thinks they are going to solve the cipher themselves, they let their own theories override good sense. It is really funny how so many “experts” are totally incompetent and so full of themselves. I’m still trying to figure out how some of them rose to such a position.
In any case, here is a challenge. Solve the following text as a normal mono-alphabetic substitution cipher and then send me the results. The “key” is just a random string of letters to hide what it is. You only need basic frequency analysis and a few relatively common digrams. If you haven’t seen my Dorabella Cipher solution, You should get about a 50-70% decrypt before the plaintext turns totally weird. Some words are oddly abbreviated and some are sort of phonetically spelled. Knowing this much, any teenager or older should be able to partially solve it. Use lower case under the ciphertext using a mono-spaced font such as Courier New or Consolas so the letters stay aligned.
When you get totally frustrated with it, send me a copy of your best partial decrypt. I never totally decrypted the cipher using pencil and paper myself so I don’t expect a complete solution from anyone. I spent about 2 weeks on this before my hill climber solved it. I’m hoping to verify an idea I had about the cipher.
Here is a cipher challenge I dreamed up last night. There are no prizes to win except for that little buzz you get when you finally solve a hard problem. If you give me the correct answer, I’ll eventually at least post the winner here. Please don’t post any answers online anywhere so it isn’t spoiled for others.
First some clues. It is a mono-alphabetic cipher except the words are not English. The language used is not common so that will at least partially frustrate statistical attacks and most if not all computer attacks. The language has been heard on TV shows and other media so it isn’t completely unknown. Bonus points if you get the English translation correct.
Before anyone goes and decides it has problems, it is supposed to have some oddities. The whole thing is a test bed for some ideas I have to make it better. Some are working and some I’m still thinking about. For the most part it should fail gracefully with an error message if you mess up the command line. It has no sanity checks so if you tell it 100000000 it will try to do that for you and it will take a really long time. If I clean out the testing stuff, it is probably worthy being a release build. As it is, you might call it a beta release except that some things just aren’t done and some didn’t work as expected. I’ll update the builds it as it evolves. On the plus side, it is a bug fixed build of the program I used to break the Dorabella Cipher. The random number generator wasn’t getting initialized so the output is a little different.
I uploaded the hill climber to my github account. Just follow the link I keep around here.
There are 3 major files. There is a 32 and 64 bit Windows console build and there is the source code zipped. I haven’t had a chance to try it, but the makefile should build it under Linux. It works with Msys2-32/64 which is very similar to a Linux environment.
Feel free to go look at the wiki page and use your favorite search engine to find out what I’m talking about. For everyone else, The Dorabella Cipher is a mono-alphabetic cipher that uses 24 symbols instead of letters. Rather than post the answer 2 pager here, I provided a link to the PDF file. There is still time to try to solve it yourself. Just ignore the link and continue on your own.
(edit) I’m working on changing the word divisions. I found some things that make much more sense.
Also, I have a big program in the works for those interested in a shotgun hill climbing solver.
One of the things those involved in cryptanalysis do is count letters. Sometimes a lot of letters. But what do all those counts represent? Something the “experts” that write books often fail to do is explain exactly what their counts are and how they arrived at them. Then, even if they do tell you something, it may still mask how the original data was compiled such as “compiled from a 30,000 word corpus”. The various ways you can count letters can completely change the results.
Knowing how your statistics were generated and what is likely to happen with a given cipher could be the difference between an easy break or a difficult mess. Below is a small part of a few digram counts of a text sample. The ciphertext samples were encrypted with a digraphic cipher. The high count is for the plaintext or equivalent ciphertext pair TH. All counts ignored word divisions.
Plaintext strict count with offset (X added before the first letter)
S 6 10 1 1 1 5 2
T 71 21 1 2 3 2 3
Plaintext strict count no offset
S 9 8 0 0 3 1 1
T 88 11 1 0 1 0 3
Plaintext moving window
S 15 18 1 1 4 6 3
T 159 32 2 2 4 2 6
Ciphertext moving window
F 8 14 17 96 4 9 6
Ciphertext strict count no offset
F 3 13 0 88 1 0 0
There are significant differences in the counts of the exact same plaintext/ciphertext. Presumably there would be statistical differences, but they converge with a large enough text. If you add the offset and no offset counts together you get the moving window count. However, the encrypted text masks it's true frequencies using the moving window count while the strict count exactly matches the plaintext strict count.
The moving window counter uses a “window” that is N wide where N may be 2 or higher. This type of counter is bad for analysis because it only moves one character at a time. It averages or otherwise simulates the effects of a large data set and blurs the actual N-gram characteristics if they exist. The moving window counter also artificially inflates the counts by an approximate factor of two. As shown above, the moving window count won't match between plaintext and ciphertext.
The strict counter only counts N sized letter groups. Because it doesn't cross N-gram boundaries, this is the counter you want when looking for N-gram characteristics. You will get exact N-gram counts. If used on a large enough file, the strict count data will converge on the moving window data. As shown above, the strict count will match known plaintext and ciphertext exactly.
The next problem seems to be one of statistics. Using my 1Gb corpus, the moving window and strict counts result in 2.605012% and 2.604406% respectively for the letter pair TH. With a large enough corpus, the two count differences are virtually insignificant and should compare proportionally.
So what did all of this accomplish? I did the work so you don't have to. When counting a known N-gram based ciphertext, it is best if you use a strict count. For reference purposes, the moving window count of a large corpus is the same as a strict count that is diffused by the text itself. Both are accurate when normalized. However, if you are comparing known plaintext and ciphertext, your best match will be a strict count because it eliminates the diffusion that a sliding window would count.
This cipher is a variant of several Polybius square based ciphers. Unlike some of these ciphers it is also a fractionated cipher. In its basic form it is no stronger than a simple digraphic cipher and can be mapped to a digraphic table. For the most part, the design is similar to about one and a half rounds of a more advanced cipher. However, this cipher has one feature that could make it a very tough nut to crack for pencil and paper solvers. The most interesting detail is I can't find any information online or in any books that mention such a cipher.
The lesser form performs a substitution, a minor transposition and then a substitution. The cipher is partially self inverting except for the intermediate mixing. I haven't tried to find an inverting mixing system so that may still be possible. It is also possible that there is a best mixing system and a worst case mixing system. The mixing makes the letter pairs dependent on each other and this is what makes it a digraphic cipher. There is more work to be done on the mixing stage.
Larger forms of the cipher can increase the block size. Basic experiments have been performed on the the digraphic version though block sizes up to six are not unreasonable. The digraphic version may be extended to even block sizes and the trigraphic version may be extended to multiples of three and larger odd sizes. As the block sizes grow, the need for a more complex intermediate stage increases.
The encrypt operation of the digraphic cipher starts by creating a pair of Polybius squares. For demonstration purposes, you may want to use a straight alphabet. Otherwise any alphabet mixing system may be used. Label one square left and the other right. Next divide the plaintext into letter pairs. These will also be referenced left and right. Encrypt each letter of the pairs with the respective squares and you will have a group of four digits for each letter pair. This is the mixing step for each group. Take the first digit and the last digit as a number pair and decrypt using the left square. Take the second and third digits as a number pair and decrypt using the right square. The result will be a new letter pair. Finish the rest of the message and copy the pairs into five letter groups for the final ciphertext.
The decrypt operation is the same as the encrypt operation except you have to unwind the digit swaps in the intermediate step. Both digit swaps are shown below.
Encrypt: 1234 = 1,4 left and 2,3 right.
The new digit pattern is then: 1423
Decrypt: 1234 = 1,3 left and 4,2 right
The greater form of this cipher would add a transposition stage on all the digits in the intermediate step like ADFGVX/ADFGX or even a double transposition. This would completely hide any true patterns and make the cipher much more difficult to break. The down side is you could no longer program it as a stream cipher though it could become a block cipher and it could still be used as a pencil and paper cipher. Care would be needed to hide any block signatures.
One question still remains. Why is a relatively simple cipher virtually unknown? The complexity of the cipher is no different than several of the fractionated and multiple operation ciphers. While you may get similar results with other digraphic ciphers, they can't be expanded to a larger letter block. This cipher also has the option to take full advantage of the fractionation by adding a layer of transposition for the full message text. By creating a block mode, it may be possible to use cipher block chaining (CBC) and other modes more typically used with modern binary ciphers.
The C source and a digraphic version is up on github.
I had this real nice post all ready for this and tumblr ate my charts. I knew tumblr hates anything so organized, but even my text based charts won’t work. So I have to do the planned post at a later time with tumblr proof charts and graphs. I was really hoping to avoid making JPG files out of them.
In any case, the frequency counter program counts only letters and the executable is compiled from the C version. It has been tested on a corpus I have that is over 1Gb in size. It isn’t exactly fast, but nothing that accesses 1Gb of data is usually very fast. On the other hand, it isn’t really horribly slow and it should only take a few minutes depending on your hardware. For small ciphertext samples and even up to 1Mb, it will be pretty fast even on older hardware..
Before you try to replicate my efforts on a 5Gb file or maybe a 10Gb file, I must warn you that you’ll need to make some changes and build your own. The posted source code expects 32 bit integers and the actual display text is formatted to 8 digits. A 5Gb file of American English text may actually be the limit though honestly I never expected to have a 1Gb corpus.
The source code and the executable are available from github.
Historically, most books explain that Caesar used a shift of 3. It is also likely that Caesar used only upper case letters in his messages though I've never seen any notes on actual messages. This is perhaps the weakest of the substitution ciphers because it only has 26 different keys.
The program is pretty straight forward and it retains both upper and lower case as well as punctuation. Unlike the core/Rot13 program, this one has a variable shift key and it allows encrypt and decrypt modes.
Below is a ciphertext example. You'll have to forgive my sense of humor.
Vjku ku c vguv qh vjg uwrgt ugetgv ekrjgt.
Vjku ku qpna c vguv. Kh vjku jcf dggp cp cevwcn
gxgpv, uqogqpg yqwnf dg ncwijkpi jauvgtkecnna
cv vjg rqqt ejqkeg qh gpetarvkqp.
There are a few modifications that are possible. Perhaps the most normal one would be conversion to upper case only. Following that would be to strip the punctuation and word divisions to create typical 5 letter groups. To be somewhat historic, the ciphertext should probably retain the word divisions at a minimum.
Note that if you use only upper case letters or only lower case letters, the program will retain that. If you omit punctuation or make 5 letter blocks then that will also be retained. Maybe the program doesn't do all the work, but it is plenty good enough to have some fun with.
Look for the letter frequency counter program to help crack this cipher. You could also try every letter of the alphabet and see which one worked.
I opened a github account to make some things a little easier. First, it is a means of archiving the code. Second, I can offer compiled executable files for those who can’t build their own. Last, I can offer copies of the build files rather than pieces. As it grows, I’ll have an index and put a link here somewhere.
To screw up really fast requires a computer. A slight delay while I get the new account unflagged. I can’t imagine a system that flags an account before anything is in it. Their support people are probably overworked.
Some new stuff coming. The Rot-13 cores for QB and C++ are done. I finished a frequency counter in C and the code for these are up on github. If I were to post a diff, there would only be about 10-15 new lines of code. So I think I got the core where I want it. I need to make several new posts here for the different files and some samples. The frequency counter is a needed tool so there can be a discussion on breaking simple substitution ciphers and extrapolating that to word based encryption like the code book.
Moving kind of killed this project for a long while. I still need to unpack some of my books so I can get some more ciphers done. On the other hand, there is still a lot of old code for the ciphers I really liked.
Something that needs to be done is to create a common file access program. In C/C++, this would be a main() function. In Quick Basic (QB) this would simply be the primary code area but I'm going to give QB command line functionality so it can act kind of like C programs. So QB will have a special main() after some code so that it behaves similar to the C main() function. To that end, here are the basics needed to "read" a text file and "write" a text file. This will form the core of virtually all the programs so that just a few functions or at most the equivalent of a C++ class is needed to do the work. A future post will add a QB equivalent and a pure C++ equivalent and it will look a lot like the C version. My main compilers for this are Dev-C++ with Mingw32/64 for C/C++, and QB64 though I can run a number of others including older 16/32 bit DOS and Windows stuff as well as Linux with Oracle Virtualbox.
Please note that I assume you have your computer properly configured with the needed compiler(s) and know the basics of using them. I'm dealing with personal BASIC and C/C++ code that can be up to 40 years old.
The code files are listed below. The cipher in the example is Rot13 or Rotation 13 which is a common usenet cipher used to hide punchlines or spoilers. It is a variant of the Caesar cipher which will be added later.
Below are the program files you need.
=====================================
/***********************************************************************
* main.c
* The core main program.
***********************************************************************/
/* Include any C libraries needed. */
#include <stdio.h>
/* Also include the local header. */
#include "work.h"
/* Allow the programs to function in a batch or script environment. */
int main(int argc, char *argv[]){
/* Declare the few variables needed. */
int errcode;
FILE *fi,*fo;
/* Error check argc and display usage instructions. */
if(argc<ARGLMTL||argc>ARGLMTU){
UsageWork();
/* Return with an error exit. */
return 1;
}
/* Open files as needed and trap errors. */
if((fi=fopen(argv[1],"rt"))==NULL){
printf("Can't open input file '%s'\n",argv[1]);
return 1;
}
if((fo=fopen(argv[2],"wt"))==NULL){
printf("Can't open output file '%s'\n",argv[2]);
fclose(fi);
return 1;
}
/* Initialize the work function. (c++ ctor) */
if((errcode=InitWork(fi,fo))!=0){
/* Init failed */
return errcode;
}
/* Call the work function. */
if((errcode=MainWork())!=0){
/* Main failed */
return errcode;
}
/* Clean up things after work is done. (c++ dtor) */
if((errcode=DoneWork())!=0){
/* Done failed */
return errcode;
}
/* Close files that were opened. */
fclose(fi);
fclose(fo);
/* Exit no error */
return 0;
}
/* End main.c */
/***********************************************************************
* work.c
* A placeholder for future projects (Rot13)
***********************************************************************/
#include <stdio.h>
#include "work.h"
/* Private function prototypes go here. */
/* Local global variables. */
FILE *fin,*fout;
int ErrorFlag;
int InitWork(FILE *fi, FILE *fo){
/* If this module is reused, make sure ErrorFlag is reset. */
ErrorFlag=0;
/* Store the file pointers for global use here. */
fin=fi;
fout=fo;
/* Nothing else needed here */
return ErrorFlag;
}
int MainWork(void){
int c;
/* A simple version of Rot13 */
while((c=fgetc(fin))!=EOF){
/* Perform rot13 on lower case only. */
if(c>='a'&&c<='z'){
c+=13;
if(c>'z')c-=26;
}
/* Perform rot13 on upper case only. */
if(c>='A'&&c<='Z'){
c+=13;
if(c>'Z')c-=26;
}
fputc(c,fout);
}
return ErrorFlag;
}
int DoneWork(void){
/* Nothing to do here. */
return ErrorFlag;
}
void UsageWork(void){
printf(" usage: work infile outfile\n");
}
/* End work.c */
/***********************************************************************
* work.h
* The header file for the work.c placeholder
***********************************************************************/
/* Some limits for the core main() program. */
#define ARGLMTL 3
#define ARGLMTU 3
/* All public functions go here. Private function prototypes are in work.c */
int InitWork(FILE *fi, FILE *fo);
int MainWork(void);
int DoneWork(void);
void UsageWork(void);
For entertainment purposes, I created a code book. All the randomness is contained in a small PRNG that was custom coded so you could actually see where the “random” code words came from. As it is all math, there is really nothing random. There is a “spinner” to try and prevent getting the same code book every time.
In the future, we will need a word frequency counter and an associated word frequency list to demonstrate breaking the code book. Until then, a toy to play with. The same program can create the English frequency and the code frequency.
This one isn’t written in C, I got carried away while writing the word file parser in QB and kept going. The sort is little more than a bubble sort. Otherwise, it could be made somewhat more compact if written in C and use the C library quicksort().
The zip file has the original word list in CSV format, the QB source code, a readme, and the code book in PDF format.
This is a favorite of mine. Nearly every programmer with any interest in crypto gets this idea and it’s usually some variant of the following. Below is a complete C program with a custom PRNG (pseudo-random number generator). It is more specifically a Linear Congruential Generator. The main purpose of the custom generator is it shows where those “random” numbers are coming from. It turns out they are not so random. You could be using a built in PRNG function such as BASIC’s RND() or C library rand() and while the specific generator used may not be the same, it can also be broken just as easily.
I use this type of PRNG because it’s easy to code and it’s pretty straight forward math with no major tricks. Some simple multiplication and addition with a special type of division. The most unfamiliar math used is a Modulus. In C it is the “%” symbol. The easiest way to define a modulus is the remainder of integer division. So if you have 7 mod(4) you have 1 remainder 3 and we throw out the 1 while keeping the 3. It makes circular alphabets or tables easy. Just the thing to make a virtual code wheel or slide. When used with an alphabet, the modulus will normally be 26.
About the program:
It was written using the Dev-C++ IDE and compiled using mingw which is a Windows port of GCC. If you use a different compiler, you may get various warnings and errors. The variables for the key and the PRNG may need to be changed to long int types for old (ancient?) 16 bit compilers. Most 32 and 64 bit compilers should be fine. This should compile and run under Linux as well. These are all simple command line or console programs using basic C library functions so that they should work for nearly anyone with a C/C++ compiler. The above system that I use is free as is GCC and Linux.
Most of the programs I post here will be some variant of the code below. To make a Caesar Cipher, you would change the key section and file read/write some then omit the entire PRNG function. A multi-purpose polyalphabetic program would be a further modification of the Caesar Cipher. Forgive the way I code some things. If I write something out, it’s still legal C and it is easier to understand. I also tend to use a compact style that can be harder to read but fits better in a post.
/******************************************************
* unbrkbl.c
* This is the cipher system that most programmers at
* least think about writing a program for.
*
* The Super Unbreakable Cipher Program
* (extreme sarcasm intended)
******************************************************/
#include <stdio.h>
#include <string.h>
int MyRnd(int seed);
int main(int argc, char *argv[]){
int dir=0,key=0;
int c,d,x,y;
FILE *fi,*fo;
/* Check for args */
if(argc!=5){
printf(" Usage: unbrkbl d key infile outfile\n");
printf(" d = Direction: e or d (encrypt or decrypt)\n");
printf(" Key = an integer from 1 to 714024\n");
printf(" infile = input path/filename\n");
printf("outfile = output path/filename\n");
return 1;
}
/* Set cipher mode. */
switch(argv[1][0]){
case 'e':
dir=1;
break;
case 'd':
dir=-1;
break;
default:
printf("ERROR: Illegal direction argument.\n");
return 1;
}
/* Set key */
x=strlen(argv[2]);
for(y=0;y<x;y++)key=key*10+argv[2][y]-48;
if(key<1||key>714024){
printf("ERROR: Illegal key value.\n");
return 1;
}
MyRand(key);
/* Open files */
if((fi=fopen(argv[3],"rt"))==NULL){
printf("ERROR: Can't open input file '%s'\n",argv[3]);
return 1;
}
if((fo=fopen(argv[4],"wt"))==NULL){
printf("ERROR: Can't open output file '%s'\n",argv[4]);
fclose(fi);
return 1;
}
/* Run the cipher */
while((c=getc(fi))!=EOF){
d=c;
c&=95;
if(c>='A'&&c<='Z'){
/* 39 is 65-26 to allow for subtraction in decrypt mode. */
d=(c-39+dir*MyRand())%26+65;
}
fputc(d,fo);
}
/* All done */
fclose(fi);
fclose(fo);
return 0;
}
int MyRand(int seed){
static unsigned int rnd, last;
if(seed>0)last=seed;
rnd=(1366*last+150889)%714025;
last=rnd;
rnd=last%26;
return rnd;
}
