'\" e
.\" -*-nroff-*-
.EQ
delim $$
.EN
.de hP
.IP
\h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
..
.ie t .ds o \(bu
.el .ds o o
.ds DH Diffie\(enHellman
.TH udpkey 1 "2012-05-08" "Mark Wooding" "distorted.org.uk tools"
.SH NAME
udpkey \- send or receive a cryptographic key via a simple UDP protocol
.SH SYNOPSIS
.B udpkey
.RB [ \-k
.IR keyring ]
.RB [ \-r
.IR seed-file ]
.I fragment-tag
.I source-spec
\&...
.br
.B udpkey
.B \-l
.RB [ \-d ]
.RB [ \-k
.IR keyring ]
.RB [ \-r
.IR seed-file ]
.RI [ address \c
.BR : ] \c
.I port
.PP
.IR source-spec :
.br
	
.IB address : port \c
.IB [ = \c
.IR tag ] \c
.IB [ # \c
.IR hash ] \c
.BR ; ...
.br
	
.BI / filename
|
.BI ./ filename
.SH DESCRIPTION
The
.B udpkey
program can run in one of two modes: either it will request fragments of
a key from a number of sources (e.g., local files or remote servers),
assemble them together, and write the result to standard output; or it
will listen on a UDP port and transmit encrypted copies of key fragments
when requested.
.PP
The intended use of
.B udpkey
is for obtaining keys early in a system's boot process, so as to decrypt
the main disk volumes.  See the discussion below regarding the security
properties of this approach.
.SS Options
The recognized command-line options are listed below.  The synopsis
shows two distinct invocations for clarity: in fact, all options are
recognized all of the time, though options which are irrelevent in the
chosen mode are silently ignored.
.TP
.B \-h, \-\-help
Print a help message to standard output and exit successfully.
.TP
.B \-v, \-\-version
Print the program's version number to standard output and exit
successfully.
.TP
.B \-u, \-\-usage
Print a brief usage summary to standard output and exit successfully.
.TP
.B \-d, \-\-daemon
If the
.B \-l
option is also given,
.B udpkey
will detach from the terminal and run in the background after
initialization.  Also, it will write messages using
.BR syslog (3)
(with facility
.BR daemon )
rather than to standard error.
.TP
.BI "\-k, \-\-keyring=" keyring
Read keys from the
.I keyring
file, rather than the default, which is the file named
.B keyring
in the current working directory.
.TP
.B \-l, \-\-listen
Listen for incoming requests for key fragments and reply to them.  The
default is to request key fragments.
.TP
.BI "\-r, \-\-random=" seed-file
Use (an initial portion of) the contents of
.I seed-file
to key the program's pseurorandom number generator.  Since
.B udpkey
is intended to run early in a system's boot procedure, it's quite
unlikely that there's a great deal of high-quality entropy available.
It's therefore useful to generate a seed while the system is running,
and store it somewhere where it can be found during early boot.
.SS Client operation
For each
.I source-spec
on the command line of the form
.BI / filename
or
.BI ./ filename
the contents (or the inital 64KB of the contents, if the file is longer)
are read as a key fragment.
.PP
For each
.I source-spec
of the form
.IP
.IB address : port \c
.RB [ = \c
.IR tag ] \c
.RB [ # \c
.IR hash ] \c
.BR ; ...
.PP
a packet is sent to each listed
.I address
and
.I port
requesting the key fragment named by
.IR fragment-tag ;
responses are decrypted using the key
.I tag
(default
.BR udpkey-kem ).
If a valid response is received from any of the listed servers (matching
the given
.I hash
if specified) then the contents are used as the key fragment; if no
response is forthcoming from any of them then the requests are
retransmitted periodically.  If no acceptable reponse is received after
a number of retransmissions,
.B udpkey
will give up.
.PP
If all of the fragments are successfully obtained then
.B udpkey
will check that they are the same length, XOR them together, and write
the result to its standard output; it finally exits with status 0.
.SS Server operaton
If the
.B \-l
option was given,
.B udpkey
runs in sever mode.  It listens for incoming UDP packets addressed to
the given
.I port
(and, if specified, the given
.I address
\(en by default, any local address will do).  If the
.B \-d
option was given, then
.B udpkey
will detach from its terminal (if any) and continue running in the
background.
.PP
A request packet contains a key tag identifying the wanted key
fragment.  The key fragment is located.  If the key data is not a plain
binary string, or the key has no
.B clients
attribute, then the request is rejected.  Otherwise, the value of the
.B clients
attribute is expected to take the form
.IP
.IR address \c
.RB [ / \c
.IR prefix-len ] \c
.RB [ = \c
.IR tag ] \c
.BR ; ...
.PP
The clauses of the attribute value are interpreted from left to right,
as follows.  If the most significant
.I prefix-len
bits (default 32 \(en i.e., all of them) of client's IP match the
corresponding bits of
.I address
then send the key fragment, encrypted using the key named
.I tag
(default
.BI client- addr \fR,
where
.I addr
is the client's IP address in dotted-quad form); no further clauses are
examined.  If no clauses match then the request is refused and no reply
is sent.
.SS Key setup
The
.B udpkey
program uses the Catacomb keyring format to store its cryptographic
keys: see
.BR keyring (5)
for the technical details.  Keys may be generated and managed using the
.BR key (1)
utility.
.PP
The security of
.BR udpkey 's
protocol (described below, for those who care about such things) is
based on the difficulty of \*(DH problems in cyclic groups.  The client
needs to know the private key; the server need only know the public
part.  Both ends must agree on the attributes associated with the key.
.PP
Two types of \*(DH groups are supported.  The group type is determined
from the appropriate key's
.B group
attribute, if present.  The possible values are as follows.
.TP
.B dh
Plain old \*(DH, in a Schnorr group \(en i.e., a prime-order subgroup of
the multiplicative group of a prime-order finite field.  An appropriate
key may be generated using a command such as
.RS
.IP
.nf
.BI "key add \-t" tag " \-adh \-LS \-b3072 \-B256 udpkey-kem group=dh \fR..."
.fi
.RE
.TP
.B ec
A prime order subgroup of the group of projective points on an elliptic
curve.  Catacomb's
.BR key (1)
program can't generate such groups, though it knows of a number of
suitable examples, or you can use your own curves.  An appropriate key
can be generated using a command such as
.RS
.IP
.BI "key add \-t" tag " \-aec \-Cnist-p256 udpkey-kem group=ec \fR..."
.RE
.PP
Other attributes on the key determine the ancillary cryptographic
algorithms used in the protocol, as follows.
.TP
.B hash
The hash function used to derive symmetric keys from the shared secret
group element.  The default is
.BR sha256 .
.TP
.B cipher
The symmetric encryption algorithm used to encrypt the key fragment.
The default is
.BR rijndael-counter .
.TP
.B mac
The message authentication code used to ensure the integrity of the
ciphertext, in the form
.IB name\fR[ / tagbits \fR].
The defaults are to use HMAC with the chosen hash function, and truncate
the tag to half of its original length.
.PP
Key fragments must contain only plain binary data: you can generate one
using a command such as
.IP
.BI "key add \-t" tag " \-abinary \-b256 udpkey-frag clients=" client-spec " \fR..."
.PP
The
.B client
attribute is mandatory; its syntax and semantics are described above.
.SS Protocol description
Let $G$ be a cyclic group with prime order $q$; we consider this as a
one-dimensional vector space over the finite field ${roman GF}(q)$.  Let
$P$ be any nonzero vector.
.PP
The client's private key is a scalar $x$; its public key is the
corresponding vector $X = x P$.  When constructing a request, a client
selects a random scalar $u$; let $U = u P$ be the corresponding vector.
The request packet consists of the key tag of the wanted key fragment
followed by a representation of the vector $U$.
.PP
When constructing a response, a server selects random scalars $v$ and
$r$, and computes $V = v P$ and $R = r P$.  It then determines $Y = v U$
and $Z = r X$, and hashes $R$ and $Z$ to obtain keys for a symmetric
cipher and MAC.  It encrypts the key fragment and authenticates the
resulting ciphertext.  Finally, the response consists of the vectors $V$
and $W = R - Y$, the MAC tag on the ciphertext, and the ciphertext
itself.
.PP
The client can determine $Y = u V$, $R = W + Y$, and compute $Z = x R$,
and thereby recover the cipher and MAC keys.
.SS Security discussion
We assume that the client can securely
.I erase
the key, and the ephemeral secret scalar $r$, from its memory once it
has finished using them.  If we detect that the client has compromised
at some point when it does not know the key, we can instruct the servers
to withhold their fragments of the key.
.PP
The dance with $U$ and $V$ is a standard ephemeral \*(DH key exchange.
The other dance with $R$ and $X$, and the symmetric encryption, is
basically DLIES.  The only trick is that $R$ is masked in the reply
using the ephemeral \*(DH key $Y$.  (Subtracting rather than adding $Y$
is more efficient.  For the server, it makes no difference, since it can
compute $-Y = (-v) U$ and add; but for the client, subtraction might be
rather slower than addition.)
.PP
We have the following properties.
.hP \*o
Passively collecting requests and responses before compromising the
client does not assist an adversary in determining the value of a key
fragment, since the ephemeral scalars $u$ and $v$ are random and
independent.  Assuming that Decisional \*(DH is hard in $G$, the
ephemeral secret $Y$ appears random to the adversary, so $W$ leaks
nothing about $R$.  The symmetric keys are therefore independent of the
adversary's view.
.IP
We can do better.  Suppose that an adversary can recover the symmetric
key given a request/reply pair.  If we assume that the symmetric
encryption is good, then the adversary must have found the key by
hashing $R$ and $Z$.  Therefore it can recover $Y = R - W$, which solves
an instance of the harder
.I Computational
(actually, Gap) \*(DH problem in $G$.
.IP
This analysis can be made rigorous and quantitative.
.hP \*o
Neither side attempts to authenticate the other explicitly.  The server
implicitly authenticates the client by encrypting its key fragment using
the client's public key.  (This encryption is standard DLIES, and
security again depends on the Gap \*(DH problem in $G$.)  The client
doesn't attempt to authenticate the server at all, though it can check
that the response is correct by comparing its hash to a known copy; this
confirms that the received key fragment is correct, and the client has
no reason to care where a correct key fragment really came from.
.hP \*o
If multiple sources are used, and each knows a fragment chosen uniformly
at random,, then none of the individual sources has enough information
to construct the complete key.
.hP \*o
Storing a key fragment in a local file means that compromising servers
doesn't help an adversary obtain the key: the client
.I must
be compromised if the adversary is to succeed.
.hP \*o
If the client is compromised, and none of the sources has revoked the
client's access to its fragment, then the game is over and the adversary
wins.  The client can obviously decrypt the fragments and assemble
them.  If any source refuses to provide its fragment, the adversary
learns nothing about the reassembled key.
.hP \*o
In practice, high quality entropy is probably in short supply during
early boot.  If an adversary can guess the ephemeral \*(DH scalar $u$
having compromised the client, he can potentially decrypt a previously
captured response.  Periodically rekeying the random number generator
\(en by rewriting the
.I seed-file
when high-quality entropy is available \(en serves to limit the exposure
to responses captured since the last rekeying.
.SH BUGS
None known.
.SH SEE ALSO
.BR key (1),
.BR crypttab (5),
.BR keyring (5),
.BR cryptsetup (8),
.BR initramfs-tools (8).
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>