Commit | Line | Data |
---|---|---|
56abd1c0 MW |
1 | %%% -*- mode: LaTeX; TeX-PDF-mode: t -*- |
2 | %%% | |
3 | %%% The TrIPE protocol specification | |
4 | %%% | |
5 | %%% (c) 2017 Straylight/Edgeware | |
6 | %%% | |
7 | ||
8 | %%%----- Licensing notice --------------------------------------------------- | |
9 | %%% | |
10 | %%% This file is part of Trivial IP Encryption (TrIPE). | |
11 | %%% | |
12 | %%% TrIPE is free software: you can redistribute it and/or modify it under | |
13 | %%% the terms of the GNU General Public License as published by the Free | |
14 | %%% Software Foundation; either version 3 of the License, or (at your | |
15 | %%% option) any later version. | |
16 | %%% | |
17 | %%% TrIPE is distributed in the hope that it will be useful, but WITHOUT | |
18 | %%% ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
19 | %%% FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
20 | %%% for more details. | |
21 | %%% | |
22 | %%% You should have received a copy of the GNU General Public License | |
23 | %%% along with TrIPE. If not, see <https://www.gnu.org/licenses/>. | |
24 | ||
25 | %%%-------------------------------------------------------------------------- | |
26 | %%% Preamble. | |
27 | ||
28 | \documentclass[a4paper, article, numbering]{strayman} | |
29 | \usepackage[T1]{fontenc} | |
30 | \usepackage[utf8]{inputenc} | |
31 | \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} | |
32 | \usepackage{mdwlist} | |
33 | \usepackage{mdwmath} | |
34 | \usepackage{crypto} | |
35 | \usepackage{mdwref} | |
36 | \usepackage{sverb} | |
37 | ||
38 | \title{TrIPE: The Trivial IP Encryption protocol} | |
39 | \author{Mark Wooding} | |
40 | %%\date{incomplete} | |
41 | ||
42 | \def\fixme#1{\marginpar{FIXME}[FIXME: #1]} | |
43 | ||
44 | \newenvironment{aside} | |
45 | {\begin{list}{}{\rightmargin=0pt}\footnotesize\item\relax} | |
46 | {\end{list}} | |
47 | ||
48 | \begin{document} | |
49 | ||
50 | %%%-------------------------------------------------------------------------- | |
51 | ||
52 | \maketitle | |
53 | \thispagestyle{empty} | |
54 | ||
55 | \begin{abstract} | |
56 | This document specifies the TrIPE protocol for IP encryption. | |
57 | ||
58 | TrIPE is a fairly simple protocol which allows a pair of hosts to exchange | |
59 | short messages, typically IP datagrams, over a hostile network while | |
60 | maintaining the properties of \emph{secrecy} and \emph{integrity}; i.e., | |
61 | that the content of the messages cannot be determined by eavesdroppers on | |
62 | the network, and that either endpoint can determine whether a message | |
63 | received is an unaltered copy of one that was sent by the other. | |
64 | ||
65 | The protocol is simple enough for a proof of security in the random-oracle | |
66 | model. | |
67 | \end{abstract} | |
68 | ||
69 | %%%-------------------------------------------------------------------------- | |
70 | \section{Introduction} \label{sec:intro} | |
71 | ||
72 | TrIPE, or `Trivial IP Encryption', is a protocol designed for the secure (but | |
73 | unreliable) transmission of IP datagrams over a hostile network between a | |
74 | pair of hosts, named \emph{peers}. Specifically, it has the following | |
75 | properties. | |
76 | \begin{itemize} | |
77 | \item \emph{Secrecy}: an adversary cannot determine anything about the | |
78 | content of transmitted messages, except for their lengths. | |
79 | \item \emph{Integrity}: a recipient can verify that a message received is an | |
80 | unaltered copy of a message sent by its peer, and which has not previously | |
81 | been received. | |
82 | \item \emph{Symmetry}: in the base protocol, the two peers behave | |
83 | identically, which simplifies implementation and analysis. Some ancillary | |
84 | portions of the protocol are asymmetric, in order to deal with asymmetry in | |
85 | the environment. | |
86 | \end{itemize} | |
87 | ||
88 | ||
89 | \subsection{Overview} \label{sec:intro.overview} | |
90 | ||
91 | The TrIPE protocol is used between a pair of \emph{peers}. Neither peer is | |
92 | distinguished in any way: there is no notion of `initiator' or `responder'. | |
93 | ||
94 | Each peer has an asymmetric key pair, consisting of a \emph{private key} | |
95 | which should be known only to the peer itself, and a matching \emph{public | |
96 | key} which must be known by other peers. | |
97 | ||
98 | The TrIPE protocol contains no messages for negotiating options such as | |
99 | cryptographic algorithms or network parameters, and there is no exchange of | |
100 | certificates. It is assumed that administrators configure their | |
101 | implementations with the necessary knowledge about the peers with which they | |
102 | wish to communicate. | |
103 | ||
104 | The protocol has two main parts. | |
105 | \begin{itemize} | |
106 | \item The \emph{key-exchange} subprotocol (\xref{sec:keyexch}) makes use of | |
107 | the peers' public and private keys to establish \emph{keyset}, known to the | |
108 | peers themselves but not to an adversary in control of the network. | |
109 | \item The \emph{bulk transfer} (\xref{sec:xfer}) subprotocol uses keysets | |
110 | established using the key-exchange protocol to transfer messages between | |
111 | the peers. | |
112 | \end{itemize} | |
113 | In addition, there are a few minor subprotocols for various special effects. | |
114 | ||
115 | %%%-------------------------------------------------------------------------- | |
116 | \section{Diffie--Hellman groups} \label{sec:dh-group} | |
117 | ||
118 | \subsection{Operations} \label{sec:dh-group.ops} | |
119 | ||
120 | A \emph{Diffie--Hellman group} consists of a pair of sets $S$ and $G$, of | |
121 | \emph{scalars} and \emph{group elements} respectively, a distinguished | |
122 | \emph{generator} element $P \in G$, and a number of operations on these | |
123 | groups. In the following descriptions, $x$ and $y$ are scalars; $X$, $Y$, | |
124 | and $Z$ are group elements; and $a$ and $a'$ are octet strings. | |
125 | ||
126 | An \emph{encoding} of group elements is defined by a pair of operations | |
127 | \id{enc} and \id{dec}, as follows. | |
128 | \begin{itemize} | |
129 | \item Given a group element $X$, $\id{enc}(X)$ encodes it as an octet string. | |
130 | \item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a group | |
131 | element $X$ and remainder string $a'$ from it. | |
132 | \end{itemize} | |
133 | Furthermore, if $a'$ is any octet string, and $X$ is any group element, then | |
134 | it must be the case that $X, a' = \id{dec}(\id{enc}(X) \cat a')$. Encodings | |
135 | of scalars are defined similarly. | |
136 | ||
137 | \begin{itemize} | |
138 | \item $\id{dh}(x, Y)$ calculates a group element $Z$. To be a proper | |
139 | Diffie--Hellman group, it must be the case that $\id{dh}(x, \id{dh}(y, P)) | |
140 | = \id{dh}(y, \id{dh}(x, P))$ for all scalars $x$ and $y$. For security, it | |
141 | must be computationally intractable to determine $\id{dh}(x, \id{dh}(y, | |
142 | P))$ given $X = \id{dh}(x, P)$ and $Y = \id{dh}(y, P)$ (i.e., the | |
143 | \emph{computational Diffie--Hellman assumption} must hold). | |
144 | \item $\id{enc-ge-public}$ and $\id{dec-ge-public}$ together define an | |
145 | encoding on group elements, for which no special properties are required. | |
146 | \item $\id{enc-ge-secret}$ and $\id{dec-ge-secret}$ together define an | |
147 | encoding on group elements where all encodings have the same length. | |
148 | \item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an | |
149 | encoding on group elements where all encodings should have the same length. | |
150 | \item $\id{enc-sc}$ and $\id{dec-sc}$ together define an encoding on scalars, | |
151 | where all encodings have the same length. Let $\id{scsz}$ be the length of | |
152 | an encoded scalar. | |
153 | \end{itemize} | |
154 | \begin{aside} | |
155 | In an ideal world, we would only have one group-element encoding rather | |
156 | than three. The present situation is caused by unfortunate historical | |
157 | mistakes. Of course, nothing prevents newer Diffie--Hellman group | |
158 | specifications from using the same (constant-length) encoding for all three | |
159 | group-element encodings described above, and, indeed, the X25519 and X448 | |
160 | groups defined below do this. | |
161 | \end{aside} | |
162 | ||
163 | ||
164 | \subsection{Primitive encoding functions} \label{sec:dh-group.encode} | |
165 | ||
166 | \subsubsection{I2OSP} | |
167 | If $\ell$ and $n$ are integers with $0 \le n < 2^{8\ell}$, then $[n]_\ell$ | |
168 | denotes the $\ell$-digit big-endian base-256 encoding of $n$. Specifically, | |
169 | let $a_0$, $a_1$, \ldots, $a_{\ell-1}$ be the unique integers such that $0 | |
170 | \le a_i < 256$ for $0 \le i < \ell$, and | |
171 | \[ n = \sum_{0\le i<\ell} 2^{8i} a_i \] | |
172 | Then $[n]_\ell$ is the $\ell$-octet string $a_{\ell-1} \cat \cdots \cat a_1 | |
173 | \cat a_0$. | |
174 | ||
175 | \subsubsection{I2VOSP} | |
176 | Given an integer $0 \le n < 2^{524288}$, the function $\id{i2vosp}(n)$ | |
177 | determines a variable-length big-endian base-256 encoding of $n$. If $n = 0$ | |
178 | then let $\ell = 1$; otherwise, let $\ell$ be the unique integer such that | |
179 | $2^{8(\ell-1)} \le n < 2^{8\ell}$; since $n$ is bounded, it must be that | |
180 | $\ell < 65536$. Then $\id{i2vosp}(n) = [\ell]_2 \cat [n]_\ell$. | |
181 | ||
182 | \subsubsection{FE2IP} | |
183 | Given an element $x$ of a finite field $\gf{q}$, the function $\id{fe2ip}$ | |
184 | determines a unique integer such that $0 \le \id{fe2ip}(x) < q$. | |
185 | ||
186 | If $q$ is prime, then $\gf{q} = \Z/q\Z$: let $\phi_q(n)$ be the unique ring | |
187 | homomorphism from $\Z$ to $\gf{q}$, and define $\id{fe2ip}(x)$ to be the | |
188 | smallest nonnegative integer $n$ such that $x = \phi_q(n)$; it is necessarily | |
189 | the case that $0 \le \id{fe2ip}(x) < q$. | |
190 | ||
191 | Otherwise, $q = r^m$ for some prime power $r$ and an integer $m > 1$. Fix an | |
192 | ordered basis $\{ u_0, u_1, \ldots, u_{m-1} \}$ for $\gf{q}$ as a vector | |
193 | space over $\gf{r}$. | |
194 | \begin{aside} | |
195 | This is often a polynomial basis: if $u(t) = u_0 + u_1 t + \cdots + u_{m-1} | |
196 | t^{m-1} + t^m$ is a monic irreducible polynomial of degree~$m$ over | |
197 | $\gf{r}$, then $\{ u_0, u_1, \cdots, u_{m-1} \}$ is a suitable basis, | |
198 | representing $\gf{q}$ as the quotient ring $\gf{r}[t]/(u(t))$. Other | |
199 | representations are also possible. | |
200 | ||
201 | In practice, this case occurs when dealing with elliptic curves, and the | |
202 | specification for a curve over a non-prime field will include a description | |
203 | of the field representation sufficient to apply this definition. | |
204 | \end{aside} | |
205 | Then any element $x \in \gf{q}$ can be written uniquely as a sum | |
206 | \[ x = \sum_{0\le i<m} u_i x_i \] | |
207 | where $x_i \in \gf{r}$ for $0 \le i < m$. Then inductively define | |
208 | \[ \id{fe2ip}(x) = \sum_{0\le i<m} r^i \id{fe2ip}(x_i) \] | |
209 | Inductively, we will have $0 \le \id{fe2ip}(x_i) < r$, and hence $0 \le x < | |
210 | r^m = q$. | |
211 | ||
212 | \subsubsection{FE2OSP} | |
213 | Given a field element $x \in \gf{q}$, the function $\id{fe2osp}(x)$ | |
214 | determines a fixed-length encoding of $x$. Let $\ell$ be the unique integer | |
215 | such that $2^{8(\ell-1)} < q \le 2^{8\ell}$. Then $\id{fe2osp}(x) = | |
216 | [\id{fe2ip}(x)]_\ell$. | |
217 | ||
218 | \subsubsection{FE2VOSP} | |
219 | Given a field element $x \in \gf{q}$ for some $q \le 2^{524288}$, the | |
220 | function $\id{fe2vosp}(x)$ determines a variable-length encoding of $x$; | |
221 | specifically, $\id{fe2vosp}(x) = \id{i2vosp}(\id{fe2ip}(x))$. | |
222 | ||
223 | \subsubsection{EC2OSP} | |
224 | Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over | |
225 | some finite field $k$, the function $\id{ec2osp}$ determines an encoding of | |
226 | $Q$. For finite points, i.e., where $Z \ne 0$, this encoding is | |
227 | fixed-length, which is good enough. If $Z = 0$, the encoding is simply | |
228 | $[0]_1$, i.e., a single zero octet. Otherwise, let $x = X/Z$ and $y = Y/Z$; | |
229 | the encoding of $Q$ is then $[4]_1 \cat \id{fe2osp}(x) \cat \id{fe2osp}(y)$. | |
230 | ||
231 | \subsubsection{EC2VOSP} | |
232 | Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over | |
233 | some finite field $k$, the function $\id{ec2vosp}$ determines a | |
234 | variable-length encoding of $Q$. If $Z = 0$, the encoding is simply $[0]_2$, | |
235 | i.e., two zero octets. Otherwise, let $x = X/Z$ and $y = Y/Z$; the encoding | |
236 | of $Q$ is then $\id{fe2vosp}(x) \cat \id{fe2vosp}(y)$. This is unambiguous | |
237 | since the first two octets of an encoding constructed by $\id{i2vosp}$ are | |
238 | not both zero. | |
239 | ||
240 | ||
241 | \subsection{Schnorr groups} \label{sec:dh-group.schnorr} | |
242 | ||
243 | Let $p$ be an odd prime, let $q$ be an odd prime factor of $p - 1$, and let | |
244 | $g \ne 1$ be an element of $\gf{p}^*$ such that $g^q = 1$. The cyclic | |
245 | subgroup $G \subseteq \gf{p}^*$ generated by $g$ is a \emph{Schnorr group}; | |
246 | the scalars are the finite field $S = \gf{q}$; and the generator is $P = g$. | |
247 | \begin{itemize} | |
248 | \item The Diffie--Hellman operation is given by $\id{dh}(x, Y) = Y^x$. | |
249 | \end{itemize} | |
250 | ||
251 | ||
252 | \subsection{Short-Weierstraß elliptic curve groups} | |
253 | \label{sec:dh-group.trad-ec} | |
254 | ||
255 | ||
256 | \subsection{The X25519 group} \label{sec:dh-group.x25519} | |
257 | ||
258 | ||
259 | \subsection{The X448 group} \label{sec:dh-group.x448} | |
260 | ||
261 | ||
262 | %%%----- That's all, folks -------------------------------------------------- | |
263 | ||
264 | % LocalWords: TrIPE LaTeX encodings endian monic OSP VOSP | |
265 | ||
266 | \end{document} |