DESCrack keyspace partitioning

What about the heuristics of partitioning the keyspace?

Seems to me that a _subset_ of all possible keys is much more likely
to appear than a random selection from an equidistributed population 0..2^56.

(P)RNG's just aren't that likely to produce a key of 010101010.....
nor 001100110011... etc etc and I have been thinking about how one might formalize 
and exploit this randomness property to increase the probability of finding the key sooner.

So a keysearch strategy should be something other than a partitioning of 2^26 into N bins
with a linear search within each bin.  I realize that it is POSSIBLE that a key of 1010101010...
was used, (excluding weak keys from consideration) ---- but I have seen "certifiable" RNG's and,
God Bless 'em, they just dont ever produce anything with any predictability.  

Is not the lack of predictability a predictable, and therefore exploitable, attribute?

Any thoughts here?




----------

geeman@best.com wrote:
> 
> What about the heuristics of partitioning the keyspace?
> 
> Seems to me that a _subset_ of all possible keys is much more likely
> to appear than a random selection from an equidistributed population 0..2^56.
> 
> (P)RNG's just aren't that likely to produce a key of 010101010.....
> nor 001100110011...

Why?  They seem just as likely as any other sequence.

 etc etc and I have been thinking about how one might formalize
> and exploit this randomness property to increase the probability of finding the key sooner.

Again, which randomness property?


Gary
--
"Of course the US Constitution isn't perfect; but it's a lot better
than what we have now."  -- Unknown.

pub  1024/C001D00D 1996/01/22  Gary Howland <gary@systemics.com>
Key fingerprint =  0C FB 60 61 4D 3B 24 7D  1C 89 1D BE 1F EE 09 06

of course, any number in the range of a random number
generator is theoretically as likely/unlikely to appear.

however, consider the case in which DES keys are generated
from ascii sequences or words that people enter in at
password prompts, which is in fact how the unix passwd file
word. these obviously have far less randomness
and Gary's attempt to narrow the keyspace is highly 
relevant.

also, I took his post as suggesting that some parts of the
keyspace ought to be searched at higher priority than
others. in the above example, keys that correspond to 
ascii sequences typable on a keyboard should be searched
first in the keyspace.

a lot of systems use DES only in conjuction with a one-time-key
generated for a particular message. (similar to the way
PGP uses IDEA for the session key, and transmits this encoded
key using RSA). in general I would say these could be considered
random in a way that the previous "less-than-random" property
doesn't hold.

geeman@best.com wrote:
>
> (P)RNG's just aren't that likely to produce a key of 010101010.....
> nor 001100110011... etc etc 

Right.  A good CSPRNG is ulikely to produce the pattern 010101010101.
It's also unlikely to produce the pattern 0011001100110011.  Oh, and
it's also unlikely to produce 01100100101001011.  In fact, a good
32-bit CSPRNG has only a 1/2^32 chance of producing any particular
bit pattern.  Of course, another way of saying that is that it's just
as likely to get an "obvious" bit pattern as it is to get any other
one.  You can't just throw away part of the keyspace based on such
bogus reasoning.  (There may be other reasons to throw away part of
the keyspace, of course.)

______c_________________________________________________________________
Mike M Nally * IBM % Tivoli * Austin TX  * How quickly we forget that
mailto:m5@tivoli.com mailto:m101@io.com  * "deer processing" and "data
http://www.io.com/~m101/                 * processing" are different!

On Thu, 3 Oct 1996, geeman@best.com wrote:


> Seems to me that a _subset_ of all possible keys is much more likely
> to appear than a random selection from an equidistributed population 0..2^56.

This is a contradiction.  Unless you were defining "subset" using a 
specific weakness in a specific RNG, in which case your argument would 
have been a tautology, saying nothing.

> (P)RNG's just aren't that likely to produce a key of 010101010.....
> nor 001100110011... etc etc and I have been thinking about how one might formalize 
> and exploit this randomness property to increase the probability of finding the key sooner.

RNG's are written to maximize randomness of of the numerical _value_ of 
the integer, independent of any arbitrary radix, including 
binary.

The "property" you describe is imaginary.  Like the Gambler's Fallacy, 
it's an artifact of our own cognitive functioning, and does not exist in 
the real world.

. . .
The radix is 13.
The answer is 42.
The question is "What do you get when you multiply 6 by 9?"

