7 \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
11 .ds DH Diffie\(enHellman
12 .TH udpkey 1 "2012-05-08" "Mark Wooding" "distorted.org.uk tools"
14 udpkey \- send or receive a cryptographic key via a simple UDP protocol
53 program can run in one of two modes: either it will request fragments of
54 a key from a number of sources (e.g., local files or remote servers),
55 assemble them together, and write the result to standard output; or it
56 will listen on a UDP port and transmit encrypted copies of key fragments
61 is for obtaining keys early in a system's boot process, so as to decrypt
62 the main disk volumes. See the discussion below regarding the security
63 properties of this approach.
65 The recognized command-line options are listed below. The synopsis
66 shows two distinct invocations for clarity: in fact, all options are
67 recognized all of the time, though options which are irrelevent in the
68 chosen mode are silently ignored.
71 Print a help message to standard output and exit successfully.
74 Print the program's version number to standard output and exit
78 Print a brief usage summary to standard output and exit successfully.
85 will detach from the terminal and run in the background after
86 initialization. Also, it will write messages using
90 rather than to standard error.
92 .BI "\-k, \-\-keyring=" keyring
95 file, rather than the default, which is the file named
97 in the current working directory.
100 Listen for incoming requests for key fragments and reply to them. The
101 default is to request key fragments.
103 .BR "\-r, \-\-random=" seed-file
104 Use (an initial portion of) the contents of
106 to key the program's pseurorandom number generator. Since
108 is intended to run early in a system's boot procedure, it's quite
109 unlikely that there's a great deal of high-quality entropy available.
110 It's therefore useful to generate a key while the system is running, and
111 store it somewhere where it can be found during early boot.
115 on the command line of the form
119 the contents (or the inital 64KB of the contents, if the file is longer)
120 are read as a key fragment.
126 .IB address : port \c
133 a packet is sent to each listed
137 requesting the key fragment named by
139 responses are decrypted using the key
143 If a valid response is received from any of the listed servers (matching
146 if specified) then the contents are used as the key fragment; if no
147 response is forthcoming from any of them then the requests are
148 retransmitted periodically. If no acceptable reponse is received after
149 a number of retransmissions,
153 If all of the fragments are successfully obtained then
155 will check that they are the same length, XOR them together, and write
156 the result to its standard output; it finally exits with status 0.
162 runs in sever mode. It listens for incoming UDP packets addressed to
165 (and, if specified, the given
167 \(en by default, any local address will do). If the
169 option was given, then
171 will detach from its terminal (if any) and continue running in the
174 A request packet contains a key tag identifying the wanted key
175 fragment. The key fragment is located. If the key data is not a plain
176 binary string, or the key has no
178 attribute then the request is rejected. Otherwise the value of the
180 attribute is expected to take the form
189 The clauses of the attribute value are interpreted from left to right,
190 as follows. If the most significant
192 bits (default 32 \(en i.e., all of them) of client's IP match the
193 corresponding bits of
195 then send the key fragment, encrypted using the key named
198 .BI client- addr \fR,
201 is the client's IP address in dotted-quad form); no further clauses are
202 examined. If no clauses match then the request is refused and no reply
207 program uses the Catacomb keyring format to store its cryptographic
210 for the technical details. Keys maybe generated and managed using the
216 protocol (described below, for those who care about such things) is
217 based on the difficulty of the \*(DH in cyclic groups. The client need
218 to know the private key; the server need only know the public part.
219 Both ends must agree on the attributes associated with the key.
221 Two types of \*(DH groups are supported. The group type is determined
222 from the appropriate key's
224 attribute, if present. The possible values are as follows.
227 Plain old \*(DH, in a Schnorr group \(en i.e., a prime-order subgroup of
228 a the multiplicative group of a prime-order finite field. An
229 appropriate key may be generated using a command such as
233 .BI "key add \-t" tag " \-adh \-LS \-b3072 \-B256 udpkey-kem group=dh \fR..."
238 A prime order subgroup of the group of projective points on an elliptic
241 program can't generate such groups, though it knows of a number of
242 suitable examples, or you can use your own curves. An appropriate man
243 be generated using a command such as
246 .BI "key add \-t" tag " \-aec \-Cnist-p256 udpkey-kem group=ec \fR..."
249 Other attributes on the key determine the ancillary cryptographic
250 algorithms used in the protocol, as follows.
253 The hash function used to derive symmetric keys from the shared secret
254 group element. The default is
258 The symmetric encryption algorithm used to encrypt the key fragment.
260 .BR rijndael-counter .
263 The message authentication code used to ensure the integrity of the
264 ciphertext, in the form
265 .IB name / tagbits \fR.
266 The default is to use HMAC with the chosen hash function, and truncate
267 the tag to half of its original length.
269 Key fragments must contain only plain binary data: you can generate one
270 using a command such as
272 .BI "key add \-t" tag " \-abinary \-b256 udpkey-frag clients=" client-spec " \fR..."
276 attribute is mandatory; its syntax and semantics are described above.
277 .SS Protocol description
278 Let $G$ be a cyclic group with prime order $q$; we consider this as a
279 one-dimensional vector space over the finite field ${roman GF}(q)$. Let
280 $P$ be any nonzero element of the group.
282 The client's private key is a scalar $x$; its public key is the
283 corresponding vector $X = x P$. When constructing a request, a client
284 selects a random scalar $u$; let $U = u P$ be the corresponding vector.
285 The request packet consists of the key tag of the wanted key fragment
286 followed by a representation of the vector $U$.
288 When constructing a response, a server selects random scalars $v$ and
289 $r$, and computes $U = u P$ and $R = r P$. It then determines $Y = v U$
290 and $Z = r X$, and hashes $R$ and $Z$ to obtain keys for a symmetric
291 cipher and MAC. It encrypts the key fragment and authenticates the
292 resulting ciphertext. Finally, the response consists of the vectors $V$
293 and $W = R - Y$, the MAC tag on the ciphertext, and the ciphertext
296 The client can determine $Y = u V$, $R = W + Y$, and compute $Z = x R$,
297 and thereby recover the cipher and MAC keys.
298 .SS Security discussion
299 We assume that the client can securely
301 the key, and the ephemeral secret scalar $r$, from its memory once it
302 has finished using them. If we detect that the client has compromised
303 at some point when it does not know the key, we can instruct the servers
304 to withhold their fragments of the key.
306 The dance with $U$ and $V$ is a standard ephemeral \*(DH key exchange.
307 The other dance with $R$ and $X$, and the symmetric encryption, is
308 basically DLIES. The only trick is that $R$ is masked in the reply
309 using the ephemeral \*(DH key $Y$. (Subtracting rather than adding $Y$
310 is more efficient. For the server, it makes no difference, since it can
311 compute $-Y = (-v) U$ and add; but for the client, subtraction might be
312 rather slower than addition.)
314 We have the following properties.
316 Passively collecting requests and responses before compromising the
317 client does not assist an adversary in determining the value of a key
318 fragment, since the ephemeral scalars $u$ and $v$ are random and
319 independent. Assuming that Decisional \*(DH is hard in $G$, the
320 ephemeral secret $Y$ appears random to the adversary, so $W$ leaks
321 nothing about $R$. The symmetric keys are therefore independent of the
324 We can do better. Suppose that an adversary can recover the symmetric
325 key given a request/reply pair. If we assume that the symmetric
326 encryption is good, then the adversary must have found the key by
327 hashing $R$ and $Z$. Therefore it can recover $Y = R - W$, which solves
328 an instance of the harder
330 (actually, Gap) \*(DH problem in $G$. This analysis can be made
331 rigorous and quantitative.
333 Neither side attempts to authenticate the other explicitly. The server
334 implicitly authenticates the client by encrypting its key fragment using
335 the client's public key. (This encryption is standard DLIES, and
336 security again depends on the Gap \*(DH problem in $G$.) The client
337 doesn't attempt to authenticate the server at all, though it can check
338 that the response is correct by comparing its hash to a known copy; this
339 confirms that the received key fragment is correct, and the client has
340 no reason to care where a correct key fragment really came from.
342 If multiple sources are used, and each knows a fragment chosen uniformly
343 at random,, then none of the individual sources has enough information
344 to construct the complete key.
346 Storing a key fragment in a local file means that compromising servers
347 doesn't help an adversary obtain the key: the client
349 be compromised if the adversary is to succeed.
351 If the client is compromised, and none of the sources has revoked the
352 client's access to its fragment, then the game is over and the adversary
353 wins. The client can obviously decrypt the fragments and assemble
354 them. If any source refuses to provide its fragment, the adversary
355 learns nothing about the reassembled key.
357 In practice, high quality entropy is probably in short supply during
358 early boot. If an adversary can guess the ephemeral \*(DH scalar $u$
359 having compromised the client, he can potentially decrypt a previously
360 captured response. Periodically rekeying the random number generator
361 \(en by rewriting the
363 when high-quality entropy is available \(en serves to limit the exposure
364 to responses captured since the last rekeying.
366 For some mysterious reason,
368 initially rejects a key from
370 but when the relevant
372 script retries, everything works. I'm not sure what's going on here.
378 .BR initramfs-tools (8).
380 Mark Wooding, <mdw@distorted.org.uk>
~mdw / udpkey / blob