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} | |
a4d41118 MW |
32 | \usepackage{longtable} |
33 | \usepackage{mathenv} | |
56abd1c0 MW |
34 | \usepackage{mdwlist} |
35 | \usepackage{mdwmath} | |
56abd1c0 | 36 | \usepackage{mdwref} |
a4d41118 | 37 | \usepackage{mdwtab} |
56abd1c0 | 38 | \usepackage{sverb} |
a4d41118 MW |
39 | \usepackage{crypto} |
40 | ||
41 | \bibliographystyle{mdwalpha} | |
42 | \numberwithin{table}{section} | |
56abd1c0 MW |
43 | |
44 | \title{TrIPE: The Trivial IP Encryption protocol} | |
45 | \author{Mark Wooding} | |
46 | %%\date{incomplete} | |
47 | ||
a4d41118 MW |
48 | \let\len\ell |
49 | \let\phi\varphi | |
50 | \let\emptyset\varnothing | |
51 | \let\emptystring\varepsilon | |
52 | \let\len\ell | |
53 | \let\octet\Sigma | |
54 | \def\syms{\mathbb{Y}} | |
55 | \def\lift#1{\lfloor#1\rfloor} | |
56 | \def\padm#1{\hbox{\kern1pt #1}} | |
57 | \def\upto{\mathbin{.\,.}} | |
58 | \def\hex#1{\texttt{#1}_x} | |
59 | \def\PP{\mathbb{P}} | |
60 | \def\bit{\mathop{\mathrm{bit}}\nolimits} | |
61 | \def\bitand{\mathord{\&}} | |
62 | \def\bitor{\mathbin{|}} | |
63 | \def\t{\cookie{t}} | |
64 | \def\nil{\cookie{nil}} | |
65 | ||
66 | \def\fixme#1{\leavevmode\marginpar{FIXME}[FIXME: #1]} | |
56abd1c0 MW |
67 | |
68 | \newenvironment{aside} | |
69 | {\begin{list}{}{\rightmargin=0pt}\footnotesize\item\relax} | |
70 | {\end{list}} | |
71 | ||
a4d41118 MW |
72 | \errorcontextlines=99 |
73 | ||
56abd1c0 MW |
74 | \begin{document} |
75 | ||
76 | %%%-------------------------------------------------------------------------- | |
77 | ||
78 | \maketitle | |
79 | \thispagestyle{empty} | |
80 | ||
81 | \begin{abstract} | |
82 | This document specifies the TrIPE protocol for IP encryption. | |
83 | ||
84 | TrIPE is a fairly simple protocol which allows a pair of hosts to exchange | |
85 | short messages, typically IP datagrams, over a hostile network while | |
86 | maintaining the properties of \emph{secrecy} and \emph{integrity}; i.e., | |
87 | that the content of the messages cannot be determined by eavesdroppers on | |
88 | the network, and that either endpoint can determine whether a message | |
89 | received is an unaltered copy of one that was sent by the other. | |
90 | ||
91 | The protocol is simple enough for a proof of security in the random-oracle | |
92 | model. | |
93 | \end{abstract} | |
94 | ||
a4d41118 MW |
95 | \tableofcontents |
96 | ||
56abd1c0 MW |
97 | %%%-------------------------------------------------------------------------- |
98 | \section{Introduction} \label{sec:intro} | |
99 | ||
100 | TrIPE, or `Trivial IP Encryption', is a protocol designed for the secure (but | |
101 | unreliable) transmission of IP datagrams over a hostile network between a | |
102 | pair of hosts, named \emph{peers}. Specifically, it has the following | |
103 | properties. | |
104 | \begin{itemize} | |
105 | \item \emph{Secrecy}: an adversary cannot determine anything about the | |
106 | content of transmitted messages, except for their lengths. | |
107 | \item \emph{Integrity}: a recipient can verify that a message received is an | |
108 | unaltered copy of a message sent by its peer, and which has not previously | |
109 | been received. | |
110 | \item \emph{Symmetry}: in the base protocol, the two peers behave | |
111 | identically, which simplifies implementation and analysis. Some ancillary | |
112 | portions of the protocol are asymmetric, in order to deal with asymmetry in | |
113 | the environment. | |
114 | \end{itemize} | |
115 | ||
116 | ||
117 | \subsection{Overview} \label{sec:intro.overview} | |
118 | ||
119 | The TrIPE protocol is used between a pair of \emph{peers}. Neither peer is | |
120 | distinguished in any way: there is no notion of `initiator' or `responder'. | |
121 | ||
122 | Each peer has an asymmetric key pair, consisting of a \emph{private key} | |
123 | which should be known only to the peer itself, and a matching \emph{public | |
124 | key} which must be known by other peers. | |
125 | ||
126 | The TrIPE protocol contains no messages for negotiating options such as | |
127 | cryptographic algorithms or network parameters, and there is no exchange of | |
128 | certificates. It is assumed that administrators configure their | |
129 | implementations with the necessary knowledge about the peers with which they | |
130 | wish to communicate. | |
131 | ||
132 | The protocol has two main parts. | |
133 | \begin{itemize} | |
134 | \item The \emph{key-exchange} subprotocol (\xref{sec:keyexch}) makes use of | |
135 | the peers' public and private keys to establish \emph{keyset}, known to the | |
136 | peers themselves but not to an adversary in control of the network. | |
137 | \item The \emph{bulk transfer} (\xref{sec:xfer}) subprotocol uses keysets | |
138 | established using the key-exchange protocol to transfer messages between | |
139 | the peers. | |
140 | \end{itemize} | |
141 | In addition, there are a few minor subprotocols for various special effects. | |
142 | ||
143 | %%%-------------------------------------------------------------------------- | |
a4d41118 | 144 | \section{Preliminaries} \label{sec:prelim} |
56abd1c0 | 145 | |
a4d41118 | 146 | \subsection{Bits} \label{sec:prelim.bit} |
56abd1c0 | 147 | |
a4d41118 MW |
148 | A \emph{bit} is an element of the set $\{ 0, 1 \}$. |
149 | ||
150 | The elementary operators $\bitand$ (`and'), $\bitor$ (`or'), and $\xor$ | |
151 | (`exclusive-or', or just `xor') are defined on bits as shown in | |
152 | \xref{tab:prelim.bit.ops}. | |
153 | \begin{table} | |
154 | \begin{tabular}[C]{|cc|ccc|} \hlx{hv} | |
155 | $a$ & $b$ & $a \bitand b$ & $a \bitor b$ & $a \xor b$ \\ \hlx{vhv} | |
156 | 0 & 0 & 0 & 0 & 0 \\ \hlx{v} | |
157 | 0 & 1 & 0 & 1 & 1 \\ \hlx{v} | |
158 | 1 & 0 & 0 & 1 & 1 \\ \hlx{v} | |
159 | 1 & 1 & 1 & 1 & 0 \\ \hlx{vh} | |
160 | \end{tabular} | |
161 | \caption{Elementary bit operators} \label{tab:prelim.bit.ops} | |
162 | \end{table} | |
163 | ||
164 | Let $n$ be an integer. For $i \ge 0$, define $\bit_i n \in \{ 0, 1 \}$ such | |
165 | that, for any $N \ge 0$, | |
166 | \[ n \equiv \sum_{0\le i<N} 2^i \bit_i n \pmod{2^N} \padm. \] | |
167 | Let $(b_i)_{i\ge0}$ be an infinite sequence of bits. If this sequence | |
168 | \emph{converges} -- i.e., there exists some $N \ge 0$ such that $b_i = b_N$ | |
169 | for all $i \ge N$ -- then there exists a unique integer $n$ -- specifically, | |
170 | $n = \sum_{0\le i<N} 2^i b_i - 2^N b_N$ -- such that $\bit_i n = b_i$ for all | |
171 | $i \ge 0$. The sequence of bits corresponding to an integer is called its | |
172 | \emph{two's complement representation}. | |
173 | ||
174 | Let $m$ and $n$ be integers. For each elementary bit operator~$\circ$, | |
175 | define $m \circ n$ to be the unique integer~$r$ such that $\bit_i r = \bit_i | |
176 | m \circ \bit_i n$. | |
177 | ||
178 | ||
179 | \subsection{Octet strings} \label{sec:prelim.string} | |
180 | ||
181 | An \emph{octet} is an integer between~0 and~255 inclusive; formally, define | |
182 | $\octet = \{ 0, 1, \ldots, 255 \}$. | |
183 | ||
184 | An \emph{octet string} is a finite sequence of octets. Define $\octet^n$ to | |
185 | be the set of $n$-octet strings, Formally, define $\octet^0 = \emptystring$, | |
186 | where $\emptystring$ denotes the empty string, and $\octet^n = \octet \times | |
187 | \octet^{n-1}$ for $n > 0$. The set of all octet strings is $\octet^* = | |
188 | \bigcup_{i\ge0} \octet^i$. | |
189 | ||
190 | Let $x, y \in \octet^*$ be octet strings. The \emph{length} of $x$, denoted | |
191 | $\len(x)$, is the unique $n$ such that $x \in \octet^n$. | |
192 | ||
193 | For any $0 \le i < \len(x)$, define the \emph{$i$th octet} of $x$ as follows. | |
194 | If $x = \emptystring$ then this is not well-defined. Otherwise, we have $x = | |
195 | (a, y)$ with $a \in \octet$ and $y \in \octet^{\len(x)-1}$. Inductively | |
196 | define $x[0] = a$, and $x[i] = y[i - 1]$ for $1 \le i < \len(x)$. | |
197 | ||
198 | When $x_i \in \octet$ for $0 \le i < n$, then $[x_0, x_1, \ldots, x_{n-1}]$ | |
199 | denotes the octet string $x \in \octet^n$ such that $\len(a) = n$ and $x[i] = | |
200 | x_i$ for $0 \le i < n$. A text string in monospace type surrounded by | |
201 | double-quote marks \texttt{"}\dots\texttt{"} denotes the octet string | |
202 | containing the corresponding ASCII code points; e.g., \texttt{"example"} | |
203 | denotes the octet string $[101, 120, 97, 109, 112, 108, 101]$. | |
56abd1c0 | 204 | \begin{aside} |
a4d41118 MW |
205 | Double quotes themselves do not occur within such strings in this |
206 | specification, so the issue of escaping does not arise. | |
56abd1c0 MW |
207 | \end{aside} |
208 | ||
a4d41118 MW |
209 | If $\ell$ and $n$ are integers with $0 \le n < 256^\ell$, then $[n]_\ell$ |
210 | denotes the $\ell$-digit big-endian base-256 encoding of $n$. Specifically, | |
211 | $a = [n]_\ell$ is the unique octet string such that $\len(a) = \ell$ and | |
212 | \[ n = \sum_{0\le i<\ell} 2^{8i} a[\ell - i - 1] \padm. \] | |
213 | Similarly, $[n]'_\ell$ denotes the $\ell$-digit little-endian base-256 | |
214 | encoding of $n$; specifically, $a = [n]'_\ell$ is the unique octet string | |
215 | such that $\len(a) = \ell$ and | |
216 | \[ n = \sum_{0\le i<\ell} 2^{8i} a[i] \padm. \] | |
56abd1c0 | 217 | |
a4d41118 MW |
218 | The \emph{concatenation} of $x$ and $y$, denoted $x \cat y$, is the octet |
219 | string $z$ such that $\len(z) = \len(x) + \len(y)$, and $z[i] = x[i]$ if $0 | |
220 | \le i < \len(x)$, or $z[i] = y[i - \len(x)]$ if $\len(x) \le i < \len(z)$. | |
56abd1c0 | 221 | |
a4d41118 MW |
222 | If $n \ge 0$, the \emph{$n$-fold repetition of $x$}, denoted $x^n$, consists |
223 | of $n$ copies of $x$ concatenated together. Formally, $x^0 = \emptystring$, | |
224 | and $x^n = x^{n-1} \cat x$ if $n \ge 1$. | |
225 | ||
226 | If $0 \le i \le j \le \len(x)$, then the \emph{substring} of $x$ | |
227 | \emph{between $i$ and $j$}, denoted $x[i \upto j]$, is the octet string $z$ | |
228 | of length $j - i$ such that $z[k] = x[k - i]$ for $0 \le k < j - i$. It is | |
229 | always the case that $x = x[0 \upto i] \cat x[i \upto j] \cat x[j \upto | |
230 | \len(x)]$. | |
231 | ||
232 | For each elementary bit operator $\circ$ defined in | |
233 | \xref{tab:prelim.bit.ops}, and each pair of octet strings $x$ and $y$ of | |
234 | equal length, define $x \circ y$ to be the octet string $z$ such that | |
235 | $\len(z) = \len(x) = \len(y)$ and $z[i] = x[i] \circ y[i]$ for $0 \le i < | |
236 | \len(z)$. | |
237 | ||
238 | ||
239 | \subsection{Integers} \label{sec:prelim.integer} | |
240 | ||
241 | Define the \emph{length} $\len(n)$ of a nonnegative integer $n \in \N$ as | |
242 | follows: if $n = 0$ then $\len(n) = 1$; otherwise, $\len(n)$ is the unique | |
243 | integer $\ell$ such that $256^{\ell-1} \le n < 256^\ell$. | |
244 | ||
245 | Numbers written in monospace type with a subscript~$x$ are in hexadecimal; | |
246 | the digits \texttt{0}--\texttt{9} have their usual values, and letters | |
247 | \texttt{a}--\texttt{f} have values 10--15. For example, $\hex{9c} = 156$. | |
248 | ||
249 | ||
250 | \subsection{Symbols} \label{sec:prelim.symbol} | |
251 | ||
252 | A \emph{symbol} is an object with no properties other than its distinctive | |
253 | identity, and no operations other than comparison for equality. Symbols are | |
254 | written as a name in monospace type, e.g., \cookie{example}. A symbol's name | |
255 | exists only to allow a human reader to distinguish it from other symbols. | |
256 | ||
257 | The set of symbols is denoted $\syms$. If $A$ is a set disjoint from | |
258 | $\syms$, then $\lift{A} = A \cup \syms$. | |
259 | ||
260 | ||
261 | \subsection{Encodings} \label{sec:prelim.encode} | |
262 | ||
263 | An \emph{encoding}~$C$ on some set of values $S$ is defined by a pair of | |
264 | operations, as follows. | |
265 | \begin{itemize} | |
266 | \item An \emph{encoding operation}~$C.\id{enc}$. Given a value $x \in S$, | |
267 | $C.\id{enc}$ encodes it as an octet string $a = C.\id{enc}(x) \in | |
268 | \octet^*$. | |
269 | \item A \emph{decoding operation}~$C.\id{dec}$. Given a string $a \in | |
270 | \octet^*$, $C.\id{dec}$ returns a pair $(x, a') = C.\id{dec}(a)$: if the | |
271 | operation succeeded, then $x \in S$ is the decoded value, and $a' \in | |
272 | \octet^*$ is the remaining suffix of~$a$; otherwise $x = | |
273 | \cookie{err-malformed}$ and $a' = \emptystring$. | |
274 | \end{itemize} | |
275 | Hence, the possible encodings of values form a prefix-free set of strings. | |
276 | Furthermore, for any $a' \in \octet^*$ and $x \in S$, it must be the case | |
277 | that $x, a' = \id{dec}(\id{enc}(x) \cat a')$. | |
278 | ||
279 | This specification does not define decoding operations explicitly; their | |
280 | behaviour is unambiguously determined by the corresponding encoding | |
281 | operations. | |
56abd1c0 MW |
282 | |
283 | \subsubsection{I2VOSP} | |
a4d41118 MW |
284 | The encoding $\id{i2vosp}$ represents an integer ~$n$ in the range $0 \le n < |
285 | 2^{524288}$ as a variable-length sequence of octets in big-endian order. | |
286 | Specifically, $\id{i2vosp}.\id{enc}(n) = [\len(n)]_2 \cat [n]_{\len(n)}$, | |
287 | which is well-defined because $0 < \len(n) < 65536$. | |
56abd1c0 MW |
288 | |
289 | \subsubsection{FE2IP} | |
290 | Given an element $x$ of a finite field $\gf{q}$, the function $\id{fe2ip}$ | |
291 | determines a unique integer such that $0 \le \id{fe2ip}(x) < q$. | |
a4d41118 MW |
292 | \begin{aside} |
293 | Note that, unlike the other definitions in this section, $\id{fe2ip}$ is a | |
294 | plain function, and not an encoding. | |
295 | \end{aside} | |
56abd1c0 | 296 | |
a4d41118 | 297 | If $q$ is prime, then $\gf{q} = \Z/q\Z$: let $\phi_q$ be the unique ring |
56abd1c0 | 298 | homomorphism from $\Z$ to $\gf{q}$, and define $\id{fe2ip}(x)$ to be the |
a4d41118 | 299 | unique integer $n$ such that $0 \le n < q$ and $x = \phi_q(n)$. |
56abd1c0 MW |
300 | |
301 | Otherwise, $q = r^m$ for some prime power $r$ and an integer $m > 1$. Fix an | |
302 | ordered basis $\{ u_0, u_1, \ldots, u_{m-1} \}$ for $\gf{q}$ as a vector | |
303 | space over $\gf{r}$. | |
304 | \begin{aside} | |
305 | This is often a polynomial basis: if $u(t) = u_0 + u_1 t + \cdots + u_{m-1} | |
306 | t^{m-1} + t^m$ is a monic irreducible polynomial of degree~$m$ over | |
307 | $\gf{r}$, then $\{ u_0, u_1, \cdots, u_{m-1} \}$ is a suitable basis, | |
308 | representing $\gf{q}$ as the quotient ring $\gf{r}[t]/(u(t))$. Other | |
309 | representations are also possible. | |
310 | ||
311 | In practice, this case occurs when dealing with elliptic curves, and the | |
312 | specification for a curve over a non-prime field will include a description | |
313 | of the field representation sufficient to apply this definition. | |
314 | \end{aside} | |
315 | Then any element $x \in \gf{q}$ can be written uniquely as a sum | |
a4d41118 MW |
316 | \[ x = \sum_{0\le i<m} u_i x_i \padm, \] |
317 | where $x_i \in \gf{r}$ for $0 \le i < m$. Inductively define | |
318 | \[ \id{fe2ip}(x) = \sum_{0\le i<m} r^i \id{fe2ip}(x_i) \padm. \] | |
319 | \begin{aside} | |
320 | On the left, \id{fe2ip} is working in the extension field $\gf{q}$; on the | |
321 | right, \id{fe2ip} is working in the subfield $\gf{r}$. | |
322 | \end{aside} | |
56abd1c0 MW |
323 | Inductively, we will have $0 \le \id{fe2ip}(x_i) < r$, and hence $0 \le x < |
324 | r^m = q$. | |
325 | ||
326 | \subsubsection{FE2OSP} | |
a4d41118 MW |
327 | The encoding $\id{fe2osp}$ represents a field element~$x \in \gf{q}$ as a |
328 | fixed-length sequence of octets. Specifically, $\id{fe2osp}.\id{enc}(x) = | |
329 | [\id{fe2ip}(x)]_{\len(q-1)}$. | |
56abd1c0 MW |
330 | |
331 | \subsubsection{FE2VOSP} | |
a4d41118 MW |
332 | The encoding $\id{fe2vosp}$ represents a field element~$x \in \gf{q}$ as a |
333 | variable-length sequence of octets; its use is deprecated. Specifically, | |
334 | $\id{fe2vosp}.\id{enc}(x) = \id{i2vosp}.\id{enc}(\id{fe2ip}(x))$. | |
56abd1c0 MW |
335 | |
336 | \subsubsection{EC2OSP} | |
a4d41118 MW |
337 | The encoding $\id{ec2osp}$ represents a (homogeneous) projective point $Q = |
338 | (X : Y : Z)$ on an elliptic curve $E(k)$ over some finite field $k$ as a | |
339 | sequence of octets. For finite points, i.e., where $Z \ne 0$, this encoding | |
340 | is fixed-length, which is good enough. If $Z = 0$, the encoding is simply | |
341 | $\id{ec2osp}.\id{enc}(Q) = [0]$, i.e., a single zero octet. Otherwise, let | |
342 | $x = X/Z$ and $y = Y/Z$; then $\id{ec2osp}.\id{enc}(Q) = [4] \cat | |
343 | \id{fe2osp}.\id{enc}(x) \cat \id{fe2osp}.\id{enc}(y)$. | |
56abd1c0 MW |
344 | |
345 | \subsubsection{EC2VOSP} | |
a4d41118 MW |
346 | The encoding $\id{ec2osp}$ represents a (homogeneous) projective point $Q = |
347 | (X : Y : Z)$ on an elliptic curve $E(k)$ over some finite field $k$ as a | |
348 | variable-length sequence of octets; its use is deprecated. If $Z = 0$, the | |
349 | encoding is simply $\id{ec2vosp}.\id{enc}(Q) = [0, 0]$, i.e., two zero | |
350 | octets. Otherwise, let $x = X/Z$ and $y = Y/Z$; then | |
351 | $\id{ec2vosp}.\id{enc}(Q) = \id{fe2vosp}(x) \cat \id{fe2vosp}(y)$. | |
352 | \begin{aside} | |
353 | This is unambiguous since the first two octets of an encoding constructed | |
354 | by $\id{i2vosp}$ are not both zero. | |
355 | \end{aside} | |
356 | ||
357 | ||
358 | \subsection{Hash functions} \label{sec:prelim.hash} | |
359 | ||
360 | A cryptographic \emph{hash function} maps input octet strings, to | |
361 | fixed-length outputs, called \emph{hashes} or, sometimes, \emph{digests}. | |
362 | \begin{aside} | |
363 | Hash functions used in practice often have large but finite limits on the | |
364 | lengths of input they can process; e.g., SHA256 can process inputs of up to | |
365 | $2^{61}$ octets. TrIPE does not need to hash messages anywhere near this | |
366 | large, so this specification ignores this detail. | |
367 | \end{aside} | |
368 | ||
369 | Hash functions are not keyed, which makes expressing the desired security | |
370 | properties difficult. The formal analysis of TrIPE models hash functions as | |
371 | a (non-programmable) \emph{random oracle} -- a magic box to which all | |
372 | parties, including the adversary, have access, which returns for each | |
373 | possible input an independent, uniformly distributed, random result, subject | |
374 | only to the requirement that it return the same result if queried again at | |
375 | the same input string. Clearly, no fixed function with a simple description | |
376 | can possibly instantiate a random oracle. | |
377 | ||
378 | Certainly, the traditional requirements of preimage resistance, | |
379 | second-preimage resistance, and collision resistance are necessary, but far | |
380 | from sufficient. | |
381 | ||
382 | A hash function~$H$ consists of the following operations and parameters. | |
383 | \begin{itemize} | |
384 | \item A \emph{hash length} $H.\id{hsz} > 0$. | |
385 | \item A \emph{block size}~$H.\id{bsz}$. If the hash function processes | |
386 | inputs in fixed-length `blocks', then $H.\id{bsz}$ is the length of these | |
387 | blocks (e.g., SHA512 acts on 128-octet blocks). If the hash function does | |
388 | not process input in fixed-length blocks, then $H.\id{bsz} = 0$. | |
389 | \item A \emph{hash operation}~$H.\id{hash}$. For any \emph{message} $x \in | |
390 | \octet^*$, $H.\id{hash}$ calculates and returns a \emph{hash} $h = | |
391 | H.\id{hash}(x) \in \octet^{H.\id{hsz}}$. | |
392 | \end{itemize} | |
393 | ||
394 | \subsubsection{RIPEMD-160} | |
395 | The RIPEMD-160 function is defined in \cite{Bosselaers:1997:RCH}. The | |
396 | function $\id{ripemd-160}.\id{hash}$ is the function defined there; | |
397 | $\id{ripemd-160}.\id{hsz} = 20$ and $\id{ripemd-160}.\id{bsz} = 64$. | |
398 | ||
399 | \subsubsection{SHA256 and SHA512} | |
400 | The SHA256 and SHA512 functions are defined in FIPS~180--4 | |
401 | \cite{Anonymous:2012:SHS}. The function $\id{sha256}.\id{hash}$ is the | |
402 | function defined there as SHA256; $\id{sha256}.\id{hsz} = 32$ and | |
403 | $\id{sha256.bsz} = 64$. Similarly, the function $\id{sha512}.\id{hash}$ is | |
404 | the function defined there as SHA512; $\id{sha512}.\id{hsz} = 64$ and | |
405 | $\id{sha512.bsz} = 128$. | |
406 | ||
407 | \subsubsection{SHA3} | |
408 | The SHA3 family of functions is defined in FIPS~202 \cite{NIST:2015:SSP}. | |
409 | For each $w \in \{ 224, 256, 384, 512 \}$, $H = \id{sha3}(w)$ is a hash | |
410 | function as follows: $H.\id{hash}$ is the function SHA3-$w$ defined in | |
411 | \cite{NIST:2015:SSP}, $H.\id{hsz} = w/8$, and $H.\id{bsz} = 200 - w/8$. | |
412 | ||
413 | ||
414 | \subsection{Mask-generation function} \label{sec:prelim.mgf} | |
415 | ||
416 | Let $H$ be a hash function, let $x \in \octet^*$, and let $0 \le n < 2^{32} | |
417 | H.\id{hsz}$. Define $\id{mgf}(H, x, n)$ by | |
418 | \begin{itemize} | |
419 | \item $\id{mgf}(H, x, 0) = \emptystring$; | |
420 | \item $\id{mgf}(H, x, i \cdot H.\id{hsz}) = \id{mgf}(H, x, (i - 1) | |
421 | H.\id{hsz}) \cat H(x \cat [i - 1]_4)$ for $0 < i < 2^{32}$; and | |
422 | \item $\id{mgf}(H, x, i \cdot H.\id{hsz} + j) = \id{mgf}(H, x, i \cdot | |
423 | H.\id{hsz}) \cat H(x \cat [i]_4)[0 \upto j]$ for $0 < i < 2^{32}$ and $0 < | |
424 | j < H.\id{hsz}$. | |
425 | \end{itemize} | |
426 | ||
427 | ||
428 | \subsection{Blockciphers} \label{sec:prelim.prp} | |
429 | ||
430 | A \emph{blockcipher}, also known as a \emph{pseudorandom permutation} | |
431 | (PRP), is a family of permutations, indexed by a \emph{key}, all acting on | |
432 | the set of octet strings of some fixed length. | |
433 | ||
434 | A blockcipher~$B$ consists of the following operations and parameters. | |
435 | \begin{itemize} | |
436 | \item A \emph{key size} $B.\id{ksz} \ge 0$. | |
437 | \item A \emph{block size} $B.\id{bsz} > 0$. | |
438 | \item An \emph{encryption operation}~$B.E$. Given a \emph{key} $K \in | |
439 | \octet^{B.\id{ksz}}$ and an input string $x \in \octet^{B.\id{bsz}}$, $B.E$ | |
440 | calculates and returns a result $y \in \octet^{B.\id{bsz}}$. | |
441 | \item An \emph{decryption operation}~$B.D$. Given a \emph{key} $K \in | |
442 | \octet^{B.\id{ksz}}$ and an input string $y \in \octet^{B.\id{bsz}}$, $B.D$ | |
443 | calculates and returns a result $x \in \octet^{B.\id{bsz}}$. For any $K$, | |
444 | $B.D(K, \cdot)$ must be the inverse of $B.E(K, \cdot)$, i.e., for all $K | |
445 | \in \octet^{B.\id{ksz}}$ and all $x \in \octet^{B.\id{bsz}}$, it holds that | |
446 | $B.D(K, B.E(K, x)) = x$. | |
447 | \end{itemize} | |
448 | \begin{aside} | |
449 | Blockcipher designs frequently offer a range of key sizes rather than just | |
450 | a single fixed size; e.g., AES offers 16-, 24-, and 32-octet keys. This | |
451 | specification treats such designs as a family of blockciphers, one for each | |
452 | distinct key size. | |
453 | \end{aside} | |
454 | ||
455 | The security requirement on blockciphers is that no efficient adversary can | |
456 | distinguish an oracle which implements $B.E$ using a randomly-chosen key from | |
457 | one which implements a randomly chosen permutation on the same set of | |
458 | strings, except with negligible probability. | |
459 | ||
460 | \subsubsection{Twofish} | |
461 | The Twofish blockcipher is defined in \cite{Schneier:1999:TEAb}. If $k \in | |
462 | \{ 0, 8, \ldots, 256 \}$ then $B = \id{twofish}(k)$ is a blockcipher defined | |
463 | as follows: the key length is $B.\id{ksz} = k/8$; the block size is | |
464 | $B.\id{bsz} = 16$; the encryption and decryption operations $B.E$ and $B.D$ | |
465 | are the Twofish encryption and decryption algorithms defined in | |
466 | \cite{Schneier:1999:TEAb}. | |
467 | ||
468 | \subsubsection{AES (Rijndael)} | |
469 | The AES blockcipher is defined in \cite{FIPS:2001:AES}, and its design | |
470 | explained in \cite{Daemen:2002:DRA}. If $k \in \{ 128, 192, 256 \}$ then $B | |
471 | = \id{aes}(k)$ is a blockcipher defined as follows: the key length is | |
472 | $B.\id{ksz} = k/8$; the block size is $B.\id{bsz} = 16$; the encryption and | |
473 | decryption operations $B.E$ and $B.D$ are the AES encryption and decryption | |
474 | algorithms defined in \cite{FIPS:2001:AES}. | |
475 | ||
476 | ||
477 | \subsection{Salsa20 and ChaCha} \label{sec:prelim.latin} | |
478 | ||
479 | Salsa20 and ChaCha are stream ciphers designed by Bernstein, defined in | |
480 | \cite{Bernstein:2005:SS} and \cite{Bernstein:2008:CVS} (rather tersely) | |
481 | respectively; \cite{Bernstein:2007:SFS} is a later description of Salsa20, | |
482 | including a thorough design rationale, but lacks a formal notation for the | |
483 | core function. | |
484 | ||
485 | If $k \in \octet^{16} \cup \octet^{32}$, and $n \in \octet^{16}$, then | |
486 | \cite{Bernstein:2005:SS} defines $\mathrm{Salsa20}_k(n) \in \octet^{64}$. | |
487 | This is generalized in \cite{Bernstein:2007:SFS} to Salsa20/$r$, for any | |
488 | (even) number of rounds~$r$. The definition of ChaCha in | |
489 | \cite{Bernstein:2008:CVS} doesn't provide a handy notation for the resulting | |
490 | function, but it seems reasonable to define $\mathrm{ChaCha}r_k(n)$ by | |
491 | analogy. | |
492 | ||
493 | For $K \in \octet^{16} \cup \octet^{32}$, $r \in \{ 0, 2, \ldots \}$, $v \in | |
494 | \octet^8$, and $0 \le i < 2^{64}$, define $\id{salsa20-core}(K, r, v, i) = | |
495 | \mathrm{Salsa20/}r_K(v \cat [i]'_8)$, and $\id{chacha-core}(K, r, v, i) = | |
496 | \mathrm{ChaCha}r_K(v \cat [i]'_8)$. | |
497 | ||
498 | Let $f$ be $\id{salsa20-core}$ or $\id{chacha-core}$, let $K \in \octet^{16} | |
499 | \cup \octet^{32}$, let $r$ be a nonnegative even integer, and let $0 \le n < | |
500 | 2^{70}$. Define $g(f, K, r, v, n)$ by | |
501 | \begin{itemize} | |
502 | \item $g(f, K, r, v, 0) = \emptystring$; | |
503 | \item $g(f, K, r, v, 64 i) = g(f, K, r, v, 64 (i - 1)) \cat f(K, r, v, i - | |
504 | 1)$ for $0 < i < 2^{64}$; and | |
505 | \item $g(f, K, r, v, 64 i + j) = g(f, K, r, v, 64 i) \cat f(K, r, v, i)[0 | |
506 | \upto j]$ for $0 < i < 2^{64}$ and $0 < j < 64$. | |
507 | \end{itemize} | |
508 | Finally, define | |
509 | \begin{itemize} | |
510 | \item $\id{salsa20}(K, r, v, n) = g(\id{salsa20-core}, K, r, v, n)$ and | |
511 | \item $\id{chacha}(K, r, v, n) = g(\id{chacha-core}, K, r, v, n)$. | |
512 | \end{itemize} | |
513 | ||
514 | ||
515 | \subsection{Symmetric encryption} \label{sec:prelim.symmenc} | |
516 | ||
517 | A \emph{symmetric encryption scheme}~$E$ consists of the following operations | |
518 | and parameters. | |
519 | \begin{itemize} | |
520 | \item A \emph{key length}~$E.\id{ksz} \ge 0$. | |
521 | \item An \emph{initialization vector size}~$E.\id{ivsz} > 0$. | |
522 | \item A safe \emph{data limit} $E.\id{n-limit} > 0$; see \xref{sec:bulk.ops}. | |
523 | \item An \emph{encryption operation}~$E.E$. Given a \emph{key} $K \in | |
524 | \octet^{E.\id{ksz}}$, an \emph{initialization vector} $v \in | |
525 | \octet^{E.\id{ivsz}}$, and a \emph{message} $m \in \octet^*$, $E.E$ | |
526 | calculates and returns a \emph{ciphertext} $y = E.E(K, v, m) \in \octet^*$. | |
527 | \item A \emph{decryption operation}~$E.D$. Given a \emph{key} $K \in | |
528 | \octet^{E.\id{ksz}}$, an \emph{initialization vector} $v \in | |
529 | \octet^{E.\id{ivsz}}$, and a \emph{ciphertext} $y \in \octet^*$, $E.D$ | |
530 | calculates and returns a \emph{message} $m = E.D(K, v, y) \in \octet^*$. | |
531 | To be a proper symmetric encryption scheme, it must hold that $E.D(K, v, | |
532 | E.E(K, v, m)) = m$ for all $K \in \octet^{E.\id{ksz}}$, all $v in | |
533 | \octet^{E.\id{ivsz}}$, and all $m \in \octet^*$. | |
534 | \end{itemize} | |
535 | \begin{aside} | |
536 | The function $E.E(K, v, \cdot)$ need not be surjective; i.e., there may be | |
537 | many $y' \in \octet^*$ for which $y' \ne E.E(K, v, m)$ for any $K$, $v$, | |
538 | $m$. There is no requirement on the result of $E.D(K, v, y')$. | |
539 | \end{aside} | |
540 | Security is defined as \emph{left-or-right indistinguishability under | |
541 | chosen-plaintext attack} (IND-CPA). An adversary is given an oracle which | |
542 | accepts pairs of messages $(m_0, m_1)$ with $\len(m_0) = \len(m_1)$. At the | |
543 | start of the game, the oracle selects $K$ uniformly at random from | |
544 | $\octet^{E.\id{ksz}}$ and chooses $b \in \{ 0, 1 \}$, also uniformly at | |
545 | random. On each query $(m_0, m_1)$, the oracle selects $v$ uniformly at | |
546 | random from $\octet^{E.\id{ivsz}}$, and returns $E.E(K, v, m_b)$ to the | |
547 | adversary. The security requirement is that no efficient adversary should be | |
548 | able to correctly guess~$b$ with probability significantly different from | |
549 | $\frac{1}{2}$. | |
550 | ||
551 | \subsubsection{Ciphertext Block Chaining} | |
552 | TrIPE's version of CBC is rather unusual. It uses ciphertext stealing rather | |
553 | than padding to deal with messages which aren't an exact multiple of the | |
554 | block size; specifically, it uses the `CBC-CS2' variant described in | |
555 | \cite{Dworkin:2010:RBC} and analysed by \cite{Rogaway:2012:SCS}. Ciphertext | |
556 | stealing doesn't work properly if the message is shorter than the block size; | |
557 | in this case, TrIPE's variant of CBC switches to Ciphertext Feedback (CFB) | |
558 | mode. | |
559 | ||
560 | Given a blockcipher $B$, the symmetric encryption scheme $E = \id{cbc}(B)$ is | |
561 | defined as follows. | |
562 | \begin{itemize} | |
563 | \item $E.\id{ksz} = B.\id{ksz}$. | |
564 | \item $E.\id{ivsz} = B.\id{bsz}$. | |
565 | \item $E.\id{n-limit} = 2^{4\cdot B.\id{bsz}-41/2} B.\id{bsz}$. | |
566 | \item Given $K$, $v$, and $m$, $E.E$ works as follows. | |
567 | \begin{enumerate} | |
568 | \item Write $\len(m) = n \cdot B.\id{bsz} + t$, where $0 \le t < | |
569 | B.\id{bsz}$. | |
570 | \item If $n = 0$, then set $y_0 = m \xor B.E(K, v)[0 \upto t]$, and go to | |
571 | step~\ref{en:cbc.enc.done}. | |
572 | \begin{aside} | |
573 | This step is CFB encryption rather than CBC-CS2. I'm not aware of any | |
574 | literature showing that this combination is secure, though in fact it | |
575 | is. The proof of CBC-CS in \cite{Rogaway:2012:SCS} shows that CBC-CS2 | |
576 | ciphertexts are indistinguishable from uniformly distributed strings; | |
577 | and this step is equivalent to setting $y_0 = m \xor E.E(K, v, | |
578 | [0]_{B.\id{bsz}})[0 \upto t]$. Since $E.E(k, v, [0]_{B.\id{bsz}})$ is | |
579 | indeed a CBC-CS2 ciphertext (indeed, it is a vanilla CBC ciphertext, | |
580 | since the message is exactly one block long), it is indistinguishable | |
581 | from uniform, and so $y_0 = m \xor E.E(k, v, [0]_{B.\id{bsz}})[0 \upto | |
582 | t]$ is also indistinguishable form uniform. | |
583 | \end{aside} | |
584 | \item For $0 \le i < n$, set $m_i = m[i \cdot B.\id{bsz} \upto (i + 1) | |
585 | \cdot B.\id{bsz}]$, and set $m_n = m[n \cdot B.\id{bsz} \upto \len(m)]$. | |
586 | \item Set $y_{-1} = v$, and, for $0 \le i < n - 1$, set $y_i = B.E(K, m_i | |
587 | \xor y_{i-1})$. | |
588 | \item If $t = 0$, then set $y_{n-1} = B.E(K, m_{n-1} \xor y_{m-2})$ and | |
589 | $y_n = \emptystring$, and go to step~\ref{en:cbc.enc.done}. | |
590 | \item Set $r = B.E(K, m_{n-1} \xor y_{n-2})$. | |
591 | \item Set $y_n = r[0 \upto t]$. | |
592 | \item Set $y_{n-1} = B.E(K, (m_n \xor y_n) \cat r[t \upto B.\id{bsz}])$. | |
593 | \item \label{en:cbc.enc.done} Finally, $E.E(K, v, m) = y_0 \cat y_1 \cat | |
594 | \cdots \cat y_{n-1} \cat y_n$. | |
595 | \end{enumerate} | |
596 | \item Given $K$, $v$, and $Y$, $E.D$ works as follows. | |
597 | \begin{enumerate} | |
598 | \item Write $\len(y) = n \cdot B.\id{bsz} + t$, where $0 \le t < | |
599 | B.\id{bsz}$. | |
600 | \item If $n = 0$, then set $m_0 = y \xor B.E(K, v)[0 \upto t]$ and go to | |
601 | step~\ref{en:cbc.dec.done}. | |
602 | \item For $0 \le i < n$, set $y_i = y[i \cdot B.\id{bsz} \upto (i + 1) | |
603 | \cdot B.\id{bsz}]$, and set $y_n = y[n \cdot B.\id{bsz} \upto \len(y)]$. | |
604 | \item Set $y_{-1} = v$, and, for $0 \le i < n - 1$, set $m_i = B.D(K, y_i) \xor | |
605 | y_{i-1}$. | |
606 | \item If $t = 0$, then set $m_{n-1} = B.D(K, y_{n-1}) \xor y_{n-2}$ | |
607 | and $m_n = \emptystring$, and go to step~\ref{en:cbc.dec.done}. | |
608 | \item Set $s = B.D(K, y_{n-1})$. | |
609 | \item Set $m_{n-1} = B.D(K, y_n \cat s[t \upto B.\id{bsz}]) \xor y_{n-2}$. | |
610 | \item Set $m_n = s[0 \upto t] \xor y_n$. | |
611 | \item \label{en:cbc.dec.done} Finally, $E.D(K, v, y) = m_0 \cat m_1 \cat | |
612 | \cdots \cat m_{n-1} \cat m_n$. | |
613 | \end{enumerate} | |
614 | \end{itemize} | |
615 | \begin{aside} | |
616 | Decryption is correct. First, encryption preserves length: if $n = 0$ then | |
617 | $y = B.E(K, v)[0 \upto t]$, so $\len(y) = t = \len(m)$; otherwise | |
618 | $\len(y_i) = B.\id{bsz}$, and $\len(y_n) = t$, and $\len(y) = n \cdot | |
619 | B.\id{bsz} + t = \len(x)$. Then, examining the decryption algorithm, we | |
620 | see the following. | |
621 | \begin{itemize} | |
622 | \item If $n = 0$ then $B.E(K, v)[0 \upto t] \xor y = B.E(K, v)[0 \upto t] | |
623 | \xor B.E(K, v)[0 \upto t] \xor m = m$. | |
624 | \item Both the encryption and decryption algorithms compute the same $y_i$, | |
625 | for $-1 \le i \le n$. Specifically, $y_{-1} = v$ and $y = y_0 \cat y_1 | |
626 | \cat \cdots \cat y_{n-1} \cat y_n$ in each case, and $\len(y_i) = | |
627 | B.\id{bsz}$ for $0 \le i < n$, and $\len(y_n) = t$. | |
628 | \item For $0 \le i < n - 1$, $B.D(K, y_i) \xor y_{i-1} = B.D(K, B.E(K, m_i | |
629 | \xor y_{i-1})) \xor y_{i-1} = m_i$. | |
630 | \item When $n > 0$ and $t = 0$, $B.D(K, y_{n-1}) \xor y_{n-2} = B.D(K, B.E(K, m_{n-1} | |
631 | \xor y_{n-2})) \xor y_{n-2} = m_{n-2}$. | |
632 | \item When $n > 0$ and $t > 0$, we have $s = B.D(K, y_{n-1}) = (m_n \xor | |
633 | y_n) \cat r[t \upto B.\id{bsz}]$, so $s[0 \upto t] = m_n \xor y_n$, and | |
634 | $s[t \upto B.\id{bsz}] = r[t \upto B.\id{bsz}]$. Hence $B.D(K, y_n \cat | |
635 | s[t \upto B.\id{bsz}]) \xor y_{n-2} = B.D(K, r[0 \upto t] \cat r[t \upto | |
636 | B.\id{bsz}]) \xor y_{n-2} = B.D(K, r) \xor y_{n-2} = m_{n-1}$; and $s[0 | |
637 | \upto t] \xor y_n = m_n$. | |
638 | \end{itemize} | |
639 | \end{aside} | |
640 | ||
641 | ||
642 | \subsection{Message authentication} \label{sec:prelim.mac} | |
643 | ||
644 | A \emph{message authentication code} (MAC) calculates a fixed-length | |
645 | \emph{tag} given a secret \emph{key} and a \emph{message}. The recipient of | |
646 | a message can recalculate the expected tag and compare it to the one | |
647 | provided: if the two match, the recipient can be confident that the message | |
648 | was not altered since it was transmitted. | |
649 | ||
650 | A message authentication code~$M$ consists of the following operations and | |
651 | parameters. | |
652 | \begin{itemize} | |
653 | \item A \emph{key size}~$M.\id{ksz} \ge 0$. | |
654 | \item A \emph{tag size}~$M.\id{tsz} > 0$. | |
655 | \item A \emph{tagging operation}~$M.\id{tag}$. Given a key~$K \in | |
656 | \octet^{M.\id{ksz}}$, and a message $m \in \octet^*$, $M.\id{tag}$ | |
657 | calculates and returns a tag $t = M.\id{tag}(K, m) \in | |
658 | \octet^{M.\id{t.tsz}}$. | |
659 | \end{itemize} | |
660 | \begin{aside} | |
661 | Some message authentication codes in the literature require an additional | |
662 | \emph{nonce} input. This specification currently does not admit such MACs. | |
663 | \end{aside} | |
664 | ||
665 | The security requirement property on message authentication codes is that an | |
666 | efficient adversary who does not know the key should be unable to determine a | |
667 | tag for any new message, even if it is allowed to query the correct tags for | |
668 | messages of its choice. | |
669 | \begin{aside} | |
670 | It is important that tags are verified in constant time, so that an | |
671 | adversary does not learn (for example) which octet of an attempted forgery | |
672 | is the first one which doesn't match the expected tag. In the presence of | |
673 | such a leak, it is easy to forge a correct tag, figuring out the right | |
674 | octets one by one. | |
675 | \end{aside} | |
676 | ||
677 | \subsubsection{HMAC} | |
678 | The HMAC construction builds a MAC from a hash function. Originally | |
679 | described in \cite{Bellare:1996:HC}, HMAC is standardized in \cite{rfc2104} | |
680 | and \cite{FIPS:2002:KHM}. | |
681 | ||
682 | If $H$ is a hash function with $H.\id{bsz} > 0$, and $0 \le k \le | |
683 | H.\id{bsz}$, then the MAC $M = \id{hmac}(H)$ is defined as follows. | |
684 | \begin{itemize} | |
685 | \item $M.\id{ksz} = k$. | |
686 | \item $M.\id{tsz} = H.\id{hsz}$. | |
687 | \item $M.\id{tag}(K, m) = H.\id{hash}(\id{pad}(K, 92) \cat | |
688 | H.\id{hash}(\id{pad}(K, 54) \cat m))$, where $\id{pad}(K, a) = | |
689 | [a]^{H.\id{bsz}} \xor (K \cat [0]^{H.\id{bsz}-k})$. | |
690 | \end{itemize} | |
691 | ||
692 | ||
693 | \subsection{Poly1305} \label{sec:prelim.poly1305} | |
694 | ||
695 | Poly1305 is a nonce-based MAC designed and specified by Bernstein | |
696 | \cite{Bernstein:2005:PAM}. | |
697 | ||
698 | For $r, s \in \octet^{16}$, and $m \in \octet^*$, define $\id{poly1305}(r, s, | |
699 | m)$ as follows. Write $m = m_0 \cat m_1 \cat \cdots \cat m_{n-1}$, where | |
700 | $\len(m_i) = 16$ for $0 \le i < n - 1$, and $1 \le \len(m_{n-1}) \le 16$. | |
701 | (If $m = \emptystring$ then $n = 0$ and no $m_i$ are defined.) | |
702 | ||
703 | \def\b{\penalty0\relax} | |
704 | Let $r' \in \gf{2^{130}-5}$ be such that $[\id{fe2ip}(r')]'_{16} = (r \bitand | |
705 | [\hex{ff},\b \hex{ff},\b \hex{ff},\b \hex{0f},\b \hex{fc},\b \hex{ff},\b | |
706 | \hex{ff},\b \hex{0f},\b \hex{fc},\b \hex{ff},\b \hex{ff},\b \hex{0f},\b | |
707 | \hex{fc},\b \hex{ff},\b \hex{ff},\b \hex{0f}]$. For $0 \le i < n$, let $m'_i | |
708 | \in \gf{2^{130}-5}$ be such that $[\id{fe2ip}(m'_i - 2^{8\len(m_i)})]'_{16} = | |
709 | m_i$. Let $u' = \sum_{0\le i<n} r'^{n-i} m'_i$. | |
710 | ||
711 | Let $\hat{s} \in \Z$ be such that $[\hat{s}]'_{16} = s$. Then | |
712 | $[\hat{t}]'_{16} = \id{poly1305}(r, s, m) \in \octet^{16}$ is the unique | |
713 | 16-octet string such that $\hat{t} \equiv \hat{s} + \id{fe2ip}(u') | |
714 | \pmod{2^{128}}$. | |
715 | ||
716 | Our $\id{poly1305}(r, m, s)$ is the same as $\mathrm{Poly1305}_r(m, s)$ in | |
717 | \cite{Bernstein:2005:PAM}. | |
718 | ||
719 | ||
720 | %%%-------------------------------------------------------------------------- | |
721 | \section{Diffie--Hellman groups} \label{sec:dh-group} | |
722 | ||
723 | \subsection{Operations} \label{sec:dh-group.ops} | |
724 | ||
725 | A \emph{Diffie--Hellman group}~$D$ consists of a pair of sets $D.S$ and | |
726 | $D.G$, of \emph{scalars} and \emph{group elements} respectively, a | |
727 | distinguished \emph{generator} element $D.P \in D.G$, and a number of | |
728 | operations on these groups. | |
729 | \begin{itemize} | |
730 | \item A \emph{group operation}~$D.\id{dh}$. Given a scalar $x \in D.S$ and a | |
731 | group element $Y \in D.G$, $D.\id{dh}$ calculates and returns a group | |
732 | element $Z = D.\id{dh}(x, Y) \in D.G (x, Y)$. To be a proper | |
733 | Diffie--Hellman group, it must be the case that $D.\id{dh}(x, D.\id{dh}(y, | |
734 | P)) = D.\id{dh}(y, D.\id{dh}(x, D.P))$ for all scalars $x$ and $y$. | |
735 | \item A \emph{validity checking operation}~$D.\id{validp}$. Given a group | |
736 | element $X \in D.G$, $D.\id{validp}$ verifies that that $Z = D.\id{dh}(y, | |
737 | X)$ can be calculated and published without leaking information about~$y$. | |
738 | If this is safe, then $D.\id{validp}(X) = \t$; otherwise, $D.\id{validp}(X) | |
739 | = \nil$. | |
740 | \begin{aside} | |
741 | Typically, this means that $X$ lies within the subgroup generated by | |
742 | $D.P$, i.e., that there exists some $x$ such that $X = D.\id{dh}(x, | |
743 | D.P)$. Some groups may have special structure that allows safety to be | |
744 | determined more cheaply. | |
745 | \end{aside} | |
746 | \item An encoding $D.\id{ge-public}$ on \emph{public group elements}, for | |
747 | which no special properties are required. | |
748 | \item An encoding $D.\id{ge-secret}$ on \emph{secret group elements}, where | |
749 | all encodings have the same length, except for a negligible fraction of | |
750 | group elements. | |
751 | \item An encoding $D.\id{ge-hash}$ on \emph{hashed group elements}, where all | |
752 | encodings \emph{should} have the same length, except for a negligible | |
753 | fraction of scalars.\footnote{% | |
754 | The existence of groups without (mostly) fixed-length hashing encodings | |
755 | is a historical mistake. If a variable-length encoding is used here, | |
756 | information about group element(s) being hashed may leak to an adversary | |
757 | through timing channels.} % | |
758 | The decoding operation is never invoked, so it need not be possible to | |
759 | implement it efficiently, though it must be theoretically possible to | |
760 | decode encodings unambiguously. | |
761 | \item An encoding $D.\id{sc}$ on \emph{scalars}, where all encodings have the | |
762 | same length, denoted $D.\id{scsz}$; i.e., $D.\id{scsz} = | |
763 | \ell(D.\id{sc}.\id{enc}(x))$ for all $x \in S$. | |
764 | \end{itemize} | |
765 | Decoding operations must validate input sufficiently that the $D.\id{dh}$ | |
766 | operation can be performed successfully and without leaking secret inputs | |
767 | during the computation; but it is \emph{not} necessary to perform further | |
768 | precise verification. For the most part, an implementation need not verify | |
769 | that an incoming group element is actually within the subgroup generated by | |
770 | $D.P$; and an elliptic-curve group need not verify that an incoming pair of | |
771 | coordinates actually correspond to a point on the curve; the necessary | |
772 | checking is shown explicitly using the Diffie--Hellman group's | |
773 | $D.\id{validp}$ function where appropriate. | |
774 | \begin{aside} | |
775 | In an ideal world, we would only have one group-element encoding rather | |
776 | than three. The present situation is caused by unfortunate historical | |
777 | mistakes. Of course, nothing prevents newer Diffie--Hellman group | |
778 | specifications from using the same (constant-length) encoding for all three | |
779 | group-element encodings described above, and, indeed, the X25519 and X448 | |
780 | groups defined below do this. | |
781 | \end{aside} | |
782 | ||
783 | For security, it must be computationally intractable to determine | |
784 | $D.\id{dh}(x, D.\id{dh}(y, D.P))$ given only $X = D.\id{dh}(x, D.P)$ and $Y = | |
785 | D.\id{dh}(y, D.P)$ (i.e., the \emph{computational Diffie--Hellman assumption} | |
786 | must hold). | |
56abd1c0 MW |
787 | |
788 | ||
789 | \subsection{Schnorr groups} \label{sec:dh-group.schnorr} | |
790 | ||
a4d41118 MW |
791 | For historical reasons, there are two variants of Schnorr groups, named |
792 | \cookie{v0} and \cookie{constlen}. The \cookie{v0} variant is deprecated; | |
793 | new deployments should use \cookie{constlen} if possible. | |
794 | ||
795 | Let $p < 2^{524288}$ be an odd prime, let $q$ be a prime factor of $p - 1$, | |
796 | let $g \ne 1$ be an element of $\gf{p}^*$ such that $g^q = 1$, and let $v$ be | |
797 | one of the symbols \cookie{v0} or \cookie{constlen}. Then $D = | |
798 | \id{schnorr}(p, q, g, v)$ is a Diffie--Hellman group, as follows. | |
799 | ||
800 | The group itself is the cyclic subgroup $D.G = \langle g \rangle \subseteq | |
801 | \gf{p}^*$ generated by $g$; the scalars are the finite field $D.S = \gf{q}$; | |
802 | and the generator is $D.P = g$. | |
803 | ||
804 | For security, $p$ must be large enough to thwart index-calculus style | |
805 | discrete-logarithm algorithms in $\gf{p}^*$, and $q$ must be large enough to | |
806 | thwart generic discrete-logarithm algorithms within the subgroup $G$. For | |
807 | new deployments, it is recommended that $p \ge 2^{3071}$ and $q \ge 2^{255}$. | |
808 | ||
56abd1c0 | 809 | \begin{itemize} |
8c3ad0db | 810 | \item The Diffie--Hellman operation is simply exponentiation in $\gf{p}$, |
a4d41118 MW |
811 | given by $D.\id{dh}(x, Y) = Y^x$. (Technically this is an abuse of |
812 | notation: exponentiation is defined for integer exponents, and $x$ is an | |
813 | element of a finite field. For every $Y \in G$, define $\theta_Y\colon \Z | |
814 | \to G$ by $\theta_Y(n) = Y^n$; then $q\Z \subseteq \ker \theta_Y$, and | |
815 | $\theta_Y$ factors through $\Z/q\Z = \gf{q}$ as $\theta_Y = \theta'_Y \circ | |
816 | \phi_q$, where $\phi_q$ is the unique ring homomorphism from $\Z$ to | |
817 | $\gf{q}$. Then $\id{dh}(x, Y) = \theta'_Y(x)$.) | |
818 | \item Since $\gf{p}$ contains at most one subgroup with any given order, | |
819 | $D.\id{validp}(X) = \t$ if and only if $X^q = 1$. | |
820 | \item The public group-element encoding is FE2VOSP in the field $\gf{p}$; | |
821 | i.e., $D.\id{ge-public} = \id{fe2vosp}$. | |
822 | \item The secret group-element encoding is FE2OSP in the field $\gf{p}$; | |
823 | i.e., $D.\id{ge-secret} = \id{fe2osp}$. | |
824 | \item If $v = \cookie{v0}$, the hash group-element encoding is FE2VOSP, so | |
825 | $D.\id{ge-hash} = D.\id{ge-public}$. If $v = \cookie{constlen}$, the hash | |
826 | group-element encoding is FE2OSP, so $D.\id{ge-hash} = | |
827 | D.\id{ge-secret}(X)$. | |
828 | \item The scalar encoding is FE2OSP in the field $\gf{q}$, i.e., $D.\id{sc} = | |
829 | D.\id{fe2osp}$; hence $D.\id{scsz} = \len(q - 1)$. | |
56abd1c0 MW |
830 | \end{itemize} |
831 | ||
832 | ||
833 | \subsection{Short-Weierstraß elliptic curve groups} | |
834 | \label{sec:dh-group.trad-ec} | |
835 | ||
a4d41118 MW |
836 | For historical reasons, there are two variants of short-Weierstraß groups, |
837 | named \cookie{v0} and \cookie{constlen}. The \cookie{v0} variant is | |
838 | deprecated; new deployments should use \cookie{constlen} if possible. | |
839 | ||
840 | Let $p$ be a prime; let $q = p^m$ be some prime power, and let $k = \gf{q}$ | |
841 | be the finite field with $q$ elements. | |
842 | ||
843 | Projective 2-space over $k$, written $\PP^2(k)$, consists of equivalence | |
844 | classes of triples $(X, Y, Z) \in k^3 \setminus \{ (0, 0, 0) \}$ under the | |
845 | equivalence relation $(X, Y, Z) \sim (t X, t Y, t Z)$ for any $t \in k | |
846 | \setminus \{ 0 \}$. The equivalence class containing $(X, Y, Z)$ is denoted | |
847 | $(X : Y : Z)$. | |
848 | ||
849 | The $k$-rational points on elliptic curve $E$, denoted $E(k)$, consist of | |
850 | those (homogeneous) projective points $(X : Y : Z) \in \PP^2(k)$ satisfying | |
851 | an equation. There are a number of cases to consider: | |
852 | \begin{itemize} | |
853 | \item if $p > 3$, then the equation is $Y^2 Z = X^3 + a X Z^2 + b Z^3$, where | |
854 | $a, b \in k$ with $4 a^3 + 27 b^2 \ne 0$; | |
855 | \item if $p = 3$, then the equation is $Y^2 Z = X^3 + c X^2 Z + a X Z^2 + b | |
856 | Z^3$, for $a \ne 0$, where $a, b, c \in k$ with $a^3 \ne c^2 (a^2 - b c)$; | |
857 | and | |
858 | \item if $p = 2$, then there are two subcases: | |
859 | \begin{itemize} | |
860 | \item for \emph{ordinary} curves, the equation is $Y^2 Z + X Y Z = X^3 + a | |
861 | X^2 Z + b Z^3$, where $a, b \in k$ with $b \ne 0$; and | |
862 | \item for \emph{supersingular} curves, the equation is $Y^2 Z + c Y Z^2 = | |
863 | X^3 + a X Z^2 + b Z^3$, where $a, b, c \in k$ with $c \ne 0$. | |
864 | \end{itemize} | |
865 | \end{itemize} | |
866 | \begin{aside} | |
867 | Implementations frequently use other coordinate systems; Jacobian | |
868 | projective coordinates are especially popular. The use of homogeneous | |
869 | coordinates in this specification is for convenience of presentation, and | |
870 | is not intended to prohibit implementations from using other coordinate | |
871 | systems internally. | |
872 | ||
873 | Most elliptic curve cryptography implementations handle only `prime fields' | |
874 | for which $p > 3$ and $m = 1$, and ordinary curves over `binary fields' | |
875 | where $p = 2$. | |
876 | \end{aside} | |
877 | ||
878 | The points of $E(k)$ form an abelian group, written additively, with identity | |
879 | $O = (0 : 1 : 0)$. Choose $P \in E(k) \setminus \{ O \}$ to generate a | |
880 | subgroup $\langle P \rangle \in E(k)$ with prime order~$r$. | |
881 | ||
882 | For security, $r$ must be large enough to thwart generic discrete-logarithm | |
883 | algorithms within the subgroup $\langle P \rangle$. For new deployments, it | |
884 | is recommended that $r \ge 2^{255}$. A number of other conditions should | |
885 | also hold. | |
886 | \begin{itemize} | |
887 | \item $r \ne q$; | |
888 | \item $m = 1$ or $m$ is prime; | |
889 | \item $r^2 > \#E(k)$; and | |
890 | \item $p^d \not\equiv 1 \pmod{r}$ for any $d < (r - 1)/100$. | |
891 | \end{itemize} | |
892 | There are well-known difficulties in implementing short-Weierstraß elliptic | |
893 | curve arithmetic free of microarchitectural side-channels. | |
894 | ||
895 | Finally, let $v$ be one of the symbols \cookie{v0} or \cookie{constlen}. | |
896 | Then $D = \id{ec}(k, E, P, r, v)$ is a Diffie--Hellman group as follows. The | |
897 | group itself is the subgroup $D.G = \langle P \rangle$ generated by $P$; the | |
898 | scalars are the finite field $S = \gf{r}$; and the generator is the point | |
899 | $D.P = P$. | |
900 | ||
901 | The Diffie--Hellman group operations are as follows. | |
902 | \begin{itemize} | |
903 | \item The Diffie--Hellman operation is elliptic curve scalar multiplication, | |
904 | given by $D.\id{dh}(x, Y) = x Y$. | |
905 | \item Since $r^2 > \#E(k)$, there can be at most one subgroup of $E(k)$ with | |
906 | order $r$; therefore $D.\id{validp}(X) = \t$ if and only if $r X = O$. | |
907 | \item The public group-element encoding is EC2VOSP; i.e., | |
908 | $D.\id{ge-public} = \id{ec2vosp}$. | |
909 | \item The secret group-element encoding is EC2OSP; i.e., | |
910 | $D.\id{ge-secret} = \id{ec2osp}$. | |
911 | \item If $v = \cookie{v0}$, the hash group-element encoding is EC2VOSP, so | |
912 | $D.\id{ge-hash} = D.\id{ge-public}$. If $v = \cookie{constlen}$, the hash | |
913 | group-element encoding is EC2OSP, so $D.\id{ge-hash} = D.\id{ge-secret}$. | |
914 | \item The scalar encoding is FE2OSP in the field $\gf{r}$, i.e., | |
915 | $D.\id{enc-sc} = \id{fe2osp}$; hence $D.\id{scsz} = \len(q - 1)$. | |
916 | \end{itemize} | |
917 | ||
56abd1c0 MW |
918 | |
919 | \subsection{The X25519 group} \label{sec:dh-group.x25519} | |
920 | ||
a4d41118 MW |
921 | The X25519 function was introduced by Bernstein in \cite{Bernstein:2006:CDH}, |
922 | where it was originally named `Curve25519'. It uses a carefully chosen | |
923 | elliptic curve over the finite field $k = \gf{p^2}$, where $p = 2^{255} - | |
924 | 19$; specifically | |
925 | \[ E(k) = \{\, (X : Y : Z) \mid Y^2 Z = X^3 + 486662 X^2 Z + X Z^2 \,\} | |
926 | \padm. | |
927 | \] | |
928 | \cite{Bernstein:2006:CDH} completely defines X25519 as a function on 32-octet | |
929 | strings. | |
930 | \begin{aside} | |
931 | Note that this is \emph{not} quite the same function as specified in | |
932 | RFC7748 \cite{rfc7748}. That specification requires that implementations | |
933 | ignore the most significant bit of public key; the original definition | |
934 | considers that bit significant (and has place-value $-19$). Correct and | |
935 | honest senders will not set this bit. | |
936 | \end{aside} | |
937 | ||
938 | Thus, $D = \id{x25519}$ is a Diffie--Hellman group as follows. Both the | |
939 | scalars and group are simply the set of all octet strings of length~32; i.e., | |
940 | $D.S = D.G = \octet^{32}$. The generator is the point $D.P = [9, 0, \ldots, | |
941 | 0]$. | |
942 | ||
943 | \begin{itemize} | |
944 | \item The Diffie--Hellman operation is the X25519 operation: $D.\id{dh}(x, Y) | |
945 | = \id{X25519}(x, Y)$. | |
946 | \item By design, X25519 is specified and secure for all possible public-key | |
947 | values; hence $D.\id{validp}(X) = \t$ for all $X \in D.G$. | |
948 | \item Group elements are already fixed-length octet strings. All three | |
949 | group-element encodings are therefore the identity function; i.e., | |
950 | $D.\id{ge-public} = D.\id{ge-secret} = D.\id{ge-hash} = X$. | |
951 | \item Scalars are already fixed-length octet strings. The scalar encoding is | |
952 | therefore the identity function, i.e., $D.\id{sc}.\id{enc}(x) = x$; and | |
953 | $D.\id{scsz} = 32$. | |
954 | \end{itemize} | |
955 | ||
56abd1c0 MW |
956 | |
957 | \subsection{The X448 group} \label{sec:dh-group.x448} | |
958 | ||
a4d41118 MW |
959 | The X448 function is fully specified in RFC7748 \cite{rfc7748}. It uses a |
960 | carefully chosen elliptic curve named `Ed448-Goldilocks', introduced by | |
961 | Hamburg in \cite{cryptoeprint:2015:625}, over the finite field $k = | |
962 | \gf{p^2}$, where $p = 2^{448} - 2^{224} - 1$, specifically, | |
963 | \[ E(k) = \{\, (X : Y : Z) \mid Y^2 Z = X^3 + 156326 X^2 Z + X Z^2 \,\} | |
964 | \padm. | |
965 | \] | |
966 | \cite{rfc7748} completely defines X448 as a function on 56-octet strings. | |
967 | ||
968 | Thus, $D = \id{x448}$ is a Diffie--Hellman group as follows. Both the | |
969 | scalars and group are simply the set of all octet strings of length~56; i.e., | |
970 | $D.S = D.G = \octet^{56}$. The generator is the point $D.P = [5, 0, \ldots, | |
971 | 0]$. | |
972 | ||
973 | \begin{itemize} | |
974 | \item The Diffie--Hellman operation is the X448 operation: $D.\id{dh}(x, Y) = | |
975 | \id{X448}(x, Y)$. | |
976 | \item By design, X448 is specified and secure for all possible public-key | |
977 | values; hence $D.\id{validp}(X) = \t$ for all $X \in D.G$. | |
978 | \item Group elements are already fixed-length octet strings. All three | |
979 | group-element encodings are therefore the identity function; i.e., | |
980 | $D.\id{ge-public} = D.\id{ge-secret} = D.\id{ge-hash} = X$. | |
981 | \item Scalars are already fixed-length octet strings. The scalar encoding is | |
982 | therefore the identity function, i.e., $D.\id{sc}.\id{enc}(x) = x$; and | |
983 | $D.\id{scsz} = 56$. | |
984 | \end{itemize} | |
985 | ||
986 | %%%-------------------------------------------------------------------------- | |
987 | \section{Bulk transforms} \label{sec:bulk} | |
988 | ||
989 | \subsection{Operations} \label{sec:bulk.ops} | |
990 | ||
991 | A \emph{bulk transform}~$T$ consists of a number of parameters and | |
992 | operations, as follows. | |
993 | \begin{itemize} | |
994 | \item A safe \emph{data limit} $E.\id{n-limit} > 0$; see \xref{sec:bulk.ops}. | |
995 | \item A \emph{key-generation operation} $T.\id{gen}$. Given an octet string | |
996 | $z \in \octet^*$, $T.\id{gen}$ derives and returns the cryptographic key~$K | |
997 | = T.\id{gen}(z)$ required by $T.E$ and $T.D$, which are described below. | |
998 | \begin{aside} | |
999 | Throughout the protocol, $x$ will be a public contribution from the | |
1000 | sender, $y$ a public contribution from the recipient (or empty), and $z$ | |
1001 | a shared secret known only to both. | |
1002 | \end{aside} | |
1003 | \item An \emph{encryption operation} $T.E$. Given a key~$K$ returned by | |
1004 | $T.\id{gen}$, a message type code $0 \le c < 2^{32}$, a sequence number $0 | |
1005 | \le i < 2^{32}$, and a message~$m \in \octet^*$, $T.E$ computes and returns | |
1006 | a ciphertext $y = T.E(K, c, i, m) \in \octet^*$ | |
1007 | \item A \emph{decryption operation} $T.D$. Given a key~$K$ returned by | |
1008 | $T.\id{gen}$, a message type code $0 \le c < 2^{32}$, and a ciphertext $y | |
1009 | \in \octet^*$, $T.D$ attempts to decrypt the ciphertext, returning a pair | |
1010 | $(i, m) = T.D(K, c, y)$. If the operation succeeds, $0 \le i < 2^{32}$ is | |
1011 | a sequence number, and $m \in \octet^*$ is the decrypted message; | |
1012 | otherwise, $i = 0$ and $m \in \syms$. For correctness, for any key~$K$ | |
1013 | returned by $T.\id{gen}$, any $0 \le c < 2^{32}$, any $0 \le i < 2^{32}$, | |
1014 | and any $m \in \octet^*$, it must hold that $T.D(K, c, T.E(K, c, i, m)) = | |
1015 | (i, m)$. | |
1016 | \end{itemize} | |
1017 | \begin{aside} | |
1018 | The security of an encryption scheme tends to degrade as more data is | |
1019 | encrypted with a single key. The data limit is chosen to keep the | |
1020 | probability of a `bad event' which compromises data security below | |
1021 | $2^{-40}.$ | |
1022 | \end{aside} | |
1023 | ||
1024 | ||
1025 | \subsection{The \cookie{v0} transform} \label{sec:bulk.v0} | |
1026 | ||
1027 | Let $E$ be a symmetric encryption scheme, let $M$ be a message authentication | |
1028 | code, and let $H$ be a hash function, such that | |
1029 | \begin{itemize} | |
1030 | \item $H.\id{hsz} \ge E.\id{ksz}$, and | |
1031 | \item $H.\id{hsz} \ge M.\id{ksz}$. | |
1032 | \end{itemize} | |
1033 | The \cookie{v0} transform $T = \id{tx-v0}(E, M, H)$ is defined as follows. | |
1034 | \begin{itemize} | |
1035 | \item $T.\id{n-limit} = E.\id{n-limit}$. | |
1036 | \item If $z$ is an octet string, then $K = T.\id{gen}(z)$ is determined as | |
1037 | follows. | |
1038 | \begin{enumerate} | |
1039 | \item Let $K_E = H.\id{hash}(\texttt{"tripe-encryption"} \cat [0] \cat z)[0 | |
1040 | \upto E.\id{ksz}]$. | |
1041 | \item Let $K_M = H.\id{hash}(\texttt{"tripe-integrity"} \cat [0] \cat z)[0 | |
1042 | \upto M.\id{ksz}]$. | |
1043 | \item Then $K = (K_E, K_M)$. | |
1044 | \end{enumerate} | |
1045 | \item If $K = (K_E, K_M) \in \octet^{E.\id{ksz}} \times | |
1046 | \octet^{M.\id{ksz}}$, $0 \le c < 2^{32}$, $0 \le i < 2^{32}$, and $m \in | |
1047 | \octet^*$, then $y = T.E(K, c, i, m)$ is determined as follows. | |
1048 | \begin{enumerate} | |
1049 | \item \label{en:bulk.v0.encrypt-iv} Choose $v$ uniformly at random from | |
1050 | $\octet^{E.\id{ivsz}}$. | |
1051 | \item Let $y_0 = E.E(K_E, v, m)$. | |
1052 | \item Let $t = M.\id{tag}(K_M, [c]_4 \cat [i]_4 \cat v \cat y_0)$. | |
1053 | \item Finally, $y = t \cat [i]_4 \cat v \cat y_0$. | |
1054 | \end{enumerate} | |
1055 | \item If $K = (K_E, K_M) \in \octet^{E.\id{ksz}} \times \octet^{M.\id{ksz}}$, | |
1056 | $0 \le c < 2^{32}$, and $y \in \octet^*$, then $(i, m) = T.D(K, c, y)$ are | |
1057 | determined as follows. | |
1058 | \begin{enumerate} | |
1059 | \item If $\len(y) < M.\id{tsz} + 4 + E.\id{ivsz}$ then set $i = 0$ and $m = | |
1060 | \cookie{err-malformed}$, and go to step~\ref{en:bulk.v0.decrypt-done}. | |
1061 | \item Let $t = y[0 \upto M.\id{tsz}]$; let $i_0 = y[M.\id{tsz} \upto | |
1062 | M.\id{tsz} + 4]$; let $v = y[M.\id{tsz} + 4 \upto M.\id{tsz} + | |
1063 | E.\id{ivsz} + 4]$; let $y_0 = y[M.\id{tsz} + E.\id{ivsz} + 4 \upto | |
1064 | \len(y)]$. | |
1065 | \item If $t \ne M.\id{tag}(K_M, [c]_4 \cat i_0 \cat v \cat y_0)$ then set | |
1066 | $i = 0$ and $m = \cookie{err-tag}$, and go to | |
1067 | step~\ref{en:bulk.v0.decrypt-done}. | |
1068 | \item Let $0 \le i < 2^{32}$ be the unique integer such that $[i]_4 = i_0$. | |
1069 | \item Let $m = E.D(K_E, v, y_0)$. | |
1070 | \item \label{en:bulk.v0.decrypt-done} Return $i$ and $m$. | |
1071 | \end{enumerate} | |
1072 | \end{itemize} | |
1073 | The random selection of~$v$ in step~\ref{en:bulk.v0.encrypt-iv} of $T.E$ | |
1074 | above admits the possibility of kleptographic leakage of secrets by a | |
1075 | malicious implementation. This transform is therefore deprecated. | |
1076 | ||
1077 | ||
1078 | \subsection{The \cookie{iiv} transform} \label{sec:bulk.iiv} | |
1079 | ||
1080 | Let $E$ be a symmetric encryption scheme, let $M$ be a message authentication | |
1081 | code, let $B$ be a blockcipher, and let $H$ be a hash function, such that | |
1082 | \begin{itemize} | |
1083 | \item $H.\id{hsz} \ge E.\id{ksz}$, | |
1084 | \item $H.\id{hsz} \ge M.\id{ksz}$, | |
1085 | \item $H.\id{hsz} \ge B.\id{ksz}$, | |
1086 | \item $B.\id{bsz} \ge 4$, and | |
1087 | \item $B.\id{bsz} \ge E.\id{ivsz}$. | |
1088 | \end{itemize} | |
1089 | The \cookie{iiv} (`implicit IV') transform $T = \id{tx-iiv}(E, M, B, H)$ is | |
1090 | defined as follows. | |
1091 | \begin{itemize} | |
1092 | \item $T.\id{n-limit} = E.\id{n-limit}$. | |
1093 | \item If $z$ is an octet string, then $K = T.\id{gen}(z)$ is determined as | |
1094 | follows. | |
1095 | \begin{enumerate} | |
1096 | \item Let $K_B = H.\id{hash}(\texttt{"tripe-blkc"} \cat [0] \cat z)[0 \upto | |
1097 | B.\id{ksz}]$. | |
1098 | \item Let $K_E = H.\id{hash}(\texttt{"tripe-encryption"} \cat [0] \cat z)[0 | |
1099 | \upto E.\id{ksz}]$. | |
1100 | \item Let $K_M = H.\id{hash}(\texttt{"tripe-integrity"} \cat [0] \cat z)[0 | |
1101 | \upto M.\id{ksz}]$. | |
1102 | \item Then $K = (K_B, K_E, K_M)$. | |
1103 | \end{enumerate} | |
1104 | \item If $K = (K_B, K_E, K_M) \in \octet^{B.\id{ksz}} \times | |
1105 | \octet^{E.\id{ksz}} \times \octet^{M.\id{ksz}}$, $0 \le c < 2^{32}$, $0 \le | |
1106 | i < 2^{32}$, and $m \in \octet^*$, then $y = T.E(K, c, i, m)$ is determined | |
1107 | as follows. | |
1108 | \begin{enumerate} | |
1109 | \item Set $v = B.E([i]_{B.\id{bsz}})[0 \upto E.\id{ivsz}]$. | |
1110 | \item Let $y_0 = E.E(K_E, v, m)$. | |
1111 | \item Let $t = M.\id{tag}(K_M, [c]_4 \cat [i]_4 \cat y_0)$. | |
1112 | \item Finally, $y = t \cat [i]_4 \cat y_0$. | |
1113 | \end{enumerate} | |
1114 | \item If $K = (K_B, K_E, K_M) \in \octet^{B.\id{bsz}} \times | |
1115 | \octet^{E.\id{ksz}} \times \octet^{M.\id{ksz}}$, $0 \le c < 2^{32}$, and $y | |
1116 | \in \octet^*$, then $(i, m) = T.D(K, c, y)$ are determined as follows. | |
1117 | \begin{enumerate} | |
1118 | \item If $\len(y) < M.\id{tsz} + 4$ then set $i = 0$ and $m = | |
1119 | \cookie{err-malformed}$, and go to step~\ref{en:bulk.iiv.decrypt-done}. | |
1120 | \item Let $t = y[0 \upto M.\id{tsz}]$; let $i_0 = y[M.\id{tsz} \upto | |
1121 | M.\id{tsz} + 4]$; let $y_0 = y[M.\id{tsz} + 4 \upto \len(y)]$. | |
1122 | \item If $t \ne M.\id{tag}(K_M, [c]_4 \cat i_0 \cat y_0)$ then set $i = 0$ | |
1123 | and $m = \cookie{err-tag}$, and go to | |
1124 | step~\ref{en:bulk.iiv.decrypt-done}. | |
1125 | \item Let $0 \le i < 2^{32}$ be the unique integer such that $[i]_4 = i_0$. | |
1126 | \item Set $v = B.E([i]_{B.\id{bsz}})[0 \upto E.\id{ivsz}]$. | |
1127 | \item Let $m = E.D(K_E, v, y_0)$. | |
1128 | \item \label{en:bulk.iiv.decrypt-done} Return $i$ and $m$. | |
1129 | \end{enumerate} | |
1130 | \end{itemize} | |
1131 | ||
1132 | ||
1133 | \subsection{The \cookie{naclbox} transform} \label{sec:bulk.naclbox} | |
1134 | ||
1135 | Let $f$ be $\id{salsa20}$ or $\id{chacha}$, and $r$ be a nonnegative even | |
1136 | integer, let $k$ be 16 or 32, and let $H$ be a hash function, such that | |
1137 | $H.\id{hsz} \ge k$. The \cookie{naclbox} transform $T = \id{tx-naclbox}(f, | |
1138 | r, k, H)$ is defined as follows. | |
1139 | \begin{itemize} | |
1140 | \item $T.\id{n-limit} = 2^{134}$. | |
1141 | \begin{aside} | |
1142 | I'm not aware of any especially useful data limit for Salsa20 or ChaCha, | |
1143 | so this is just an upper bound on the amount of data which can be | |
1144 | encrypted with a single key. | |
1145 | \end{aside} | |
1146 | \item If $z$ is an octet string, then $T.\id{gen}(z) = | |
1147 | H.\id{hash}(\texttt{"tripe-encryption"} \cat [0] \cat z)[0 \upto k]$. | |
1148 | \item If $K \in \octet^k$, $0 \le c < 2^{32}$, $0 \le i < 2^{32}$, and $m | |
1149 | \in \octet^*$, then $y = T.E(K, c, i, m)$ is determined as follows. | |
1150 | \begin{enumerate} | |
1151 | \item Set $v = [i]_4 \cat [c]_4$. | |
1152 | \item Let $u = f(K, r, v, \len(m) + 32)$. | |
1153 | \item Let $y_0 = m \xor u[32 \upto \len(u)]$. | |
1154 | \item Let $r = u[0 \upto 16]$, and $s = u[16 \upto 32]$. | |
1155 | \item Let $t = \id{poly1305}(r, s, y_0)$. | |
1156 | \item Finally, $y = t \cat [i]_4 \cat y_0$. | |
1157 | \end{enumerate} | |
1158 | \item If $K \in \octet^k$, $0 \le c < 2^{32}$, and $y \in \octet^*$, then | |
1159 | $(i, m) = T.D(K, c, y)$ are determined as follows. | |
1160 | \begin{enumerate} | |
1161 | \item If $\len(y) < 20$ then set $i = 0$ and $m = \cookie{err-malformed}$ | |
1162 | and go to step~\ref{en:bulk.naclbox.decrypt-done}. | |
1163 | \item Let $t = y[0 \upto 16]$; let $i_0 = y[16 \upto 20]$; let $y_0 = y[20 | |
1164 | \upto \len(y)]$. | |
1165 | \item Set $v = i_0 \cat [c]_4$. | |
1166 | \item Let $u = f(K, r, v, \len(m) + 32)$. | |
1167 | \item Let $r = u[0 \upto 16]$, and $s = u[16 \upto 32]$. | |
1168 | \item If $t \ne \id{poly1305}(r, s, y_0)$ then set $i = 0$ and $m = | |
1169 | \cookie{err-tag}$, and go to step~\ref{en:bulk.naclbox.decrypt-done}. | |
1170 | \item Let $0 \le i < 2^{32}$ be the unique integer such that $[i]_4 = i_0$. | |
1171 | \item Let $m = y_0 \xor u[32 \upto \len(u)]$. | |
1172 | \item \label{en:bulk.naclbox.decrypt-done} Return $i$ and $m$. | |
1173 | \end{enumerate} | |
1174 | \end{itemize} | |
1175 | ||
1176 | %%%-------------------------------------------------------------------------- | |
1177 | \section{High-level protocol structure} \label{sec:highlev} | |
1178 | ||
1179 | \subsection{Message structure} \label{sec:highlev.msg} | |
1180 | ||
1181 | TrIPE messages are transmitted over UDP \cite{rfc768}. Where a fixed port | |
1182 | number is wanted, implementations should use port~4070, which has been | |
1183 | allocated by IANA. | |
1184 | ||
1185 | The first octet of a packet holds a type code. The interpretation of the | |
1186 | remaining octets depends on the type code. The defined type codes are | |
1187 | summarized in \xref{tab:highlev.msgtype}. Message codes in the range | |
1188 | 240--255 are reserved for implementation-specific features and experiments. | |
1189 | \begin{table} | |
1190 | \begin{tabular}[C]{|l|c|c|} \hlx{hv} | |
1191 | \textbf{Name} & \textbf{Code} & \textbf{Section} \\ \hlx{vhv} | |
1192 | MSG\_PACKET & $\hex{00}$ & \ref{sec:xfer.packet} \\ \hlx{vhv} | |
1193 | KX\_PRECHAL & $\hex{10}$ & \ref{sec:keyexch.prechal} \\ \hlx{v} | |
1194 | KX\_CHAL & $\hex{11}$ & \ref{sec:keyexch.chal} \\ \hlx{v} | |
1195 | KX\_REPLY & $\hex{12}$ & \ref{sec:keyexch.reply} \\ \hlx{v} | |
1196 | KX\_SWITCH & $\hex{13}$ & \ref{sec:keyexch.switch} \\ \hlx{v} | |
1197 | KX\_SWITCHOK & $\hex{14}$ & \ref{sec:keyexch.switchok} \\ \hlx{vhv} | |
1198 | MISC\_NOP & $\hex{20}$ & \ref{sec:misc.nop} \\ \hlx{v} | |
1199 | MISC\_PING & $\hex{21}$ & \ref{sec:misc.ping} \\ \hlx{v} | |
1200 | MISC\_PONG & $\hex{22}$ & \ref{sec:misc.pong} \\ \hlx{v} | |
1201 | MISC\_EPING & $\hex{23}$ & \ref{sec:misc.eping} \\ \hlx{v} | |
1202 | MISC\_EPONG & $\hex{24}$ & \ref{sec:misc.epong} \\ \hlx{v} | |
1203 | MISC\_GREET & $\hex{25}$ & \ref{sec:misc.greet} \\ \hlx{vh} | |
1204 | \end{tabular} | |
1205 | \caption{Defined message types} \label{tab:highlev.msgtype} | |
1206 | \end{table} | |
1207 | ||
1208 | In general, messages do not identify the sending or receiving peers | |
1209 | explicitly; instead, these are implied by the IP addresses and port numbers | |
1210 | in the encapsulating datagram. | |
1211 | ||
1212 | ||
1213 | \subsection{Keysets} \label{sec:highlev.keyset} | |
1214 | ||
1215 | A \emph{keyset}~$S$ is an object with components | |
1216 | \begin{itemize} | |
1217 | \item a bulk transform $S.T$; | |
1218 | \item bulk-transform keys $S.K_T$ and $S.K_R$; | |
1219 | \item a next outgoing sequence number $0 \le S.i_T \le 2^{32}$; | |
1220 | \item a set $S.I_R \subseteq 2^{\{i\in\Z\mid0\le i<2^{32}\}}$, which is a | |
1221 | conservative approximation of the set of seen incoming sequence numbers; | |
1222 | \item an integer~$n \ge 0$; | |
1223 | \item a pair of times $\id{t-limit}$ and $\id{t-exch}$; | |
1224 | \item a pair of integers $\id{n-limit}$ and $\id{n-exch}$; and | |
1225 | \item a flag $\id{kx-queued-p} \in \{ \nil, \t \}$. | |
1226 | \end{itemize} | |
1227 | ||
1228 | \subsubsection{Initialization} | |
1229 | The operation $\id{init-keyset}$ constructs a new keyset~$S$ given a bulk | |
1230 | transform~$T$ and three octet strings~$x$, $y$, and $z$. The operation | |
1231 | $\id{init-keyset}$ proceeds as follows. | |
1232 | \begin{enumerate} | |
1233 | \item $S.T = T$. | |
1234 | \item $S.K_T = T.\id{gen}(x \cat y \cat z)$; $S.K_R = T.\id{gen}(y \cat x | |
1235 | \cat z)$. | |
1236 | \item $S.i_T = 0$. | |
1237 | \item $S.I_R = \emptyset$. | |
1238 | \item $S.n = 0$. | |
1239 | \item $S.\id{t-limit}$ is the time one hour into the future; $S.\id{t-exch}$ | |
1240 | is a random time between thirty and fifty minutes hour into the future. | |
1241 | \begin{aside} | |
1242 | The randomization breaks symmetry. If both peers re-initiate key | |
1243 | exchange simultaneously, then the key-exchange protocol may take twice as | |
1244 | many round trips as would normally be necessary. | |
1245 | \end{aside} | |
1246 | \item $S.\id{n-limit} = T.\id{n-limit}$; $S.\id{n-exch} = \lfloor | |
1247 | T.\id{n-limit}/2 \rfloor$. | |
1248 | \item $S.\id{kx-queued-p} = \nil$. | |
1249 | \end{enumerate} | |
1250 | ||
1251 | \subsubsection{Encryption and decryption} | |
1252 | The operation $\id{encrypt}$ encrypts a message~$m \in \octet^*$, given a | |
1253 | keyset~$S$ and a message type code $0 \le c < 2^{32}$, returning a ciphertext | |
1254 | or failure indicator $y \in \lift{\octet^*}$. The operation $\id{encrypt}(S, | |
1255 | c, m)$ proceeds as follows. | |
1256 | \begin{enumerate} | |
1257 | \item If $S.\id{t-exch}$ is in the past, or $S.n \le S.\id{n-exch} < S.n + | |
1258 | \len(m)$, or $S.i_T = 2^{31}$, and $S.\id{kx-queued-p} = \nil$, then | |
1259 | \begin{enumerate} | |
1260 | \item initiate a fresh key-exchange with the peer | |
1261 | (\xref{sec:keyexch.init}); and | |
1262 | \item update $S.\id{kx-queued-p} \gets \t$. | |
1263 | \end{enumerate} | |
1264 | \item If $S.\id{t-limit}$ is in the past, or $S.\id{n-limit} < S.n + | |
1265 | \len(m)$, or $S.i_T = 2^{32}$, then return $\cookie{err-expired}$. | |
1266 | \item Let $y = S.T.E(S.K_T, c, S.i_T, m)$. | |
1267 | \item Update $S.i_T \gets S.i_T + 1$. | |
1268 | \item Update $S.n \gets S.n + \len(m)$. | |
1269 | \item Return $y$. | |
1270 | \end{enumerate} | |
1271 | ||
1272 | The operation $\id{decrypt}$ decrypts a ciphertext~$y \in \octet^*$, given a | |
1273 | keyset~$S$ and a message type code $0 \le c < 2^{32}$, returning a message or | |
1274 | failure indicator $m \in \lift{\octet^*}$. The operation $\id{decrypt}(S, c, | |
1275 | y)$ proceeds as follows. | |
1276 | \begin{enumerate} | |
1277 | \item Let $(i, m) = S.T.D(S.K_R, c, y)$. | |
1278 | \item If $m \in \syms$ then return $m$. | |
1279 | \begin{aside} | |
1280 | There are many reasons this might fail, not necessarily as a result of | |
1281 | enemy action. \fixme{discussion} | |
1282 | \end{aside} | |
1283 | \item If $i \in S.I_R$ then return $\cookie{err-replay}$. | |
1284 | \begin{aside} | |
1285 | The message is a replay. This may indicate an attack; conscientious | |
1286 | implementations will report this in a log. | |
1287 | \end{aside} | |
1288 | \item Update $S.I_R \gets \id{upd-seq}(S.I_R, i)$. The detailed choice of | |
1289 | the function $\id{upd-seq}$ is implementation specific, but the following | |
1290 | properties must hold, so as to cope reliably with a limited amount of | |
1291 | packet reordering by the network while strictly forbidding message replay. | |
1292 | In the following, let $I' = I \cup \{ i \}$, and let $\hat{\imath} = \max | |
1293 | I'$. | |
1294 | \begin{itemize} | |
1295 | \item It must be a conservative approximation to the union operation: | |
1296 | $I' \subseteq \id{upd-seq}(I, i)$. | |
1297 | \item It must not include sequence numbers beyond the largest seen so far: | |
1298 | $\max \id{upd-seq}(I, i) = \hat{\imath}$. | |
1299 | \item It must accurately reflect the state of the 31 sequence numbers | |
1300 | preceding the largest seen so far: $j \in \id{upd-seq}(I, i) \iff j \in | |
1301 | I'$ for $\hat{\imath} - 32 < j < \hat{\imath}$. | |
1302 | \end{itemize} | |
1303 | \item Return $m$. | |
1304 | \end{enumerate} | |
1305 | ||
1306 | %%%-------------------------------------------------------------------------- | |
1307 | \section{Key exchange} \label{sec:keyexch} | |
1308 | ||
1309 | This is the most complicated part of the TrIPE protocol. | |
1310 | ||
1311 | Key exchange occurs between a pair of peers. Key exchange is symmetrical, so | |
1312 | it is described from the point of view of one peer. | |
1313 | ||
1314 | ||
1315 | \subsection{Key exchange state} \label{sec:keyexch.state} | |
1316 | ||
1317 | An implementation maintains its \emph{key-exchange state} in an object~$X$, | |
1318 | with components | |
1319 | \begin{itemize} | |
1320 | \item a Diffie--Hellman group $X.D$; | |
1321 | \item a hash function $X.H$; | |
1322 | \item the implementation's own private key $X.a \in X.D.S$; | |
1323 | \item the implementation's own public key $X.A \in X.D.G$; | |
1324 | \item its peer's public key $X.B \in X.D.G$; | |
1325 | \item a pending keyset $X.S$; | |
1326 | \item an ephemeral secret $X.r \in X.D.S$; | |
1327 | \item a corresponding ephemeral group element $X.R \in X.D.G$; and | |
1328 | \item a flag $X.\id{activep} \in \{ \nil, \t \}$. | |
1329 | \end{itemize} | |
1330 | A pair of peers must be configured with the same Diffie--Hellman group and | |
1331 | hash. If an implementation's private key is $X.a$, then its public key $X.A | |
1332 | = X.D.\id{dh}(X.a, X.D.P)$. | |
1333 | ||
1334 | The initial pending keyset~$X.S$ and ephemeral values~$X.r$ and $X.R$ may be | |
1335 | arbitrary; initially, $X.\id{activep} = \nil$. | |
1336 | ||
1337 | ||
1338 | \subsection{Initiating key exchange} \label{sec:keyexch.init} | |
1339 | ||
1340 | Key exchange can be initiated in several ways: | |
1341 | \begin{itemize} | |
1342 | \item when a peer starts up, because it has no established keyset; | |
1343 | \item when the $\id{encrypt}$ operation (\xref{sec:highlev.keyset}) | |
1344 | determines that a keyset needs replacing; | |
1345 | \item when a peer receives KX\_PRECHAL (\xref{sec:keyexch.prechal}) and no | |
1346 | key exchange is currently in progress. | |
1347 | \end{itemize} | |
1348 | The procedure to initiate key-exchange is as follows. | |
1349 | \begin{enumerate} | |
1350 | \item If $X.\id{activep} = \t$, then there is nothing to do: return | |
1351 | immediately. | |
1352 | \item Select a new ephemeral secret $r \in X.S$ uniformly at random; update | |
1353 | $X.r \gets r$ and $X.R \gets X.D.\id{dh}(X.r, X.D.P)$. | |
1354 | \item Update $X.\id{activep} \gets \t$. | |
1355 | \item If key-exchange was not initiated as a result of an incoming | |
1356 | KX\_PRECHAL message, then send KX\_PRECHAL \xref{sec:keyexch.prechal}. | |
1357 | \end{enumerate} | |
1358 | ||
1359 | ||
1360 | \subsection{Utility functions} \label{sec:keyexch.util} | |
1361 | ||
1362 | The following definitions will be used throughout the key-exchange | |
1363 | subprotocol. | |
1364 | ||
1365 | \subsubsection{Challenge cookie construction} | |
1366 | Let $R' \in X.D.G$ be a group element; then define $\id{challenge-cookie}(R') | |
1367 | = X.H.\id{hash}(\texttt{"tripe-cookie"} \cat [0] \cat | |
1368 | X.D.\id{ge-hash}.\id{enc}(R'))$. | |
1369 | ||
1370 | \subsubsection{Expected-reply hash} | |
1371 | Let $A, R', R, U \in X.D.G$ be group elements; then | |
1372 | \[ \id{expected-reply-hash}(A, R', R, U) = | |
1373 | X.H.\id{hash}(\begin{eqnalign}[l<{{}}][t] | |
1374 | \texttt{"tripe-expected-reply"} \cat [0] \cat \\ | |
1375 | X.D.\id{ge-hash}.\id{enc}(A) \cat \\ | |
1376 | X.D.\id{ge-hash}.\id{enc}(R') \cat \\ | |
1377 | X.D.\id{ge-hash}.\id{enc}(R) \cat \\ | |
1378 | X.D.\id{ge-hash}.\id{enc}(U)) \padm. | |
1379 | \end{eqnalign} | |
1380 | \] | |
1381 | ||
1382 | \subsubsection{Check-value construction} | |
1383 | Let $R' \in X.D.G$ be a group element; then $\id{make-check-value}(R')$ is | |
1384 | defined as follows. | |
1385 | \begin{enumerate} | |
1386 | \item Let $U = X.D.\id{dh}(X.r, X.B)$. | |
1387 | \item Let $h = \id{expected-reply-mask}(X.A, R', X.R, U)$. | |
1388 | \item Then $\id{make-check-value}(R') = X.D.\id{sc}.\id{enc}(X.r) | |
1389 | \xor \id{mgf}(X.H, h, X.D.\id{scsz})$. | |
1390 | \end{enumerate} | |
1391 | ||
1392 | \subsubsection{Check-value verification} | |
1393 | Let $R' \in X.D.G$ be a group element and $c \in \octet^{X.D.\id{scsz}}$ an | |
1394 | octet string; then $\id{check-value-ok-p}(R', c)$ is defined as follows. | |
1395 | \begin{enumerate} | |
1396 | \item Let $U = X.D.\id{dh}(X.a, R')$. | |
1397 | \item Let $h = \id{expected-reply-mask}(X.B, X.R, R', U)$. | |
1398 | \item Let $(r', c') = X.D.\id{sc}.\id{dec}(c \xor \id{mgf}(X.H, h, | |
1399 | X.D.\id{scsz}))$. | |
1400 | \item If $r' \in X.D.S$ and $c' = \emptystring$ and $X.D.\id{dh}(r', X.D.P) = | |
1401 | R'$ then $\id{check-value-ok-p}(R', c) = \t$; otherwise | |
1402 | $\id{check-value-ok-p}(R', c) = \nil$. | |
1403 | \end{enumerate} | |
1404 | ||
1405 | ||
1406 | \subsection{The prechallenge message KX\_PRECHAL} \label{sec:keyexch.prechal} | |
1407 | ||
1408 | \subsubsection{Transmission} | |
1409 | Sending KX\_PRECHAL proceeds as follows. | |
1410 | \begin{enumerate} | |
1411 | \item Let $m' = [\hex{10}] \cat X.D.\id{ge-public}.\id{enc}(X.R)$. | |
1412 | \item Transmit $m'$ to the peer. | |
1413 | \end{enumerate} | |
1414 | ||
1415 | \subsubsection{Retransmission} | |
1416 | An implementation should retransmit KX\_PRECHAL message periodically while | |
1417 | key-exchange is active. The following strategy is recommended. Add a new | |
1418 | component $X.t$ to the state. When key exchange is initiated, initialize | |
1419 | $X.t = 2$. Perform the following procedure at key-exchange initiation, and | |
1420 | at every retransmission. | |
1421 | \begin{enumerate} | |
1422 | \item If $X.\id{activep} = \nil$, then do nothing and return. | |
1423 | \item Select $t$ at random between $5/6\,X.t$ and $7/6\,X.t$. | |
1424 | \item Schedule retransmission $t$ seconds into the future. | |
1425 | \item Update $X.t \gets \min(5/4\,X.t, 300)$. | |
1426 | \end{enumerate} | |
1427 | ||
1428 | \subsubsection{Reception} | |
1429 | On receipt of a KX\_PRECHAL message $m'$, perform the following procedure. | |
1430 | \begin{enumerate} | |
1431 | \item Set $m_0 = m'[1 \upto \len(m')]$. (We know $m' = [\hex{10}] \cat | |
1432 | m_0$.) | |
1433 | \item Set $(R', m_1) = X.D.\id{ge-public}.\id{dec}(m_0)$. If $R' \in \syms$ | |
1434 | then the message is malformed: discard it. | |
1435 | \item If $m_1 \ne \emptystring$ then the message is malformed: discard it. | |
1436 | \item Set $m = [\hex{11}] \cat X.D.\id{ge-public}.\id{enc}(X.R) \cat | |
1437 | \id{challenge-cookie}(R') \cat \id{make-check-value}(R')$. | |
1438 | \item Transmit $m$ to the peer. | |
1439 | \end{enumerate} | |
1440 | ||
1441 | ||
1442 | \subsection{The challenge message KX\_CHAL} \label{sec:keyexch.chal} | |
1443 | ||
1444 | \subsubsection{Reception} | |
1445 | On receipt of a KX\_CHAL message $m'$, perform the following procedure. | |
1446 | \begin{enumerate} | |
1447 | \item Set $m_0 = m'[1 \upto \len(m')]$. (We know $m' = [\hex{11}] \cat | |
1448 | m_0$.) | |
1449 | \item Set $(R', m_1) = X.D.\id{ge-public}.\id{dec}(m_0)$. If $R' \in \syms$ | |
1450 | then the message is malformed; discard it. | |
1451 | \item If $\len(m_1) \ne X.H.\id{hsz} + X.D.\id{scsz}$ then the message is | |
1452 | malformed; discard it. | |
1453 | \item Set $h' = m_1[0 \upto X.H.\id{hsz}]$ and $c' = m_1[X.D.\id{scsz} \upto | |
1454 | \len(m_1)]$. | |
1455 | \item If $h' \ne \id{challenge-cookie}(X.R)$ then the message is malformed; | |
1456 | discard it. | |
1457 | \item If $\id{check-value-ok-p}(R', c') \ne \t$ then the message is | |
1458 | malformed; discard it. | |
1459 | \item Set $Z = X.D.\id{dh}(X.r, R')$. | |
1460 | \fixme{Need per-challenge state.} | |
1461 | \end{enumerate} | |
1462 | ||
1463 | %%%-------------------------------------------------------------------------- | |
1464 | \section{Message transfer} \label{sec:xfer} | |
1465 | ||
1466 | \fixme{describe} | |
1467 | ||
1468 | %%%-------------------------------------------------------------------------- | |
1469 | \section{Miscellaneous protocol aspects} \label{sec:misc} | |
1470 | ||
1471 | \subsection{No-operation (keepalive)} \label{sec:misc.nop} | |
1472 | \fixme{describe} | |
1473 | ||
1474 | \subsection{Transport and encrypted ping} \label{sec:misc.ping} | |
1475 | \fixme{describe} | |
1476 | ||
1477 | \subsection{Greetings} \label{sec:misc.greet} | |
1478 | \fixme{describe} | |
1479 | ||
1480 | \subsection{Tokens and knocking} \label{sec:misc.knock} | |
1481 | \fixme{describe} | |
1482 | ||
1483 | %%%----- Back matter -------------------------------------------------------- | |
1484 | ||
1485 | \bibliography{mdw-crypto,eprint,rfc,% | |
1486 | cryptography1990,cryptography2000,cryptography2010,hash} | |
1487 | ||
1488 | \appendix | |
1489 | ||
1490 | %%%-------------------------------------------------------------------------- | |
1491 | \section{Summary of notation} \label{sec:notation} | |
1492 | ||
1493 | \begin{longtable}[c]{|l|p{10cm}|} \hlx{hv} | |
1494 | \textbf{Notation} & \textbf{Meaning} \\ \hlx{vh} | |
1495 | \endhead \hlx{bh} | |
1496 | \endfoot \hlx{v} | |
1497 | ||
1498 | $\cookie{example}$ & A symbol. \\ \hlx{v} | |
1499 | $\syms$ & The set of symbols. \\ \hlx{v} | |
1500 | $\lift{A}$ & The set $A$ lifted to include | |
1501 | symbols. \\ \hlx{vh/v} | |
1502 | ||
1503 | $\octet = \{ 0, 1, \dots, 255 \}$ & | |
1504 | The set of octets. \\ \hlx{v} | |
1505 | $\octet^*$ & The set of all octet strings. \\ \hlx{v} | |
1506 | $\octet^\ell$ & The set of octet strings of | |
1507 | length~$\ell$. \\ \hlx{v} | |
1508 | $\emptystring$ & The empty octet string. \\ \hlx{v} | |
1509 | $\ell = \len(x)$ & The length of an octet | |
1510 | string. \\ \hlx{v} | |
1511 | $x[i]$ & The $i$th octet of string~$x$ \\ \hlx{v} | |
1512 | $x[i \upto j]$ & The $(j - i)$-octet substring | |
1513 | of~$x$, starting at | |
1514 | position~$i$. \\ \hlx{v} | |
1515 | $x \cat y$ & The concatenation of $x$ | |
1516 | and~$y$. \\ \hlx{v} | |
1517 | $x^n$ & The $n$-fold repetition of | |
1518 | $x$. \\ \hlx{v} | |
1519 | $x \bitand y$ & The bitwise and of $x$ | |
1520 | and~$y$. \\ \hlx{v} | |
1521 | $x \bitor y$ & The bitwise (inclusive) or of | |
1522 | $x$ and~$y$. \\ \hlx{v} | |
1523 | $x \xor y$ & The bitwise exclusive-or of | |
1524 | $x$ and~$y$. \\ \hlx{v} | |
1525 | $[a_0, a_1, \ldots, a_{n-1}]$ & The $n$-octet string consisting | |
1526 | of octets $a_0$, $a_1$, \ldots, | |
1527 | $a_{n-1}$. \\ \hlx{v} | |
1528 | \texttt{"example"} & The octet string holding the | |
1529 | ASCII encoding of a text | |
1530 | string. \\ \hlx{v} | |
1531 | $[n]_\ell$ & The $\ell$-octet big-endian | |
1532 | encoding of $n$. \\ \hlx{v} | |
1533 | $[n]'_\ell$ & The $\ell$-octet little-endian | |
1534 | encoding of $n$. \\ \hlx{vh/v} | |
1535 | ||
1536 | $\ell = \len(n)$ & The `length' of an integer. \\ \hlx{v} | |
1537 | $\hex{9c}$ & An integer in hexadecimal. \\ \hlx{vh/v} | |
1538 | ||
1539 | $C$ & An encoding. \\ \hlx{v} | |
1540 | $C.\id{enc}$ & The encoding operation. \\ \hlx{v} | |
1541 | $C.\id{dec}$ & The decoding operation. \\ \hlx{vh/v} | |
1542 | ||
1543 | $H$ & A hash function. \\ \hlx{v} | |
1544 | $H.\id{hsz}$ & The hash output size. \\ \hlx{v} | |
1545 | $H.\id{bsz}$ & The hash block size. \\ \hlx{v} | |
1546 | $h = H.\id{hash}(m)$ & The hashing operation. \\ \hlx{vh/v} | |
1547 | ||
1548 | $B$ & A blockcipher (PRP). \\ \hlx{v} | |
1549 | $B.\id{ksz}$ & The blockcipher key size. \\ \hlx{v} | |
1550 | $B.\id{bsz}$ & The blockcipher block size. \\ \hlx{v} | |
1551 | $y = B.E(K, x)$ & The blockcipher encryption | |
1552 | operation. \\ \hlx{v} | |
1553 | $x = B.D(K, y)$ & The blockcipher decryption | |
1554 | operation. \\ \hlx{vh/v} | |
1555 | ||
1556 | $E$ & A symmetric encryption | |
1557 | scheme. \\ \hlx{v} | |
1558 | $E.\id{ksz}$ & The symmetric encryption | |
1559 | key size. \\ \hlx{v} | |
1560 | $E.\id{ivsz}$ & The symmetric encryption | |
1561 | initialization vector size. \\ \hlx{v} | |
1562 | $y = E.E(K, v, m)$ & The symmetric encryption | |
1563 | operation. \\ \hlx{v} | |
1564 | $m = E.D(K, v, y)$ & The symmetric decryption | |
1565 | operation. \\ \hlx{vh/v} | |
1566 | ||
1567 | $M$ & A message authentication | |
1568 | code (MAC). \\ \hlx{v} | |
1569 | $M.\id{ksz}$ & The MAC key size. \\ \hlx{v} | |
1570 | $M.\id{tsz}$ & The MAC tag size. \\ \hlx{v} | |
1571 | $t = M.\id{tag}(K, m)$ & The MAC tagging operation. \\ \hlx{vh/v} | |
1572 | ||
1573 | $D$ & A Diffie--Hellman group. \\ \hlx{v} | |
1574 | $D.S$ & The set of scalars. \\ \hlx{v} | |
1575 | $D.G$ & The set of group elements. \\ \hlx{v} | |
1576 | $D.P$ & The well-known generator. \\ \hlx{v} | |
1577 | $D.\id{scsz}$ & The length of an encoded | |
1578 | scalar. \\ \hlx{v} | |
1579 | $Z = D.\id{dh}(x, Y)$ & The group operation. \\ \hlx{v} | |
1580 | $D.\id{ge-public}$ & The public group-element | |
1581 | encoding. \\ \hlx{v} | |
1582 | $D.\id{ge-secret}$ & The secret group-element | |
1583 | encoding. \\ \hlx{v} | |
1584 | $D.\id{ge-hash}$ & The group-element encoding | |
1585 | for hashing. \\ \hlx{v} | |
1586 | $D.\id{sc}$ & The scalar encoding. \\ \hlx{vh/v} | |
1587 | ||
1588 | $T$ & A bulk transform. \\ \hlx{v} | |
1589 | $K = T.\id{gen}(x, y, z)$ & The bulk transform | |
1590 | key-generation operation. \\ \hlx{v} | |
1591 | $y = T.E(K, i, c, m)$ & The bulk transform encryption | |
1592 | operation. \\ \hlx{v} | |
1593 | $(i, m) = T.D(K, c, y)$ & The bulk transform decryption | |
1594 | operation. \\ \hlx{v} | |
1595 | ||
1596 | \end{longtable} | |
56abd1c0 MW |
1597 | |
1598 | %%%----- That's all, folks -------------------------------------------------- | |
1599 | ||
a4d41118 MW |
1600 | % LocalWords: TrIPE LaTeX encodings endian monic osp vosp TrIPE's schnorr |
1601 | % LocalWords: constlen Weierstraß abelian additively keyexch xfer dec dh | |
1602 | % LocalWords: validp ge sc scsz fe decrypts sha th hsz hbsz ok hv iiv | |
1603 | % LocalWords: naclbox crypto eprint rfc PRP FIPS ripemd eblk bcksz aes | |
1604 | % LocalWords: rijndael chacha surjective indistinguishability bsz MACs ccc | |
1605 | % LocalWords: hmac IANA vh ripemd mgf ksz aes cbc ivsz tsz fc tx blkc kx | |
1606 | % LocalWords: prechal chal switchok bh nop eping epong exch kx upd activep | |
1607 | % LocalWords: retransmit lev | |
56abd1c0 MW |
1608 | |
1609 | \end{document} |