Nash

Nash is a non-cryptographic message digest/authentication/verification system. It is not a signature.

Digest? Signature?

This sort of "digest" refers to a data fingerprint; it is used to mark a message in some way unlikely to be duplicated. A signature is an extra strong digest, in which duplication is supposed to be (practically) impossible. (Note: I refer to fingerprint/digest interchangeably; only when referring to a cryptographic-type digest do I use the term signature.)

The formula is: n = sigma c[0..s-1]; q = s + n.

Informal explanation:

Now, here's the idea. Digest mechanisms such as MD-5 (and hash127) are designed for cryptographic security. However, they are also used in non-cryptographic applications. For their purpose, they are excellent. On the other hand, there is a void in performance and usefulness where such security is not needed.

For an example of nash vs. other algorithms, imagine a browser download. A server may mark the HTTP header with a digest (e.g., Content-MD5) of the supposed message. Any accidental corruption en route from here to the client will be detected by a compatible browser via a check against the digest of the actual download, and the real file resident on the server.

If a malicious intruder were to alter this file in transit (substituting a different file, for example) he could just as well alter the header, and fool the browser into accepting just about anything. So you see, this is not strictly a cryptographic scenario (in fact, the only function of the digest can be as a checksum value--i.e., "the message adds up right, so it must be OK"), and a real signature is unnecessary.

Naming:

Nash comes from N-Hash, as hash can refer to an authentication-type digest, and N refers to the methodology of my own algorithm. Together they produce the last name of Ronald Nash, a nice guy I know.

Usage:

[input] | nash; # prints "nash N\n" (where N is a decimal number).

Bugs:

Nash as a computer program is limited by the size of integer limits. (My design assumes that the value of q will never overflow.) I simply use an "unsigned long int" (probably 32 bits). This means that anything longer than 16,777,216 bytes (but a random average of twice this much) might produce an incorrect digest. I'm sure someone could find a bigger number for a particular machine.

Download:

nash.tar.gz (600 bytes)

Installation:

I include a Makefile; probably nash belongs in /usr/local/bin.

Assurance of performance:

The central premise leading to the use of nash is its speed. If it were not faster in its place than MD-5, etc., there would be no point using it. I can assure you that it is faster. My tests, conducted with a very rudimentary implementation, show that it is on the order of 1000% faster (compared to full-grown, professional-quality md5 software). When inlined with other items, such as browsers, mail programs, and even text editors, there is no reason this gap cannot become even greater.

Nash produces a very sensitive message fingerprint, exactly the sort necessary for detection of extremely minor errors. (Note: by definition, all types of signatures can theoretically be violated.) Its value is essential in confirming faithful transmission of data--especially through networks, including the Internet--, without complicated and resource-wasting overhead.

Anyway, nash takes 0.60 sec to do 100,000,000 bytes (on a little, cute, small, and old machine).

Assurance of insecurity:

(Yeah, you did a double-take, didn't you? :-) Read on; it might not be what you think, but it's important.)

While nash is a perfectly functional solution, it only goes so far; its job is different from and complementary to other, "secure," message digest techniques. Although uncommon in practice, it is certainly possible to forge a message which is undistinguishable based only on nash digests. So that nobody will begin to rely solely on nash, or dishonestly present it as a signature substitute, I also provide source for a forgery program (in forge.c), able to create a forged message matching any given nash fingerprint. I repeat, nash is non-cryptographic, and I provide this code for the purpose of example and emphasis.

http://www.myersdaily.org/joseph/unix/nash.txt