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
56 program can run in one of two modes: either it will request fragments of
57 a key from a number of sources (e.g., local files or remote servers),
58 assemble them together, and write the result to standard output; or it
59 will listen on a UDP port and transmit encrypted copies of key fragments
64 is for obtaining keys early in a system's boot process, so as to decrypt
65 the main disk volumes. See the discussion below regarding the security
66 properties of this approach.
68 The recognized command-line options are listed below. The synopsis
69 shows two distinct invocations for clarity: in fact, all options are
70 recognized all of the time, though options which are irrelevent in the
71 chosen mode are silently ignored.
74 Print a help message to standard output and exit successfully.
77 Print the program's version number to standard output and exit
81 Print a brief usage summary to standard output and exit successfully.
88 will detach from the terminal and run in the background after
89 initialization. Also, it will write messages using
93 rather than to standard error.
95 .BI "\-k, \-\-keyring=" keyring
98 file, rather than the default, which is the file named
100 in the current working directory.
103 Listen for incoming requests for key fragments and reply to them. The
104 default is to request key fragments.
106 .BI "\-r, \-\-random=" seed-file
107 Use (an initial portion of) the contents of
109 to key the program's pseurorandom number generator. Since
111 is intended to run early in a system's boot procedure, it's quite
112 unlikely that there's a great deal of high-quality entropy available.
113 It's therefore useful to generate a seed while the system is running,
114 and store it somewhere where it can be found during early boot.
118 on the command line of the form
122 the contents (or the inital 64KB of the contents, if the file is longer)
123 are read as a key fragment.
129 .IB address : port \c
136 a packet is sent to each listed
140 requesting the key fragment named by
142 responses are decrypted using the key
146 If a valid response is received from any of the listed servers (matching
149 if specified) then the contents are used as the key fragment; if no
150 response is forthcoming from any of them then the requests are
151 retransmitted periodically. If no acceptable reponse is received after
152 a number of retransmissions,
156 If all of the fragments are successfully obtained then
158 will check that they are the same length, XOR them together, and write
159 the result to its standard output; it finally exits with status 0.
165 runs in sever mode. It listens for incoming UDP packets addressed to
168 (and, if specified, the given
170 \(en by default, any local address will do). If the
172 option was given, then
174 will detach from its terminal (if any) and continue running in the
177 A request packet contains a key tag identifying the wanted key
178 fragment. The key fragment is located. If the key data is not a plain
179 binary string, or the key has no
181 attribute, then the request is rejected. Otherwise, the value of the
183 attribute is expected to take the form
192 The clauses of the attribute value are interpreted from left to right,
193 as follows. If the most significant
195 bits (default 32 \(en i.e., all of them) of client's IP match the
196 corresponding bits of
198 then send the key fragment, encrypted using the key named
201 .BI client- addr \fR,
204 is the client's IP address in dotted-quad form); no further clauses are
205 examined. If no clauses match then the request is refused and no reply
210 program uses the Catacomb keyring format to store its cryptographic
213 for the technical details. Keys may be generated and managed using the
219 protocol (described below, for those who care about such things) is
220 based on the difficulty of \*(DH problems in cyclic groups. The client
221 needs to know the private key; the server need only know the public
222 part. Both ends must agree on the attributes associated with the key.
224 Two types of \*(DH groups are supported. The group type is determined
225 from the appropriate key's
227 attribute, if present. The possible values are as follows.
230 Plain old \*(DH, in a Schnorr group \(en i.e., a prime-order subgroup of
231 the multiplicative group of a prime-order finite field. An appropriate
232 key may be generated using a command such as
236 .BI "key add \-t" tag " \-adh \-LS \-b3072 \-B256 udpkey-kem group=dh \fR..."
241 A prime order subgroup of the group of projective points on an elliptic
244 program can't generate such groups, though it knows of a number of
245 suitable examples, or you can use your own curves. An appropriate key
246 can be generated using a command such as
249 .BI "key add \-t" tag " \-aec \-Cnist-p256 udpkey-kem group=ec \fR..."
252 Other attributes on the key determine the ancillary cryptographic
253 algorithms used in the protocol, as follows.
256 The hash function used to derive symmetric keys from the shared secret
257 group element. The default is
261 The symmetric encryption algorithm used to encrypt the key fragment.
263 .BR rijndael-counter .
266 The message authentication code used to ensure the integrity of the
267 ciphertext, in the form
268 .IB name\fR[ / tagbits \fR].
269 The defaults are to use HMAC with the chosen hash function, and truncate
270 the tag to half of its original length.
272 Key fragments must contain only plain binary data: you can generate one
273 using a command such as
275 .BI "key add \-t" tag " \-abinary \-b256 udpkey-frag clients=" client-spec " \fR..."
279 attribute is mandatory; its syntax and semantics are described above.
280 .SS Protocol description
281 Let $G$ be a cyclic group with prime order $q$; we consider this as a
282 one-dimensional vector space over the finite field ${roman GF}(q)$. Let
283 $P$ be any nonzero vector.
285 The client's private key is a scalar $x$; its public key is the
286 corresponding vector $X = x P$. When constructing a request, a client
287 selects a random scalar $u$; let $U = u P$ be the corresponding vector.
288 The request packet consists of the key tag of the wanted key fragment
289 followed by a representation of the vector $U$.
291 When constructing a response, a server selects random scalars $v$ and
292 $r$, and computes $V = v P$ and $R = r P$. It then determines $Y = v U$
293 and $Z = r X$, and hashes $R$ and $Z$ to obtain keys for a symmetric
294 cipher and MAC. It encrypts the key fragment and authenticates the
295 resulting ciphertext. Finally, the response consists of the vectors $V$
296 and $W = R - Y$, the MAC tag on the ciphertext, and the ciphertext
299 The client can determine $Y = u V$, $R = W + Y$, and compute $Z = x R$,
300 and thereby recover the cipher and MAC keys.
301 .SS Security discussion
302 We assume that the client can securely
304 the key, and the ephemeral secret scalar $r$, from its memory once it
305 has finished using them. If we detect that the client has compromised
306 at some point when it does not know the key, we can instruct the servers
307 to withhold their fragments of the key.
309 The dance with $U$ and $V$ is a standard ephemeral \*(DH key exchange.
310 The other dance with $R$ and $X$, and the symmetric encryption, is
311 basically DLIES. The only trick is that $R$ is masked in the reply
312 using the ephemeral \*(DH key $Y$. (Subtracting rather than adding $Y$
313 is more efficient. For the server, it makes no difference, since it can
314 compute $-Y = (-v) U$ and add; but for the client, subtraction might be
315 rather slower than addition.)
317 We have the following properties.
319 Passively collecting requests and responses before compromising the
320 client does not assist an adversary in determining the value of a key
321 fragment, since the ephemeral scalars $u$ and $v$ are random and
322 independent. Assuming that Decisional \*(DH is hard in $G$, the
323 ephemeral secret $Y$ appears random to the adversary, so $W$ leaks
324 nothing about $R$. The symmetric keys are therefore independent of the
327 We can do better. Suppose that an adversary can recover the symmetric
328 key given a request/reply pair. If we assume that the symmetric
329 encryption is good, then the adversary must have found the key by
330 hashing $R$ and $Z$. Therefore it can recover $Y = R - W$, which solves
331 an instance of the harder
333 (actually, Gap) \*(DH problem in $G$.
335 This analysis can be made rigorous and quantitative.
337 Neither side attempts to authenticate the other explicitly. The server
338 implicitly authenticates the client by encrypting its key fragment using
339 the client's public key. (This encryption is standard DLIES, and
340 security again depends on the Gap \*(DH problem in $G$.) The client
341 doesn't attempt to authenticate the server at all, though it can check
342 that the response is correct by comparing its hash to a known copy; this
343 confirms that the received key fragment is correct, and the client has
344 no reason to care where a correct key fragment really came from.
346 If multiple sources are used, and each knows a fragment chosen uniformly
347 at random,, then none of the individual sources has enough information
348 to construct the complete key.
350 Storing a key fragment in a local file means that compromising servers
351 doesn't help an adversary obtain the key: the client
353 be compromised if the adversary is to succeed.
355 If the client is compromised, and none of the sources has revoked the
356 client's access to its fragment, then the game is over and the adversary
357 wins. The client can obviously decrypt the fragments and assemble
358 them. If any source refuses to provide its fragment, the adversary
359 learns nothing about the reassembled key.
361 In practice, high quality entropy is probably in short supply during
362 early boot. If an adversary can guess the ephemeral \*(DH scalar $u$
363 having compromised the client, he can potentially decrypt a previously
364 captured response. Periodically rekeying the random number generator
365 \(en by rewriting the
367 when high-quality entropy is available \(en serves to limit the exposure
368 to responses captured since the last rekeying.
376 .BR initramfs-tools (8).
378 Mark Wooding, <mdw@distorted.org.uk>
~mdw / udpkey / blob