Patent on comparing two values which are put through a hash function to determine if the same

Question

I came across this patent titled “Similarity-based access control of data in a data processing system” (priority date: 1995-04-11).

Abstract:

Similarity of data items is determined by analyzing corresponding segments of the data items. A function is applied to each segment of a data item and the output of that function is compared to the output of the same function applied to a corresponding segment of another data item. A function may be applied to the output of the functions. The functions may be hash or message digest functions.

The way I understand the legalese, it appears to patent comparing the output of a hash function to determine if the inputs are equal. This is an extremely trivial operation and is utilized in most websites today.

Most websites and other password-security applications will use a one-way hash function on the saved password. This is so that the password can not be retrieved in case of a hack. I'm sure that this was round before the world wide web even though. I'm pretty sure that some UNIX-like operating systems used one-way hashing for passwords.

So is there any prior art for this, or am I misinterpreting the patent?

Here's the text of claim 1:

A computer-implemented method, the method comprising:

• (A) for a first data item comprising a first plurality of parts,
  • (a1) applying a first function to each part of said first plurality of parts to obtain a corresponding part value for each part of said first plurality of parts, wherein each part of said first plurality of parts comprises a corresponding sequence of bits, and wherein the part value for each particular part of said first plurality of parts is based, at least in part, on the corresponding bits in the particular part, and wherein two identical parts will have the same part value as determined using said first function, wherein said first function comprises a first hash function; and
  • (a2) obtaining a first value for the first data item, said first value obtained by applying a second function to the part values of said first plurality of parts of said first data item, said second function comprising a second hash function;
• (B) for a second data item comprising a second plurality of parts,
  • (b1) applying said first function to each part of said second plurality of parts to obtain a corresponding part value for each part of said second plurality of parts, wherein each part of said second plurality of parts consists of a corresponding sequence of bits, and wherein the part value for each particular part of said second plurality of parts is based, at least in part, on the corresponding bits in the particular part of the second plurality of parts; and
  • (b2) obtaining a second value for the second data item by applying said second function to the part values of said second plurality of parts of said second data item; and
• (C) ascertaining whether or not said first data item corresponds to said second data item based, at least in part, on said first value and said second value.

Answer 1

This seems to be roughly equivalent to what the rsync protocol does (as noted by Alex Chamberlain). From the rsync technical report (1998):

The rsync algorithm consists of the following steps:

1. ᵦ splits the file B into a series of non-overlapping fixed-sized blocks of size S bytes1. The last block may be shorter than S bytes.
2. For each of these blocks ᵦ calculates two checksums: a weak ``rolling'' 32-bit checksum (described below) and a strong 128-bit MD4 checksum.
3. ᵦ sends these checksums to α.
4. α searches through A to find all blocks of length S bytes (at any offset, not just multiples of S) that have the same weak and strong checksum as one of the blocks of B. This can be done in a single pass very quickly using a special property of the rolling checksum described below.
5. sends ᵦ a sequence of instructions for constructing a copy of A. Each instruction is either a reference to a block of B, or literal data. Literal data is sent only for those sections of A which did not match any of the blocks of B.

Answer 2

The essential element of this patent seems to be computing a hash based on other hashes. Here are some examples:

1. Compute a hash for each file on a disk. Then compute a hash for each directory based on the hashes of the files it contains. Use those directory hashes to determine whether two directories have identical contents.

2. Compute a hash for each frame of a video. Then compute a hash for each video based on the hashes of its individual frames. Use that to determine if two videos are identical.

3. In any object oriented language with a collections framework, every object provides a method to compute a hash code. A collection computes its hash code based on the hash codes of the objects it contains.

Does anyone know of a collections framework from prior to 1995 that worked that way? Java 1.0 was released in Jan. 1996, so it just missed the cutoff. STL is older, but the initial version didn't include hashing containers. Perhaps something in Smalltalk? Objective C? Eiffel? Ada?

EDIT:

Bingo! I downloaded the source code for Python 1.0.1, released in January 1994. Found in tupleobject.c:

static long
tuplehash(v)
    tupleobject *v;
    {
    register long x, y;
    register int len = v->ob_size;
    register object **p;
    x = 0x345678L;
    p = v->ob_item;
    while (--len >= 0) {
        y = hashobject(*p++);
        if (y == -1)
            return -1;
        x = (x + x + x) ^ y;
    }
    x ^= v->ob_size;
    if (x == -1)
        x = -2;
    return x;
}

