SKSP Simple Key Search Protocol

Authors:

Andy Brown <asb@nexor.co.uk>
Piete Brooks <Piete.Brooks@cl.cam.ac.uk>
Adam Back <adam@cypherspace.org>


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 <version> <id> [ <client> ]

   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
   <version> argument.  The client argument is optional.  A server
   should examine the <version> argument in order to determine if it can
   speak the version of the protocol that the client requires.

   The <id> 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 <id>
   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 <client> 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 <pid>

   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 <pid> <size>

   The KEYS command obtains a range of keys for the client to search.
   Two arguments are given.

   The <pid> is the numeric project identifier that should have been
   obtained by the client using the INFO command.

   The <size> 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 <pid> <code> <arg1> <arg2> <arg3>

   The ACK command is used for three purposes, each indicated by the
   value of <code>.  The values of the other arguments depend on <code>.
   The <pid> argument is a project identifier that a client has obtained
   from the WORK command.

   2.6.1.  ACK <pid> SEARCHED <checksum> <first> <count>

      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.  <first> is the number of the first key to eliminate and
      <count> is the total number to eliminate, including <first>.

      The <checksum> is calculated by summing, modulo 65536, the <first>
      and <count> 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 <first> and <checksum> arguments should be specified in hex,



Back, Brooks, Brown                                             [Page 7]





RFC XXXX             The Simple Key Search Protocol    July, August 1995


      the <count> in decimal.

   2.6.2.  ACK <pid> REJECTED 0 <first> <count>

      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 <first> argument should
      be given in hexadecimal, the <count> in decimal.

   2.6.3.  ACK <pid> FOUND 0 <key> 0

      This is the form of ACK command that a client should use if it
      finds the successful key.  <key> should be the key in question.
      The zero parameters are reserved for possible future use.  The
      <key> 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 <comment>

   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 <period>

   The client is advised that it should call the server back after at
   least <period> number of seconds has elapsed, and repeat the session
   starting at the command that caused the WAIT to be issued.

3.2.  601 STOP [<host> [<port>]]

   The client is advised that it should stop using this server.  If a
   <host> 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 <port> argument is
   supplied then the client should use it instead of the default of
   19957.  Obviously <port> is never supplied without <host>.

   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
   "<CRLF>.<CRLF>" 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 <a.brown@nexor.co.uk> 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 <a.brown@nexor.co.uk> 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























Back, Brooks, Brown                                            [Page 13]

Comments, html bugs to me (Adam Back) at <adam@cypherspace.org>