In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
Most broken cryptosystems do not fail because the underlying mathematics is wrong. They fail because a seemingly harmless implementation choice quietly destroys the hard problem the scheme was supposed to rely on. In this post, I show three examples of exactly that: a Diffie–Hellman setup with weak primes, a matrix-based variant that leaks the exponent through Jordan blocks, and an elliptic-curve implementation that skips the point-on-curve check and can be tricked onto a malicious curve. None of these failures look dramatic at first glance. That is exactly why they are dangerous.
1 - Insecure Primes
Danger: Application of the Pohlig-Hellmann Algorithm
Picking insecure primes is the most basic mistake that can be made when setting up a Diffie–Hellman key agreement over finite fields. One might ask:
"How can a prime be insecure?"
To understand this, it is helpful to know that cryptography is all about groups, which are necessary for reducing the size of the involved integers. To achieve this, we reduce the integers modulo an integer p, which naturally creates multiplicative groups. The size of the group is determined by the prime factorisation of $p$. For a prime number $p$, this boils down to the factors of $p - 1$. To see this, you have to know the Chinese Remainder Theorem (CRT). This basically says, if you have an unknown integer $X$ that can be described with known equations \begin{align*} X &\equiv r_1 \pmod{p_1} \\ X &\equiv r_2 \pmod{p_2} \\ &\ldots \\ X &\equiv r_n \pmod{p_n} \\ \end{align*} for coprime integers $p_i$ then $X$ can be uniquely be determined modulo $\prod^n_{i=1} p_i$ efficiently.
EXAMPLE
Let $X$ be unknown but you happen to know \begin{align*} X &\equiv 2 \pmod{3} \\ X &\equiv 1 \pmod{5} \\ X &\equiv 9 \pmod{11} \end{align*} It is $3*5*11 = 165$, so there is only one positive integer $X$ less than $165$ which fullfils this system of equations and can be determined by \[ X \equiv 2*\frac{165}{3}I_3 + 1*\frac{165}{5}I_5 + 9*\frac{165}{11}I_{11} \pmod{165} \] The integers $I_3$,$I_5$ and $I_{11}$ are simply the multiplicative inverses of \begin{align*} \frac{165}{3}I_3 = 55I_3 &\equiv 1 \pmod{3} \Rightarrow I_3 \equiv 1 \pmod{3} \\ \frac{165}{5}I_5 = 33I_5 &\equiv 1 \pmod{5} \Rightarrow I_5 \equiv 2 \pmod{5} \\ \frac{165}{11}I_{11} = 15I_{11} &\equiv 1 \pmod{11} \Rightarrow I_{11} \equiv 3 \pmod{11} \end{align*} and can be computed efficiently using the extended Euclidean algorithm. So we have \[ X \equiv 2*55*1 + 1*33*2 + 9*15*3 \equiv 86 \pmod{165} \] So $X=86$ is the answer.
Let $X$ be unknown but you happen to know \begin{align*} X &\equiv 2 \pmod{3} \\ X &\equiv 1 \pmod{5} \\ X &\equiv 9 \pmod{11} \end{align*} It is $3*5*11 = 165$, so there is only one positive integer $X$ less than $165$ which fullfils this system of equations and can be determined by \[ X \equiv 2*\frac{165}{3}I_3 + 1*\frac{165}{5}I_5 + 9*\frac{165}{11}I_{11} \pmod{165} \] The integers $I_3$,$I_5$ and $I_{11}$ are simply the multiplicative inverses of \begin{align*} \frac{165}{3}I_3 = 55I_3 &\equiv 1 \pmod{3} \Rightarrow I_3 \equiv 1 \pmod{3} \\ \frac{165}{5}I_5 = 33I_5 &\equiv 1 \pmod{5} \Rightarrow I_5 \equiv 2 \pmod{5} \\ \frac{165}{11}I_{11} = 15I_{11} &\equiv 1 \pmod{11} \Rightarrow I_{11} \equiv 3 \pmod{11} \end{align*} and can be computed efficiently using the extended Euclidean algorithm. So we have \[ X \equiv 2*55*1 + 1*33*2 + 9*15*3 \equiv 86 \pmod{165} \] So $X=86$ is the answer.
The Pohlig-Hellman works exactly the same way. Let $p-1 = \prod^n_{i=1} q_i$, then it uses the small prime numbers $q_i$ to span such a system of equations.
"But how to get these equations?"
This can be achieved via subgroup testing. I will illustrate this by an example using $p=211$.
It happens that $p-1$ is smooth, namey $210 = 2*3*5*7$. We now create four equations - like in the example -
for the four primes $q_1 = 2, q_2 = 3, q_3 = 5$ and $q_4 = 7$.
Assume you are faced with the discrete logarithm problem:
$$41^x = 159 \pmod{211}$$.
The integer $41$ is primitive in $\mathbb{F}^*_{211}$, that means, it generates the whole group, i.e.,
all integer in the intervall $(1,210)$ for some exponent $e$ in $41^e \pmod{211}$.
We know from Fermats little Theorem that
$$\mathsf{[Fermat]}\;\;41^{210*y} \equiv 1 \pmod{211}, \text{ for any integer } y$$
We start with $q_1 = 2$. If you want to know if $x$ is divisible by $2$ you compute
\[
159^{\frac{210}{2}} \equiv (41^x)^{\frac{210}{2}} \equiv 41^{105x} \pmod{211}
\] Suppose $x$ is even, then you can write $x = 2x'$ hence, according to [Fermat]
\[
41^{105x} \equiv 41^{210x'} \equiv 1 \pmod{211}
\] If $x$ is odd you get a result different from $1$.
In our example it is $150^{105} \neq 1 \pmod{211}$. We dont need to test further, because
if it is not even, it must be odd. So we got our first equation
\[
x \equiv 1 \pmod{2}.
\] Now switch to $q_2 = 3$. We test
\[
159^{\frac{210}{3}} \equiv (41^x)^{\frac{210}{3}} \equiv 41^{70x} \equiv 14 \pmod{211}
\] So this is not $\equiv 1$, hence $x$ is not divisible by $3$. Lets test $x-1$. We compute
\[
(159\cdot 41^{-1})^{\frac{210}{3}} \equiv (41^{x-1})^{\frac{210}{3}} \equiv 41^{70(x-1)} \equiv 1 \pmod{211}
\] So we know additionally
$$x-1 \equiv 0 \pmod{3} \Leftrightarrow x \equiv 1 \pmod{3}$$
You execute this for all primes $q_i$. After at most $q_i-1$ test, you found the correct remainder of $x \pmod{q_j}$
and can build up your system of equations.
So a prime number with $p-1$ conisting of small prime numbers makes a prime number insecure.
2 - Insecure Matrix
Danger: The characteristic polynomial may have a multiple root
Diffie–Hellman key exchange is not restricted to cyclic groups like $\mathbb{Z}_p^*$. In principle, one can also work in more complex algebraic structures, such as the group of invertible $n \times n$ matrices over a finite field, denoted by $\mathbf{GL}(n,\mathbb{F}_p)$.
At first glance, this seems like a natural generalization: instead of exponentiating numbers, we exponentiate matrices. The protocol remains structurally identical. For example, let us fix $p = 23$ and choose a generator matrix
\begin{align*} \mathbf{M} := \left( \begin{matrix} 11 & 1 & 8 \\ 4 & 3 & 17 \\ 1 & 3 & 19 \end{matrix} \right) \end{align*}The matrix has full rank and appears perfectly suitable. As in the classical setting, we compute \[ \mathbf{M}^e \equiv \mathbf{R} \pmod{p} \] where $e$ is the secret exponent. So far, everything behaves exactly like standard Diffie–Hellman. But this is where a subtle — and critical — issue arises.
Every square matrix has an associated characteristic polynomial, defined by
\[ P(x) = \text{det}(x\mathbf{I}-\mathbf{M}) \]
whereof $\mathbf{I}$ is the identity matrix. For our matrix, we obtain
\begin{align*}
\text{det}
\left(
\begin{matrix}
x-11 & -1 & -8 \\
-4 & x-3 & -17 \\
-1 & -3 & x-19
\end{matrix}
\right) = x^3 + 13*x^2 + 6*x + 13 =: P(x)
\end{align*}
At this point, nothing seems suspicious. However, factoring the polynomial reveals the problem:
\[ P(x) = (x-7)*(x-13)^2 \]
The eigenvalue $13$ appears with multiplicity two. This seemingly harmless detail completely undermines the security of the system.
To understand why, we use the Jordan normal form.
Any matrix $\mathbf{M}$ can be written as
\[ \mathbf{M} = \mathbf{P}*\mathbf{J}*\mathbf{P}^{-1} \]
where $\mathbf{J}$ is a block-diagonal matrix encoding the eigenvalues.
This representation can be found efficiently. In our case we obtain:
\[ \mathbf{J} =
\left(
\begin{matrix}
7 & 0 & 0 \\
0 & 13 & 1 \\
0 & 0 & 13
\end{matrix}
\right),
\mathbf{P} =
\left(
\begin{matrix}
1 & 9 & 1 \\
11 & 13 & 0 \\
1 & 15 & 10
\end{matrix}
\right)
\]
The crucial observation is the Jordan block corresponding to the repeated eigenvalue $13$. The extra $1$ on the superdiagonal appears only when the
characteristic polynomial has multiple roots.
Now consider exponentiation. Using the decomposition, we get
\[
\mathbf{M}^e = \mathbf{P}*\mathbf{J}^e*\mathbf{P}^{-1}
\]
While $\mathbf{P}$ is irrelevant for the hardness of the problem, the structure of $\mathbf{J}^e$ is decisive. A direct computation shows
\[
\left(
\begin{matrix}
7^e & 0 & 0 \\
0 & 13^e & e*13^{e-1} \\
0 & 0 & 13^e
\end{matrix}
\right)
\]
This is the key weakness: the exponent $e$ appears linearly in the superdiagonal entry. Unlike classical discrete logarithms, where $e$ is hidden
inside an exponent, here it leaks directly. In other words, recovering $e$ is no longer a hard problem — it becomes a simple algebraic computation.
EXAMPLE
We choose $p = 23$ and take the matrix $\mathbf{M}$ from above. We set the secret exponent to $e=19$ and hence we get
\[
\left(
\begin{matrix}
11 & 1 & 8 \\
4 & 3 & 17 \\
1 & 3 & 19
\end{matrix}
\right)^{19} \equiv
\left(
\begin{matrix}
5 & 10 & 11 \\
17 & 17 & 9 \\
10 & 7 & 16
\end{matrix}
\right)
\] This is the random group element that is used within the Diffie-Hellman key agreement and the computation of $e$ should be hard. However, an attacker can compute:
\[
\begin{align*}
&\mathbf{P}^{-1}*
\left(
\begin{matrix}
5 & 10 & 11 \\
17 & 17 & 9 \\
10 & 7 & 16
\end{matrix}
\right)*
\mathbf{P}\\
&=
\left(
\begin{matrix}
11 & 0 & 0 \\
0 & 2 & 10 \\
0 & 0 & 2
\end{matrix}
\right)
\end{align*}
\]
and extract the secret exponent via
\[ 10*13*2^{-1} \equiv 19 = e \pmod{23} \]
Conclusion: Using matrix groups for Diffie–Hellman is dangerous unless the structure is carefully controlled. In particular, matrices whose characteristic polynomial has repeated roots introduce Jordan blocks — and these leak the exponent directly. What looks like a harmless generalization completely breaks the security model.
3 - No Point-on-Curve Check
Danger: Malicious curves may have smooth order
In modern terminology, this belongs to the family of invalid-curve attacks: the implementation performs scalar multiplication on attacker-controlled points without first verifying that those points lie on the intended elliptic curve.
To avoid the mistake from the first example (Insecure Primes), let us assume that the chosen elliptic curve $$ y^2 = x^3 + ax + b \pmod{p} $$
has already been validated properly — in particular, that the number of points $\#\mathbb{E}$ is a large prime. Otherwise, the Pohlig–Hellman algorithm could already be a potential danger to its security.
Now let us take a closer look at how elliptic curve arithmetic actually works.
An elliptic curve is defined by the parameters $a$, $b$, and the prime $p$. However, the group operation — point addition — follows fixed formulas.
Addition of two unequal points
Let $Q = (x_q,y_q)$ and $P = (x_p,y_p)$ with $P \neq Q$. Further set
$$s \equiv (y_p - y_q)(x_p - x_q)^{-1} \pmod{p}$$
then the point $P+Q = R = (x_r,y_r)$ is
\begin{align*}
x_r &\equiv s^2 - x_p - x_q \pmod{p}\\
y_r &\equiv -y_p + s(x_p - x_r) \pmod{p}
\end{align*}
Addition of two equal points
Let $Q = (x_q,y_q)$. Further set
$$s \equiv (3x_q^2 + a)(2y_q)^{-1} \pmod{p}$$
then the point $Q + Q = R = (x_r,y_r)$ is
\begin{align*}
x_r &\equiv s^2 - 2x_p \pmod{p}\\
y_r &\equiv -y_p + s(x_p - x_r) \pmod{p}
\end{align*}
This are the usual operation when two points are added. These addition formulas work for all curves. Look at Wikipedia, you will find it there.
Do you notice something strange?
I said above that the elliptic curve is defined by the coefficients $a$ and $b$ as
well as the prime $p$. How often does the parameter $b$ occur during the addition?
Never! It never occurs. Think about it!
This is a subtle but extremely important observation: the addition formulas never use $b$. They only depend on $a$ and the coordinates of the points.
This means that when computing a scalar multiplication like $e \cdot Q$, the algorithm itself has no way of verifying whether the input point $Q$ actually lies on the intended curve.
If no explicit point-on-curve check is performed, the implementation will blindly process any pair $(x,y)$ that “looks like” a point on the curve.
This opens the door for a powerful attack.
An attacker can choose a different curve $$ \mathbb{E}_m: y^2 = x^3 + ax + b_m \pmod{p} $$ where only the parameter $b$ is modified. Since the arithmetic does not depend on $b$, the victim’s implementation will unknowingly perform computations on this malicious curve.
The attacker carefully selects $b_m$ such that the number of points $\#\mathbb{E}_m$ is smooth, i.e., it factors into small primes. This makes the discrete logarithm problem easy via the Pohlig–Hellman algorithm.
The attack then proceeds as follows:
- The attacker chooses a malicious curve $\mathbb{E}_m$ with smooth order, with a different $b$ paramter.
- He selects a point $P = (x_m,y_m)$ on $\mathbb{E}_m$.
- He sends $P$ to the victim.
- The victim (without validation) computes $R = e \cdot P$ and return $R$ to the attacker.
- The attacker uses the smooth group structure of $\mathbb{E}_m$ to recover $e$ from $R$.
In other words, the security of the system is completely bypassed — not by breaking the original curve, but by tricking the implementation into working on a different one.
EXAMPLE
We set $p$ to the $128$bit prime number: $$p = 170141183460469231731690208590126496519$$ We further set $a=3$. For $b = 126$ we the the curve $\mathbb{E}: y^2 = x^3 + 3x + 126$ with number of points: $$ \#\mathbb{E} = 170141183460469231740150999661564610341$$ So the number of points on it is a large prime number. The attacker searches for a malicious curve $\mathbb{E}_m$ via a smooth number of points. For $b_m = 451$ we that the number of points on $\mathbb{E}_m: y^2 = x^3 + 3x + 451$ is \begin{align*} \#\mathbb{E}_m = &2 * 3^2 * 36191 * 64811 * 134839 *\\ &2452103 * 32042947 * 380365357 \end{align*}
We set $p$ to the $128$bit prime number: $$p = 170141183460469231731690208590126496519$$ We further set $a=3$. For $b = 126$ we the the curve $\mathbb{E}: y^2 = x^3 + 3x + 126$ with number of points: $$ \#\mathbb{E} = 170141183460469231740150999661564610341$$ So the number of points on it is a large prime number. The attacker searches for a malicious curve $\mathbb{E}_m$ via a smooth number of points. For $b_m = 451$ we that the number of points on $\mathbb{E}_m: y^2 = x^3 + 3x + 451$ is \begin{align*} \#\mathbb{E}_m = &2 * 3^2 * 36191 * 64811 * 134839 *\\ &2452103 * 32042947 * 380365357 \end{align*}
Since this order is smooth, the attacker can efficiently compute discrete logarithms and recover the secret scalar $e$.
Conclusion: Always verify that received points lie on the intended curve. Skipping this single check completely destroys the security of elliptic curve cryptography.
Comments
Post a Comment