@@@ proto wip

[tripe] / doc / tripe-protocol.tex

%%% -*- mode: LaTeX; TeX-PDF-mode: t -*-
%%%
%%% The TrIPE protocol specification
%%%
%%% (c) 2017 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of Trivial IP Encryption (TrIPE).
%%%
%%% TrIPE is free software: you can redistribute it and/or modify it under
%%% the terms of the GNU General Public License as published by the Free
%%% Software Foundation; either version 3 of the License, or (at your
%%% option) any later version.
%%%
%%% TrIPE is distributed in the hope that it will be useful, but WITHOUT
%%% ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
%%% FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
%%% for more details.
%%%
%%% You should have received a copy of the GNU General Public License
%%% along with TrIPE.  If not, see <https://www.gnu.org/licenses/>.

%%%--------------------------------------------------------------------------
%%% Preamble.

\documentclass[a4paper, article, numbering]{strayman}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
\usepackage{mdwlist}
\usepackage{mdwmath}
\usepackage{crypto}
\usepackage{mdwref}
\usepackage{sverb}

\title{TrIPE: The Trivial IP Encryption protocol}
\author{Mark Wooding}
%%\date{incomplete}

\def\fixme#1{\marginpar{FIXME}[FIXME: #1]}

\newenvironment{aside}
  {\begin{list}{}{\rightmargin=0pt}\footnotesize\item\relax}
  {\end{list}}

\begin{document}

%%%--------------------------------------------------------------------------

\maketitle
\thispagestyle{empty}

\begin{abstract}
  This document specifies the TrIPE protocol for IP encryption.

  TrIPE is a fairly simple protocol which allows a pair of hosts to exchange
  short messages, typically IP datagrams, over a hostile network while
  maintaining the properties of \emph{secrecy} and \emph{integrity}; i.e.,
  that the content of the messages cannot be determined by eavesdroppers on
  the network, and that either endpoint can determine whether a message
  received is an unaltered copy of one that was sent by the other.

  The protocol is simple enough for a proof of security in the random-oracle
  model.
\end{abstract}

%%%--------------------------------------------------------------------------
\section{Introduction} \label{sec:intro}

TrIPE, or `Trivial IP Encryption', is a protocol designed for the secure (but
unreliable) transmission of IP datagrams over a hostile network between a
pair of hosts, named \emph{peers}.  Specifically, it has the following
properties.
\begin{itemize}
\item \emph{Secrecy}: an adversary cannot determine anything about the
  content of transmitted messages, except for their lengths.
\item \emph{Integrity}: a recipient can verify that a message received is an
  unaltered copy of a message sent by its peer, and which has not previously
  been received.
\item \emph{Symmetry}: in the base protocol, the two peers behave
  identically, which simplifies implementation and analysis.  Some ancillary
  portions of the protocol are asymmetric, in order to deal with asymmetry in
  the environment.
\end{itemize}


\subsection{Overview} \label{sec:intro.overview}

The TrIPE protocol is used between a pair of \emph{peers}.  Neither peer is
distinguished in any way: there is no notion of `initiator' or `responder'.

Each peer has an asymmetric key pair, consisting of a \emph{private key}
which should be known only to the peer itself, and a matching \emph{public
key} which must be known by other peers.

The TrIPE protocol contains no messages for negotiating options such as
cryptographic algorithms or network parameters, and there is no exchange of
certificates.  It is assumed that administrators configure their
implementations with the necessary knowledge about the peers with which they
wish to communicate.

The protocol has two main parts.
\begin{itemize}
\item The \emph{key-exchange} subprotocol (\xref{sec:keyexch}) makes use of
  the peers' public and private keys to establish \emph{keyset}, known to the
  peers themselves but not to an adversary in control of the network.
\item The \emph{bulk transfer} (\xref{sec:xfer}) subprotocol uses keysets
  established using the key-exchange protocol to transfer messages between
  the peers.
\end{itemize}
In addition, there are a few minor subprotocols for various special effects.

%%%--------------------------------------------------------------------------
\section{Diffie--Hellman groups} \label{sec:dh-group}

\subsection{Operations} \label{sec:dh-group.ops}

An \emph{encoding} on some set of values $S$ is defined by a pair of
operations \id{enc} and \id{dec}, as follows.
\begin{itemize}
\item Given a value $x \in S$, $\id{enc}(x)$ encodes it as an octet string.
\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a value $x$
  and remainder string $a'$ from it.
