From: Mark Wooding <mdw@distorted.org.uk>
Date: Wed, 11 Oct 2017 01:00:08 +0000 (+0100)
Subject: doc/tripe-protocol.tex: Start on a new protocol specification.
X-Git-Url: https://git.distorted.org.uk/~mdw/tripe/commitdiff_plain/56abd1c0e98f874fe0863db3417ea02eee073f53

doc/tripe-protocol.tex: Start on a new protocol specification.

This is one of the two main missing pieces.
---

diff --git a/doc/tripe-protocol.tex b/doc/tripe-protocol.tex
new file mode 100644
index 00000000..d03a4b1c
--- /dev/null
+++ b/doc/tripe-protocol.tex
@@ -0,0 +1,266 @@
+%%% -*- 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}
+
+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.
+
+An \emph{encoding} of group elements is defined by a pair of operations
+\id{enc} and \id{dec}, as follows.
+\begin{itemize}
+\item Given a group element $X$, $\id{enc}(X)$ encodes it as an octet string.
+\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a group
+  element $X$ and remainder string $a'$ from it.
+\end{itemize}
+Furthermore, if $a'$ is any octet string, and $X$ is any group element, then
+it must be the case that $X, a' = \id{dec}(\id{enc}(X) \cat a')$.  Encodings
+of scalars are defined similarly.
+
+\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.
+\item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an
+  encoding on group elements where all encodings should have the same length.
+\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}
+\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 given by $\id{dh}(x, Y) = Y^x$.
+\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
+
+\end{document}