karn@epic.bellcore.com (Phil R. Karn) (02/22/91)
Archive-name: security/hashing/md4-draft/1991-02-21 Archive: rsa.com:/pub/rfc.md4.draft [192.80.211.13] Original-posting-by: karn@epic.bellcore.com (Phil R. Karn) Original-subject: Re: Authentication Reposted-by: emv@ox.com (Edward Vielmetti) In article <1991Feb21.062516.29456@csn.org>, bear@tigger.Colorado.EDU (Bear Giles) writes: |> It is not necessary to encrypt the entire file. Most modern cryptology |> books will discuss this in more detail, but one good verification (for |> small messages, no more than 30k) is to calculate several different CRC |> values across the message. If you carefully choose N independent 16-bit |> CRC polynomials you should be able to get nearly (1 in 65536)^N unique ids. Actually, the trend is to use special hash functions that are "hard" to invert. MD4 is one such function; it accepts an arbitrary number of bits as input and produces a 16-byte "signature" as output. It is claimed that finding any two messages that hash to the same signature would take on the order of 2^64 operations, and finding a message that hashes to a given signature would take on the order of 2^128 operations. This is considerably harder to fool than even a collection of linear CRCs, and because it was designed for software implementation, it is also very fast: 83Kbytes/sec on my 25 MHz 386. (MD4 runs much better on real computers: almost 3 megabytes/sec on my Sparc 2. That's because the algorithm does a lot of operations on 32-bit integers.) MD4's originator has made it available by anonymous FTP from rsa.com. I'm making it the basis of a one-time password scheme for UNIX. Maybe it will work in the NOS mailbox too. Phil