It's doing precisely what the patent describes: computing a hash for the tuple based on the hashes of the objects it contains. That hash then gets used in various contexts to determine identity, such as when you use it as a dictionary key. (See the source code in mappingobject.c.) I believe this is very clear prior art.

Answer 3

Let's look at a typical case, in plain English.

(A) for a first data item comprising a first plurality of parts,

Consider a file or message A composed of several blocks A1,…,An, where each block is a sequence of bits: A = A1 || … || An where || denotes concatenation.

(a1) applying a first function to each part of said first plurality of parts to obtain a corresponding part value for each part of said first plurality of parts, wherein each part of said first plurality of parts comprises a corresponding sequence of bits, and wherein the part value for each particular part of said first plurality of parts is based, at least in part, on the corresponding bits in the particular part, and wherein two identical parts will have the same part value as determined using said first function, wherein said first function comprises a first hash function; and

Let H be a hash function. For each block Ai, compute H(Ai): that's the “corresponding part value” of the part Ai. “Based on the corresponding bits in the particular part” is inherent in using a hash function, as in “two identical parts will have the same part value”.

(a2) obtaining a first value for the first data item, said first value obtained by applying a second function to the part values of said first plurality of parts of said first data item, said second function comprising a second hash function;

Let G be a hash function of many arguments — for example, calculating the hash of the concatenation of its argument. The “first value for the first data item” is U = G(H(A1),…,H(An)).

(B) for a second data item comprising a second plurality of parts, (…)

Do it again for a second file B = B1 || … || Bm: the second value is V = G(H(B1),…,H(Bm)).

(C) ascertaining whether or not said first data item corresponds to said second data item based, at least in part, on said first value and said second value.

The claimed method is to compare A and B using U and V, i.e. to compare two messages using the hash of the concatenation of the hashes of the blocks in each message.

This is a well-known technique called hash trees, here with a depth of 2. Hash trees are also called Merkle trees, because they were invented and patented by Ralph Merkle in 1979. US patent 4309569 is prior art for this claim. Merkle teaches breaking a message into parts, calculating the hash of each part (F(Yi) in equation (1)) and calculating the hash of a plurality of parts (H(i,j,Y) in equation (2)) (col.2 l.54–65). Merkle teaches applying the same method to a second message (col.3 l.50–56: the method is applied both by the transmitter and by the receiver). Merkle teaches comparing the two data items based on the hash values (called “root values” in Merkle, col.3 l.52–56).

Claims 2–21 are simple refinements of claim 1 and are not inventive in their own right. Claims 22, 32 and 36 concern the use of the hash values to look up objects in a database. This is arguably not obvious from Merkle. However, the use of hash trees in Python as shown by peastman is prior art for that use.

Answer 4

Looking at the claims (at least claim 1), this isn't quite like rsync. In particular, it specifies using, not just one, but two separate hash functions for each block.

The patent does not, however mention "bloom filter" anywhere -- which seems like an odd omission, given that it sounds a lot like a Bloom filter (which was invented ~25 years before the patent was filed).

Answer 5

Comparing hashes is the basis of the standard UNIX password authentication system. This was not included in the very first versions of UNIX, but it is described in detail in a paper dated April 3, 1978, and must therefore have been implemented prior to that date.

The UNIX system was first implemented with a password file that contained the actual passwords of all the users, and for that reason the password file had to be heavily protected against being either read or written. Although historically, this had been the technique used for remote-access systems, it was completely unsatisfactory for several reasons.

[...]

The obvious solution is to arrange that the passwords not appear in the system at all, and it is not difficult to decide that this can be done by encrypting each user’s password, putting only the encrypted form in the password file, and throwing away his original password (the one that he typed in). When the user later tries to log in to the system, the password that he types is encrypted and compared with the encrypted version in the password file. If the two match, his login attempt is accepted. Such a scheme was first described in [3, p.91ff.]. It also seemed advisable to devise a system in which neither the password file nor the password program itself needed to be protected against being read by anyone.

All that was needed to implement these ideas was to find a means of encryption that was very difficult to invert, even when the encryption program is available. Most of the standard encryption methods used (in the past) for encryption of messages are rather easy to invert. A convenient and rather good encryption program happened to exist on the system at the time; it simulated the M-209 cipher machine [4] used by the U.S. Army during World War II. It turned out that the M-209 program was usable, but with a given key, the ciphers produced by this program are trivial to invert. It is a much more difficult matter to find out the key given the cleartext input and the enciphered output of the program. Therefore, the password was used not as the text to be encrypted but as the key, and a constant was encrypted using this key. The encrypted result was entered into the password file.

In modern cryptographic parlance, this describes a trapdoor function, better known as a hash.