INTERNET-DRAFT J. Floyd
<draft-floyd-distributed-search-01.txt> 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
<jered@mit.edu>
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
<Piete.Brooks@cl.cam.ac.uk>)
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]