Columbia crypto box

[Greg Rose]

At 10:43 PM 2/11/2003 -0800, Bill Frantz wrote:
>I wrote:
> >(IIRC, basically what the device did was reveal 16 bits of a DES key.)
>
>It has been pointed out to me that they were even more clever than that.
>(This technique could allow a dictionary attack on known/probable plain
>text.)  What they did instead was, take a 56 bit DES key through a one way 
>function, zero certain bits so only 40 are variable, take the result 
>through another one way function, and use the result as a DES key for 
>encryption.
>
>For details see US patent 5,323,464: 
>http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/search-bool.html&r=47&f=G&l=50&co1=AND&d=ptxt&s1=Matyas.INZZ.&OS=IN/Matyas&RS=IN/Matyas

This *still* allows a dictionary attack; in fact, it allows a more powerful 
one than revealing 16 bits of the key does.

If you just reveal 16 bits of the key, then an adversary either needs to 
store 2^56 dictionary entries, or enumerate 2^40 keys.

If you do as CDMF does, there are effectively only 2^40 possible 56-bit 
keys; these can be precomputed and stored on eg. tape. (7.5 terabytes, well 
within tape library range 10 years ago.) So you can *still* brute force the 
keys just as easily, noting that all this really does is avoid two hash 
function invokations per key. More, though, you can now compute and store 
(in comparable tape space) the dictionary, so CDMF *does* allow a 
precomputed dictionary attack that requires only storage for 2^40 
dictionary entries (whatever size they are).

So CDMF isn't that neat, really...

Greg.


Greg Rose                                       INTERNET: ggr at qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com