Method and apparatus to scale and unroll an incremental hash function

• US 20060101039A1
• Filed: 11/09/2005
• Published: 05/11/2006
• Est. Priority Date: 11/10/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huber, John David
• Granted Patent: US 7,783,688 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A method and apparatus speeding up an incremental hash function is described. The method may comprise receiving a data string including a plurality of N data samples and, as each data sample is received, multiplying the data samples to obtain data sample multiplication results and multiplying a current hash value by a constant to obtain a hash multiplication result. Thereafter, the data sample multiplication results are added to the hash multiplication result to obtain new current hash values and a hash value of the data string is defined as the new hash value. In an embodiment, a moving window of length wl may be defined and data samples that were received wl to wl+N bytes previously may be multiplied with the constant raised to the power of w to wl+Nl to obtain n subtraction results.

Claims

1. A method of speeding up an incremental hash function, the method comprising:

receiving a data string including a plurality of data samples;

as each data sample is received,

maintaining a plurality of hash values, one for each data sample that can be received in parallel;

for each hash value, multiplying the current hash value by a constant to obtain a hash value multiplication result;

for each data sample, multiplying the data sample by a predetermined constant to obtain a sample multiplication result; and

for each hash value, adding a plurality of sample multiplication results and subtracting previously stored sample multiplication results to obtain a new current hash value.

2. The method of claim 1, which comprises:

storing data samples in parallel in an array including a plurality of segments; and

when sufficient data samples are present in the array, performing the multiplying, adding, and defining of the hash value in parallel on each segment of the array.

3. The method of claim 1, which comprises:

defining a moving window of length wl;

defining a number of hash values H computed concurrently;

defining a number of data samples arriving concurrently to also be H;

defining the hash multiplier constant to be k;

updating the first hash value by adding the first data sample multiplied by the constant k to the last hash value multiplied by k and subtracting the data sample that was received wl bytes previously with the constant raised to the power of wl;

updating the second hash value by adding the first data sample multiplied by the constant k raised to the power 2 and the second data sample multiplied by the constant k to the last hash value multiplied by k to the power of 2 and subtracting the data sample that was received wl bytes previously with the constant raised to the power of wl+1; and

subtracting the data sample received wl+1 bytes previously raised to the power wl; and

updating the I-th hash value by adding the correspondingly multiplied values of the first I data samples to the last hash value multiplied by k to the power of I and subtracting the correspondingly multiplied values of bytes previously received wl to wl+I.

4. The method of claim 3, which comprises:

storing data samples in parallel in an array including a plurality of segments; and

when sufficient data samples are present in the array, performing the multiplying, subtracting and defining the hash value in parallel on each segment of the array.

5. A machine readable-medium embodying instructions which, when executed by a machine, cause the machine to perform the method of claim 1.

6. Apparatus to speeding up an incremental hash function, the apparatus comprising a modified hash function module to receive a data string including a plurality of data samples, wherein as each data sample is received the modified hash function module:

maintains a plurality of hash values, one for each data sample that can be received in parallel;

for each hash value, multiplies the current hash value by a constant to obtain a hash value multiplication result;

for each data sample, multiplies the data sample by a predetermined constant to obtain a sample multiplication result; and

for each hash value, adds a plurality of sample multiplication results and subtracting previously stored sample multiplication results to obtain a new current hash value.

7. The apparatus of claim 6, wherein:

data samples are stored in parallel in an array including a plurality of segments; and

when sufficient data samples are present in the array, the multiplying, adding, and defining of the hash value is performed in parallel on each segment of the array.

8. The apparatus of claim 6, wherein the modified hash function module:

defines a moving window of length wl;

defines a number of hash values H computed concurrently;

defines a number of data samples arriving concurrently to also be H;

defines the hash multiplier constant to be k;

updates the first hash value by adding the first data sample multiplied by the constant k to the last hash value multiplied by k and subtracting the data sample that was received wl bytes previously with the constant raised to the power of wl;

updates the second hash value by adding the first data sample multiplied by the constant k raised to the power 2 and the second data sample multiplied by the constant k to the last hash value multiplied by k to the power of 2 and subtracting the data sample that was received wl bytes previously with the constant raised to the power of wl+1, and subtracting the data sample received wl+1 bytes previously raised to the power wl; and

updates the I-th hash value by adding the correspondingly multiplied values of the first I data samples to the last hash value multiplied by k to the power of I and subtracting the correspondingly multiplied values of bytes previously received wl to wl+I.

9. The apparatus of claim 8, wherein:

data samples are stored in parallel in an array including a plurality of segments; and

when sufficient data samples are present in the array, the multiplying, subtracting and defining the hash value is performed in parallel on each segment of the array.

10. Apparatus to calculate a hash value of a data string as each data sample is received, the apparatus comprising:

means for receiving the data string including a plurality of data samples;

means for multiplying a current hash value by a constant to obtain a hash value multiplication result;

means for multiplying a current hash value by a constant to obtain a sample multiplication result;

means for adding and subtracting the received data sample multiplication result to the previous hash value to obtain a new current hash value; and

means for defining a hash value of the data string as the new hash value.