\end{itemize}
Hence, the possible encodings of values form a prefix-free set of strings.
Furthermore, if $a'$ is any octet string, and $x \in S$ is any value, then it
must be the case that $x, a' = \id{dec}(\id{enc}(x) \cat a')$.

A \emph{Diffie--Hellman group} consists of a pair of sets $S$ and $G$, of
\emph{scalars} and \emph{group elements} respectively, a distinguished
\emph{generator} element $P \in G$, and a number of operations on these
groups.  In the following descriptions, $x$ and $y$ are scalars; $X$, $Y$,
and $Z$ are group elements; and $a$ and $a'$ are octet strings.
\begin{itemize}
\item $\id{dh}(x, Y)$ calculates a group element $Z$.  To be a proper
  Diffie--Hellman group, it must be the case that $\id{dh}(x, \id{dh}(y, P))
  = \id{dh}(y, \id{dh}(x, P))$ for all scalars $x$ and $y$.  For security, it
  must be computationally intractable to determine $\id{dh}(x, \id{dh}(y,
  P))$ given $X = \id{dh}(x, P)$ and $Y = \id{dh}(y, P)$ (i.e., the
  \emph{computational Diffie--Hellman assumption} must hold).
\item $\id{enc-ge-public}$ and $\id{dec-ge-public}$ together define an
  encoding on group elements, for which no special properties are required.
\item $\id{enc-ge-secret}$ and $\id{dec-ge-secret}$ together define an
  encoding on group elements where all encodings have the same length, except
  with negligible probability.
\item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an encoding
  on group elements where all encodings \emph{should} have the same length,
  except with negligible probability.\footnote{%
    The existence of groups without (mostly) fixed-length hashing encodings
    is a historical mistake.  If a variable-length encoding is used here,
    information about group element(s) being hashed may leak to an adversary
    through timing channels.} %
  The decoding operation is never invoked, so it need not be possible to
  implement it efficiently, though it must be theoretically possible to
  decode encodings unambiguously.
\item $\id{enc-sc}$ and $\id{dec-sc}$ together define an encoding on scalars,
  where all encodings have the same length.  Let $\id{scsz}$ be the length of
  an encoded scalar.
\end{itemize}
In the following descriptions, decoding functions are not described explicitly
Decoding operations must validate input sufficiently that the $\id{dh}$
operation can be performed successfully and without leaking secret inputs
during the computation; but it is \emph{not} necessary to perform further
precise verification.  For example, an implementation need not verify that an
incoming group element is actually within the subgroup generated by $P$; and
an elliptic-curve group need not verify that an incoming pair of coordinates
actually correspond to a point on the curve.
\begin{aside}
  In an ideal world, we would only have one group-element encoding rather
  than three.  The present situation is caused by unfortunate historical
  mistakes.  Of course, nothing prevents newer Diffie--Hellman group
  specifications from using the same (constant-length) encoding for all three
  group-element encodings described above, and, indeed, the X25519 and X448
  groups defined below do this.
\end{aside}


\subsection{Primitive encoding functions} \label{sec:dh-group.encode}

\subsubsection{I2OSP}
If $\ell$ and $n$ are integers with $0 \le n < 2^{8\ell}$, then $[n]_\ell$
denotes the $\ell$-digit big-endian base-256 encoding of $n$.  Specifically,
let $a_0$, $a_1$, \ldots, $a_{\ell-1}$ be the unique integers such that $0
\le a_i < 256$ for $0 \le i < \ell$, and
\[ n = \sum_{0\le i<\ell} 2^{8i} a_i \]
Then $[n]_\ell$ is the $\ell$-octet string $a_{\ell-1} \cat \cdots \cat a_1
\cat a_0$.

\subsubsection{I2VOSP}
Given an integer $0 \le n < 2^{524288}$, the function $\id{i2vosp}(n)$
determines a variable-length big-endian base-256 encoding of $n$.  If $n = 0$
then let $\ell = 1$; otherwise, let $\ell$ be the unique integer such that
$2^{8(\ell-1)} \le n < 2^{8\ell}$; since $n$ is bounded, it must be that
$\ell < 65536$.  Then $\id{i2vosp}(n) = [\ell]_2 \cat [n]_\ell$.

\subsubsection{FE2IP}
Given an element $x$ of a finite field $\gf{q}$, the function $\id{fe2ip}$
determines a unique integer such that $0 \le \id{fe2ip}(x) < q$.

