HEnbane: Why 2¹⁰¹ Keys Did Not Mean 2¹⁰¹ Work

Some cryptosystems are broken by a subtle improvement to a well-studied attack. GRAFHEN failed for a more instructive reason: it published millions of equations derived from a small secret tuple, then treated the number of tuples that existed before publication as evidence of security. HEnbane uses those public equations to reconstruct an equivalent key directly. It decrypts all five released challenges based on symmetric groups, with a slowest end-to-end reconstruction of about 25 seconds, and recovers the representation and labels of a later challenge over $\mathrm{SL}_2(343)$ in about 38 seconds.

The construction is easy to picture. A ciphertext is a long word such as acbbeadcadbb..., and the secret key assigns a group element to each letter. A rewriting system is just a collection of rules for replacing one string of symbols with an equivalent one: for example, a rule ab : c lets you rewrite dab as dc. GRAFHEN publishes millions of such rules, each saying that two words have the same value under the hidden assignment. These rules are meant to conceal the representation inside a large non-confluent system, but they also provide a very large set of exact constraints on the secret. HEnbane reads them as equations rather than as rewriting noise.

The technical break is only part of the lesson. GRAFHEN combines sophisticated group theory with several elementary cryptographic pitfalls: interpreting keyspace size as attack cost, treating one unsuccessful attack as positive security evidence, and responding to an implementation-specific attack by increasing the parameter that implementation happened to expose. This article explains both the attack and that methodological failure without assuming advanced group theory. The complete statements, proofs, and experimental protocol are available in the paper.

How GRAFHEN hides its key

A GRAFHEN ciphertext is a word over a small public alphabet, such as $a,b,c,d,e$. The secret key assigns a group element to each letter. In the original parameter sets these elements are permutations, so evaluating acb means composing the secret permutation for $a$, then the one for $c$, then the one for $b$. Decryption determines which subgroup or coset contains the result.

The public rewriting system contains equations between words that evaluate to the same element under the secret assignment. These equations make it possible to transform a ciphertext into many equivalent forms, which is intended to conceal the underlying representation. The system is very large and non-confluent: there is no unique reduced form that would immediately reveal what a word means. The recommended single-copy degree-11 instance contains about 22 million relations.

The recommended construction also combines two copies of the base group. Lowercase and uppercase alphabets describe the two secret tuples, while mixed relations specify how the copies interact. The associated semidirect instances contain about 44 million public relations. GRAFHEN also proposes a public-key conversion, but this changes ciphertext production rather than the secret representation or its rewriting relations.

What the 2¹⁰¹ estimate misses

For the original degree-11 parameters with five generators, GRAFHEN reports approximately

$$11!^4 \approx 2^{101}$$

equivalence classes of keys. The arithmetic is not the problem; the interpretation is. This quantity estimates the number of classes among possible generator tuples before a particular public rewriting system is fixed. An attacker receives much more than the group and the generator count: they receive millions of equations generated from one specific tuple. The Sudoku analogy is apt here. There are about $6.7\times10^{21}$ completed Sudoku grids, but the cost of solving a published puzzle is not the cost of enumerating all grids because the clues drastically constrain the answer. GRAFHEN’s relations are its clues.

Under the same isomorphism hypothesis used in GRAFHEN’s key analysis, a fixed publication is particularly restrictive. Every generating tuple that satisfies all its public relations is obtained from the secret tuple by an automorphism of the target group. For a symmetric group of degree other than six, this is essentially a consistent renaming of the points on which all secret permutations act. The written tuple changes, but its relations and decryption behavior do not.

This changes the meaning of the key count. Uniformly sampling complete tuples and testing them against the publication would indeed take about $2^{101}$ trials in expectation. That is an upper bound for a blind search that deliberately ignores the structure of the equations. It is neither a lower bound on reconstruction nor an estimate of the cost of a relation-guided algorithm. The relevant security question is therefore not how many key classes existed before publication, but how difficult it is to recover any compatible representation from the published relations.

The Zauberlehrling problem

There is a broader design failure behind this calculation. I think of it as the Zauberlehrling problem: mathematical sophistication can too easily be mistaken for cryptographic evidence. A construction may use deep and correct mathematics while still failing for reasons that are basic from an adversarial perspective. Knowing a great deal about groups is not the same skill as knowing what constitutes evidence for the security of a cryptosystem.

