In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This complete...
In this post I want to revisit an observation from years ago that seems to address K4 directly. It begins with a simple experiment: split the K4 ciphertext at every W. Once you do that, an unexpected frequency pattern emerges. A related discussion can be found in [1]
For a quick introduction, I put together a short video that explains the basic idea behind this “W-splitting” approach.
Collection of Facts
So, actually there are some surprising facts that come together here.
-
The letter 'W' is distributed in such a way that K4 can be split into blocks of a reasonable length.
OBKR UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO TWTQSJQSSEKZZWATJKLUDIAWINFBNYP VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAREach of the blocks has a suitable length to contain one or more english words.
B1 = OBKRUOXOGHULBSOLIFBB B2 = FLRVQQPRNGKSSOT B3 = TQSJQSSEKZZ B4 = ATJKLUDIA B5 = INFBNYPVTTMZFPK B6 = GDKZXTJCDIGKUHUAUEKCAR
-
Using 'W' as the splitting indicator removes one letter completely from the ciphertext. This leaves us with an alphabet of size 25. This may be suitable for some suggested approaches, such as using Polybius squares, but may cause problems for others.
-
The known plaintext clues fit perfectly into the blocks without overlapping. Hence the blocks probably also reveal word boundaries, if we assume that words dont fall into two different blocks.
B1 = OBKRUOXOGHULBSOLIFBB B2 = EASTNORTHEASTOT B3 = TQSJQSSEKZZ B4 = ATJKLUDIA B5 = INFBBERLINCLOCK B6 = GDKZXTJCDIGKUHUAUEKCAR
You could speculate the "OT" after "EASTNORTHEAST" perhaps is "OF" or "TO" and the form letters "INFB" before "BERLINCLOCK" maybe something like "FROM".
-
The six blocks are arranged into two groups but not arbitrarily, but based on their parity.
Group 1 B1 = OBKRUOXOGHULBSOLIFBB B3 = TQSJQSSEKZZ B5 = INFBNYPVTTMZFPK Group 2 B2 = FLRVQQPRNGKSSOT B4 = ATJKLUDIA B6 = GDKZXTJCDIGKUHUAUEKCAR
-
The two groups have the same number of letters (46), which is necessary for the most prominent feature: the frequency distribution of the letters in the two blocks is identical.
Letter frequency - Group 1
Letter frequency - Group 2
The labels differ, but the histogram shape is exactly the same in both groups.
Speculations
So how could such a pattern arise? Whatever the explanation is, it does not look like the accidental by-product of an ordinary cipher. Standard substitutions, transpositions, or Vigenère-like methods can certainly produce local irregularities, but they do not naturally produce two parity-based groups of equal length that also share an identical frequency profile after splitting on a single letter. That does not rule such methods out completely, but it strongly suggests that some additional organizing rule is present.
I asked Sanborn if he was surprised that K4
has remained unsolved for 35 years.
He was not. The K4 code was devised “in collaboration
with a cryptographer who encrypts national
security secrets”, Sanborn said.
I asked if a solution existed at all. What better way to ensure the long shelf life of a cipher and there- fore a sculpture? What cleverer bit of conceptual art at the heart of the American intelligence com- munity? He shrugged this off.
“It is a solid system, and I fucked with it.”
“What do you mean you fucked with it?”
“I can’t say.”
Interview Jim Sanborn - Financial Times Weekend
I asked if a solution existed at all. What better way to ensure the long shelf life of a cipher and there- fore a sculpture? What cleverer bit of conceptual art at the heart of the American intelligence com- munity? He shrugged this off.
“It is a solid system, and I fucked with it.”
“What do you mean you fucked with it?”
“I can’t say.”
Interview Jim Sanborn - Financial Times Weekend
This statement—“It is a solid system, and I fucked with it.”—has always stood out to me. It suggests that K4 may not be based on a fundamentally new cipher, but rather on a known, “solid” construction that was deliberately altered. In other words: the difficulty might not come from the core method itself, but from the way it has been modified.
You can easily take a solid system then "fuck with it" - i.e. change/tweak it in some direction - to make a new or even (in your eyes) harder system. And that kind of modification can go in very different directions. Starting from a sound system, even small tweaks can have disproportionate effects:
- The system may become unintentionally weaker
- The system may lose uniqueness (multiple valid decryptions)
- The system gets too hard to be broken by current methods
The last point is particularly interesting in the context of the observations above. A carefully—or even carelessly—introduced constraint could force the ciphertext into exhibiting artificial symmetries, such as the identical frequency profiles seen in the two groups. This would not necessarily strengthen the cipher in a classical sense, but it could significantly obscure its structure and mislead standard analytical approaches.
From that perspective, the W-splitting phenomenon might not be a coincidence at all, but a side effect of such a “tampering” step. Perhaps
two components were combined under an additional rule. Perhaps a balancing constraint was imposed. Or perhaps a transformation was applied that preserves
certain global statistics while destroying local interpretability.
However, this also raises a more uncomfortable possibility: what if the modification was not clean? If the system was “messed with” in a way that breaks some of the usual assumptions cryptanalysts rely on, then we may be facing something that is not just difficult—but structurally awkward. Not unsolvable, but resistant to the kinds of methods we instinctively try first.
In that sense, the symmetry observed here might be less of a direct clue and more of a warning. It tells us that something artificial is going on—but not necessarily what. Any convincing approach to K4 should therefore not only explain the ciphertext, but also account for these imposed regularities. Ignoring them feels risky. Over-interpreting them may be just as dangerous.
So perhaps the right takeaway is this: instead of asking which cipher produces K4, we may need to ask which cipher, once “fucked with”, produces something that looks like this.
[1] https://glthr.com/a-fresh-perspective-on-kryptos-k4
Comments
Post a Comment