8 \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
12 .ds DH Diffie\(enHellman
13 .TH udpkey 1 "2012-05-08" "Mark Wooding" "distorted.org.uk tools"
15 udpkey \- send or receive a cryptographic key via a simple UDP protocol
54 program can run in one of two modes: either it will request fragments of
55 a key from a number of sources (e.g., local files or remote servers),
56 assemble them together, and write the result to standard output; or it
57 will listen on a UDP port and transmit encrypted copies of key fragments
62 is for obtaining keys early in a system's boot process, so as to decrypt
63 the main disk volumes. See the discussion below regarding the security
64 properties of this approach.
66 The recognized command-line options are listed below. The synopsis
67 shows two distinct invocations for clarity: in fact, all options are
68 recognized all of the time, though options which are irrelevent in the
69 chosen mode are silently ignored.
72 Print a help message to standard output and exit successfully.
75 Print the program's version number to standard output and exit
79 Print a brief usage summary to standard output and exit successfully.
86 will detach from the terminal and run in the background after
87 initialization. Also, it will write messages using
91 rather than to standard error.
93 .BI "\-k, \-\-keyring=" keyring
96 file, rather than the default, which is the file named
98 in the current working directory.
101 Listen for incoming requests for key fragments and reply to them. The
102 default is to request key fragments.
104 .BI "\-r, \-\-random=" seed-file
105 Use (an initial portion of) the contents of
107 to key the program's pseurorandom number generator. Since
109 is intended to run early in a system's boot procedure, it's quite
110 unlikely that there's a great deal of high-quality entropy available.
111 It's therefore useful to generate a seed while the system is running,
112 and store it somewhere where it can be found during early boot.
116 on the command line of the form
120 the contents (or the inital 64KB of the contents, if the file is longer)
121 are read as a key fragment.
127 .IB address : port \c
134 a packet is sent to each listed
138 requesting the key fragment named by
140 responses are decrypted using the key
144 If a valid response is received from any of the listed servers (matching
147 if specified) then the contents are used as the key fragment; if no
148 response is forthcoming from any of them then the requests are
149 retransmitted periodically. If no acceptable reponse is received after
150 a number of retransmissions,
154 If all of the fragments are successfully obtained then
156 will check that they are the same length, XOR them together, and write
157 the result to its standard output; it finally exits with status 0.
163 runs in sever mode. It listens for incoming UDP packets addressed to
166 (and, if specified, the given
168 \(en by default, any local address will do). If the
170 option was given, then
172 will detach from its terminal (if any) and continue running in the
175 A request packet contains a key tag identifying the wanted key
176 fragment. The key fragment is located. If the key data is not a plain
177 binary string, or the key has no
179 attribute, then the request is rejected. Otherwise, the value of the
181 attribute is expected to take the form
190 The clauses of the attribute value are interpreted from left to right,
191 as follows. If the most significant
193 bits (default 32 \(en i.e., all of them) of client's IP match the
194 corresponding bits of
196 then send the key fragment, encrypted using the key named
199 .BI client- addr \fR,
202 is the client's IP address in dotted-quad form); no further clauses are
203 examined. If no clauses match then the request is refused and no reply
208 program uses the Catacomb keyring format to store its cryptographic
211 for the technical details. Keys may be generated and managed using the
217 protocol (described below, for those who care about such things) is
218 based on the difficulty of \*(DH problems in cyclic groups. The client
219 needs to know the private key; the server need only know the public
220 part. Both ends must agree on the attributes associated with the key.
222 Two types of \*(DH groups are supported. The group type is determined
223 from the appropriate key's
225 attribute, if present. The possible values are as follows.
228 Plain old \*(DH, in a Schnorr group \(en i.e., a prime-order subgroup of
229 the multiplicative group of a prime-order finite field. An appropriate
230 key may be generated using a command such as
234 .BI "key add \-t" tag " \-adh \-LS \-b3072 \-B256 udpkey-kem group=dh \fR..."
239 A prime order subgroup of the group of projective points on an elliptic
242 program can't generate such groups, though it knows of a number of
243 suitable examples, or you can use your own curves. An appropriate key
244 can be generated using a command such as
247 .BI "key add \-t" tag " \-aec \-Cnist-p256 udpkey-kem group=ec \fR..."
250 Other attributes on the key determine the ancillary cryptographic
251 algorithms used in the protocol, as follows.
254 The hash function used to derive symmetric keys from the shared secret
255 group element. The default is
259 The symmetric encryption algorithm used to encrypt the key fragment.
261 .BR rijndael-counter .
264 The message authentication code used to ensure the integrity of the
265 ciphertext, in the form
266 .IB name\fR[ / tagbits \fR].
267 The defaults are to use HMAC with the chosen hash function, and truncate
268 the tag to half of its original length.
270 Key fragments must contain only plain binary data: you can generate one
271 using a command such as
273 .BI "key add \-t" tag " \-abinary \-b256 udpkey-frag clients=" client-spec " \fR..."
277 attribute is mandatory; its syntax and semantics are described above.
278 .SS Protocol description
279 Let $G$ be a cyclic group with prime order $q$; we consider this as a
280 one-dimensional vector space over the finite field ${roman GF}(q)$. Let
281 $P$ be any nonzero vector.
283 The client's private key is a scalar $x$; its public key is the
284 corresponding vector $X = x P$. When constructing a request, a client
285 selects a random scalar $u$; let $U = u P$ be the corresponding vector.
286 The request packet consists of the key tag of the wanted key fragment
287 followed by a representation of the vector $U$.
289 When constructing a response, a server selects random scalars $v$ and
290 $r$, and computes $V = v P$ and $R = r P$. It then determines $Y = v U$
291 and $Z = r X$, and hashes $R$ and $Z$ to obtain keys for a symmetric
292 cipher and MAC. It encrypts the key fragment and authenticates the
293 resulting ciphertext. Finally, the response consists of the vectors $V$
294 and $W = R - Y$, the MAC tag on the ciphertext, and the ciphertext
297 The client can determine $Y = u V$, $R = W + Y$, and compute $Z = x R$,
298 and thereby recover the cipher and MAC keys.
299 .SS Security discussion
300 We assume that the client can securely
302 the key, and the ephemeral secret scalar $r$, from its memory once it
303 has finished using them. If we detect that the client has compromised
304 at some point when it does not know the key, we can instruct the servers
305 to withhold their fragments of the key.
307 The dance with $U$ and $V$ is a standard ephemeral \*(DH key exchange.
308 The other dance with $R$ and $X$, and the symmetric encryption, is
309 basically DLIES. The only trick is that $R$ is masked in the reply
310 using the ephemeral \*(DH key $Y$. (Subtracting rather than adding $Y$
311 is more efficient. For the server, it makes no difference, since it can
312 compute $-Y = (-v) U$ and add; but for the client, subtraction might be
313 rather slower than addition.)
315 We have the following properties.
317 Passively collecting requests and responses before compromising the
318 client does not assist an adversary in determining the value of a key
319 fragment, since the ephemeral scalars $u$ and $v$ are random and
320 independent. Assuming that Decisional \*(DH is hard in $G$, the
321 ephemeral secret $Y$ appears random to the adversary, so $W$ leaks
322 nothing about $R$. The symmetric keys are therefore independent of the
325 We can do better. Suppose that an adversary can recover the symmetric
326 key given a request/reply pair. If we assume that the symmetric
327 encryption is good, then the adversary must have found the key by
328 hashing $R$ and $Z$. Therefore it can recover $Y = R - W$, which solves
329 an instance of the harder
331 (actually, Gap) \*(DH problem in $G$.
333 This analysis can be made rigorous and quantitative.
335 Neither side attempts to authenticate the other explicitly. The server
336 implicitly authenticates the client by encrypting its key fragment using
337 the client's public key. (This encryption is standard DLIES, and
338 security again depends on the Gap \*(DH problem in $G$.) The client
339 doesn't attempt to authenticate the server at all, though it can check
340 that the response is correct by comparing its hash to a known copy; this
341 confirms that the received key fragment is correct, and the client has
342 no reason to care where a correct key fragment really came from.
344 If multiple sources are used, and each knows a fragment chosen uniformly
345 at random,, then none of the individual sources has enough information
346 to construct the complete key.
348 Storing a key fragment in a local file means that compromising servers
349 doesn't help an adversary obtain the key: the client
351 be compromised if the adversary is to succeed.
353 If the client is compromised, and none of the sources has revoked the
354 client's access to its fragment, then the game is over and the adversary
355 wins. The client can obviously decrypt the fragments and assemble
356 them. If any source refuses to provide its fragment, the adversary
357 learns nothing about the reassembled key.
359 In practice, high quality entropy is probably in short supply during
360 early boot. If an adversary can guess the ephemeral \*(DH scalar $u$
361 having compromised the client, he can potentially decrypt a previously
362 captured response. Periodically rekeying the random number generator
363 \(en by rewriting the
365 when high-quality entropy is available \(en serves to limit the exposure
366 to responses captured since the last rekeying.
374 .BR initramfs-tools (8).
376 Mark Wooding, <mdw@distorted.org.uk>
~mdw / udpkey / blob