INTERNET-DRAFT J. Floyd MIT SIPB Expires 3/31/97 February 1997 Distributed Search Management Protocol Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Distribution of this memo is unlimited. Please send comments to Abstract There are a number of instances in which the search for a particular value (for instance, a cryptographic key) can be distributed across a large number of machines, however there is not currently a standard protocol for doing so. A great many algorithms may be used for searches; because these algorithms may differ greatly, the protocol used must be flexible enough to be easily extended. Overview When a large group of individuals wish to efficiently and automatically assist in searching a given search space with a given algorithm, they must contact a server to request a section of the search space. This service must accept requests on UDP port xxxx, and should accept requests on TCP port xxxx as well. Some requests may exceed UDP packet size, and thus must be sent via TCP. [The author suggests port 7533 for historical reasons.] The protocol itself has two phases, a request phase and a reporting phase. The request phase consists of a single request message followed by a single reply message. The reporting phase consists of a client reply, followed by a server acknowledgement. For UDP Floyd [Page 1] Internet Draft Distributed Search Management Protocol February, 1997 transport, each message must be fully contained in a single UDP packet. For TCP transport, each message is preceded by the length of the message in octets, represented as a two-byte big-endian integer. All values are unsigned, and in network byte order (big-endian) unless otherwise noted. Request Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |protocol vers. | msg. type | software ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | flags | #capabilities | RESERVED | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | timeout (in seconds) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / client description / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ For each capability: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | capability ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search space request / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ protocol vers. (8 bits) Contains the hex constant 0x01. msg. type Message type, hex constant 0x01 for Request Message. software ID (16 bits) The client software field may set this field to identify itself to the server. This may be used to reject clients with known problems. flags (8 bits) bits 7-2 RESERVED (must be 0) bit 1 Space Allocation Flag bit 0 Proxy Space Allocation Flag: If this is not set, the server will attempt to allocate the requested key space OR LESS for the client. If this bit is set, the server will attempt to allocate the requested key space OR MORE for the client. (Distributed servers will should set this bit, all other clients should not.) Proxy: If the proxy bit is set, the client is indicating that it is acting as a proxy for another machine or machines. Distributed servers, and disconnected operation proxies should set this bit. # capabilities (8 bits) Floyd [Page 2] Internet Draft Distributed Search Management Protocol February, 1997 number of algorithm capability records to follow. RESERVED (16 bits) Reserved for future use. These bits must be 0. timeout (in seconds) (32 bits) The amount of time following the allocation of the requested search space at which the server should not expect a reply from the client. Zero seconds (0x0000) means that the server should never timeout. (Servers are not required to support this field.) client description (variable) A C-style NULL-terminated string. This string may contain whatever message the client wishes to use to identify itself for statistical purposes. (It is suggested that the client software and operating system be identified here, but this is entirely up to the implementation.) capability ID (32 bits) Identifier for an algorithm the client supports. A given capability ID may appear only once in a request. See below for assigned identifiers. search space request (64 bits) Size (in keys) the client requests for the given algorithm. Notification Message Notification Messages may be sent from the server to the client in lieu of an Allocation Message. Further Notification messages can be sent, optionally terminated with an Allocation message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |protocol vers. | msg. type | software ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | notify type | flags | type-specific data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ protocol vers. (8 bits) Contains the hex constant 0x01. msg. type Message type, hex constant 0x02 for Notification Message. software ID (16 bits) The server software field may set this field to identify itself to the client. notify type (8 bits) Notification type (see Notification Types) flags (8 bits) bits 7-1 RESERVED (must be 0) bit 0 Last Message Last Message Flag: If this is not set, the client should expect another Notification or Allocation Message to follow this one. If this bit is set, this is the last message (and no Allocation Message will be sent.) type-specific data (variable) Floyd [Page 3] Internet Draft Distributed Search Management Protocol February, 1997 Data specific to the notification type. (see Notification Types) Allocation Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |protocol vers. | msg. type | software ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | result code | session ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | capability ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | timeout (in seconds) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / client ID (opaque data) / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # hosts | hostnames / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / algorithm-specific data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ protocol vers. (8 bits) Contains the hex constant 0x01. msg. type Message type, hex constant 0x03 for Allocation Message. software ID (16 bits) The server software field may set this field to identify itself to the client. result code (16 bits) Contains the status of the search space request. Must be 0x0000 (big-endian integer) if the request succeeds. If the request fails, the result code must be 0x0001 if the request is malformed, or 0x0002 if the server has no job matching the client's capabilities. The result code must be 0x0003 if the server does not accept messages with the given protocol version. The result code must be 0x0004 if the server does not accept messages with the given Software ID. Although only four non-zero result codes are specified here, the client should interpret any non-zero result code as a failure. session ID (16 bits) Identifier for the search space to which the client has been assigned. (In general, a server will not have more than a small number of active sessions.) This is _not_ an identifier for the client. capability ID (32 bits) Identifier for the algorithm to be used on the search space assigned. timeout (in seconds) (32 bits) The amount of time following the allocation of the requested search space at which the server does not expect a reply from the client. Zero seconds (0x0000) means that the server should never timeout. (Servers that do not support this field should set it to Floyd [Page 4] Internet Draft Distributed Search Management Protocol February, 1997 0x0000 to indicate no timeout.) client ID (opaque data) (64 bits) The client must store this value and return it with any replies to server. # hosts (8 bits) The number of hosts to follow. hostnames (variable) The hostnames of the servers to which the client may deliver responses, as a C-style NULL-terminated strings. In most cases, this will be the same as the space distribution server, but not always. (In most cases, there will be only one host specified.) algorithm-specific data (variable) Algorithm-specific data (see below) Client Response Message 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |protocol vers. | msg. type | software ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | result code | session ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | capability ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / client ID (opaque data) / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / algorithm-specific data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ protocol vers. (8 bits) Contains the hex constant 0x01. msg. type Message type, hex constant 0x05 for Client Response Message. software ID (16 bits) The client software field may set this field to identify itself to the server. result code (16 bits) Contains the status of the client search. Must be 0x0000 (big- endian integer) if the search completed without locating a result. The result code must be 0x0001 if a result was found by the search. If the search did not proceed successfully and the client wishes these results to be discarded, the result code must be 0x0002. The server should interpret any other non-zero result code as a failure. session ID (16 bits) Identifier for the search space to which the client has been assigned. capability ID (32 bits) Identifier for the algorithm used on the search space assigned. client ID (opaque data) (64 bits) The opaque data sent to the client with the request. algorithm-specific data (variable) Floyd [Page 5] Internet Draft Distributed Search Management Protocol February, 1997 Algorithm-specific data. Server Acknowledgement 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |protocol vers. | msg. type | software ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | result code | session ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | capability ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / client ID (opaque data) / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ protocol vers. (8 bits) Contains the hex constant 0x01 msg. type Message type, hex constant 0x06 for Server Acknowledgement. software ID (16 bits) The server software field may set this field to identify itself to the client. result code (16 bits) Contains the status of the client. Must be 0x0000 (big-endian integer) if the server acknowledges the searched space. The result code must be 0x0001 if the server rejects the searched space. The client should interpret any other non-zero result code as a failure. session ID (16 bits) Identifier for the search space to which the client has been assigned. capability ID (32 bits) Identifier for the algorithm used on the search space assigned. client ID (opaque data) (64 bits) The opaque data sent to the client with the request. Notification Types 0x00 Null Message This message should be ignored. No type-specific data. 0x01 Server Redirect The server may send this message if it is heavily loaded and wishes the client to use a different server. Type-specific data: Floyd [Page 6] Internet Draft Distributed Search Management Protocol February, 1997 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # hosts | hostnames / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ # hosts The number of hosts to follow. hostname (variable) The hostnames of the servers that the client may contact for key allocation, as a C-style NULL-terminated strings. 0x02 Client Idle Type-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | idle time (in seconds) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ idle time (32 bits) Time, in seconds, that the client should idle before sending future requests. 0x03 Client Exit The server may send this message if it wishes the client software to terminate. There is no algorithm-specific data. 0x04 Operator Notify The server may send this message to notify the client operator of any important information. Type-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / ASCII message / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ASCII message (variable) A C-style NULL-terminated string. 0x05 - 0xFF Reserved for future use Assigned Identifiers and Algorithm-Specific Data [Author's Note: This section will move to a separate document, as it will be updated much more frequently.] 0x00000000 - 0x0FFFFFFF Development and Testing 0x00000000 Null Search This algorithm searches the search space for the index specified. Floyd [Page 7] Internet Draft Distributed Search Management Protocol February, 1997 Allocation Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | blen | base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search value / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ blen (8 bits) The length, in octets, of the base and search value fields. base (variable) The base index into the search space where the client is to begin searching. search length (64 bits) The number of entries in the search space, starting as base, assigned to the client. search value (variable) The value being searched for. (In this null search, it is found when it is the index checked by the client.) Client Response Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | blen | base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search value / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ blen (8 bits) The length, in octets, of the base and search value fields. base (variable) The base index into the search space where the client ACTUALLY BEGAN searching. search length (64 bits) The number of entries in the search space, starting as base, ACTUALLY searched by the client. search value (variable) If the solution was found, this field must be set to the index in the search space at which the key was found. If not found, this field is ignored, and must be set to 0. 0x00000001 - 0x0FFFFFFF Reserved for future use 0x10000000 - 0x1FFFFFFF Cryptographic searches 0x10000000 - 0x100FFFFF RC5-based searches 0x10000000 - 0x1000FFFF Known Cleartext, first block 0x10000000 - 0x100000FF RC5-32/12/xx (last byte is xx) 0x10000005 RC5-32/12/5 Floyd [Page 8] Internet Draft Distributed Search Management Protocol February, 1997 0x10000006 RC5-32/12/6 0x10000007 RC5-32/12/7 0x10000008 RC5-32/12/8 0x10000009 RC5-32/12/9 0x1000000A RC5-32/12/10 0x1000000B RC5-32/12/11 0x1000000C RC5-32/12/12 0x1000000D RC5-32/12/13 0x1000000E RC5-32/12/14 0x1000000F RC5-32/12/15 0x10000010 RC5-32/12/16 (etc.) These algorithms search the search space for the RC5 key that yields a known first block cleartext, from a given first block ciphertext and initialization vector. Allocation Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / IV / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fblength | first blocks cipher / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / first blocks clear / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | #challenges | +-+-+-+-+-+-+-+-+ For each challenge: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / challenge block / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | dlength | server challenge data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ base (8*x bits, where x is the keysize in bytes) The base index into the search space where the client is to begin searching. search length (64 bits) The number of entries in the search space, starting as base, assigned to the client. IV (64 bits) The initialization vector used for encryption. fblength length, in octets, of the first blocks cipher and first blocks clear fields. first blocks cipher (variable) The first blocks of the ciphertext. first blocks clear (variable) Floyd [Page 9] Internet Draft Distributed Search Management Protocol February, 1997 The first (known) blocks of the cleartext. # challenges (8 bits) The number of challenges to follow. challenge block (fblength) The ciphertext decrypted with a random key from the assigned search space. To prove to the server that the client has searched the assigned space, it must return the key used for this encryption. dlength (8 bits) length, in octets, of the server challenge data field. server challenge data (dlength) Opaque data for the server to identify what key was used to yield the challenge block. It is suggested that the server encrypt the key value with a secret RC5 key, however any secure method is allowable. Client Response Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / key / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / checksum / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / last / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | #responses | +-+-+-+-+-+-+-+-+ For each response: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / response key / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | dlength | server challenge data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ base (8*x bits, where x is the keysize in bytes) The base index into the search space where the client ACTUALLY BEGAN searching. search length (64 bits) The number of entries in the search space, starting as base, that the client ACTUALLY searched. key (8*x bits, where x is the keysize in bytes) If the solution was found, this field must be the found key. If not found, this field is ignored, and must be set to 0. checksum (64 bits) The XOR of the results of all test encryptions over the assigned keyspace, on the first known block. (For verification purposes.) Floyd [Page 10] Internet Draft Distributed Search Management Protocol February, 1997 last (64 bits) The results of the test encryption using the IV and cleartext, using the last key in the search space on the first known block. (For verification purposes.) # responses (8 bits) The number of challenge responses to follow response key (8*x bits, where x is the keysize in bytes) The key found that yielded a given challenge block. dlength (8 bits) length, in octets, of the server challenge data field. server challenge data (dlength) Opaque data for the server to identify what key was used to yield the challenge block. 0x10000100 - 0x1000FFFF Reserved for other RC5 variants 0x10010000 - 0x100FFFFF Reserved for other types 0x10100000 - 0x101FFFFF DES-based searches 0x10100000 - 0x1010FFFF Known Cleartext, first block 0x10100000 DES-56 Known Cleartext, first block This algorithm searches the search space for the DES key that yields a known first block cleartext, from a given first block ciphertext and initialization vector. Allocation Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / IV / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / fblength | first blocks cipher / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / first blocks clear / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | #challenges | +-+-+-+-+-+-+-+-+ For each challenge: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / challenge block / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | dlength | server challenge data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ base (64 bits) The base index into the search space where the client is to begin searching. (The search space is only a 56-bit space.) search length (64 bits) The number of entries in the search space, starting as base, Floyd [Page 11] Internet Draft Distributed Search Management Protocol February, 1997 assigned to the client. IV (64 bits) The initialization vector used for encryption. fblength length, in octets, of the first blocks cipher, first blocks clear, and challenge block fields. first blocks cipher (fblength) The first blocks of the ciphertext. first blocks clear (fblength) The first (known) blocks of the cleartext. # challenges (8 bits) The number of challenges to follow. challenge block (fblength) The ciphertext decrypted with a random key from the assigned search space. To prove to the server that the client has searched the assigned space, it must return the key used for this encryption. dlength (8 bits) length, in octets, of the server challenge data field. server challenge data (dlength) Opaque data for the server to identify what key was used to yield the challenge block. It is suggested that the server encrypt the key value with a secret DES key, however any secure method is allowable. Client Response Message algorithm-specific data: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / base / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / search length / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / key / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / checksum / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / last / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | #responses | +-+-+-+-+-+-+-+-+ For each response: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ / response key / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | dlength | server challenge data / +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ base (64 bits) The base index into the search space where the client ACTUALLY BEGAN searching. search length (64 bits) Floyd [Page 12] Internet Draft Distributed Search Management Protocol February, 1997 The number of entries in the search space, starting as base, that the client ACTUALLY searched. key (64 bits) If the solution was found, this field must be the found key. If not found, this field is ignored, and must be set to 0. checksum (64 bits) The XOR of the results of all test encryptions over the assigned keyspace, on the first known block. (For verification purposes.) last (64 bits) The results of the test encryption using the IV and cleartext, using the last key in the search space. (For verification purposes.) # responses (8 bits) The number of challenge responses to follow response key (64 bits) The key found that yielded a given challenge block. dlength (8 bits) length, in octets, of the server challenge data field. server challenge data (dlength) Opaque data for the server to identify what key was used to yield the challenge block. 0x10110000 - 0x101FFFFF Reserved for other types 0x10200000 - 0x1FFFFFFF Reserved for other ciphers 0x20000000 - 0xEFFFFFFF Reserved for future use 0xFFFFF000 - 0xFFFFFFFF Reserved for Server Meta-algorithms Protocol Usage Within this protocol, the client initiates all transactions with servers. The client first sends a Request Message to the server. The server may then return zero or more Notification Messages, optionally followed by an Allocation Message. If the client does not receive the messages it expects, it may resend it's request after a reasonable period of time. After a client has searched some or all of its assigned search space (or wishes to relinquish the space), it sends a Client Response message to the server. The server replies to this with a Server Acknowledgement. The client should not assume a piece of search space has been acknowledged until it receives a Server Acknowledgement, and may resent its Client Response Message if it so wishes. A client may also report to the server that it has searched a part of the search space which it had not previously been assigned. To do this it must send the server a Client Response Message describing the Floyd [Page 13] Internet Draft Distributed Search Management Protocol February, 1997 space it searched, and proceed as normal from that point. Security Considerations Defense against malicious attacks was a key consideration in the design of this protocol, and this system is reasonably protected from many attacks. The largest concern is the possibility of malicious clients requesting large segments of key space and then quickly acknowledging it as searched. The RC5 and DES key search protocols defend against this in two ways, via a checksum for later verification, and via challenge ciphertexts. Clients are to XOR all decrypted keys together, so that a later client can confirm the results. This is only somewhat helpful; if a malicious client is ackowledging keyspace, this won't be realized until the key space is searched again. The server challenge mechanism provide a much higher level of protection. When the server assigns a section of the key space, it randomly chooses a key within that space and decrypts the ciphertext with it. It then sends this decryption, along with opaque data to later identify the challenge, to the client. When the client acknowledges the key space, it must provide the key the server used to generate the challenge. This method requires that on average at least half the keyspace must be searched, which will slow down any malicious clients considerably. It only requires an additional comparison per key on the client's part, which is a very low cost for the security provided. So that distributed servers may be used, multiple challenge texts are supported. A distributed server passes down to clients the challenges it has received, along with a seperate challenge it chooses, that it knows to be in the key space. The client must return all challenge keys that it finds in the search space. This system cannot defend against a client finding the key, but not reporting it to the servers. In a distributed search, a user who finds the key but does not report it to the server, and instead takes credit for the key themself, will likely be discovered as they will not be able to account for the processor cycles used. Client Considerations When using UDP transport, requests must fit in one packet. This limits the construction of some messages, for instance, the Request Message. The number of capabilities is limited to the number that will fit in a single UDP packet. (If the server cannot provide any search space for the first algorithms a client presents, the client should send another request with different capabilities.) If the server is unable to provide any search space for the client, it should not immediately ask the server again. The client must wait a minimum of 30 minutes before contacting the server again, or may Floyd [Page 14] Internet Draft Distributed Search Management Protocol February, 1997 optionally terminate. Server Implementation Suggestions This protocol should be flexible enough to allow a variety of client distribution schemes. The author recommends a system in which search space is assigned to clients and (optionally) logged to a file, but in which the server does not actively expire regions of the search space. Once the server reaches the end of the search space, it will start reassigning unacknowledged segments. This significantly reduces the memory and processor requirements of the server. (This method was employed in 1996 by Piete Brooks ) The server would only assign search space in blocks of powers of two, to facilitate search space management. Client responses would be logged to a file (for future reference), and the server would keep track of acknowledged keyspace with a bitmap of the acknowledged blocks. Expiration This Internet Draft expires on March 31, 1997. Author's Address Jered Floyd Student Information Processing Board 84 Massachusetts Avenue Rm. W20-557 Cambridge, MA 02139 Phone: +1 617 253 7788 Email: jered@mit.edu Floyd [Page 15]