Fuzzy hash algorithm

• US 8,484,152 B2
• Filed: 06/26/2009
• Issued: 07/09/2013
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: GoSecure, Inc.
• Original Assignee: HBGary, Inc. (Mantech International Corporation)
• Inventors: Hoglund, Michael Gregory
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/459,203
• Publication Number:
  US 20110093426A1
• Time in Patent Office: 1,474 Days
• Field of Search: 706/52
• US Class Current: 706/52
• CPC Class Codes: G06F 21/562 Static detection
• CPC Class Codes: G06F 21/563 by source code analysis
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

An embodiment of the invention provides a method for and an apparatus for classifying a data object by use of a fuzzy hash. The method and apparatus can perform steps including: aligning a window in a target data object; reading content within the window; hashing the content within the window in order to calculate a hash value; splicing a spliced portion from the hashed value; and storing the spliced portion as part of a fuzzy hash.

Claims

1. A method of classifying a data object by use of a fuzzy hash, the method comprising:

aligning a window in a target data object;

reading content within the window;

hashing the content within the window in order to calculate a hash value;

splicing a spliced portion from the hashed value; and

storing the spliced portion as part of a fuzzy hash.

2. The method of claim 1, further comprising:

comparing the fuzzy hash with a reference fuzzy hash in order to classify the data object.

3. The method of claim 1, further comprising:

storing, into a buffer, a plurality of meta-tags corresponding to data blocks that are overlapped by the window, wherein a meta-tag corresponding to an associated data block.

4. The method of claim 1, wherein the hash comprises a summation of contents within the window.

5. The method of claim 1, wherein calculation of the hash is initiated by a trigger.

6. The method of claim 1, wherein the spliced portion comprises a significant byte of the hash.

7. The method of claim 1, further comprising:

determining a running entropy value for contents that are overlapped by the window;

if the running entropy value is at least at a threshold value, then shifting into a high entropy mode; and

if the running entropy value is below a threshold value, then shifting into a non-high entropy mode.

8. The method of claim 7, further comprising:

in the high entropy mode, using a trigger associated with the high entropy mode.

9. The method of claim 8, wherein the trigger comprises a shift register.

10. The method of claim 8, further comprising:

performing a hash of the contents that are overlapped by the window, in the high entropy mode.

11. The method of claim 8, further comprising:

in the non-high entropy mode, shifting into one of a text mode, code mode, or binary structure mode.

12. The method of claim 11, further comprising:

in the text mode, using a trigger associated with the text mode in order to initiate calculation of the hash.

13. The method of claim 11, further comprising:

in the code mode, using a trigger associated with the code mode in order to initiate calculation of the hash.

14. The method of claim 11, further comprising:

in the binary structure mode, using a trigger associated with the binary structure mode in order to initiate calculation of the hash.

15. The method of claim 11, further comprising:

using probability values of the text mode, code mode, or binary structure mode in order to determine if a shift will be made to the text mode, code mode, or binary structure mode during the non-high entropy mode.

16. The method of claim 11, further comprising:

in the non-high entropy mode, performing a hash of meta-tags of the content that are overlapped by the window.

17. The method of claim 1, wherein the fuzzy hash comprises a calculated sequence of bytes.

18. An apparatus for classifying a data object by use of a fuzzy hash, the apparatus comprising:

an engine, executed by a processor, configured to align a window in a target data object, read content within the window, hash the content within the window in order to calculate a hash value, splice a spliced portion from the hashed value; and

store the spliced portion as part of a fuzzy hash.

19. The apparatus of claim 18, wherein the engine is configured to compare the fuzzy hash with a reference fuzzy hash in order to classify the data object.

20. The apparatus of claim 18, wherein the engine is configured to store, into a buffer, a plurality of meta-tags corresponding to data blocks that are overlapped by the window, wherein a meta-tag corresponding to an associated data block.

21. The apparatus of claim 18, wherein the hash comprises a summation of contents within the window.

22. The apparatus of claim 18, wherein calculation of the hash is initiated by a trigger.

23. The apparatus of claim 18, wherein the spliced portion comprises a significant byte of the hash.

24. The apparatus of claim 18, wherein the engine is configured to determine a running entropy value for contents that are overlapped by the window, and if the running entropy value is at least at a threshold value, then shift into a high entropy mode, and if the running entropy value is below a threshold value, then shift into a non-high entropy mode.

25. The apparatus of claim 24, wherein the engine is configured to use a trigger associated with the high entropy mode, in the high entropy mode.

26. The apparatus of claim 25, wherein the trigger comprises a shift register.

27. The apparatus of claim 25, wherein the engine is configured to perform a hash of the contents that are overlapped by the window, in the high entropy mode.

28. The apparatus of claim 25, wherein the engine is configured to shift into one of a text mode, code mode, or binary structure mode, in the non-high entropy mode.

29. The apparatus of claim 28, wherein the engine is configured to use a trigger associated with the text mode in order to initiate calculation of the hash, in the text mode.

30. The apparatus of claim 28, wherein the engine is configured to use a trigger associated with the code mode in order to initiate calculation of the hash, in the code mode.

31. The apparatus of claim 28, wherein the engine is configured to use a trigger associated with the binary structure mode in order to initiate calculation of the hash, in the binary structure mode.

32. The apparatus of claim 28, wherein the engine is configured to use probability values of the text mode, code mode, or binary structure mode in order to determine if a shift will be made to the text mode, code mode, or binary structure mode during the non-high entropy mode.

33. The apparatus of claim 28, wherein the engine is configured to perform a hash of meta-tags of the content that are overlapped by the window, in the non-high entropy mode.

34. The apparatus of claim 18, wherein the fuzzy hash comprises a calculated sequence of bytes.

35. An article of manufacture, comprising:

a non-transitory computer-readable medium having stored thereon instructions to;

align a window in a target data object;

read content within the window;

hash the content within the window in order to calculate a hash value;

splice a spliced portion from the hashed value; and

store the spliced portion as part of a fuzzy hash.

36. An apparatus, comprising a processor, for classifying a data object by use of a fuzzy hash, the apparatus comprising:

means for aligning a window in a target data object;

means for reading content within the window;

means for hashing the content within the window in order to calculate a hash value;

means for splicing a spliced portion from the hashed value; and

means for storing the spliced portion as part of a fuzzy hash.