Skip to content
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
298 lines (242 sloc) 10.8 KB
\title{Xolotl ratchet}
\subtitle{A selectively stateful mixnet format for post-quantum anonymity}
\author{Jeffrey Burdges}
% \section{}
% L\'aszl\'o Baba's quasi-polynomial time algorithm for graph isomorphism\cite{Babai-GI}
We describe a new double ratchet construction Xolotl,
inspired by the Axolotl ratchet, % \cite{Axolotl},
that integrates with the Sphinx mix network packet format \cite{Sphinx}.
We argue this opens the door to compact mix network formats with
truly hybrid anonymity, meaning they rest upon the stronger of
the security assumptions required by
the different public key primitives employed.
\section{Problem} % Post-quantum key sizes
Amongst the chief obstacles to deploying post-quantum cryptography are
the comparatively large key sizes. As a comparison :
A recent Ring-LWE key exchange New Hope \cite[\S7, p.10]{NewHope} needs
key sizes of 1824 or 2048 bytes, both of which must be ephemeral,
while one McEliece-like system McBits % \cite{McBits,InitRec}
needs a staggering 1MB for public keys.
Super-singular isogeny Diffie-Hellman (SIDH) \cite[p. 21]{SIDH-2016} keys
are only 564 bytes, or 751 bytes uncompressed, but
the key exchange requires at least 100 times as much CPU time as
an ECDH key exchange with equivalent classical security.
Anonymity tools like mix networks are sensitive to key size because
users interact with numerous nodes and key material overhead is
quadratic in the number of hops. % $n(n+1)/2$
% \section{Sphinx key blinding}
Sphinx \cite{Sphinx} is a packet format for anonymizing mix networks
that is provably secure in the universal composability framework, and
addresses the key material burden by mutating or reblinding a
single ephemeral public key $\alpha$ with each hop,
as opposed to unwrapping an unrelated public key for each hop.
An ECC key is blinded by multiplication with a shared secret scalar
derived from the Diffie-Hellman exchange:
After selecting an initial private scalar $x_0$,
public curve point $\alpha_0 = x_0 G$, and
a sequence of $n$ nodes with keys $Y_i = y_i G$,
we recursively define
\[ \begin{aligned}
\textrm{shared secret}\quad
s_i &:= x_i Y_i = y_i \alpha_i \mathcomma \\
\textrm{blinding factor}\quad
b_i &:= H(\alpha_i,s_i) \mathcomma \\
\textrm{next private key}\quad
x_{i+1} &:= b_i x_i \mathcomma \\ % \quad\textrm{and} \\
\textrm{next public key}\quad
\alpha_{i+1} &:= b_i \alpha_i \quad\textrm{for $i < n$.} \\
\end{aligned} \]
Our $i$th node replaces $\alpha_i$ by $\alpha_{i+1}$.
We therefore ask if any post-quantum public key exchanges admit
suitable key blinding tricks similar to Sphinx.
The answer appears to be {\bf no}, for much similar reasons to
why these primitives fail to yield convenient signature schemes.
There are blinding operations but they incur significant costs
that are asymptotic in the number of hops.
In SIDH, a public key should not possess enough information to compute
another isogeny whose kernel consumes torsion of the same prime.
As a result, attempts to blind SIDH keys for signature schemes add
yet another torsion prime, increasing the size of the base field.
In Ring-LWE, there is enough flexibility for blinding constructions,
again increasing the key size, and indeed a primitive similar to
universal reencryption exists \cite{963628}.
We declare such schemes unsuitable for another reason though:
If all blinding keys $b_i$ are equally likely, then the security of
elliptic curve key blinding depends only upon the security of $s_i$.
Any similar statement for Ring-LWE or SIDH appear to require invoking
their underlying security assumptions in a second and perhaps different way.
As a result, any hybrid variant of Sphinx still depends upon its
post-quantum primitives' underlying security assumptions!
We consider this a dramatic sacrifice since both SIDH and Ring-LWE
remain quite young, suggesting that either could be broken well
before the invention of quantum computers.
We could build a hybrid protocol with naive mix network packet format
that unwraps a new public key with each hop, making key material size
quadratic in the number of hops.
% In this vein, a circuit based approach
% like Tor at least avoids transmitting unnecessary key material, but
% risks exposing circuit metadata in the process.
Instead, we draw inspiration from the Axolotl ratchet % \cite{Axolotl}
which remains secure against Shor's algorithm if
first instantiated with a single post-quantum key exchange.
Axolotl itself continues using the same public key until witnessing
the other side reply with it, which meshes poorly with the mix networks
for several reasons.
First, we prefer to exploit the elliptic curve point
already in our Sphinx header, which must change with each packet.
Second, we cannot oblige mix nodes to directly communicate with
the sender, as that becomes onion routing and Tor's territory.
Instead, we hope to improve anonymity over Tor alone by
judiciously exploiting high latency and not creating circuits per se.
We resolve these tensions by ``swapping the order'' of the hash iteration
ratchet and the two-step ECDH ratchet that make up Axolotl.
In fact, we shall exploit the ECDH operation already in Sphinx rather
than adding a typical two-step ECDH ratchet.
Although the mix node's key is not ephemeral, any Sphinx mix network
should already rotate node keys for constant-time replay protection.
A typical rotation period should be a week or month.
% sometimes faster than the reply rate seen in Pond or Signal.
\noindent {\bf Xolotl ratchet description :}
A node begins as if decoding a typical Sphinx packet by
verifying the MAC,
producing the shared secret $s_i$, and
unwrapping one layer of the header's onion layer,
but then pauses to check for a ratchet flag.
If not found, then it continues with Sphinx as usual,
extracting the next hop and MAC, and unwrapping a payload onion.
If found, then we extract the ratchet instructions instead.
These ratchet instructions consist of
a chain name $\cn$ and chain index $j$,
along with the length of the previous chain, or
perhaps other information for closing the previous chain.
We define
\[ \begin{aligned}
\textrm{chain start}\quad
\ck_0 &:= H(\textrm{``Start''} \,||\, \sk) \mathcomma \\
\textrm{chain name}\quad
\cn &:= H(\textrm{``Name''} \,||\, \ck_0) \mathcomma \\
\textrm{chain keys}\quad
\ck_{j+1} &:= H(\textrm{``Chain''} \,||\, \ck_j) \mathcomma \\
\textrm{link keys}\quad
\lk_j &:= H(\textrm{``Link''} \,||\, \ck_j) \mathcomma \\
\textrm{packet keys}\quad
s' &:= H(\lk_j \,||\, s_i) \mathcomma \\ % \quad\textrm{and} \\
\textrm{source keys}\quad
\sk_j &:= H(\textrm{``Source''} \,||\, s') \mathperiod \\
\end{aligned} \]
In essence, there is a hash iteration ratchet named by $\cn$
% with internal state $(\ck, (a,\lk_a), \ldots, (b,\lk_b))$,
from which we determine a link key $\lk$.
We hash $\lk$ with the Sphinx shared secret $s_i$ to produce
an altered Sphinx shared secret $s'$.
We finally conclude by running Sphinx with $s'$ to produce the
blinding factor $b_i$ and unwrap both the Sphinx header and body.
\begin{tikzcd}[ampersand replacement=\&, column sep=small]
\cdot \ar[r] \& \cdot \ar[r] \ar[d] \& \cdot \ar[r] \ar[d] \& \cdot \ar[r] \ar[d] \& \ck \ar[r, dotted] \& ? \& \\
\& \lk \ar[d] \& \lk \ar[d] \& \lk \ar[d] \& \& \& \\
\& \ECDH \ar[d] \& \ECDH \ar[d] \& \ECDH\ar[d] \& \& \& \\
\& \mk \& \mk \ar[dddll, in=90, out=270] \& \mk \ar[dddlll, dotted, in=30, out=270] \& \& \& \\
\cdot \ar[r] \& \cdot \ar[r] \ar[d] \& \cdot \ar[r] \ar[d] \& \cdot \ar[r] \ar[d] \& \cdot \ar[r] \ar[d] \& \ck \& \& \\
\& \lk \ar[d] \& \lk \ar[d] \& \lk \ar[d, dotted] \& \lk \ar[d] \& \& \& \\
\& \ECDH \ar[d] \& \ECDH \ar[d] \& ? \& \ECDH\ar[d] \& \& \& \\
\& \mk \& \mk \& \& \mk \& \& \& \\
Assuming an initial ratchet source was created using a post-quantum
key exchange, an Xolotl ratchet retains that post-quantum security.
It also provides an interesting measure of forward secrecy against
a classical adversary.
For these advantages, we have exposed,
to the node $i$ hosting the ratchet, that all packets using this
particular ratchet have either the same sender or receiver.
There is no need for every hop to employ a ratchet, % though,
but specific usage patterns require detailed analysis.
\[ \begin{aligned}
\textrm{User} \to &\textrm{Tor} \to \textrm{Xolotl} \to \textrm{Sphinx} \to \\
\quad &\to \textrm{Xolotl} \to \textrm{Sphinx} \to \textrm{Cross} \to \cdots
\end{aligned} \]
An initial ``guard'' ratchet should be created anew for each session.
We believe that retaining middle ratchets for longer periods could
improve forward secrecy over creating them all anew with each session.
There are many concerns around this point however, primarily balancing
the improved forward secrecy with the risk of linking packets across
different sessions, but
also practical matters like ratchet storage requirements on mix nodes.
On that point, Ratchet link keys must expire with node keys,
capping their lifetime anyways,
but source keys or chain keys could outlive them.
Aside from usage patterns and ratchet longevity,
there are several interesting possible enhancements worth discussing :
% \begin{itemize}
% \item
An onion header could contain a SIDH key accessed by a single mix node,
allowing for post-quantum security at one middle hop
where no ratchet exists.
% \item
A standard hash iteration ratchet could occupy considerable space
if early messages see long delays.
We believe a tree-like hash ratchet configuration would be more efficient,
especially if ratchets are used with SURBs.
% \item
Ratchets could be given away to other users, thereby allowing a
collaborative form of forward secrecy, and obfuscating ownership.
In principle, adversaries could not break middle ratchets without
breaking all cryptography up through to the messaging layer itself,
which could reasonably employ multiple post-quantum key exchanges,
possibly even McBits.
% \end{itemize}
% \section*{Acknowledgements}
% This work benefits from the financial support of the Brittany Region
% (ARED 9178) and a grant from the Renewable Freedom Foundation.
You can’t perform that action at this time.