handling weak keys using random selection and CSPRNGs
Greg Rose
ggr at qualcomm.com
Fri Oct 13 13:46:18 EDT 2006
At 17:05 -0400 2006/10/12, Steven M. Bellovin wrote:
>This is a very interesting suggestion, but I suspect people need to be
>cautious about false positives. MP3 and JPG files will, I think, have
>similar entropy statistics to encrypted files; so will many compressed
>files.
Actually, no. I have a general purpose stats program that I often use
for cryptanalysis as part of my tookit. I pointed it at my photos
folder, and every single jpeg file had results like this:
samples: 88246
unique: 256
sum: 11413854
sum squares: 1943201034
maximum: 255
minimum: 0
range: 255
mean: 129.34132
variance: 5291.1565
std dev: 72.740336
median: 130
exp freq: 344.71094
max freq: 623
mode count: 1
mode: 0
min freq: 109
unmode count: 1
unmode: 192
chi^2: 4375.0414
chi^2 df: 255
pr(chi^2): 1.00000 (*** certainly non-uniform distribution ***)
bad buckets: 96
KS+: 1.0002392
pr(KS+): 0.86510
KS-: 6.6097712
pr(KS-): 1.00000 (*** certainly non-uniform distribution ***)
KS(both): 3.8050052
pr(KS_BOTH): 1.00000
The simplest test is just the chi-squared test on the frequency of
bytes, and it's way out of range on even fairly small jpegs. The
Kolmogorov-Smirnoff test almost always bingos too. And even if the
chi-squared passes, the binomial test on individual byte-value
frequencies will flag the data as non-random; note the "bad buckets"
count above; the detailed output is suppressed when the chi-squared
test fails, since there will generally be too much of it.
The only things that it usually passes as good are for-purpose random
number generators' or ciphers' outputs. Everything else (including a
terabyte of RC4 output, executables, zip archives, jpegs, mpegs,
mp3s, ...) that I've pointed it at, fails one or more of the tests.
True random-looking-ness is hard to find... :-)
Greg.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list