Concealing targeted attacks on the TLSH similarity digest scheme

Concealing targeted attacks on the TLSH similarity digest scheme

Speakers: Gábor Fuchs, Doctoral researcher, Budapest University of Technology and Economics

Conference: DFDS

YouTube: https://www.youtube.com/watch?v=0HMHcPbfeb0

Overview

In the realm of digital forensics and malware analysis, similarity digest schemes, often referred to as fuzzy hashes, play a crucial role in identifying and classifying related files. Unlike traditional cryptographic hashes, which produce vastly different outputs for even minor input changes, fuzzy hashes are designed to generate similar outputs for similar inputs, enabling the detection of approximate matches. This talk, presented by Gábor Fuchs, a doctoral researcher at the Budapest University of Technology and Economics, delves into a significant vulnerability within one of the most widely used fuzzy hashing algorithms: TLSH (Trend Micro Locality Sensitive Hash).

Fuchs's research demonstrates that TLSH, despite its perceived robustness against natural mutations, is highly susceptible to targeted attacks. These attacks involve crafting minimal modifications to a file that either evade detection (anti-blacklisting) or masquerade as benign (anti-whitelisting) by manipulating the resulting TLSH hash. The core innovation presented in this talk addresses a critical weakness of previous attack methodologies: the reliance on modifying unused regions of a file, which defenders could easily detect and mitigate. Fuchs introduces novel techniques to disguise these malicious modifications as legitimate machine code, making them significantly harder for defenders to identify and neutralize. This research has profound implications for the security tools that rely on TLSH, such as those used by VirusTotal, highlighting an urgent need for more resilient similarity digest schemes.

Background

▶ Watch: Introduction to Similarity Digest Schemes and TLSH (0:00)

The concept of similarity digest schemes emerged to address limitations of traditional cryptographic hashes in scenarios requiring approximate matching. Cryptographic hashes, like SHA-256, are excellent for verifying exact file integrity, where any single bit flip results in a completely different hash. However, in contexts like malware analysis, where variants of a malicious program might differ by only a few bytes (e.g., in compiler artifacts, obfuscation techniques, or minor feature additions), cryptographic hashes fail to link these related samples. Fuzzy hashes, on the other hand, produce a digest where the similarity between two digests directly correlates with the similarity of their original inputs. This property allows for a difference score to be calculated between two digests, indicating their degree of resemblance.

This capability underpins two primary application classes: fuzzy blacklisting and fuzzy whitelisting. In fuzzy blacklisting, systems can identify and reject files that are similar to known malicious artifacts, even if they aren't exact matches. This is invaluable in malware detection, where polymorphic variants are common. Conversely, fuzzy whitelisting allows for the acceptance of files similar to known benign ones, aiding in filtering out legitimate software. Other applications include digital forensics, where analysts can quickly pre-select interesting artifacts similar to previously identified ones, and malware classification, where clustering similar samples helps in identifying malware families. The efficacy of all these applications hinges on the assumption that attackers cannot easily manipulate these schemes to achieve desired outcomes.

TLSH stands as one of the most prominent and widely adopted similarity digest schemes, often employed in large-scale systems like VirusTotal for binary and malware analysis. It was designed to be robust against "natural or random mutations"—unintentional changes that might occur during compilation or minor code adjustments. However, Fuchs's prior work (dating back two years) established that TLSH is vulnerable to targeted attacks. These earlier attacks, described in the speaker's previous publications, demonstrated how an attacker could make minimal, behavior-preserving modifications (typically 1-10% of the file) to achieve an anomalous difference score.

The previous attack framework comprised three general steps:

1. Identify modifiable areas: Locate regions within a file, particularly ELF binaries (Linux executables), that can be altered without affecting the program's runtime behavior. These often include unused padding bytes or sections not loaded into memory.
2. Determine bucket count goals: Based on how TLSH internally processes data into "buckets," define target ranges for these bucket counts to force a desired change in the final digest.
3. Craft byte sequences: Generate specific byte sequences to insert into the modifiable areas, aiming to hit the predetermined bucket count goals.

