[52441] in cryptography@c2.net mail archive
Re: handling weak keys using random selection and CSPRNGs
daemon@ATHENA.MIT.EDU (Greg Rose)
Fri Oct 13 15:40:38 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <20061012170555.bc426219.smb@cs.columbia.edu>
Date: Fri, 13 Oct 2006 10:46:18 -0700
To: "Steven M. Bellovin" <smb@cs.columbia.edu>
From: Greg Rose <ggr@qualcomm.com>
Cc: "Leichter, Jerry" <leichter_jerrold@emc.com>,
"Travis H." <solinym@gmail.com>,
Cryptography <cryptography@metzdowd.com>
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@metzdowd.com