HEnbane illustrates why this distinction matters. The attack did not require a deeper classification theorem or a more sophisticated understanding of the target groups. It required asking what information the public relations reveal, whether the advertised key count survives conditioning on that information, and whether an equivalent representation is already enough to decrypt. Those are cryptanalytic questions, and they cut across the mathematical sophistication of the construction.

The distinction is especially important for an ambitious claim such as noise-free FHE. Avoiding the noise-management machinery of lattice-based schemes would be a major advantage, so the evidentiary standard should be stronger, not weaker. Mathematical elegance, the authority of experts, and the apparent complexity of a presentation cannot replace a reduction to a clearly stated hard problem or a falsifiable average-case reconstruction assumption.

Remarkably, the GRAFHEN paper contains much of its own diagnosis. It analyzes key equivalence, explains the role of automorphisms, and reports an unsuccessful Todd-Coxeter experiment that tries to classify ciphertexts without recovering a key. Because that experiment did not break a semidirect instance above degree 7, the paper presents key recovery as the significantly harder problem. HEnbane attacks exactly that supposedly harder problem: it reconstructs an equivalent key and decrypts the recommended instances in seconds. A failed attack only rules out that attack; it cannot establish that another attack target is hard. The first practical HEnbane break (which was based on a custom CDCL solver) took days rather than years and ran on one high-end desktop rather than specialist hardware. The security argument had identified the relevant risk, but drew the wrong conclusion from the available evidence.

How HEnbane reconstructs a representation

HEnbane treats the rewriting rules as equations over complete group elements. It first derives a manageable collection of short consequences from the public relations. Individual rules are designed to avoid obvious simplifications, but different rules can interact: if they imply $ABCDX=ABY$, group cancellation gives the much more useful equality $CDX=Y$. The extraction is deliberately incomplete, but every retained consequence is valid.

The attack then searches for two generator values while removing choices that differ only by a symmetry of the target group. Once those seeds are fixed, the short equations determine the remaining generators one after another. In the two-copy construction, the mixed public relations align the second tuple with the first rather than leaving an independent recovery problem. For the supplied instances, this is enough to reconstruct both copies without a large unstructured search.

Finally, every candidate is checked against the complete publication, not only the shortened relation set used during search. It must generate the intended target group and satisfy all internal and mixed relations; labelled ciphertexts are verified separately. The implementation contains a complete fallback for instances where the two-seed propagation stops early, but that machinery is not needed for any of the reported challenges. The paper gives the full algorithm and its completeness bounds.

Why an equivalent representation is sufficient

HEnbane generally recovers an equivalent key rather than the literal secret tuple. Consistently renaming the points changes the written permutations but preserves every relation and transports the subgroup structure used for decryption. The recovered tuple can therefore recognize zero exactly as the secret tuple does. More generally, even a simpler homomorphic image is enough if it preserves the zero/nonzero distinction, so a repair must prevent more than literal recovery of the intended key.

Fresh encryptions of zero then give a direct CPA distinguisher without first recovering the complete hidden zero subgroup. Under independent, matched sampling, the target alone guarantees distinguishing advantage greater than one half after 14 zero queries at degree 7 and 26 at degree 11; the benchmark’s smaller masking subgroup reduces this to 10. In the paper’s advantage normalization, exceeding one half corresponds to a guessing success probability above $75\%$ for a uniform challenge bit. The paper gives the precise criterion and finite-sample proof.

Experimental results

The following table reports mean end-to-end reconstruction times over ten runs on an AMD Ryzen 9 9950X. The symmetric instances used 30 search workers and the matrix challenge used one. These measurements include loading the instance, preprocessing, reconstruction, coupling, central lifting where applicable, and writing the solution. The independent complete-corpus verification pass was timed separately.

Target	Construction	Public relations	Result	Mean time
$S_7$	Single copy	42,137	Decrypted	0.12 s
$S_7$	Two copies	83,586	Decrypted	0.52 s
$S_{11}$	Single copy	22,000,002	Decrypted	22.41 s
$S_{11}$	Two copies	44,608,403	Decrypted	25.41 s
$S_{11}$	Public-key variant	44,608,403	Decrypted	25.44 s
$\mathrm{SL}_2(343)$	Author-supplied challenge	39,285,006	Representation and labels recovered	37.66 s