The anti-blacklisting attack aimed to increase the difference score between an original malicious file and its modified version, making the modified version appear dissimilar to the original and thus evade detection. The anti-whitelisting attack, conversely, sought to achieve a low difference score, ideally a complete digest collision, where a modified malware sample would appear identical to a known benign binary. This would allow malware to masquerade as legitimate software.

A critical weakness of this earlier approach, however, was its reliance on modifying unused regions of the file. As Fuchs points out, a sophisticated defender could easily counter this by detecting such unused regions and either zeroing them out or excising them before calculating the TLSH hash. This vulnerability provided a clear path for defenders to invalidate the attack. The current research specifically addresses this defensive countermeasure by developing methods to disguise the attack sequences as legitimate components of the binary.

Key Findings

▶ Watch: Overview of previous anti-blacklisting and anti-whitelisting attacks (4:20)

The central and most significant finding of this research is that TLSH remains insecure even when attackers are constrained by syntactic requirements for their modifications. Specifically, Gábor Fuchs demonstrates that attack sequences can be successfully disguised as valid machine code, rendering the defender's strategy of sanitizing unused file regions ineffective. This means an attacker can still achieve their anti-blacklisting or anti-whitelisting goals while making their modifications appear as integral, executable parts of the binary.

The solution to disguising attack sequences involves two primary challenges, each with novel contributions:

1. Claiming executable space: The researchers developed methods to ensure the crafted attack sequence resides within an executable memory region. This was achieved through two distinct strategies:

• Extending an existing segment: By leveraging slack spaces in memory (even if not explicitly present in the file) and manipulating the file-to-memory mappings, the attack sequence can be appended to an existing executable segment. This strategy proved highly successful.
• Adding a completely new segment: This involves inserting a new entry into the binary's program header table, effectively creating a new executable region. While more challenging due to the need for a "useless" existing entry, it offers greater flexibility in terms of space allocation.

1. Generating valid machine code: The existing greedy generation algorithm for crafting attack byte sequences was extended to incorporate rules for generating syntactically valid instructions. Focusing on ARM instructions relevant to IoT malware, the modified algorithm now checks if a chosen byte would make the current 4-byte instruction invalid and, if so, rejects it and backtracks. This ensures the injected bytes form legitimate machine code.

The evaluation of these techniques yielded compelling results:

• The extending segment strategy achieved an 84% success rate for the anti-blacklisting attack and an impressive 72% success rate for the more challenging anti-whitelisting attack (aiming for near-total collisions with benign GCC output).
• The new segment strategy, while less successful overall (2.49%), was limited by the rarity of suitable "useless" entries in the program header table, rather than a fundamental flaw in the technique.
• Crucially, the overhead introduced by generating valid ARM instructions was minimal, increasing the attack sequence size by only 2%. This demonstrates that the syntactic constraints do not significantly impede the attack's efficiency.

These findings collectively underscore a critical vulnerability in TLSH: its inability to withstand targeted, stealthy modifications that mimic legitimate code. The research effectively neutralizes a key defensive countermeasure and necessitates a re-evaluation of how fuzzy hashing is employed in security-sensitive applications.

Technical Deep Dive

▶ Watch: Technical challenge: Claiming executable memory space for code (8:20)

The technical foundation of this research builds upon an understanding of how TLSH operates and then systematically subverts its mechanisms through carefully crafted modifications.

At a high level, TLSH processes an input file (e.g., a binary) by using a sliding window. From each position of this window, it extracts certain features. These features are then mapped to a fixed number of hash buckets. Instead of storing the features directly, TLSH only stores the counts of how many features mapped to each bucket. This array of bucket counts forms the basis for constructing the final digest. The similarity between two TLSH digests is then determined by comparing these bucket count arrays.

The speaker's previous generalized attack framework aimed to manipulate these bucket counts.

