Developing algorithm for detecting plain text via frequency analysis

Question

I'm currently attempting the Matasano Crypto Challenges as a basic intro to cryptography. For solving some of the earlier challenges I utilised n-grams to determine which is going to be the most likely English plain text. It has been quite successful.

I'm up to attempting to break repeating XOR, which involves grouping bytes in their suspected single byte XOR group, and cracking them in this fashion. As this will be disjointed text, it appears I will need to use frequency analysis as opposed to n-grams.

I implemented a basic scoring system (similar to the below source code) source.

function getEntropy(str) {
    var sum = 0;
    var ignored = 0;
    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if      (c >= 65 && c <=  90) sum += Math.log(ENGLISH_FREQS[c - 65]);  // Uppercase
        else if (c >= 97 && c <= 122) sum += Math.log(ENGLISH_FREQS[c - 97]);  // Lowercase
        else ignored++;
    }
    return -sum / Math.log(2) / (str.length - ignored);
}

With short cipher texts though I've had the issue that garbled text with more printable ASCII has scored higher than correctly formed English. I.e. FKDASDOFD may score higher than THE RIVER, as it's got a space which isn't counted towards its score.

From this, I've been trying to come up with a way of perhaps scoring the letter count against it's expected frequency, while penalising the score for each letter the further it is away from it's expected value according to normal distribution.

For example, a very rough though process of algorithm I'm trying to implement.

1) "a" has a frequency of 8.167%. 
2) Evaluate the frequency in the candidate plain text and compare that      against the expected value (8.167%). 
3) Penalise the 'score' by multiplying it by [1-(std dev cumulative prob)]. For example if it was 1 std dev away from expected, multiply the score by [1-0.68], 3 std deviations, [1-0.997], etc.
4) Add the cumulative score for each letter to evaluate the most likely plain text. 

My questions are.

1. Is there a better, established, algorithm out there for performing frequency analysis?
2. Is it simply the nature of short cipher / plain texts that there will be inherent inaccuracy in evaluating the probability of English plain text?
3. Is my proposed method ridiculous / naive / stupid in some way?

Thanks folks, attempting to learn so sorry if there are trivial mistakes or invalid assumptions in this question.

Answer 1

As otus suggests in the comments, it's better to first calculate the frequency of each letter in the decrypted message, and then compare the frequency distribution to what would be expected for English text.

For the comparison, you can use chi-squared ($\chi^2$) testing. (Actually, for just comparing the likelihoods of different decryptions, you don't even need the complete test.) To do this, start by comparing the actual observed number of occurrences $N_{\rm obs}(c)$ of each character $c$ in the decrypted message with the expected number of occurrences $N_{\rm exp}(c)$ of that character in a piece of English text of the same length (i.e. its expected frequency times the length of the message), and calculate the test statistic $$\chi^2 = \sum_c \frac{\left( N_{\rm obs}(c) - N_{\rm exp}(c) \right)^2}{N_{\rm exp}(c)},$$ i.e. the sum of the squared differences between the observed and the expected frequency, divided by the expected frequency. The smaller this $\chi^2$ is, the more closely the decrypted message resembles English.*

Here's some basic JS code to calculate $\chi^2$ for English ASCII text:

// http://en.algoritmy.net/article/40379/Letter-frequency-English
var english_freq = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,  // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,  // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,  // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074                     // V-Z
];

function getChi2 (str) {
    var count = [], ignored = 0;
    for (var i = 0; i < 26; i++) count[i] = 0;

    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if (c >= 65 && c <= 90) count[c - 65]++;        // uppercase A-Z
        else if (c >= 97 && c <= 122) count[c - 97]++;  // lowercase a-z
        else if (c >= 32 && c <= 126) ignored++;        // numbers and punct.
        else if (c == 9 || c == 10 || c == 13) ignored++;  // TAB, CR, LF
        else return Infinity;  // not printable ASCII = impossible(?)
    }

    var chi2 = 0, len = str.length - ignored;
    for (var i = 0; i < 26; i++) {
        var observed = count[i], expected = len * english_freq[i];
        var difference = observed - expected;
        chi2 += difference*difference / expected;
    }
    return chi2;
}

If you're only interested in finding the most likely decryption(s), that's all you need to do. Just sort the decryptions (and corresponding candidate keys) by $\chi^2$ in increasing order, and print out the first few entries.

If you also wish to estimate the actual likelihood of the message being English (or, rather, the likelihood that picking random letters with frequencies matching English text could yield such a message), you'll also need to determine the number of degrees of freedom $k$ for the model (which, for a simple model like this, is simply the size of the plaintext alphabet minus one**) and then integrate the chi-squared distribution for $k$ degrees of freedom up to $\chi^2$ (or just compare it to a precalculated table). But just for comparing the likelihood of different decryptions, the raw $\chi^2$ value is enough.

