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 | ||
8c3ad0db MW |
120 | An \emph{encoding} on some set of values $S$ is defined by a pair of |
121 | operations \id{enc} and \id{dec}, as follows. | |
122 | \begin{itemize} | |
123 | \item Given a value $x \in S$, $\id{enc}(x)$ encodes it as an octet string. | |
124 | \item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a value $x$ | |
125 | and remainder string $a'$ from it. | |
126 | \end{itemize} | |
127 | Hence, the possible encodings of values form a prefix-free set of strings. | |
128 | Furthermore, if $a'$ is any octet string, and $x \in S$ is any value, then it | |
129 | must be the case that $x, a' = \id{dec}(\id{enc}(x) \cat a')$. | |
130 | ||
56abd1c0 MW |
131 | A \emph{Diffie--Hellman group} consists of a pair of sets $S$ and $G$, of |
132 | \emph{scalars} and \emph{group elements} respectively, a distinguished | |
133 | \emph{generator} element $P \in G$, and a number of operations on these | |
134 | groups. In the following descriptions, $x$ and $y$ are scalars; $X$, $Y$, | |
135 | and $Z$ are group elements; and $a$ and $a'$ are octet strings. | |
56abd1c0 MW |
136 | \begin{itemize} |
137 | \item $\id{dh}(x, Y)$ calculates a group element $Z$. To be a proper | |
138 | Diffie--Hellman group, it must be the case that $\id{dh}(x, \id{dh}(y, P)) | |
139 | = \id{dh}(y, \id{dh}(x, P))$ for all scalars $x$ and $y$. For security, it | |
140 | must be computationally intractable to determine $\id{dh}(x, \id{dh}(y, | |
141 | P))$ given $X = \id{dh}(x, P)$ and $Y = \id{dh}(y, P)$ (i.e., the | |
142 | \emph{computational Diffie--Hellman assumption} must hold). | |
143 | \item $\id{enc-ge-public}$ and $\id{dec-ge-public}$ together define an | |
144 | encoding on group elements, for which no special properties are required. | |
145 | \item $\id{enc-ge-secret}$ and $\id{dec-ge-secret}$ together define an | |
8c3ad0db MW |
146 | encoding on group elements where all encodings have the same length, except |
147 | with negligible probability. | |
148 | \item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an encoding | |
149 | on group elements where all encodings \emph{should} have the same length, | |
150 | except with negligible probability.\footnote{% | |
151 | The existence of groups without (mostly) fixed-length hashing encodings | |
152 | is a historical mistake. If a variable-length encoding is used here, | |
153 | information about group element(s) being hashed may leak to an adversary | |
154 | through timing channels.} % | |
155 | The decoding operation is never invoked, so it need not be possible to | |
156 | implement it efficiently, though it must be theoretically possible to | |
157 | decode encodings unambiguously. | |
56abd1c0 MW |
158 | \item $\id{enc-sc}$ and $\id{dec-sc}$ together define an encoding on scalars, |
159 | where all encodings have the same length. Let $\id{scsz}$ be the length of | |
160 | an encoded scalar. | |
161 | \end{itemize} | |
8c3ad0db MW |
162 | In the following descriptions, decoding functions are not described explicitly |
163 | Decoding operations must validate input sufficiently that the $\id{dh}$ | |
164 | operation can be performed successfully and without leaking secret inputs | |
165 | during the computation; but it is \emph{not} necessary to perform further | |
166 | precise verification. For example, an implementation need not verify that an | |
167 | incoming group element is actually within the subgroup generated by $P$; and | |
168 | an elliptic-curve group need not verify that an incoming pair of coordinates | |
169 | actually correspond to a point on the curve. | |
56abd1c0 MW |
170 | \begin{aside} |
171 | In an ideal world, we would only have one group-element encoding rather | |
172 | than three. The present situation is caused by unfortunate historical | |
173 | mistakes. Of course, nothing prevents newer Diffie--Hellman group | |
174 | specifications from using the same (constant-length) encoding for all three | |
175 | group-element encodings described above, and, indeed, the X25519 and X448 | |
176 | groups defined below do this. | |
177 | \end{aside} | |
178 | ||
179 | ||
180 | \subsection{Primitive encoding functions} \label{sec:dh-group.encode} | |
181 | ||
182 | \subsubsection{I2OSP} | |
183 | If $\ell$ and $n$ are integers with $0 \le n < 2^{8\ell}$, then $[n]_\ell$ | |
184 | denotes the $\ell$-digit big-endian base-256 encoding of $n$. Specifically, | |
185 | let $a_0$, $a_1$, \ldots, $a_{\ell-1}$ be the unique integers such that $0 | |
186 | \le a_i < 256$ for $0 \le i < \ell$, and | |
187 | \[ n = \sum_{0\le i<\ell} 2^{8i} a_i \] | |
188 | Then $[n]_\ell$ is the $\ell$-octet string $a_{\ell-1} \cat \cdots \cat a_1 | |
189 | \cat a_0$. | |
190 | ||
191 | \subsubsection{I2VOSP} | |
192 | Given an integer $0 \le n < 2^{524288}$, the function $\id{i2vosp}(n)$ | |
193 | determines a variable-length big-endian base-256 encoding of $n$. If $n = 0$ | |
194 | then let $\ell = 1$; otherwise, let $\ell$ be the unique integer such that | |
195 | $2^{8(\ell-1)} \le n < 2^{8\ell}$; since $n$ is bounded, it must be that | |
196 | $\ell < 65536$. Then $\id{i2vosp}(n) = [\ell]_2 \cat [n]_\ell$. | |
197 | ||
198 | \subsubsection{FE2IP} | |
199 | Given an element $x$ of a finite field $\gf{q}$, the function $\id{fe2ip}$ | |
200 | determines a unique integer such that $0 \le \id{fe2ip}(x) < q$. | |
201 | ||
202 | If $q$ is prime, then $\gf{q} = \Z/q\Z$: let $\phi_q(n)$ be the unique ring | |
203 | homomorphism from $\Z$ to $\gf{q}$, and define $\id{fe2ip}(x)$ to be the | |
204 | smallest nonnegative integer $n$ such that $x = \phi_q(n)$; it is necessarily | |
205 | the case that $0 \le \id{fe2ip}(x) < q$. | |
206 | ||
207 | Otherwise, $q = r^m$ for some prime power $r$ and an integer $m > 1$. Fix an | |
208 | ordered basis $\{ u_0, u_1, \ldots, u_{m-1} \}$ for $\gf{q}$ as a vector | |
209 | space over $\gf{r}$. | |
210 | \begin{aside} | |
211 | This is often a polynomial basis: if $u(t) = u_0 + u_1 t + \cdots + u_{m-1} | |
212 | t^{m-1} + t^m$ is a monic irreducible polynomial of degree~$m$ over | |
213 | $\gf{r}$, then $\{ u_0, u_1, \cdots, u_{m-1} \}$ is a suitable basis, | |
214 | representing $\gf{q}$ as the quotient ring $\gf{r}[t]/(u(t))$. Other | |
215 | representations are also possible. | |
216 | ||
217 | In practice, this case occurs when dealing with elliptic curves, and the | |
218 | specification for a curve over a non-prime field will include a description | |
219 | of the field representation sufficient to apply this definition. | |
220 | \end{aside} | |
221 | Then any element $x \in \gf{q}$ can be written uniquely as a sum | |
222 | \[ x = \sum_{0\le i<m} u_i x_i \] | |
223 | where $x_i \in \gf{r}$ for $0 \le i < m$. Then inductively define | |
224 | \[ \id{fe2ip}(x) = \sum_{0\le i<m} r^i \id{fe2ip}(x_i) \] | |
225 | Inductively, we will have $0 \le \id{fe2ip}(x_i) < r$, and hence $0 \le x < | |
226 | r^m = q$. | |
227 | ||
228 | \subsubsection{FE2OSP} | |
229 | Given a field element $x \in \gf{q}$, the function $\id{fe2osp}(x)$ | |
230 | determines a fixed-length encoding of $x$. Let $\ell$ be the unique integer | |
231 | such that $2^{8(\ell-1)} < q \le 2^{8\ell}$. Then $\id{fe2osp}(x) = | |
232 | [\id{fe2ip}(x)]_\ell$. | |
233 | ||
234 | \subsubsection{FE2VOSP} | |
235 | Given a field element $x \in \gf{q}$ for some $q \le 2^{524288}$, the | |
236 | function $\id{fe2vosp}(x)$ determines a variable-length encoding of $x$; | |
237 | specifically, $\id{fe2vosp}(x) = \id{i2vosp}(\id{fe2ip}(x))$. | |
238 | ||
239 | \subsubsection{EC2OSP} | |
240 | Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over | |
241 | some finite field $k$, the function $\id{ec2osp}$ determines an encoding of | |
242 | $Q$. For finite points, i.e., where $Z \ne 0$, this encoding is | |
243 | fixed-length, which is good enough. If $Z = 0$, the encoding is simply | |
244 | $[0]_1$, i.e., a single zero octet. Otherwise, let $x = X/Z$ and $y = Y/Z$; | |
245 | the encoding of $Q$ is then $[4]_1 \cat \id{fe2osp}(x) \cat \id{fe2osp}(y)$. | |
246 | ||
247 | \subsubsection{EC2VOSP} | |
248 | Given a projective point $Q = (X : Y : Z)$ on an elliptic curve $E(k)$ over | |
249 | some finite field $k$, the function $\id{ec2vosp}$ determines a | |
250 | variable-length encoding of $Q$. If $Z = 0$, the encoding is simply $[0]_2$, | |
251 | i.e., two zero octets. Otherwise, let $x = X/Z$ and $y = Y/Z$; the encoding | |
252 | of $Q$ is then $\id{fe2vosp}(x) \cat \id{fe2vosp}(y)$. This is unambiguous | |
253 | since the first two octets of an encoding constructed by $\id{i2vosp}$ are | |
254 | not both zero. | |
255 | ||
256 | ||
257 | \subsection{Schnorr groups} \label{sec:dh-group.schnorr} | |
258 | ||
259 | Let $p$ be an odd prime, let $q$ be an odd prime factor of $p - 1$, and let | |
260 | $g \ne 1$ be an element of $\gf{p}^*$ such that $g^q = 1$. The cyclic | |
261 | subgroup $G \subseteq \gf{p}^*$ generated by $g$ is a \emph{Schnorr group}; | |
262 | the scalars are the finite field $S = \gf{q}$; and the generator is $P = g$. | |
263 | \begin{itemize} | |
8c3ad0db MW |
264 | \item The Diffie--Hellman operation is simply exponentiation in $\gf{p}$, |
265 | given by $\id{dh}(x, Y) = Y^x$. | |
266 | \item | |
56abd1c0 MW |
267 | \end{itemize} |
268 | ||
269 | ||
270 | \subsection{Short-Weierstraß elliptic curve groups} | |
271 | \label{sec:dh-group.trad-ec} | |
272 | ||
273 | ||
274 | \subsection{The X25519 group} \label{sec:dh-group.x25519} | |
275 | ||
276 | ||
277 | \subsection{The X448 group} \label{sec:dh-group.x448} | |
278 | ||
279 | ||
280 | %%%----- That's all, folks -------------------------------------------------- | |
281 | ||
8c3ad0db | 282 | % LocalWords: TrIPE LaTeX encodings endian monic OSP VOSP TrIPE's |
56abd1c0 MW |
283 | |
284 | \end{document} |