2
$\begingroup$

I'm doing the Matasano crypto challenges. After implementing a naive character frequency scoring (that worked), i was looking for something mathematically more precise and found this thread: Developing algorithm for detecting plain text via frequency analysis

While the Chi Squared analysis does work for me, I encountered a problem. My current code just sets the score to infinity if I encounter a nonprintable character. I want to avoid doing that, since a possible plaintext could contain a few ascii non printable characters. (for example it is actually unicode and contains a greek word) But when I ignore every non printable character for scoring, as I already do with chars like ".,!\n\t", I run into the problem that strings with a few high scoring characters and lots of junk get scored better than actual english plaintext.

My current code is as follows: (frequency is a dict that associates ord(character) with its frequency for a-z and space)

import frequency
import copy
from math import inf
from string import printable

def score_string(inp):
exp_dist = copy.deepcopy(frequency.frequency)
length = len(inp)
for key in exp_dist:
    exp_dist[key] *= length
dist = dict.fromkeys(exp_dist.keys(), 0)
for char in inp.lower():
    if chr(char) not in printable:  # This is the part i like to avoid
        return inf
    if char in dist:
        dist[char] += 1
score = 0
for key in exp_dist:
    score += (dist[key]-exp_dist[key])**2/exp_dist[key]
return score

If I understand what is going on correctly, my issue is that for shorter strings (the example i worked with was 34 characters) the negative impact of even a single low scoring printable charater outweights the negative impact of a character that is ignored by the scoring by alot.

I'm looking for an elegant way of guaranteeing that nonprintables affect the score worse than any printable character but don't dismiss them completely.

$\endgroup$
7
  • $\begingroup$ Hi! 1) Your code is wrong. A single 'off' letter should not cause $\chi^2 = \infty $. Remember that it's a stochastic measure. 2) Greek is not English. 3) Non printable characters are not English. $\endgroup$
    – Paul Uszak
    Mar 3, 2019 at 13:25
  • 1
    $\begingroup$ im aware of these issues. but since i don't have frequency data for the remaining bytes i cant think of a better reasonable solution than assuming their frequency is 0 resulting in the fraction in chi square becoming infinite (or undefined with another interpretation of positive value/0) english text may very well contain nonenglish characters. your comment would be an example for that. $\endgroup$
    – nahema
    Mar 3, 2019 at 13:51
  • $\begingroup$ In entropy calculations for files like Shakespeare, we simply drop any characters we don't like. That eliminates f(char) = 0. We also convert all printable text to upper case. And $\chi$ isn't English, it's maths drawn in ink. As is $\int_0^\infty \mathrm{e}^{-x}\,\mathrm{d}x$. Remember that a single metric like chi is a very broad brush approach and therefore you have to compromise (a lot). Just some observations... $\endgroup$
    – Paul Uszak
    Mar 3, 2019 at 14:09
  • $\begingroup$ docs.scipy.org/doc/scipy/reference/generated/… $\endgroup$
    – Paul Uszak
    Mar 3, 2019 at 14:11
  • 1
    $\begingroup$ @PaulUszak $\chi$ is a greek letter (and therefore an example of a non-english character appearing in an english sentence). It is not an $x$. $\endgroup$
    – Ella Rose
    Mar 3, 2019 at 14:26

1 Answer 1

3
$\begingroup$

One approach you might try is applying additive smoothing via pseudocounts. At its most basic, this can be as simple as adding 1 to the number of times each byte (or $n$-tuple, or whatever) occurs in your corpus before calculating the frequencies. This allows you to calculate a non-zero (although possibly very small) likelihood for any decrypted byte string, even those containing bytes that never appear in your original corpus.

So, for example, if you started with a 1,000,000 byte corpus of English text, where the byte e occurs 124,319 times and the byte ` occurs 0 times, you'd increment those counts to 124,320 and 1 respectively, and the total number of bytes observed to 1,000,256, before dividing the counts by this total to obtain the smoothed frequency of each byte in the corpus (e.g. 1 / 1,000,256 ≈ 0.000000997 for the byte `).

The mathematical theory behing why this seemingly arbitrary adjustment makes sense is kind of tricky, but basically it turns out to be a sensible way to adjust the probabilities obtained from a series of observations to account for the possibility that some rare but possible outcomes might simply not have appeared by chance during the finite number of observations made.

(In particular, analyzed in the framework of Bayesian statistics, this smoothing rule turns out to yield the same expected posterior probabilities as we'd get by starting from a "flat prior", i.e. the assumption that any distribution of byte frequencies is equally likely, and repeatedly applying Bayes' theorem to update this belief as we observe new bytes in the corpus. Furthermore, if we did have reason to believe a priori that some bytes should be more likely than others even before looking at the corpus, we could include this prior information by assigning the more likely bytes pseudocounts higher than 1.)

Of course, if you're using a given table of byte / letter frequences instead of compiling your own, you'd have to guesstimate the amount of smoothing needed yourself. But you can still do it: just multiply each frequency by some assumed corpus size (e.g. 1,000), increment them by one and (if needed) rescale them back down so that they sum to one again.

$\endgroup$
6
  • $\begingroup$ 0.000000997 seems smallish. I think that @nahema is looking for a single $\chi^2$ value for each test. What would you estimate the %age difference in score to be between your additive smoothing method and simply dropping all non printables (and Greek and any $\chi$s)? $\endgroup$
    – Paul Uszak
    Mar 4, 2019 at 13:48
  • $\begingroup$ @PaulUszak: It is indeed small, but that's what you'd expect the estimated occurrence rate of something to be, if we don't observe a single instance of it among a million examined cases. (Whether a 1MB corpus of English text that doesn't include a single ` should be considered sufficiently diverse is another matter. If you used e.g. this site as your corpus source, you'd certainly find quite a few of them.) $\endgroup$ Mar 4, 2019 at 13:57
  • $\begingroup$ Anyway, as the OP notes, simply ignoring any plaintext bytes that we don't have non-zero frequency data for would give unrealistically low (=good) $\chi^2$ scores to plaintexts that mostly consist of such characters. For example, if we only had frequency data for letters, deciding to ignore all bytes that are not ASCII letters would cause the answer is 42 to score much higher (=worse) than, say, ^.E`##7a%{e>1'=/. With smoothed frequencies, the latter string would instead get assigned some very high (but still finite) score reflecting the large number of non-letter bytes in it. $\endgroup$ Mar 4, 2019 at 14:07
  • 1
    $\begingroup$ In any case, the general answer to "my frequency data is bad/incomplete" is to compile a better set of frequencies from a sufficiently large and diverse corpus, making sure not to discard any bytes as "irrelevant". Additive smoothing just helps to deal with any remaining biases caused by the finite size of the corpus. $\endgroup$ Mar 4, 2019 at 14:14
  • $\begingroup$ While this solution seems to be a pretty good way of adressing my issue i found that i still get undesirable result because the strings im dealing with are just to small. The following Note from docs.scipy.org/doc/scipy/reference/generated/… seems to be the underlying issue "This test is invalid when the observed or expected frequencies in each category are too small. A typical rule is that all of the observed and expected frequencies should be at least 5." $\endgroup$
    – nahema
    Mar 22, 2019 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.