At 10:43 PM 2/11/2003 -0800, Bill Frantz wrote:
I wrote:This *still* allows a dictionary attack; in fact, it allows a more powerful one than revealing 16 bits of the key does.
>(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
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: [EMAIL PROTECTED]
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 [EMAIL PROTECTED]
