Don’t Make a Hash of Analysis, Go Fuzzy

Security Operations Center (SOC) analysts spend a lot of their time and effort trying to identify if a document has changed, possibly signifying it has been compromised. The leading method of doing so involves using a hashing algorithm.

Using hash we can tell if there has been even the slightest change to a document. But what happens when the change is insignificant or our purpose is to locate similar files that don’t have the exact same hash?

This is as thorough – and as immensely cumbersome – as it sounds. Documents can undergo many minor modifications (date change, adding a reference, text revisions, etc.) which don’t necessarily signify the document has been compromised in any way. Chasing after every hash leads SOC analysts down a rabbit hole of countless checks and swallows up huge amounts of time.

Commonly used hash functions today are highly sensitive to bitwise changes. However, malwares are usually grouped into families that include an endless number of variants. Trying to identify a malware with a hash can be like trying to find a needle in a haystack.

There is a better way that not all security analysts are aware of, but their lives could be made much easier and more effective if they did: Fuzzy Hashing.

Fuzzy hashing (a.k.a. approximate matching or similarity hashing) is a technique that’s used to identify similarities in binary data, regardless of the slight changes between them. For example, two malwares generated by the same builder, which both statically configure binary files in the same way, will have high similarity scores. While these algorithms started to gain popularity in the field of digital forensics in 2006, it was not until 2014 that the National Institute for Standards and Technologies (NIST) developed standard definitions, to be officially recognized by the industry. This method can be used to group malware, so if an analyst comes across an approximately similar type of file, they can learn about its functionality and apply appropriate detection/prevention/mitigation mechanisms.

This field is actually quite mature, and today there are a number of fuzzy hashing algorithms that have stood the test of time and usage. A great example for a scale-up usage for malware clustering using Elasticsearch was presented by Virus Bulletin, which also developed a tool for this purpose.

The approach that was recently used for validating whether a known file may have been modified, is using cryptographic hash tables of known files (e.g. NIST’s National Software Reference Library (NSRL)). The problem with this approach is comparing big hash tables consisting of one-way hashes. This situation requires a long comparing process against this list, which affects performance and seldom yields valuable results. NIST also support the use of approximate matching and significantly contributed to the research done in the field.

There are several leading types of Fuzzy Hashes available today, each of which brings to the table unique benefits. We'll be focusing on one type that stands out from the others:

• Context Triggered Piecewise Hashing (CTPH): Unlike cryptographic hashes, which are designed to test for object identity, similarity schemes seek to uncover objects that have non-trivial similarities in their bit-stream representation. In Context Triggered Piecewise Hashing (CTPH) the approach is to identify trigger points to divide a given input into chunks/blocks.

• Ssdeep: The most common example of CTPH. The concept behind ssdeep is to identify contexts within binary data and to store the sequence of hashes for each of he pieces in between contexts. Ssdeep scores range from 0, representing no similarity, to 100 being very similar. While ssdeep has gained some popularity, the fixed-size hash it produces quickly loses granularity and works for relatively small files of similar sizes.

• Sdhash: Published four years after ssdeep, Sdhash quickly overcame its predecessor. A work presented by Breitinger and Baier in 2012 shows that this algorithm is more robust and difficult to overcome than ssdeep — security wise.

• Imphash: A type of LSH that groups PE files by their import tables. A PE’s import table can tell a lot about the intention of the file, and sometimes the same sequence of imports can indicate some level of relativity.

• Locality Sensitive Hashing (or LSH): Sometimes confused with Approximate matching, LSH aims at mapping similar objects into the same bucket, used for nearest neighbor search and data clustering, while approximate matching outputs a similarity digest that is comparable. Approximate matching provides a means to assess/quantify the relationship between two files beyond same/not same.

• Virus Total: A main global source of information regarding malware identification, provides both ssdeep and imphash in its detailed report and can be used for further investigation using NIST’s Hash lists. Plus, Totalhash provides the ability to search through a VT entries DB using the imphash of a file.

These algorithms were designed to support digital investigation, but are also used for many other fields related to security, like Network traffic analysis, for identifying restricted files transfer on the network and preventing data leakage (DLP). They are also ideal for classification of malware and Biometrics identification.

These algorythms have endless potential in improving and providing more solutions in information security field, which makes them a must-have in every SOC analyst’s tool kit and assures you'll hear about it again in the future.