The verifier checked every public relation and every labelled word. No exact generator orders were supplied to the attack. The results establish a practical break of all five released symmetric challenges, including the originally recommended degree-11 semidirect construction and its public-key variant.

These are measured attacks rather than an asymptotic theorem about every possible key, but that qualification should not obscure the practical conclusion. Every released symmetric challenge, including the recommended construction and its public-key variant, is broken, and the result extends to independently generated degree-11 keys (Maverick). GRAFHEN has not demonstrated a credible path to secure parameters within the current design; doing so would require a structural redesign and a new security assumption, not merely a larger instance.

The revised projective-linear challenge

The July revision of GRAFHEN proposes $\mathrm{PSL}_2(343)$ as a new target. Its analysis of an earlier HEnbane prototype substituted the natural permutation degree 344 into that solver’s point-by-point worst-case bound, giving an estimate of the form $2^{1720}$. This bound described the data representation and branching strategy of an earlier implementation, not an inherent cost of reconstruction in the abstract group.

The current HEnbane backend represents elements by compact projective matrices and performs the expensive search directly in $\mathrm{PSL}_2(343)$. The challenge supplied by the GRAFHEN authors uses exact equalities in the central cover $\mathrm{SL}_2(343)$, where a projective matrix has two lifts differing by a sign. HEnbane first reconstructs both generator tuples in the quotient and aligns them through the mixed relations. It then recovers the ten missing signs by solving a linear system over $\mathbb F_2$ and verifies the lifted tuple against all 39,285,006 exact relations.

The projective orbit search takes about 3.45 seconds, while the complete end-to-end run takes about 37.7 seconds. The degree-344 action is constructed only after recovery for an independent generation test and is not used during the search. This experiment shows that the earlier degree-based estimate does not describe this supplied instance.

The supplied labels do not form a valid GRAFHEN encoding of a bit: class 0 is represented by $I$ and class 1 by $-I$, which become the same element in $\mathrm{PSL}_2(343)$; retaining the sign in $\mathrm{SL}_2(343)$ makes the class-1 representative central, conflicting with a requirement proved by GRAFHEN itself. This limits the interpretation of the labels as a complete revised FHE instantiation, but it does not diminish the reconstruction result. The GRAFHEN authors supplied this challenge specifically to obtain an implementation result for the revised target, and HEnbane reconstructs the exact $\mathrm{SL}_2(343)$ representation in the form provided, recovers the central labels, and verifies every public relation. The experiment therefore directly answers the practical reconstruction question posed by the challenge.

What went wrong and what a repair requires

The main issue is the gap between counting possible keys and analyzing a fixed public presentation. The public rules are not passive obfuscation: they are a structured system of constraints on a small number of unknown group elements. Automorphisms reduce the meaningful search space, short consequences force generators, and the mixed rules align the two internal copies. Increasing the number of published relations can strengthen these effects as well as increase storage and evaluation costs.

Changing the group or increasing its representation degree may raise the cost of a particular implementation, but it does not remove the fixed-presentation result under the isomorphism hypothesis. Likewise, changing the masking sampler does not prevent representation recovery and only changes the distribution used by the subsequent distinguishing step. A revised security argument must address relation-guided reconstruction rather than compare parameters with the worst-case bound of one solver.

A structural repair would need to abandon the isomorphic-presentation setting, for example by giving the secret evaluation map a nontrivial kernel. Even this is not sufficient on its own: the public presentation must make it hard to construct every efficiently represented finite image that preserves the zero/nonzero distinction. That requirement should be stated as a falsifiable average-case assumption and evaluated together with practical key generation, public-key size, homomorphic evaluation, and reconstruction experiments.

The relevant question is no longer whether every conceivable output of the key generator has been individually broken. Cryptographic proposals are deployed from concrete parameter recommendations and justified by a security argument. Here the recommended instances fall in seconds, independently generated keys fall to another method, the proposed replacement target does not stop representation recovery, and no reconstruction-hardness assumption explains why scaling should reverse that pattern. Taken together, this is strong evidence that the current cryptosystem is not viable.

HEnbane’s implementation and reproducible artifacts are available on GitHub. The full paper contains the formal reconstruction results, the exact zero-predicate criterion, the finite-sample security bound, and the complete experimental details.