chiark / gitweb /
 author Mark Wooding Wed, 11 Oct 2017 21:51:27 +0000 (22:51 +0100) committer Mark Wooding Wed, 11 Oct 2017 21:51:27 +0000 (22:51 +0100)
 doc/tripe-protocol.tex patch | blob | blame | history

index d03a4b1..2ab0015 100644 (file)
@@ -117,23 +117,22 @@ In addition, there are a few minor subprotocols for various special effects.

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

+An \emph{encoding} on some set of values $S$ is defined by a pair of
+operations \id{enc} and \id{dec}, as follows.
+\begin{itemize}
+\item Given a value $x \in S$, $\id{enc}(x)$ encodes it as an octet string.
+\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a value $x$
+  and remainder string $a'$ from it.
+\end{itemize}
+Hence, the possible encodings of values form a prefix-free set of strings.
+Furthermore, if $a'$ is any octet string, and $x \in S$ is any value, then it
+must be the case that $x, a' = \id{dec}(\id{enc}(x) \cat a')$.
+
A \emph{Diffie--Hellman group} consists of a pair of sets $S$ and $G$, of
\emph{scalars} and \emph{group elements} respectively, a distinguished
\emph{generator} element $P \in G$, and a number of operations on these
groups.  In the following descriptions, $x$ and $y$ are scalars; $X$, $Y$,
and $Z$ are group elements; and $a$ and $a'$ are octet strings.
-
-An \emph{encoding} of group elements is defined by a pair of operations
-\id{enc} and \id{dec}, as follows.
-\begin{itemize}
-\item Given a group element $X$, $\id{enc}(X)$ encodes it as an octet string.
-\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a group
-  element $X$ and remainder string $a'$ from it.
-\end{itemize}
-Furthermore, if $a'$ is any octet string, and $X$ is any group element, then
-it must be the case that $X, a' = \id{dec}(\id{enc}(X) \cat a')$.  Encodings
-of scalars are defined similarly.
-
\begin{itemize}
\item $\id{dh}(x, Y)$ calculates a group element $Z$.  To be a proper
Diffie--Hellman group, it must be the case that $\id{dh}(x, \id{dh}(y, P)) @@ -144,13 +143,30 @@ of scalars are defined similarly. \item$\id{enc-ge-public}$and$\id{dec-ge-public}$together define an encoding on group elements, for which no special properties are required. \item$\id{enc-ge-secret}$and$\id{dec-ge-secret}$together define an - encoding on group elements where all encodings have the same length. -\item$\id{enc-ge-hash}$and$\id{dec-ge-hash}$together define an - encoding on group elements where all encodings should have the same length. + encoding on group elements where all encodings have the same length, except + with negligible probability. +\item$\id{enc-ge-hash}$and$\id{dec-ge-hash}$together define an encoding + on group elements where all encodings \emph{should} have the same length, + except with negligible probability.\footnote{% + The existence of groups without (mostly) fixed-length hashing encodings + is a historical mistake. If a variable-length encoding is used here, + information about group element(s) being hashed may leak to an adversary + through timing channels.} % + The decoding operation is never invoked, so it need not be possible to + implement it efficiently, though it must be theoretically possible to + decode encodings unambiguously. \item$\id{enc-sc}$and$\id{dec-sc}$together define an encoding on scalars, where all encodings have the same length. Let$\id{scsz}$be the length of an encoded scalar. \end{itemize} +In the following descriptions, decoding functions are not described explicitly +Decoding operations must validate input sufficiently that the$\id{dh}$+operation can be performed successfully and without leaking secret inputs +during the computation; but it is \emph{not} necessary to perform further +precise verification. For example, an implementation need not verify that an +incoming group element is actually within the subgroup generated by$P$; and +an elliptic-curve group need not verify that an incoming pair of coordinates +actually correspond to a point on the curve. \begin{aside} In an ideal world, we would only have one group-element encoding rather than three. The present situation is caused by unfortunate historical @@ -245,7 +261,9 @@$g \ne 1$be an element of$\gf{p}^*$such that$g^q = 1$. The cyclic subgroup$G \subseteq \gf{p}^*$generated by$g$is a \emph{Schnorr group}; the scalars are the finite field$S = \gf{q}$; and the generator is$P = g$. \begin{itemize} -\item The Diffie--Hellman operation is given by$\id{dh}(x, Y) = Y^x$. +\item The Diffie--Hellman operation is simply exponentiation in$\gf{p}$, + given by$\id{dh}(x, Y) = Y^x$. +\item \end{itemize} @@ -261,6 +279,6 @@ the scalars are the finite field$S = \gf{q}$; and the generator is$P = g\$.

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

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

\end{document}