Let any search begin with self-knowledge...    Douglas B. Renner

Hi fellow flamers, cuss'ers, ect..

Some one recently gave me a copy of an article in Der Spiegel
(unfortunately in german!) stating that Crypto AG of Switzerland
had passed the keys to the German Govt without informing the
customer.

Can someone confirm, elaborate, dispute...... please.... :)

Thanks.



---------------------------------------------------------------------------
Flame AAway.....
" Sticks and stones may break my bones, but words will never hurt me"
===========================================================================

On Thu, 10 Oct 1996, pclow wrote:

> Hi fellow flamers, cuss'ers, ect..
> 
> Some one recently gave me a copy of an article in Der Spiegel
> (unfortunately in german!) stating that Crypto AG of Switzerland
> had passed the keys to the German Govt without informing the
> customer.
> 
> Can someone confirm, elaborate, dispute...... please.... :)

I can confirm the rumors, that is that the rumors are circulating.
I saw the Spiegel article.  I believe it.
Crypto AG is known for its government (ahem) sympathies.

Stay away from Switzerland.  All sorts of nasties in there.

> 
> Thanks.
> 

--
I hate lightning - finger for public key - Vote Monarchist
unicorn@schloss.li

On Thu, 10 Oct 1996, pclow wrote:

> Hi fellow flamers, cuss'ers, ect..
> 
> Some one recently gave me a copy of an article in Der Spiegel
> (unfortunately in german!) stating that Crypto AG of Switzerland
> had passed the keys to the German Govt without informing the
> customer.

This is nothing new. But how about faxing the article to John Young, so 
we all may benefit?


Thanks,
--Lucky

Lucky Green wrote:
> > Some one recently gave me a copy of an article in Der Spiegel
> > (unfortunately in german!) stating that Crypto AG of Switzerland
> > had passed the keys to the German Govt without informing the
> > customer.
> 
> This is nothing new. But how about faxing the article to John Young, so
> we all may benefit?

Can someone email me John Young's fax number? 

Thanks.

At 7:48 PM -0700 10/3/96, geeman@best.com wrote:
>What about the heuristics of partitioning the keyspace?
>
>Seems to me that a _subset_ of all possible keys is much more likely
>to appear than a random selection from an equidistributed population 0..2^56.
>
>(P)RNG's just aren't that likely to produce a key of 010101010.....
>nor 001100110011... etc etc and I have been thinking about how one might
>formalize
>and exploit this randomness property to increase the probability of
>finding the key sooner.


A PRNG is of course "just as likely" to produce 01010101010101...010101 as
it is to produce, say, "01110011101010....010100001010001001010 or any
other of the possible seequences. The key is that 01010101010101...010101
is a "special sequence," just like a "royal flush" is a "special hand" in
poker.

The formalism for this is "algorithmic information theory," or "descriptive
complexity theory," developed more or less independently by Kolmogoroff,
Chaitin, Martin-Lof, and others, mostly in the 1960s. The core idea is
this: "a number is random if it has no shorter description than itself."
That is, a random number is not compressible.

In the example above, the sequence "01010101010101...010101" has a simple
generating algorithm: "alternating 0s and 1s," and this is a shorter
description than the actual sequence. Naturally, there are relatively few
sequences with short descriptions (translation: "nearly all" sequences
"look to be random").

(One of the exciting conclusions is that no number can ever be _proved_ to
be random, via the Halting Problem, so I use the very term "random" with
this in mind. Substitute a more nuanced "a number believed to be random"
for every occurrence of "random." We can say that a number was generated
from, say, what we believe to be a "naturally random" process, e.g.,
radioactive decay, but we cannot prove the number is random. We can of
course prove it to be nonrandom if we can find a generator which
consistently generates it. This is the essence of von Neumann's comment
that the output of a PRNG algorithm cannot be random.)

These ideas are closely related to notions of entropy, compressibility,
etc. The standard works in English are by Gregory Chaitin, at IBM. He has
several books out, including a collection of his articles, "Information and
Randomness." Also, several readable articles in "Scientific American."

He also has an extensive Web site, last I looked, so some searches on his
name and/or algorithmic information theory should produce good results.


--Tim May

"The government announcement is disastrous," said Jim Bidzos,.."We warned IBM
that the National Security Agency would try to twist their technology."
[NYT, 1996-10-02]
We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1,257,787-1 | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."