deletions | additions
diff --git a/untitled.tex b/untitled.tex
index 95253cb..8cc8b52 100644
--- a/untitled.tex
+++ b/untitled.tex
...
\section{Abstract}
This paper shows how several ring-LWE based key exchange protocols can be broken, under the assumption that the same key share is used for multiple exchanges. This indicates that, if these key exchange protocols are used, then it will be necessary for a fresh key share be generated for each exchange, and that these key exchange protocols cannot be used as a drop in replacement for
protocols designs which use Diffie-Hellman static key shares.
\section{Introduction}
Key agreement protocols are one of the oldest public key
protocols primitives known, dating back to the Diffie-Hellman protocol\cite{Diffie_1976}. In a key agreement protocol, each side selects
a private
values, value, and exchange
a public
values value (key shares); in most such protocols, each side sends a single message. Then, both side do computations based on their private
values value and the other side's public key shares, and derive the same secret value. The security goal is that someone
just listening into the exchanged public key shares would find it infeasible to derive that secret value.
Now, Diffie-Hellman would be vulnerable to a Quantum Computer; one research topic is to find alternatives that would be secure in that environment. Several such proposed alternatives are based on the ring-LWE problem. From a protocol standpoint, these proposals work largely like Diffie-Hellman, each side selects private values, one side sends its public value, the other side replies, and then they both compute a shared secret.
With Diffie-Hellman, it is perfectly safe to reuse the same public key share for multiple exchanges.
For example, One such use is the "static Diffie-Hellman"; in this case, Alice might select a private value, and publish the corresponding key share. Then, when Bob, Carol, Dave and Eve want to communicate with Alice, they can take Alice's key share, select their own private values, and then send to Alice their key shares, thus creating a secure connection.
In this case, as As long as Alice takes some well-known precautions, the connections are independent; Eve gets no advantage on deriving the secret used in the Alice to Bob connection.
This paper
shows will show that ring-LWE based key agreement protocols are not safe in this scenario; if Alice uses the same private value repeatedly, then Eve (by sending a series of messages, and seeing how Alice responds) is able to recover Alice's private value (and if Alice used that same static value to communicate to Bob, Eve can then listen into that conversation).
\section{Ring-LWE Key Exchange}
The Ring-LWE problem\cite{Lyubashevsky_2013} is a problem that works in the Ring $\mathbb{Z}[x]/(x^N+1, p)$, for
integer integers $N$ and
prime $p$.
The hard problem is that for Ring Elements $a, e$ "small" random values, and $s$ random, it is infeasible to distinguish pairs of the form $a, as + e$ from random.
There are a number of proposed key agreement protocols based on Ring-LWE, including \cite{Ding_2012}, \cite{Peikert_2014}, \cite{Alkim_2015}, \cite{Singh_2015}
While these protocols differ in the details, they all follow the same basic paradigm.
\begin{itemize}
\item Alice and Bob agree on a random element
$a$; $A$; it may be a global parameter, or it may be based on a seed provided by Alice
\item Alice selects "small" elements
$s$ $S$ and
$e$; $E$; these values (actually,
$s$; $S$; Alice doesn't actually need
to remember the value of
$e$) $E$) are Alice's private secret.
\item Alice computes the value
$b $B =
as AS +
e$; E$; this value is Alice's public key share, which she sends to Bob
\item Bob also selects small elements
$s'$ $S'$ and
$e'$; $E'$; he computes the value
$u $U =
as' AS' +
e'$ E'$ and the value
$v' $V' =
bs'$. BS'$.
\item Bob then uses
$v'$ $V'$ to compute an error-reconcilation vector
$c$; $C$; he sends
$u, c$ $U, C$ to Alice
\item Alice computes the value
$v $V =
us$ US$
\item Both sides then use the error-reconciliation vector
$c$ $C$ to convert their
$v, v'$ $V, V'$ into a shared secret, converting each coefficient of
$v, v'$ $V, V'$ into one bit.
\end{itemize}
Some versions of the key agreement add additional error vectors at some places; as the attack can be modified to account for this, we will ignore it.
The idea behind this protocol is that Alice computes
$v $V =
ass' SS'A +
se'$, SE'$, while Bob computes
$v' $V' =
ass' SSA' +
s'e$, S'E$, they differ by
$se' $SE' -
s'e$, S'E$, as
$s, s', e, e'$ $S, S', E, E'$ are small elements, this is (with high probability) also small, and so each element of
$v$ $V$ is "close" to the corresponding element of
$v'$. $V'$.
Of course, being close doesn't mean that they're identical; if we used any fixed mapping of the coefficients of
$v, v'$ $V, V'$ to the shared secrets would mean that we would have some probability that an element of
$v$ $V$ would be on one side of the boundary, while the same element of
$v'$ $V'$ would be on the other.
That's where the error-reconciliation vector comes in. We logically split up the possible coefficient values into four quadrants; quadrant I ($[0,
p/4]$), p/4)$), quadrant II ($[p/4,
p/2]$), p/2)$), quadrant III ($[p/2,
3p/4]$), 3p/4)$), and quadrant IV ($[3p/4, p-1]$)
There is a bit within the error-reconciliation that corresponds to each coefficient; it determines whether quadrants I and II are considered the same (e.g. values there would map to a 0 bit, while values in quadrants III and IV would map to a 1 bit); or whether quadrants I and IV are considered the same (e.g. values there would map to a 0 bit, while values in quadrants II and III would map to a 1 bit).
The intention is that Bob would, for each coefficient value of
$v'$, $V'$, determine the value of the error-reconcilation bit that would give the largest possible leeway for errors. As long as any error is no more than $p/8$, it will always be possible for Alice and Bob to agree on the shared secret.
\section{The Attack}
...
\begin{itemize}
\item Alice uses a ring-LWE key exchange protocol to establish secure connections
\item Alice uses the same key share to communicate with both Bob and the attacker Eve
\item Eve's goal is to recover the value
$s$ $S$ the corresponds to Alice's public key share (and thus be able to decrypt Alice's traffic)
\item Eve can perform the ring-LWE exchange protocol with Alice multiple times (with Eve providing a fresh key share each time)
\item Each time after Alice and Eve has performed the key exchange protocol, Alice will derive her shared secret; Eve when then be able to generate one guess to that shared secret, and Alice will indicate whether that guess matches what she has or not.
\end{itemize}
...
This last step can be implemented by continuing on with the protocol that used the key establishment; Alice and Eve may derive keys based on the shared secret. What Eve can do is generate her keys based on her guess; if Alice is able to decrypt (and respond) based on those keys, then (with high probability) Eve's guess of the shared secret was correct; if Alice rejects the exchange, then Eve's guess was not correct.
\subsection{Basic Oracle Query}
To make a query, Eve mostly follows the protocol; she selects small
$s', e'$ $S', E'$ values (albeit not randomly), she computes
$v'$, $V'$, and generates the error-reconcilation vector
$c$ $C$ honestly, except for one location.
She deliberately selects
$s', e'$ $S', E'$ so that coefficient 0 of Alice's computation of
$us$ $US$ is near 0; for coefficient 0, Eve sets
it that error-reconcliation bit so that the values in
the range $[0,
p/2]$ p/2)$ are mapped to
0, one bit vlaue, while values in $[p/2, p-1]$ are mapped to
1. the other. As Eve is able to compute correctly all the other bits of the shared secret (as she is performing the rest of the protocol honestly), this gives her a way to test the sign of that one intermediate value.
In particular, if we select an
$s'$, $S'$, and call $\delta =
ass'[0]$ SS'A[0]$ (where the notation
$f[0]$ $F[i]$ specifies coefficient
0 i-th of the ring element
$f$), $F$), and we use
$e' $E' = (x)^{-i}$ (for some integer $i$, where $(x)$ stands for the ring element with a 1 in coefficient 1, and 0 elsewhere), then a
query key share of
$(js'a $(jS'A +
ke')$ kE')$ (for small integer $j, k$) would allow us to determine the sign of
$(kass' $(kSS'A +
s(x)^{-i})[0] S(x)^{-i})[0] = \delta j +
ks[i]$. k \cdot S[i]$.
\subsection{The actual attack}
The first step in the attack for Eve is to find a lightweight value
$s'$ $S'$ where
$(ass')[0] $(SS'A)[0] = \pm 1$. She can do this by searching for values
$s'$ $S'$ which consists of at most two coefficents
of are $[1, -1]$ and the rest 0, and for which
$s'b[0]$ $S'B[0]$ is a small value. As
$s'b $S'B =
s'(as S'(AS +
e) E) =
ass' SS'A +
s'e$ S'E$ where
$e$ $E$ is known to be small, such a
$s'$ $S'$ has a good probability of meeting the criteria.
We can further refine potential
$s'$ $S'$ values by probing how a
$s'$ $S'$ value works with several $i$
values; coefficients; by fixing an $i$ value, and trying several $j$ values, and for each such value, to a binary search for the $k$ value such that $j\delta +
ks[i]$ kS[i]$ is one sign, and $j\delta +
(k+1)s[i]$ (k+1)S[i]$ is the other; this gives us the approximate value of
$s[i]/\delta$ $S[i]/\delta$ value, and we can use this to deduce whether $\delta = \pm 1$. We can also deduce the sign of $\delta$.
Once we have such an
$s'$ $S'$ value, then the attack is easy. We can set $k=\delta$, and for any $i$, query the sign $j +
s[i]$, S[i]$, or in other words, whether $j \ge
s[i]$. S[i]$. Binary search will quickly (with a handful of probes) give us the exact value of
$s[i]$. $S[i]$.
We query
$s[i]$ $S[i]$ for each $i$, that gives us the entire value of
$s$, $S$, and the attack has succeeded.
The above would take approximately 5,000 queries (assuming that standard ring size of $N=1024$).
