Re: Federal Key Registration Agency

[Carl Ellison <cme@ACM.ORG>]

At 21:20 -0400 6/20/96, Michael Froomkin wrote:
>[...] AG Reno's assertion
>that it would take the government a year to break one DES message with a
>"supercomputer".  She presumably believes this.  We know the number for
>known plaintext attacks, but assuming you don't have a known plaintext,
>what's a more reasonable assumption?

If the plaintext is ASCII text, the time is the same but the machine is a
little more expensive.  What you do is process 8 or more blocks of
ciphertext in parallel, matching the high order bit of each byte to 0.
With 8 blocks, you get 64 high order bits -- more than the number of key
bits -- so you're not likely to guess wrong.

If the signal is audio instead of text, I don't know what you look for.
That depends on the compression algorithm.

If the signal is compressed text, again I would need to see the comressor
output.

If all you have is one or two blocks of text (e.g., a bank transaction) you
decrypt and decide whether the result is just impossible.  If it's possible
(and there will be many) you send the trial key on to a second processor (a
more general one) to try that key on the whole message to decide if the
message is still possible.

If that processor likes a given key, you send the result to a human -- who
chooses among all the possibles.

In other words, this doesn't have to be one-step-to-success.  All you're
doing is pruning the keyspace to something more manageable.

 - Carl


+------------------------------------------------------------------------+
|Carl M. Ellison   cme@acm.org     http://www.clark.net/pub/cme          |
|PGP: E0414C79B5AF36750217BC1A57386478 & 61E2DE7FCB9D7984E9C8048BA63221A2|
|  "Officer, officer, arrest that man!  He's whistling a dirty song."    |
+-------------------------------------------- Jean Ellison (aka Mother) -+