A Cypherpunks Working Group A. Back Request for Comments: XXXX P. Brooks July, August 1995 A. Brown The Simple Key Search Protocol Status of this memo This memo defines an Experimental Protocol for the Internet community. This memo does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. 1. Introduction Modern cryptographic systems are designed such that the security of the algorithm lies entirely in the key that it uses. Without the key, an attacker is left with the task of trying every possible key until one is found that decrypts the data. Some algorithms have a fixed size key, including the famous Data Encryption Standard (DES) which has a key size of 56 bits (x possible keys). Even at the time DES was invented the key size was a point of controversy with many experts believing that large and powerful organisations had the necessary hardware to try all the keys in a reasonable time. More than 15 years later this key size is now looking even more vulnerable. More modern cryptosystems such as the International Data Encryption Standard (IDEA), whose use became widespread through its use in the Pretty Good Privacy (PGP) program, use a key size of 128 bits (x possible keys). This many keys makes a brute force attack on the algorithm utterly infeasible for any computer, or indeed all the computers in the world, using current computing technology. This does of course assume that there are no other weaknesses in the algorithm that make finding the key computationally cheaper than brute force. Other algorithms, such as RC4 (developed by RSADSI Inc.) have a variable key size. This means that in general the longer key you choose, the greater the security that you get. Since we've mentioned RC4 we might as well relate its controversial recent history here in brief. Unlike many ciphers used in the commercial world, RC4 is not protected by a patent. Patent protection would have involved disclosure of the algorithm to the public. Instead, RSADSI chose to keep RC4 as a trade secret and thus it is believed that they gained a sort of "fast track" through the export approvals that are required before US citizens may use a cipher in products that are to be sold Back, Brooks, Brown [Page 1] RFC XXXX The Simple Key Search Protocol July, August 1995 outside the USA and Canada. A condition of the export approval was that the cipher be restricted to a 40 bit key. Whilst out of the reach of the average workstation on your desk today, 40 bits is well within the capabilities of many large organisations and is probably trivial for the supercomputers used by the intelligence agency that approved the export. In early 1995 someone anonymously sent some source code that implemented RC4 to various Internet mailing lists and news groups. Whether this was done legally or not is a matter for law enforcement, what really mattered was that RC4 was no longer a trade secret, and the cipher used (mostly unknowingly) by millions of people in the applications they use every day was now known to anyone that cared. Readers of the sci.crypt newsgroup and the cypherpunks mailing list knew that the 40 bit limit for exportable RC4 was way too low and merely had the effect of lulling users into a false sense of security. They knew that alone they could not search a 40 bit keyspace in a reasonable time, but an organised effort could do it. That is how the Simple Key Search Protocol (SKSP) was inspired. The goal of SKSP is to allow anyone with an internet connection and some computer time to donate to take part in a project to search a keyspace. 1.1. Server Architecture A central server holds the details of any number of projects, including the keys that have been searched and those that have been requested and not yet searched for each project. Figure 1 illustrates the architecture of a server. +-------------------Server------------------+ | | | +---Project 1----+ +---Project n----+ | | | details | | details | | | | keys searched | ... | keys searched | | | | keys allocated | | keys allocated | | | +----------------+ +----------------+ | | | +-----++--------++---------------++---------+ || || ... || client 1 client 2 client n Figure 1. Server architecture The server listens on a port number for incoming connections from clients that wish to take part in one of the projects. As well as requesting keys from the server, the clients can (and must) also Back, Brooks, Brown [Page 2] RFC XXXX The Simple Key Search Protocol July, August 1995 retrieve the vital project details from the server. These details will include such things as the plaintext and ciphertext that the key search programs will require. 1.2. Client Architechture Client programs are designed to contact the server and ask for a range of keys to search. The number of keys that a client asks for is decided by the user and will typically be determined by the computing power available to them. A typical client program will be able to advise its user on the speed of their machine and how many hours a particular number of keys will take to search. A client implementation may choose not store details of keys requested by its user. It is expected that in this form the client will send the results of a request directly to a dedicated search program, whose output will be interpreted further by the client when it decides what to report back to the server. Another implementation may choose to perform some project management in which requested keys are remembered internally and the user can choose when to search them. In short, the level of sophistication of client programs depends on their designers. 1.3. Local Key Farming There are many users, typically systems administrators, that have entire laboratories full of computers that can be used to take part in a key searching project. In this situation it is possible to have a local server that is used to request large chunks of keyspace from the central server. This local server would then "farm out" the requested keys to its lab full of workstations. As each workstation completed its search, the local server would take the results and forward them back to the central server. Local servers such as this have the benefit of knowing the state of the workstations it serves. It may choose to allocate keys based on machine load, time of day etc. Figure 2 illustrates this sort of arrangement. Central Server / \ / \ / \ +-----Local Server 1-----+ +-----Local Server 1-----+ | / \ | | / \ | | / \ | | / \ | | / \ | | / \ | Back, Brooks, Brown [Page 3] RFC XXXX The Simple Key Search Protocol July, August 1995 | Client 1 Client 2 ... | | Client 1 Client 2 ... | +------------------------+ +------------------------+ Figure 2. Local servers 2. Command Reference This section lists the commands, syntax and response codes that are used during a communication session between clients and servers. 2.1. Session Initialisation To start a session, the client makes a call to a known server on port number 19957. Once a successful client-server connection is made, the server greets the client with a message of the following form: 221 SKSP server ready The message itself is dependent on the implementation of the server. A client should assume that the receipt of a 221 message means that the server is ready to start a session. 2.2. HELO [ ] The HELO command is used by the client to establish a common version of the protocol that they can speak, this is indicated by the argument. The client argument is optional. A server should examine the argument in order to determine if it can speak the version of the protocol that the client requires. The argument is a unique string chosen by the client that the server will use to match KEYS and ACK commands together. It is expected that the server will use this string to perform statistics gathering about the search, e.g. who has been responsible for what percentage of the work. The e-mail address of the user is ideal for this purpose since it will be unique. Persons worried about anonymity are encouraged to use an anonymous remailer address. The really paranoid should choose some other arbitrary string that stands a good chance of being unique. The client argument, if supplied, should be the full name of the user. This will be useful where the e-mail address supplied for is cryptic, or the user wishes to use a pseudonym. The HELO argument is mandatory. Servers will refuse to perform all commands, with the exception of HELP and QUIT, until a valid HELO is Back, Brooks, Brown [Page 4] RFC XXXX The Simple Key Search Protocol July, August 1995 received from the client. Possible response codes from the HELO command are: 251 HELO client using protocol version x "client" is the argument, if supplied. "x" is the version of the protocol that the client and server have agreed to talk. 501 Incorrect number of arguments 502 Protocol version not supported 550 Internal error 552 HELO already received, this one ignored 2.3. INFO The INFO command lists all projects that are known to the server. It has no arguments. The possible response codes are: 311 Project list follows, terminated by . on own line 513 No projects available 501 Incorrect number of arguments 550 Internal error 551 HELO not received yet One project is described per-line. A project description consists of 6 colon-separated fields. The fields are, in order: project identifier A number used by the client when sending commands to the server that require a project identifier code. project type A short text string that identifies the type of project. For instance, this might be "ssl" for a project that is attempting an SSL key search. project description A brief text string that describes the purpose of the project. Arbitrarily chosen by the project manager. project status A short text string that explains the current status of the project. Project managers might insert a sort of percent-done Back, Brooks, Brown [Page 5] RFC XXXX The Simple Key Search Protocol July, August 1995 indicator in here. manager e-mail address The Internet e-mail address of the person managing this project. All comments regarding the project should be sent to this address. server to be contacted for keys for this project The server and port number that a client should call to get new keys from, and report searched keys to. The format of this is "machine.domain/port". 2.4. WORK The WORK command is used to obtain details about a numbered project. It takes one argument, a project identifier. Clients should use the INFO command to obtain a list of valid project identifiers. The client should issue the WORK command to the server that it obtained the INFO from, not the key server. The possible response codes to this command are: 310 Project details follow, terminated by . on own line 510 No such project 511 Project finished 500 Syntax error 501 Incorrect number of arguments 550 Internal error 551 HELO not received yet The format of the project file returned by the WORK command is dependent on the project type. New project types are expected to be added as time goes by, and their respective project file formats will be made available to client writers at that time. 2.5. KEYS The KEYS command obtains a range of keys for the client to search. Two arguments are given. The is the numeric project identifier that should have been obtained by the client using the INFO command. The argument is the greatest number of keys that the client wishes to search. The number of keys requested depends on the type of project. For instance, in an SSL project the number may refer to key segments Back, Brooks, Brown [Page 6] RFC XXXX The Simple Key Search Protocol July, August 1995 rather than individual keys. It is acceptable for a server to return less than the requested number of keys if it does not have exactly the requested amount left to allocate. Server implementors should be aware that the receipt of a valid "KEYS" command means that any previous KEYS command received during the current session should be committed immediately to the server's database. The possible response codes are: 210 xxx yyy xxx refers to the first key, yyy refers to the number of keys. The comments about "keys" in the previous paragraph applies. xxx will be returned by the server in hexadecimal, yyy will be returned in decimal. 510 No such project 511 Project finished 512 Cannot allocate 514 Parameter out of range 500 Syntax error 501 Incorrect number of arguments 550 Internal error 551 HELO not received yet 2.6. ACK The ACK command is used for three purposes, each indicated by the value of . The values of the other arguments depend on . The argument is a project identifier that a client has obtained from the WORK command. 2.6.1. ACK SEARCHED This form of ACK informs the server that a number of keys have been searched by the client and may be eliminated from the overall search. is the number of the first key to eliminate and is the total number to eliminate, including . The is calculated by summing, modulo 65536, the and arguments, and the project configuration file that is returned by the WORK command. All lines that begin with the '#' character should be excluded from the checksum, as should all whitespace characters (space, TAB (0x9), CR and LF). The and arguments should be specified in hex, Back, Brooks, Brown [Page 7] RFC XXXX The Simple Key Search Protocol July, August 1995 the in decimal. 2.6.2. ACK REJECTED 0 This form if ACK informs the server that the range of keys given by the two arguments should be re-integrated into the server's database of keys that have not yet been searched. It is envisaged that clients will use this command when they find that they have requested more keys than they can sensibly process. The argument of zero is reserved for future use. The argument should be given in hexadecimal, the in decimal. 2.6.3. ACK FOUND 0 0 This is the form of ACK command that a client should use if it finds the successful key. should be the key in question. The zero parameters are reserved for possible future use. The command should be given in hexadecimal. The possible return codes from an ACK command are: 250 OK 510 No such project 511 Project finished 514 Parameter out of range 515 Incorrect checksum 500 Syntax error 501 Incorrect number of arguments 550 Internal error 551 HELO not received yet 2.7. QUIT This indicates to the server that the client has finished and would like to terminate the session. On receipt of a QUIT command the server should update its database with information received from the last KEYS command, if any. It should then write a response code and close the transmission channel to the client. The QUIT command takes no arguments. Possible response codes are: 220 server says goodbye to client at date "server" may be filled in with the Internet name of the server. "client" may be filled in with the Internet name of the client, as supplied to the HELO command. "date" should be the current date and time. Back, Brooks, Brown [Page 8] RFC XXXX The Simple Key Search Protocol July, August 1995 501 Incorrect number of arguments 2.8. HELP This command is used by a client to get some information from the server about the commands that it understands. The possible return codes are: 312 Help information follows, terminated by . on own line 500 Syntax error 501 Incorrect number of arguments 550 Internal error The form of the help information returned is entirely dependent on the server implementation. For instance, a server may choose to just list the available commands. Another implementation may choose to implement a more complex help system where arguments are accepted to the HELP command that specify the subject on which help is required. However, all implementations must accept HELP with no arguments. 2.9. COMM This command is used by the client to indicate a comment to the server. Typically the client should identify itself with a name and version number. The possible return codes are: 550 Internal error 250 OK 222 Client out of date, please upgrade The exact format of the "222" message is dependent on the advice that the server wishes to give the client. Note that this is only advice, not an error, and the client can continue with its session since it has already agreed a protocol version via the HELO command. 3. Server-Client Commands In addition to the normal response codes that are listed with each command, a client should be prepared to receive and process, at any time, any of the commands listed in this section. After receiving such a command from the server, the client should respond immediately with a QUIT command before continuing processing. If QUIT is not the next command sent, then the behaviour of the server is undefined. Back, Brooks, Brown [Page 9] RFC XXXX The Simple Key Search Protocol July, August 1995 3.1. 600 WAIT The client is advised that it should call the server back after at least number of seconds has elapsed, and repeat the session starting at the command that caused the WAIT to be issued. 3.2. 601 STOP [ []] The client is advised that it should stop using this server. If a argument is supplied then the client should contact the named machine and continue the session there instead, starting at the command that caused the STOP to be issued. If the argument is supplied then the client should use it instead of the default of 19957. Obviously is never supplied without . It is possible for the client to get into a STOP loop where a server orders the client to go back to a previous server that issued a STOP to the client. The client should abort processing if this happens and report the error to the server operators. 4. Miscellaneous This section describes various technical details that servers and clients will need to follow in order to successfully interoperate with each other. 4.1. Transparency Without some provision for data transparency the character sequence "." ends any multi-line reply and cannot be sent by the client. In general, clients are not aware of such "forbidden" sequences. To allow all replies to be transmitted transparently the following procedures are used. Before sending a line of text the sender checks the first character of the line. If it is a period, one additional period is inserted at the beginning of the line. When a line of text is received by the receiver it checks the line. If the line is composed of a single period it is the end of the response. If the first character is a period and there are other characters on the line, the first character is deleted. 4.2. Character Set Both servers and clients should limit themselves to using the printable subset of the ASCII character set plus CR (hex 0D) and LF (hex OA). This subset is the range 32..127 (hex 20..7F). Back, Brooks, Brown [Page 10] RFC XXXX The Simple Key Search Protocol July, August 1995 4.3. Line Endings Servers and clients must send, and be prepared to receive lines of text that are terminated either by the sequence CRLF, or by a single LF character. No other character sequences are acceptable to denote the end of a line. 4.4. Case Commands are case independent. That is "WORK" is the same as "work" is the same as "WoRk". Fixed arguments to commands such as "ACK" are also case independent. 4.5. Sizes Implementations of clients and servers that pose no restrictions on the sizes of command lines they receive are infinitely more preferable to those that use hard-coded limits. However, in the knowledge that there are languages in existence that do not support dynamic memory allocation, servers and clients should limit the lines that they transmit to 512 characters or less, including the [CR]LF terminator. 5. Example Sessions This section shows some example exchanges between the client and a server. 5.1. The INFO command In the following example some of the lines that follow the INFO command end with a backslash ('\') character. These characters do not appear in the session, they are just here to keep the line lengths in this document down to reasonable level. 221 SKSP server ready, Ver 1 to 1. You have 30 seconds. HELO 1 a.brown@nexor.co.uk Andy Brown 251 HELO Andy Brown using version 1 COMM W32C1.0 250 OK INFO 311 Project list follows, terminated by . on own line 1192:demo:allocates sequential:running:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 11fa:rc4:simple test:running:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 2:rc4:Original, failed scan:done:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 Back, Brooks, Brown [Page 11] RFC XXXX The Simple Key Search Protocol July, August 1995 289c:ssl:Hal Finney's SSL Challenge:running:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 294a:rc4ck:check rc4 works:running:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 99:test:client testing:running:pb@cl.cam.ac.uk:\ sksp.brute.cl.cam.ac.uk/19957 QUIT 220 Goodbye mirage.nexor.co.uk 5.2. The WORK command The WORK command gets the information about a project. In this example, the client is using the project ID of "294a" that it obtained from the INFO command (see section 5.1) to get the full details of the project from the server. 221 SKSP server ready, Ver 1 to 1. You have 30 seconds. HELO 1 a.brown@nexor.co.uk Andy Brown 251 HELO Andy Brown using version 1 COMM W32C1.0 250 OK WORK 294a 310 Project details follows, terminated by . on own line # simple check that the rc4 code, etc works, and timings displayed # PROJECT-ID 294a # key is 0000012345 COMMENT a test rc4 bruting to demo that your code works PLAIN-TEXT 68656c6c6f20776f726c640a CIPHER-TEXT 481cdfd219d8fbfd680c9b2a QUIT 220 Goodbye mirage.nexor.co.uk 6. Security Considerations The protocol requires the server to trust the results reported by the clients. There is no provision for the server to prove that a client has searched a keyspace, and indeed it may not even be practicallly possible to do so. APPENDIX A: Return Codes Command completed successfully 210 xxx yyy (Successful response from KEYS command) 220 server says goodbye to client at date 221 SKSP server ready 222 Client out of date, please upgrade 250 OK Back, Brooks, Brown [Page 12] RFC XXXX The Simple Key Search Protocol July, August 1995 251 HELO client using protocol version x More information follows 310 Project details follow, terminated by . on own line 311 Project list follows, terminated by . on own line 312 Help information follows, terminated by . on own line Error detected by server 500 Syntax error 501 Incorrect number of arguments 502 Protocol version not supported 503 Unknown command 510 No such project 511 Project finished 512 Cannot allocate 513 No projects available 514 Parameter out of range 515 Incorrect checksum 550 Internal error 551 HELO not received yet 552 HELO already received, this one ignored Action required by client 600 WAIT 601 STOP APPENDIX B: Authors In no particular order: Andrew Brown Piete Brooks Adam Back Back, Brooks, Brown [Page 13]