If $q$ is prime, then $\gf{q} = \Z/q\Z$: let $\phi_q(n)$ be the unique ring
homomorphism from $\Z$ to $\gf{q}$, and define $\id{fe2ip}(x)$ to be the
smallest nonnegative integer $n$ such that $x = \phi_q(n)$; it is necessarily
the case that $0 \le \id{fe2ip}(x) < q$.

Otherwise, $q = r^m$ for some prime power $r$ and an integer $m > 1$.  Fix an
ordered basis $\{ u_0, u_1, \ldots, u_{m-1} \}$ for $\gf{q}$ as a vector
space over $\gf{r}$.
\begin{aside}
  This is often a polynomial basis: if $u(t) = u_0 + u_1 t + \cdots + u_{m-1}
  t^{m-1} + t^m$ is a monic irreducible polynomial of degree~$m$ over
  $\gf{r}$, then $\{ u_0, u_1, \cdots, u_{m-1} \}$ is a suitable basis,
  representing $\gf{q}$ as the quotient ring $\gf{r}[t]/(u(t))$.  Other
  representations are also possible.

  In practice, this case occurs when dealing with elliptic curves, and the
  specification for a curve over a non-prime field will include a description
  of the field representation sufficient to apply this definition.
\end{aside}
Then any element $x \in \gf{q}$ can be written uniquely as a sum
\[ x = \sum_{0\le i<m} u_i x_i \]
where $x_i \in \gf{r}$ for $0 \le i < m$.  Then inductively define
\[ \id{fe2ip}(x) = \sum_{0\le i<m} r^i \id{fe2ip}(x_i) \]
Inductively, we will have $0 \le \id{fe2ip}(x_i) < r$, and hence $0 \le x <
r^m = q$.

\subsubsection{FE2OSP}
Given a field element $x \in \gf{q}$, the function $\id{fe2osp}(x)$
determines a fixed-length encoding of $x$.  Let $\ell$ be the unique integer
such that $2^{8(\ell-1)} < q \le 2^{8\ell}$.  Then $\id{fe2osp}(x) =
[\id{fe2ip}(x)]_\ell$.

\subsubsection{FE2VOSP}
Given a field element $x \in \gf{q}$ for some $q \le 2^{524288}$, the
function $\id{fe2vosp}(x)$ determines a variable-length encoding of $x$;
specifically, $\id{fe2vosp}(x) = \id{i2vosp}(\id{fe2ip}(x))$.

\subsubsection{EC2OSP}
Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over
some finite field $k$, the function $\id{ec2osp}$ determines an encoding of
$Q$.  For finite points, i.e., where $Z \ne 0$, this encoding is
fixed-length, which is good enough.  If $Z = 0$, the encoding is simply
$[0]_1$, i.e., a single zero octet.  Otherwise, let $x = X/Z$ and $y = Y/Z$;
the encoding of $Q$ is then $[4]_1 \cat \id{fe2osp}(x) \cat \id{fe2osp}(y)$.

\subsubsection{EC2VOSP}
Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over
some finite field $k$, the function $\id{ec2vosp}$ determines a
variable-length encoding of $Q$.  If $Z = 0$, the encoding is simply $[0]_2$,
i.e., two zero octets.  Otherwise, let $x = X/Z$ and $y = Y/Z$; the encoding
of $Q$ is then $\id{fe2vosp}(x) \cat \id{fe2vosp}(y)$.  This is unambiguous
since the first two octets of an encoding constructed by $\id{i2vosp}$ are
not both zero.


\subsection{Schnorr groups} \label{sec:dh-group.schnorr}

Let $p$ be an odd prime, let $q$ be an odd prime factor of $p - 1$, and let
$g \ne 1$ be an element of $\gf{p}^*$ such that $g^q = 1$.  The cyclic
subgroup $G \subseteq \gf{p}^*$ generated by $g$ is a \emph{Schnorr group};
the scalars are the finite field $S = \gf{q}$; and the generator is $P = g$.
\begin{itemize}
\item The Diffie--Hellman operation is simply exponentiation in $\gf{p}$,
  given by $\id{dh}(x, Y) = Y^x$.
\item 
\end{itemize}


\subsection{Short-Weierstraß elliptic curve groups}
\label{sec:dh-group.trad-ec}


\subsection{The X25519 group} \label{sec:dh-group.x25519}


\subsection{The X448 group} \label{sec:dh-group.x448}


%%%----- That's all, folks --------------------------------------------------

%  LocalWords:  TrIPE LaTeX encodings endian monic OSP VOSP TrIPE's

\end{document}