Re: handling weak keys using random selection and CSPRNGs

2006-10-16 Thread Marcos el Ruptor

Now, you said compressed files and you might not have meant
pictures, but note that L-Z style compressed files don't really have
much in the way of headers. If the headers were a problem, you'd
expect longer files to bury any deviation in the noise, but it
doesn't. The longer the files I test the more certainly non-random
they are.

I stand by my statements.

Greg.


Hello, Greg!

I did not say anything about pictures. I only said that it's not that hard 
to find a compression algorithm or a source of randomness or a simple PRNG 
that will pass all kinds of randomness tests. You said it's hard, I said it 
wasn't. Maybe you want to try testing something packed with WinRK or Durilca 
for example. You could probably even test the whole files packed with 
them...


Although I totally agree with you that JPEG or ZIP (Deflate) or LZ 
compressed data could only pass randomness tests if the data was random to 
begin with. But come on, such weak ancient algorithms hardly qualify as 
randomness benchmarks. Modern decent compression algorithms like those used 
in Stuffit or Allume reduce JPEGs by about 25% or so (losslessly). No wonder 
your tests show a bias!


On the other hand, maybe you have an amazing brilliant randomness test there 
that fails all the compressed files and makes diehard look like a baby's 
rattle... If that is the case, do share! ;-)


Ruptor 



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Leichter, Jerry
| Given how rare weak keys are in modern ciphers, I assert that code to cope
| with them occurring by chance will never be adequately tested, and will be
| more likely to have security bugs.  In short, why bother?
Beyond that:  Are weak keys even detectable using a ciphertext-only
attack (beyond simply trying them - but that can be done with *any* small
set of keys)?  If not, what's the attack?  One could posit an attack
in which some of the plaintext is known, and an attacker could detect
the weak key from known ciphertext/plaintext pairs and then use the
detected key to attack the rest of the ciphertext.  But that's an odd
attack to defend against - why not just try all the weak keys (or,
again, any small subset of keys) and see if they work?

The only kind of weak key that would matter is one that leaves the
ciphertext mainly or entirely unchanged - e.g., leaves most of the
bits unchanged or most of them always flipped.  This suggests that,
rather than looking for weak keys as such, it might be worth it to
do continuous online testing:  Compute the entropy of the generated
ciphertext, and its correlation with the plaintext, and sound an
alarm if what you're getting looks wrong.  This might be a
worthwhile thing to have, not just for detecting weak keys, but
to detect all kinds of software and hardware failures.  Since it's
outside of the actual encryption datapath, a bug either fails to
sound an alarm when it should - leaving you where you were without
this new check - or sounds a false alarm, which unless it occurs
too often, shouldn't be such a big deal.

-- Jerry


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Steven M. Bellovin
On Thu, 12 Oct 2006 16:50:13 -0400 (EDT), Leichter, Jerry
[EMAIL PROTECTED] wrote:

 This suggests that,
 rather than looking for weak keys as such, it might be worth it to
 do continuous online testing:  Compute the entropy of the generated
 ciphertext, and its correlation with the plaintext, and sound an
 alarm if what you're getting looks wrong.  This might be a
 worthwhile thing to have, not just for detecting weak keys, but
 to detect all kinds of software and hardware failures.  Since it's
 outside of the actual encryption datapath, a bug either fails to
 sound an alarm when it should - leaving you where you were without
 this new check - or sounds a false alarm, which unless it occurs
 too often, shouldn't be such a big deal.
 
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.

For a more substantive, less hand-wavey analysis, see
http://www.isoc.org/isoc/conferences/ndss/05/proceedings/papers/storageint.pdf
which has actual file system entropy measurements. 


--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Leichter, Jerry
|  This suggests that,
|  rather than looking for weak keys as such, it might be worth it to
|  do continuous online testing:  Compute the entropy of the generated
|  ciphertext, and its correlation with the plaintext, and sound an
|  alarm if what you're getting looks wrong.  This might be a
|  worthwhile thing to have, not just for detecting weak keys, but
|  to detect all kinds of software and hardware failures.  Since it's
|  outside of the actual encryption datapath, a bug either fails to
|  sound an alarm when it should - leaving you where you were without
|  this new check - or sounds a false alarm, which unless it occurs
|  too often, shouldn't be such a big deal.
|  
| 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.
I'm not sure which direction you want false positive to refer to.  If
the input is already random-looking, then any encryption of it, good or
bad (other than very silly ones which grossly expand the input) will
also be random-looking.  So you'll never trip the output doesn't look
random enough detector.  On the other hand, some simple correlation
analysis between input and output *might* detect some simple failures.
(You could also look for the non-random pieces, like the headers on
JPG's.  Not sure it's really worth it - about the only time you're
going to find that is when the output and the input are essentially
identical.)
-- Jerry
 