---

^{*) You have to calculate this sum over all the letters in the alphabet, including those that don't actually occur in the message, for which $N_{\rm obs}(c)$ simply equals $0$. Conversely, any characters that don't occur in your frequency table would, in principle, have $N_{\rm exp}(c) = 0$, and thus yield $\chi^2 = \infty$ if they occur in the message. In practice, to avoid such infinite results, you may wish to either ignore such characters or assign them some more or less arbitrary small frequency. One reasonable choice, if you're compiling your own frequency tables from a corpus of text, is to use additive smoothing by incrementing the observed count of each character in the corpus by one.}

^{**) The one degree of freedom is lost because the sum of the character counts must obviously equal the length of the message, which is fixed a priori. Thus, we're not completely free to choose how many times each character occurs in the message; having chosen all but one of the counts, the last count is unique determined by the others.}

Answer 2

My humble contribution to this thread: in order to give some plaintext an "English-score", I found out that the Bhattacharyya coefficient is quite usefull:

The Bhattacharyya coefficient is an approximate measurement of the amount of overlap between two statistical samples. The coefficient can be used to determine the relative closeness of the two samples being considered.

(from Wikipedia)

Therefore, if you have the English language frequency, you can calculate the letters frequency of your nominated plaintext, and then calculate the BC. When comparing plaintexts decrypted using different keys, this method can be helpful the one that is most likely makes sense.

A nice example (not by me) can be found here - look for the englishness function...

Answer 3

The accepted answer is correct, but I wanted to add an update since the sample set of frequencies given in the accepted answer doesn't always work so well for the Matasano Crypto Challenges. In particular, it is nice to have the frequency of the space character (0x20). For example, the following array has the experimental frequencies for all 26 letters followed by the "space" character (0x20):

static double[] expFreqsIncludingSpace = { 
0.0651738, 0.0124248, 0.0217339, 0.0349835,  //'A', 'B', 'C', 'D',...
0.1041442, 0.0197881, 0.0158610, 0.0492888, 
0.0558094, 0.0009033, 0.0050529, 0.0331490,
0.0202124, 0.0564513, 0.0596302, 0.0137645, 
0.0008606, 0.0497563, 0.0515760, 0.0729357, 
0.0225134, 0.0082903, 0.0171272, 0.0013692, 
0.0145984, 0.0007836, 0.1918182} ; //'Y', 'Z', ' '

And here's some sample Java code that uses the Frequency array to score any given String.

public static Double scoreString(String inString){
    String upString = inString.toUpperCase();
    int CHARS_CONSIDERED=27; //all uppercase letters and space
    int[] charCounts = new int[CHARS_CONSIDERED];
    double[] charFreqs = new double[CHARS_CONSIDERED];      
    int totCount = 0;

    for(char c : upString.toCharArray()){
        int index = (int)(c-'A');
        if(index>=0 && index<26){
            charCounts[index]++;
            totCount++;
        }
        if(c==' '){ //considering "space" the 27th letter of the alphabet
            charCounts[26]++;
            totCount++;
        }
    }
    if(totCount==0)totCount=1; //avoid divide by zero

    double chiSquaredScore=0.0;
    for(int i=0;i<CHARS_CONSIDERED;i++){
        charFreqs[i]=((double)charCounts[i])/((double)totCount);            
        chiSquaredScore+=(charFreqs[i]-expFreqsIncludingSpace[i])*(charFreqs[i]-expFreqsIncludingSpace[i])/(expFreqsIncludingSpace[i]);
    }
    return chiSquaredScore;     
}

Answer 4

Language models

The statistically correct approach for this is called https://en.wikipedia.org/wiki/Language_model and is used in various context in computational linguistics. It amounts to evaluating how probable is the particular message given an assumption about the "language" (technically, "xml messages packed according to iso-yyyy standard" also counts as "language" in this context") it's written in.

When looking at only single letter/byte frequencies the chi-squared test mentioned would work better, however, if your process results in a lot of plaintext candidates that need to be scored, then the field of language modeling can do much better when looking at a wider context, even simple 3-gram or 5-gram models can give you much more information and can be easily calculated if you have some sample data of what you expect to see in plaintexts.

Answer 5

you could also use some grammar to eliminate false positives, for example, in portuguese, before the letter "p" or "b" there should be a "m" and after the letter "q" there is always a "u", after the letter "l" it will be a vogal or the letter "h".

There are patterns like these in english, i just can't seem to remember now xD