1. Identifying modifiable areas: For ELF binaries, these often include .note sections, .comment sections, or padding bytes between segments that are not loaded into executable memory or are ignored by the loader. The key is that changes in these regions do not alter the program's behavior.
2. Determining bucket count goals: By analyzing how specific byte sequences impact the bucket counts, the attackers can define target intervals for each bucket. The goal is to shift the distribution of counts in a way that leads to the desired difference score (high for anti-blacklisting, low for anti-whitelisting).
3. Crafting byte sequences: The original framework used a greedy generation algorithm. This algorithm iteratively selects the next byte to insert into the modifiable region. At each step, it evaluates which byte, when added, moves the current bucket counts closest to their predefined goals.

The new contribution in this work centers on disguising these attack sequences as legitimate machine code, thereby overcoming the "zeroing out unused regions" defense. This involves two major technical challenges:

Challenge 1: Claiming Executable Space

To make the injected bytes appear as legitimate code, they must reside within memory regions marked as executable. The speaker explored two strategies:

Strategy A: Extending an Existing Segment

This approach involves appending the attack sequence to an existing executable segment (e.g., the .text section). The primary constraint here is that modifying the size or offset of an existing segment in the file can cascade into breaking the binary, as other parts of the file (and their memory mappings) would shift.

The solution leverages the distinction between file content and memory image:

• The attack sequence is added to the end of the file.
• The p_filesz (file size) field of the target executable segment's program header table entry is increased to include the size of the attack sequence.
• Crucially, the p_memsz (memory size) field is also increased. This ensures that when the segment is loaded into memory, the new attack sequence is mapped into executable memory.
• To avoid breaking existing offsets, the p_offset of the segment is kept unchanged. This means the attack sequence might be physically distant from the original segment content in the file, but it will appear contiguous in memory after the original segment's content. This "hacking" of mappings requires careful manipulation of p_filesz and p_memsz to ensure the memory image remains consistent for the legitimate parts of the binary while incorporating the attack code. This strategy relies on finding "slack spaces" in the memory layout, which often exist after legitimate segments.

Strategy B: Adding a Completely New Segment

This strategy offers more control over the size and placement of the attack sequence. It involves adding a new entry to the program header table (PHT). The PHT is a critical structure in ELF binaries that describes how different parts of the file should be loaded into memory.

• Adding a new entry is problematic because the PHT is typically a fixed-size array, often located between other critical data structures. Shifting these structures to accommodate a new PHT entry would almost certainly break the binary.
• The solution: Identify a "useless" or unused entry within the existing PHT. Sometimes, compilers or linkers might leave placeholder entries, or an entry might point to a non-existent or irrelevant segment. If such an entry is found, it can be overwritten with a new program header entry that points to the attack sequence.
• This new entry would define a new executable segment, specifying its p_offset (where the attack sequence is in the file), p_filesz, p_memsz, and p_flags (setting the executable bit). This provides a clean way to allocate a dedicated executable region for the attack code. However, the rarity of "useless" PHT entries makes this strategy less broadly applicable.

Challenge 2: Generating Valid Machine Code

Once executable space is claimed, the next challenge is to ensure the bytes injected into this space form syntactically valid machine code. The scope of this work focused on ARM instructions, commonly found in IoT malware.

• The existing greedy generation algorithm was adapted. Instead of simply picking the byte that best optimizes bucket counts, an additional validation step was introduced.
• ARM instructions are typically 4 bytes long and must be 4-byte aligned. The algorithm considers a 4-byte chunk at a time.
• When the greedy algorithm proposes a byte, it first checks if this byte, in conjunction with the preceding bytes in the current 4-byte instruction slot, would lead to an invalid ARM instruction.
• If the byte would make the instruction invalid, it is rejected. The algorithm then backtracks, trying other bytes until a valid one is found or it determines no valid instruction can be formed from the current state.
• This iterative process, guided by bucket count optimization but constrained by instruction validity rules, ensures that the final attack sequence is both effective in manipulating TLSH and syntactically legitimate ARM machine code. The speaker reported that this additional complexity only increased the attack sequence size by a marginal 2%, indicating its efficiency.

