Cryptanalysis on the HHSS Obfuscation Arising From Absence of Safeguards

Jung Hee Cheon, Minki Hhan, Jiseung Kim, Changmin Lee

TL;DR

This paper presents a novel polynomial-time attack that can distinguish between obfuscated programs generated by the HHSS obfuscator, even when those programs are functionally equivalent. This attack exploits a weakness in the HHSS construction related to the "left kernel" of branching program matrices, demonstrating that HHSS fails to achieve the promised indistinguishability obfuscation for general-purpose programs.

What Problem Does This Paper Address?

Software obfuscation aims to protect intellectual property by making it difficult to reverse-engineer a program. Indistinguishability Obfuscation (iO) is a theoretical ideal for obfuscation, guaranteeing that two functionally equivalent programs, when obfuscated, are computationally indistinguishable to an adversary. This property has significant implications for secure computation, functional encryption, and deniable encryption.

Recently, the HHSS obfuscator, based on graded encoding schemes and matrix branching programs, was proposed as a state-of-the-art implementation. However, prior work has shown that many iO candidates are vulnerable to cryptanalysis. This paper addresses the question of whether the HHSS obfuscator, particularly its implementation for general-purpose programs, truly achieves indistinguishability, or if it suffers from similar vulnerabilities. The authors specifically investigate if functionally equivalent programs can be distinguished after being obfuscated by HHSS.

Methods

The core of the attack relies on the concept of the "left kernel" of a matrix. A left kernel vector v of a matrix M is a non-zero vector such that v * M = 0. The authors leverage the fact that the HHSS obfuscator uses matrix branching programs (BPs) and a graded encoding scheme.

The attack proceeds as follows:

  1. Identify Functionally Equivalent Programs: The authors consider two functionally equivalent read-once branching programs, P and P', represented by matrices {Mi,b} and {Ni,b} respectively.
  2. Exploit Left Kernel: They identify a short vector v that is in the left kernel of a matrix from P (e.g., v * M1,1 = 0) but not in the left kernel of the corresponding matrix from P' (e.g., v * N1,1 != 0). This is possible because functionally equivalent BPs can still have different matrix structures.
  3. Evaluate Obfuscated Program: The obfuscated program O(P) is essentially an encoded representation of the BP. The attack involves multiplying the left kernel vector v with the encoded matrices derived from the obfuscated program.
  4. Distinguish Based on Norm: Due to the properties of the graded encoding scheme and the left kernel vector, the norm (size) of the resulting vector after this multiplication will be significantly different depending on whether the obfuscated program originated from P or P'. Specifically, if the obfuscated program is from P, the norm will be small; if it's from P', the norm will be large. This difference allows an adversary to distinguish between the two obfuscated programs.

The attack is shown to be effective even when dealing with "evasive functions," which are programs that output a specific value (e.g., 0) with high probability. The authors also analyze how their attack applies to variants of HHSS obfuscation with added safeguards like scalar bundling and bookend vectors.

Datasets

Not discussed in the paper. The paper focuses on theoretical cryptanalysis and does not use specific datasets for evaluation. Instead, it uses abstract representations of branching programs and their obfuscations.

Key Insights and Ideas

  • Left Kernel as a Weakness: The most significant insight is that the left kernel of the underlying branching program matrices provides a critical vulnerability in the HHSS obfuscation scheme. This is a structural property that the obfuscation process fails to hide effectively.
  • Distinguishing Evasive Functions: The attack's applicability to obfuscated evasive functions is particularly noteworthy. Evasive functions are often considered harder to attack because it's difficult to obtain "encodings of zero" from their honest evaluations. This attack bypasses that difficulty by directly using the structural properties of the BP.
  • Simplicity of the Attack: The attack's core idea is relatively simple: find a vector that "annihilates" a part of one BP but not the other, and then use this vector to probe the obfuscated program.
  • Impact on iO Security: The paper demonstrates that HHSS, despite its claims, does not achieve general-purpose indistinguishability obfuscation, as functionally equivalent programs can be distinguished.

Key Results

  • The paper presents a polynomial-time distinguishing attack on the HHSS obfuscation scheme.
  • The attack can distinguish between obfuscated versions of functionally equivalent read-once branching programs.
  • The attack is effective even when the obfuscated programs correspond to evasive functions.
  • The authors show that variants of HHSS obfuscation with scalar bundling and bookend vectors are also distinguishable using similar techniques.
  • The attack is not applicable to GGH15 BP obfuscation with all safeguards, leaving that as an open problem.

Limitations and Future Work

  • Limited to Read-Once BPs: The presented HHSS construction and the attack are primarily focused on read-once branching programs. The paper mentions that HHSS removes "scalar bundling," which is relevant for more complex BPs.
  • Safeguards: While the paper analyzes some safeguards (scalar bundling, bookend vectors), it acknowledges that distinguishing GGH15 obfuscations with all safeguards remains an open problem. This suggests that more sophisticated obfuscation techniques might still be secure against this specific attack.
  • Specific Encoding Scheme: The attack is tailored to the GGH15 graded encoding scheme used in HHSS. It's not immediately clear if it generalizes to other iO constructions based on different underlying primitives.
  • Future Work: The authors explicitly state that distinguishing GGH15 obfuscations with all safeguards is an open problem, indicating a clear direction for future research. Further investigation into how to break these more robust obfuscations would be valuable.

Summary updated

BibTeX
@article{cheon2018cryptanalysis,
  author = {Jung Hee Cheon and Minki Hhan and Jiseung Kim and Changmin Lee},
  title = {{Cryptanalysis on the HHSS Obfuscation Arising From Absence of Safeguards}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}

Loading related content...

Figure