Method and apparatus to scale and unroll an incremental hash function

• US 7,783,688 B2
• Filed: 11/09/2005
• Issued: 08/24/2010
• Est. Priority Date: 11/10/2004
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huber, John David
• Primary Examiner(s): Wu; Yicun
• Assistant Examiner(s): Zhao; Yu
• Application Number:
  US11/271,134
• Publication Number:
  US 20060101039A1
• Time in Patent Office: 1,749 Days
• Field of Search: 370/395, 370/366, 711/216, 711/253, 711/256
• US Class Current: 713/187
• 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 performing an incremental hash function on a data string, the method comprising:

using a processor to perform at least a portion of one or more of the following acts;

receiving the data string over a network at a network interface device, the data string including a plurality of data samples B₀ to B_I, wherein represents a number of data samples that are received in parallel;

defining a moving window of length wl within the data string;

as the plurality of data samples are received, calculating and maintaining a corresponding plurality of hash values H₀ to H_I, one hash value for each data sample that can be received in parallel;

wherein calculating the plurality of hash values includes;

defining a hash multiplier constant to be k;

calculating a first hash value H₀ by adding a first data sample B₀ to a last hash value H_I, and by subtracting a data sample that was received wl bytes previously multiplied by k^wl;

calculating a second hash value H₁ by adding the first data sample B₀ multiplied by k and a second data sample B₁ to the last hash value H_I, by subtracting the data sample that was received wl bytes previously multiplied by k^wl+1, and by subtracting a data sample received wl+1 bytes previously multiplied by k^wl;

calculating the last hash value H_Iby adding the correspondingly multiplied values of the first data samples to the last hash value H_I, and by subtracting the correspondingly multiplied values of bytes received from wl to wl+previously;

combining the calculated first hash value through last hash value into a result;

using the result to identify content in the form of a particular reference string; and

performing a particular action based upon the particular reference string.

2. The method of claim 1, which comprises:

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

when sufficient data samples are present in the array, performing the calculating and maintaining of the plurality of hash values in parallel on each segment of the array.

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

4. Apparatus to perform an incremental hash function on a data string, the apparatus comprising:

at least one processor; and

a memory including instructions which, when executed, provide a modified hash function module to receive the data string including a plurality of data samples B₀ to B₁, wherein represents a number of data samples that are received in parallel, wherein a moving window of length wl is defined with the data string, and wherein, as the plurality of data samples are received, the modified hash function module calculates and maintains a corresponding plurality of hash values H₀ to H_I, one hash value for each data sample that can be received in parallel;

wherein calculating the plurality of hash values includes;

defining a hash multiplier constant to be k;

calculating a first hash value H₀ by adding a first data sample B₀ to a last hash value H_I, and by subtracting a data sample that was received wl bytes previously multiplied by k^wl;

calculating a second hash value H₁ by adding the first data sample B₀ multiplied by k and a second data sample B₁ to the last hash value H_I, by subtracting the data sample that was received wl bytes previously multiplied by k^wl+1, and by subtracting a data sample received wl+1 bytes previously multiplied by k^wl;

calculating the last hash value H_I by adding the correspondingly multiplied values of the first data samples to the last hash value H_I, and by subtracting the correspondingly multiplied values of bytes received from wl to wl+previously;

combining the calculated first hash value through last hash value into a result;

using the result to identify content in the form of a particular reference string; and

performing a particular action based upon the particular reference string.

5. The apparatus of claim 4, wherein:

the 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 calculating and maintaining of the plurality of hash values is performed in parallel on each segment of the array.

6. Apparatus to perform an incremental hash function on a data string, the apparatus comprising:

at least one processor; and

memory including instructions which, when executed, provide modified hash function means to receive the data string including a plurality of data samples B₀ to B_I, wherein represents a number of data samples that are received in parallel, wherein a moving window of length wl is defined with the data string, and wherein, as the plurality of data samples are received, the modified hash function means calculates and maintains a corresponding plurality of hash values H₀ to H_I, one hash value for each data sample that can be received in parallel;

wherein calculating the plurality of hash values includes;

defining a hash multiplier constant to be k;

calculating a first hash value H₀ by adding a first data sample B₀ to a last hash value H_I, and by subtracting a data sample that was received wl bytes previously multiplied by k^wl;

calculating a second hash value H₁ by adding the first data sample B₀ multiplied by k and a second data sample B₁ to the last hash value H_I, by subtracting the data sample that was received wl bytes previously multiplied by k^wl+1, and by subtracting a data sample received wl+1 bytes previously multiplied by k^wl;

calculating the last hash value H_I by adding the correspondingly multiplied values of the first data samples to the last hash value H_I, and by subtracting the correspondingly multiplied values of bytes received from wl to wl+previously;

combining the calculated first hash value through last hash value into a result;

using the result to identify content in the form of a particular reference string; and

performing a particular action based upon the particular reference string.

7. The apparatus of claim 6 further comprising means for defining a hash value of the data string as a new hash value.