| For a more substantive, less hand-wavey analysis, see
| http://www.isoc.org/isoc/conferences/ndss/05/proceedings/papers/storageint.pdf
| which has actual file system entropy measurements. 
| 
| 
|   --Steven M. Bellovin, http://www.cs.columbia.edu/~smb
| 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Travis H.

On 10/12/06, Leichter, Jerry [EMAIL PROTECTED] wrote:

Beyond that:  Are weak keys even detectable using a ciphertext-only
attack (beyond simply trying them - but that can be done with *any* small
set of keys)?


Yes, generally, that's the definition of a weak key.


But that's an odd
attack to defend against - why not just try all the weak keys (or,
again, any small subset of keys) and see if they work?


Because that's the definition of brute forcing, and generally the key
distribution
is close to uniform in any [symmetric] system that is worth a second glance?


do continuous online testing:  Compute the entropy of the generated
ciphertext, and its correlation with the plaintext, and sound an
alarm if what you're getting looks wrong.


This is a decent idea.  Of course, there are scads of problems that
are not detectable by a simple memoryless markov model, but this
would be a decent sanity check on all but the smallest of plaintexts.

I would also want continuous monitoring of my HWRNG outputs; maybe
I wouldn't want a simple entropy check, which a properly-functioning
HWRNG will fail with a probability predicted by chance, but perhaps
a graphical display of the previous values.  I'm not a visual thinker,
but I don't think any amount of statistics are going to be as useful in
detecting deviations from uniformity as a plot and a human brain.
--
The obvious mathematical breakthrough would be the development of an
easy way to factor large prime numbers.'' [sic] -- Bill Gates  --
URL:http://www.subspacefield.org/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Perry E. Metzger

Travis H. [EMAIL PROTECTED] writes:
 On 10/12/06, Leichter, Jerry [EMAIL PROTECTED] wrote:
 Beyond that:  Are weak keys even detectable using a ciphertext-only
 attack (beyond simply trying them - but that can be done with *any* small
 set of keys)?

 Yes, generally, that's the definition of a weak key.

No, that is not the definition of a weak key.

Look at DES weak keys, for example. They are simply keys for which the
encryption and decryption transform are identical -- encrypting twice
with the weak key returns you to the plaintext -- but they are not in
some way obviously detectable without trying them.

Might I suggest reading the literature on this before discussing it
further?

Perry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-13 Thread Greg Rose

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.0 (*** certainly non-uniform distribution ***)
bad buckets:  96
KS+:  1.0002392
pr(KS+):  0.86510
KS-:  6.6097712
pr(KS-):  1.0 (*** certainly non-uniform distribution ***)
KS(both): 3.8050052
pr(KS_BOTH):  1.0

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 [EMAIL PROTECTED]


Re: handling weak keys using random selection and CSPRNGs

2006-10-12 Thread Steven M. Bellovin
Given how rare weak keys are in modern ciphers, I assert that code to cope
with them occurring by chance will never be adequately tested, and will be
more likely to have security bugs.  In short, why bother?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


handling weak keys using random selection and CSPRNGs

2006-10-10 Thread Travis H.

Hi all,

It occured to me that there is a half-decent way to avoid weak keys in
algorithms
when it is undesirable or impossible to prompt the user for a
different passphrase.
It is even field-upgradable if new weak keys are found.

Basically, instead of using the hash of the passphrase up front, you do a PRNG
expansion of the passphrase.  For example,
k_1 = hash(1||passphrase)
k_2 = hash(2||passphrase)

and so on.

The important thing here is that it is not something like the following:

k_1 = hash(passphrase)
k_2 = hash(k_1)
...
k_n = hash(k_(n-1)

In that method, the number of input states is limited by the hash size, whereas
the former algorithm has a number of states that the k sequence can be in
is limited by the size of the passphrase.  I suppose that a running hash
would be limited by the size of the hash state (chaining variables).

Next you construct k = k_1 || k_2 || ... k_n

The computation can be done incrementally on an as-needed basis.

Then, you read in the number of weak keys, and perform a random selection
on the number of valid keys using the algorithm I posted earlier, with k as
the source of unpredictability.  This leaves you with a random number between
0 and the number of non-weak keys minus one.  Then you iterate over the weak
keys in numerical order, incrementing the value from the previous step
by one if it exceeds the weak key's numerical value.  This part runs in
time linear with the number of weak keys, not the size of the non-weak keyspace.

You are left with a value that has a uniform distribution over the
non-weak keys.

The random selection algorithm may run indefinitely, but the chances of
that are infinitesimal.  If there are a huge number of weak keys, then it
may take longer, but I'd be willing to bet that CPU speed increases faster
than discovery of weak keys, and if it doesn't the user might be
inconvenienced enough to upgrade to a less broken cipher algorithm.
--
The obvious mathematical breakthrough would be the development of an
easy way to factor large prime numbers.'' [sic] -- Bill Gates  --
URL:http://www.lightconsulting.com/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]