Newsgroups: comp.archives Path: utzoo!utgpu!news-server.csri.toronto.edu!ox.com!emv From: karn@epic.bellcore.com (Phil R. Karn) Subject: [rec.radio.amateur.policy] Re: Authentication Message-ID: <1991Feb21.210125.16657@ox.com> Followup-To: rec.radio.amateur.policy Sender: emv@ox.com (Edward Vielmetti) Reply-To: karn@thumper.bellcore.com Organization: Packet Communications Research Group (Bellcore) References: <106@shasta.Stanford.EDU> <1991Feb19.044235.10447@cunixf.cc.columbia.edu> <1991Feb21.050748.9808@ux1.cso.uiuc.edu> <1991Feb21.062516.29456@csn.org> <1991Feb21.015923@epic.bellcore.com> Date: Thu, 21 Feb 1991 21:01:25 GMT Approved: emv@ox.com (Edward Vielmetti) X-Original-Newsgroups: rec.radio.amateur.policy 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 Brought to you by Super Global Mega Corp .com