By solving these two challenges, the research presents a robust method for concealing targeted TLSH attacks, making them significantly harder for static analysis tools to detect based on simple modification patterns.

Demo / Proof of Concept

▶ Watch: Generating valid ARM machine code for attack sequences (10:50)

While the talk did not feature a live demonstration, the research meticulously evaluated the proposed attack framework against a substantial dataset, serving as a comprehensive proof of concept. The evaluation aimed to quantify the success rates of both anti-blacklisting and anti-whitelisting attacks when constrained by the requirement to generate valid machine code and claim executable space.

The evaluation set comprised 2,000 ARM malware samples, reflecting the speaker's focus on IoT malware. For each sample, the framework attempted to perform the attacks using the newly developed techniques.

For the anti-blacklisting attack, the goal was to achieve a difference score of at least 86 between the original and modified malware. A difference score of 86 is specifically recommended by the authors of TLSH for distinguishing binaries, making it a challenging but realistic target for evasion.

For the anti-whitelisting attack, the objective was even more ambitious: to achieve an "almost total hash collision" with a known benign binary. The chosen benign target was a GCC compiler output for the same ARM architecture, representing a common and unequivocally legitimate executable. This scenario tests the attacker's ability to completely masquerade malicious code as benign.

The results, broken down by the strategy used to claim executable space, were highly revealing:

Extending Existing Segment Strategy

This strategy, which involves appending the attack sequence to an existing executable segment and manipulating file-to-memory mappings, proved remarkably successful:

• Anti-blacklisting attack: Achieved a success rate of 84%. This high rate indicates that attackers can reliably make their malware appear sufficiently dissimilar to its original form, bypassing fuzzy blacklists.
• Anti-whitelisting attack: Achieved a success rate of 72%. Even for the more difficult task of forging near-total hash collisions with benign software, the framework was highly effective.
• Fuchs noted that many of the failed cases were attributable to "really weird malware files" with unusual and often malformed binary structures, such as illegal segments, segments loading data from beyond the file's end, or overlapping segments. These anomalies made it impossible for the patching framework to guarantee binary integrity.

Adding New Segment Strategy

This strategy, which requires identifying and overwriting a "useless" entry in the program header table, had a significantly lower success rate:

• Overall success rate: Only 2.49%.
• This low success rate is primarily due to the inherent rarity of "useless" program header entries in real-world binaries, rather than a lack of efficacy in the technique itself. When such an entry was found, the strategy was effective, but its applicability is limited by the target binary's structure.

A crucial additional measurement was the overhead in attack sequence size caused by the constraint of generating valid ARM instructions. The evaluation found this overhead to be only 2% more compared to generating arbitrary bytes. This demonstrates that the syntactic validity requirement does not significantly increase the attack's footprint or complexity, making it a highly practical approach for attackers.

In summary, the evaluation serves as a robust proof of concept, demonstrating that targeted TLSH attacks are highly effective even when forced to inject valid machine code into executable regions. The high success rates, coupled with minimal overhead, highlight the severity of this vulnerability for any system relying on TLSH for security-critical functions.

Defensive Implications

▶ Watch: Conclusion: TLSH insecurity and future research (14:10)

The findings presented by Gábor Fuchs carry significant and concerning implications for cybersecurity defenders who rely on TLSH and similar fuzzy hashing schemes for malware detection, digital forensics, and threat intelligence. The research effectively neutralizes previous defensive countermeasures and demands a fundamental re-evaluation of how these tools are used.

Firstly, the most immediate implication is that defenders can no longer rely on detecting modifications in unused file regions. The previous strategy of "zeroing out" or "cutting out" identified unused sections before calculating a TLSH hash is now rendered ineffective. Attackers can embed their hash-manipulating sequences directly into executable memory, disguised as legitimate machine code. This forces defenders to confront the possibility that seemingly valid code within a binary might, in fact, be an artifact of a targeted attack designed to fool similarity algorithms.

