Developing algorithm for detecting plain text via frequency analysis 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 &lt; str.length; i++) {
        var c = str.charCodeAt(i);
        if      (c &gt;= 65 &amp;&amp; c &lt;=  90) sum += Math.log(ENGLISH_FREQS[c - 65]);  // Uppercase
        else if (c &gt;= 97 &amp;&amp; c &lt;= 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. 


Is there a better, established, algorithm out there for performing frequency analysis?
Is it simply the nature of short cipher / plain texts that there will be inherent inaccuracy in evaluating the probability of English plain text?
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.
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 &lt; 26; i++) count[i] = 0;

    for (var i = 0; i &lt; str.length; i++) {
        var c = str.charCodeAt(i);
        if (c &gt;= 65 &amp;&amp; c &lt;= 90) count[c - 65]++;        // uppercase A-Z
        else if (c &gt;= 97 &amp;&amp; c &lt;= 122) count[c - 97]++;  // lowercase a-z
        else if (c &gt;= 32 &amp;&amp; c &lt;= 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 &lt; 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.