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."
participants (9)
-
Black Unicorn -
Douglas B. Renner -
Gary Howland -
geeman＠best.com -
Lucky Green -
Mike McNally -
pclow -
Timothy C. May -
Vladimir Z. Nuri