Secondly, the core premise of fuzzy hashing for robust security, particularly against sophisticated adversaries, is significantly weakened. If an attacker can reliably produce a variant of malware that generates a high difference score (anti-blacklisting) or a near-total hash collision with a benign binary (anti-whitelisting), then existing blacklists and whitelists based on TLSH become unreliable. This directly impacts:

• Malware detection systems: They may fail to identify known malware families if variants are crafted to evade TLSH.
• Threat intelligence platforms: The ability to accurately cluster and classify malware families based on TLSH similarity is compromised.
• Digital forensics: The rapid pre-selection of interesting artifacts based on similarity to known malicious files becomes less trustworthy.

Thirdly, this research highlights the need for more robust similarity digest schemes. As Fuchs mentioned, his future work involves creating new schemes that are inherently more resilient to these types of targeted attacks. Until such schemes are widely adopted, defenders must acknowledge the limitations of current fuzzy hashing algorithms.

Defenders should consider the following actionable strategies:

• Layered Security: Do not rely solely on fuzzy hashing for critical security decisions. Integrate it with other detection mechanisms such as dynamic analysis (sandboxing), behavioral analysis, heuristic scanning, and more advanced static analysis that understands program semantics rather than just byte patterns.
• Enhanced Static Analysis: Develop or employ static analysis tools that can identify unusual code patterns, even within seemingly valid machine code. This might involve looking for code sections that are never executed, unusual control flow graphs, or code that doesn't align with compiler output conventions.
• Focus on Runtime Behavior: Shift emphasis towards analyzing the runtime behavior of executables. If a file exhibits malicious behavior, its TLSH hash value becomes secondary to its actions.
• Integrity Checks: Implement more stringent integrity checks that go beyond simple hash comparisons. This could involve cryptographically signing legitimate binaries and verifying these signatures, or employing more advanced attestation mechanisms.
• Contextual Analysis: Treat TLSH scores as one data point among many. Correlate TLSH similarity with other indicators, such as file origin, execution environment, network activity, and system changes. An anomalous TLSH score, even if it appears to evade detection, might still be suspicious when combined with other contextual factors.
• Regular Algorithm Review: Security researchers and practitioners should continuously review and challenge the robustness of widely used security algorithms like TLSH against novel attack vectors.

In conclusion, the research serves as a stark warning: TLSH, while useful, is not a silver bullet against sophisticated adversaries. Defenders must adapt by adopting multi-faceted detection strategies and pushing for the development of next-generation similarity digest schemes that can withstand these advanced, camouflaged attacks.

Key Takeaways

• TLSH is vulnerable to targeted attacks: Despite its robustness against natural mutations, TLSH can be manipulated by attackers to achieve desired hash outcomes, even when modifications are constrained.
• Attackers can disguise modifications as legitimate code: The research demonstrates that malicious byte sequences can be embedded within executable memory regions and crafted to appear as syntactically valid ARM machine code.
• Two primary strategies for code injection: Attackers can either extend existing executable segments by manipulating file-to-memory mappings or, less commonly, add entirely new segments by overwriting "useless" entries in the program header table.
• High success rates with minimal overhead: The framework achieved 84% success for anti-blacklisting and 72% for anti-whitelisting attacks against ARM malware, with the overhead for generating valid machine code being only 2% of the attack sequence size.
• Reliance on unused regions is no longer a defense: The ability to disguise attacks as legitimate code renders previous defensive strategies, such as zeroing out unused file regions, ineffective against sophisticated adversaries.
• Urgent need for more robust fuzzy hashing: The findings highlight that current similarity digest schemes like TLSH are insufficient for robust security against targeted attacks, necessitating the development of next-generation algorithms.

About the Speaker(s)

Gábor Fuchs is a doctoral researcher at Cry's lab, part of the Budapest University of Technology and Economics. Although he presented this research during his first semester as a PhD student, he emphasized that this work represents a continuation of research he had been conducting for multiple years, including throughout his Master of Science studies. His academic focus is on understanding and improving the security of similarity digest schemes, initially by identifying their vulnerabilities and, in his future work, by developing more resilient algorithms.