ERights Home elib / distrib / vattp 
Back to: Data Pluribus Overview x On to: Testing Data-Pluribus

VatTP Startup Protocol


Written by Bill Frantz (frantz-at-pwpconsult.com). Current as of 7/2/1998. Includes the fixes for resolving crossed connection conflicts.

Update September 8, 1998 [Bill] - Change RegistrarID to VatID. Include changes to detect that a connectToVatAt() call has connected to self (in Outgoing Expect IAM and Incoming Expect GIVEINFO). Document message formats and key generation for the supported crypto suites.
Update September 18, 1998 [Bill] - Fix minor errors.
Update August 29, 2000 [Bill] - Add 3DES_SDH_M2 encryption using standard CBC, separate message number, and HMAC as the preferred protocol.
Update December 22, 2000 [Bill] - Fix typos. Clarify details of processing for the 3DES_SDH_M2 protocol.


Basic Message Formats

The Connection Startup Protocol uses messages formatted with java.io.DataOutputStream. The first byte of the message is one of the types defined in org.erights.e.net.data.Msg. PROTOCOL_VERSION, PROTOCOL_ACCEPTED, and STARTUP are used in the startup protocol. The startup protocol uses writeUTF(), writeShort() (read with readUnsignedShort()), and write(byte[]) in sending the pieces of the protocol. These are refered to as UTF, short, and byte[] in the descriptions below.

The PROTOCOL_VERSION message: (byte type=PROTOCOL_VERSION=1, UTF 1stProtocolID, UTF 2ndProtocolID, ...). The only protocol version currently supported is "E1".

The PROTOCOL_ACCEPTED message: (byte type=PROTOCOL_ACCEPTED=3, UTF protocolID).

The STARTUP message is used for all the rest of the messages: (byte type=STARTUP=2, byte token, arguments). Where arguments and their format are defined in the protocol description below, and token is defined in org.erights.e.net.data.StartUpProtocol and is one of:

    final private static int TOK_BYE                =  1;
    final private static int TOK_DUP                =  2;
    final private static int TOK_GIVEINFO           =  3;
    final private static int TOK_GO                 =  4;
    final private static int TOK_GOTOO              =  5;
    final private static int TOK_IAM                =  6;
    final public  static int TOK_IWANT              =  7;
    final public  static int TOK_NOT_ME             =  8;
    final private static int TOK_QUIT               =  9;
    final private static int TOK_REPLYINFO          = 10;
    final public  static int TOK_TRY                = 11;
    final private static int TOK_RESUME             = 12;
    final private static int TOK_YOUCHOSE           = 13;
    final public  static int TOK_ERR_PROTOCOL       = -2;
    final private static int TOK_ERR_WRONG_ID       = -3;
    final private static int TOK_ERR_INTERNAL       = -4;

Connection Establishment

There are three layers of code responsible for connections in the data comm system. The top level is VatTPMgr. It is responsible for all the connections between a E vat and other vats. It includes methods such as "VatTPConnection getConnection(remoteVatID , searchPath)" and "connectToVatAt(IP:port)" which either create a connection and returns it, or return an existing connection.

The connection to a specific other vat is handled by the VatTPConnection object. It is responsible for building new connections and resuming suspended connections.

The connection to a specific machine is handled by the DataPath object. It, along with its SendThread and RecvThread, handles one TCP connection.

The normal connection build process starts with the connection call to the VatTPMgr described above. The remoteVatID parameter specifies which specific vat is wanted, and the searchPath parameter specifies places to look for it. The search path is normally a set of Process Location Servers to query. There is a specific VatID ("0") which is recognized as "any vat listening at the IP:port passed in the connectToVatAt() call on the VatTPMgr.

The search for a vat starts by building a DataPath to the first address on the search path, normally a PLS. If that PLS knows where the vat is, it returns the IP address and port number which is inserted into the search path. The currently active instance of DataPath has then completed its job, so it closes the TCP connection, and notifies the VatTPConnection that it has shutdown. The VatTPConnection then builds a new DataPath to try the next address in the search path.

The connection startup protocol (Alice is connecting to Bob) used by the DataPath is as follows. Note that there are two interleaved protocol negotiations involved. The version of the E protocol to use, and the low level encryption/compression protocol. The E protocol negotiation is over quickly, while the encryption protocol negotiation involves the exchange of keys and the verification of identities.

In the description below, <PROBLEM> is one of ERR_PROTOCOL, if a wrong protocol message type was received or the remote end is using an unsupported version of the protocol, or ERR_WRONG_ID if the far end responds IAM for the wrong vatID or the remote public key does not hash to the vatID. TOK_ERR_INTERNAL is used to notify the other end that an internal error has caused the connection attempt to fail.

The protocol is described using the notation, "Sender: message paremeters (comments)"

-------------------Outgoing Startup State------------------------
 Alice: PROTOCOL_VERSION <list of E protocol versions supported>.

 Alice: IWANT <UTF bobVatID>


-----------------Incoming New Connection State-------------------
   Bob: PROTOCOL_ACCEPTED UTF version of E protocol to use,
    or  <PROBLEM> and throw exception.

------------------Incoming Expect IWANT State--------------------
   Bob: IAM <UTF bobVatID> <UTF bobsPathToBob> <short keyLen>
                      <byte[] bobPublicKey>
                                             (continue with protocol)
    or  NOTME                                (try next site in search path)
    or  TRY <UTF possibleAlternatePath>      (add to search path, try next site)
    or  DUP                                  (crossed connections, quietly stop)
    or  <PROBLEM>                                    (stop)
-------------------Outgoing Expect IAM State---------------------

If Alice receives TRY, as she would from the PLS, she adds the <possibleAlternatePath> to her search path and shuts down the DataPath. If she receives NOTME (NotMe) she just shuts down the DataPath without adding to the path. The VatTPConnection will build a new DataPath to try the next entry in the path (if any).

If Alice receives Bob's IAM:

 Alice: GIVEINFO <UTF aliceVatID> <UTF alicesPathToAlice>
                 <short keyLen> <byte[]alicePublicKey>
    or  NOTME                                (Bob's VatID is the same as Alice's)
    or  DUP                                  (duplicated connection, quietly stop)
    or  <PROBLEM>                                    (stop)
-----------------Incoming Expect GIVEINFO State------------------

If Bob receives an invalid message type:

   Bob: <PROBLEM>                                    (stop)

If Bob receives Alice's NOTME, he recognizes that Alice tried to connect to herself and stops.

If Bob receives Alice's GIVEINFO and Bob only knows of one connection:

   Bob: REPLYINFO <UTF cryptoProtocols>           (continue)

If Bob receives Alice's GIVEINFO and Bob knows of crossed connections and Bob is the catbird:

   Bob: REPLYINFO <UTF cryptoProtocols>              (continue)
    or  DUP                                          (stop, crossed connections)

If Bob receives Alice's GIVEINFO and Bob knows of crossed connections and Alice is the catbird:

   Bob: REPLYINFO <UTF cryptoProtocols>              (continue)
    or  YOUCHOSE  <UTF cryptoProtocols>              (continue)

Where <cryptoProtocols> is a comma separated list of crypto protocol versions that Bob knows (see <version> below), in order from most favored to least favored.



Crossed connection notes

A crossed connection exists when Alice tries to build a connection to Bob at the same time Bob is trying to build a connection to Alice. If Bob's vatID is greater than Alice's, then Bob is the "catbird" and must decide which of the two connections to use. Otherwise Alice is the catbird and she must be notified that she is to decide.

Since the GIVEINFO state is on an incoming connection, Bob is in a position to notice that he is also in the process of building a connection to Alice, and the potential for crossed connections exists. If he is not the catbird he notifies Alice that she must decide by sending the YOUCHOSE message.

If he is the catbird, he looks at the state of the outgoing connection. He decides to keep the incoming or the outgoing connection based on that state:

    ST_UNSTARTED                      Keep incoming
    ST_OUTGOING_EXPECT_IAM            Keep incoming
    ST_OUTGOING_EXPECT_REPLYINFO      Keep incoming
    ST_OUTGOING_EXPECT_GOTOO          Keep outgoing
    ST_EXPECT_MESSAGE                 Keep outgoing

If Alice receives the YOUCHOSE message on her outgoing connection attempt, she looks at the state of any incoming connection for Bob's vatID she may know about. She decides to keep the incoming or the outgoing connection based on that state:

    No connection known               Keep outgoing
    ST_INCOMING_EXPECT_IWANT          Keep outgoing
    ST_INCOMING_EXPECT_GIVEINFO       Keep outgoing
    ST_INCOMING_EXPECT_GO             Keep incoming
    ST_EXPECT_MESSAGE                 Keep incoming

When Bob eliminates the outgoing connection or Alice eliminates the incoming connection, they shutdown the path they are terminating. This action causes the TCP connection to be closed and the DataPath to be shutdown.


----------------Outgoing Expect REPLYINFO State------------------

If Alice received an invalid message type:

 Alice: <PROBLEM>                                    (stop)

If Alice receives a DUP she stops attempting to connect on the MsgConnection. If she receives one of the <PROBLEM> responses, she generates an error log and stops attempting to connect on the MsgConnection.

If Alice receives a YOUCHOSE, she choses which connection to eliminate.

 Alice: QUIT                          (If she keeps the incoming)

Otherwise she processes the YOUCHOSE the same as a REPLYINFO.

If Alice receives Bob's REPLYINFO and there is an outgoing suspendID:

 Alice: RESUME <short len> <byte[] suspendID>
                                      (resume suspended connection)

If Alice receives Bob's REPLYINFO and it includes a crypto protocol Alice supports:

 Alice: GO <crypto parameters>        (continue)

If Alice receives Bob's REPLYINFO and it includes CRYPTO_NONE:

Alice: GO (continue, no crypto)

Otherwise when Alice receives Bob's REPLYINFO:

 Alice: ERR_PROTOCOL                  (can't agree on crypto)


--------------------Incoming Expect GO State---------------------

If Bob received an invalid message type:

   Bob: <PROBLEM>                     (stop)

If Bob receives a RESUME from Alice and the suspendID matches his suspendID:

   Bob: GOTOO                         (resume connection)

If Bob receives a RESUME and the suspendIDs do not match:

   Bob: BYE                           (Wrong suspendID)

If Bob receives a QUIT he stops attempting to connect on the DataPath.

If Bob receives a GO and detects a crossed connection and decides that this DataPath should be abandoned:

   Bob: BYE                           (crossed connections)

If Bob receives a GO and expects a RESUME:

   Bob: BYE                           (discarded resumable connection)

If Bob receives a GO and it includes a supported crypto <version>:

   Bob: GOTOO <crypto parameters>     (Bob starts encrypted session)

Otherwise if the GO does not include a supported crypto <version>:

   Bob: GOTOO <CRYPTO_NONE>           (Bob starts unencrypted session)


-------------------Outgoing Expect GOTOO State-------------------

If Alice received an invalid message type:

 Alice: <PROBLEM>                                    (stop)

If Alice receives a BYE, she stops attempting to connect on the MsgConnection.

If Alice receives Bob's GOTOO, she starts an encrypted session or unencrypted session depending on what Bob has sent for <crypto parameters>. Thence both can send each other E messages according to the message protocol.


Definition of message components

 <crypto parameters> are:
      <UTF version> <version specific parameters>

 The value of <version> is selected from the currently supported list:
      "None"      - No crypto used. No version specific parameters.
      "3DES_SDH_M" - Triple DES with DH key agreement and MAC.  <DHparameters>
                    are the version specific parameters.
                    More than one E message may be included a an
                    encrypted packet.
      "3DES_SDH_M2" - Triple DES/CBC with DH key agreement and HMAC. <DHparameters> 
                    are the version specific parameters. 
                    More than one E message may be included a an
                    encrypted packet.

      

The <DHparameters> are shipped as two sequences of (short len. byte[] data). They are:

<gx mod m>,<DSA signature on messages sent + gx mod m>

N.B. The signature covers the startup protocol in addition to just gx mod m. This is to guard against an attack where a man in the middle can change the list of supported encryption types and force no encryption when both ends would prefer encrypted links. The specific messages included in the signature are:

    Outgoing connection

    • GIVEINFO
    • IAM
    • IWANT
    • PROTOCOL_VERSION

    Incoming Connection

    • PROTOCOL_ACCEPTED
    • IAM
    • REPLYINFO
    • YOUCHOSE

Key Generation and Message Formats

This section deals with two granualities of message. There are the E messages, which are a direct result of E.send and E.sendOnly operations. Several of these messages may be combined into a single TCP level message for transmission over the TCP connection. This second kind of message will be called a TCP message.

These TCP messages are described using a notation which gives the length of each element and its value. For example, a 4 byte integer length is described as (4,length). The fields are written one after another to indicate concatination. For example: (4,length) (length,data).

For encryption version == "None"

    Key generation: There are, of course, no keys generated.

    TCP Message format: (4,length) (length,message)

For encryption version == "3DES_SDH_M" (deprecated)

    Key generation

    This encryption version calculated 4 separate "keys". They are: a 24 byte 3DES key, a 64 byte MAC key, an 8 byte initial sendIV, and an 8 byte initial receiveIV. First a Diffie-Hellman secret (dhSecret) is calculated by taking the gx mod m value received from the other side and calculating BigInteger secret = (gx mod m)y mod m using the standard Java BigInteger class. Then byte[] dhSecret = secret.toByteArray();

    The individual keys are calculated from dhSecret using MD5 and a 16 byte pad consisting of a single byte repeated 16 times as follows:

      3DESKey1 is the first 8 bytes of md5((16,pad)(n,dhSecret)) with 0x55 for the pad.
      3DESKey2 is the second 8 bytes of md5((16,pad)(n,dhSecret)) with 0x55 for the pad.
      3DESKey3 is the first 8 bytes of md5((16,pad)(n,dhSecret)) with 0xaa for the pad.

      MACKey is md5((16,pad)(n,dhSecret)) with 0x11 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x22 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x33 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x44 for the pad.

      The sendIV and receiveIV are calculated by md5((16,pad)(n,dhSecret)) with 0x99 for the pad. If the connection is an outgoing connection, the sendIV is the first 8 bytes and the receiveIV is the second 8 bytes. If the connection is an incoming connection, the sendIV is the second 8 bytes and the receiveIV is the first 8 bytes.

    TCP Message format

    (n,totalLength) (20,SHA1_MAC) (n,msgLength1) (msgLength1,message) ... (n,pad)

    The totalLength and msgLength fields are sent in compressed format. For values between 0 and 127 (27-1), the value is sent as one byte (with one high zero bit). For values between 128 and 16,383 (214-1), the value is sent as 2 bytes (with two high zero bits). For values between 16,384 and 2,097,151 (221-1), the value is sent as 3 bytes (with three high zero bits). Since the maximum size message is 1,048,576 (220), this encoding covers all the legal messages.

    The totalLength field is the length in bytes of the all the messages including their compressed length field. It does not include the 20 byte Message Authentication Code (MAC), the pad, or the length of the totalLength field.

    The MAC is calculated using SHA1 and the authentication key generated as part of key generation. The MAC is the result of: SHA1( (64,MACKey ) (n,msgLength1) (msgLength1,message) ... (64,MACKey ) ).

    After the TCP message is generated as above, it is encrypted using Triple DES EDE in Cypher Block Chaining mode. (See Applied Cryptography by Bruce Schneier for details.) The first Initialization Vector (IV) is calculated as part of key generation. The next TCP message uses an IV which is one higher than the previous one. The IV is considered to be an 8 byte unsigned integer in big endian format for this addition.

For encryption version == "3DES_SDH_M2"

    Note that this protocol is the same as "3DES_SDH_M", except that a the MAC is HMAC, the message number is sent separately, and the last block of the previous message is used as the CBC IV for the next message.

    Key generation

    This encryption version calculated 4 separate "keys". They are: a 24 byte 3DES key, a 64 byte MAC key, an 8 byte initial sendIV, and an 8 byte initial receiveIV. First a Diffie-Hellman secret (dhSecret) is calculated by taking the gx mod m value received from the other side and calculating BigInteger secret = (gx mod m)y mod m using the standard Java BigInteger class. Then byte[] dhSecret = secret.toByteArray();

    The individual keys are calculated from dhSecret using MD5 and a 16 byte pad consisting of a single byte repeated 16 times as follows:

      3DESKey1 is the first 8 bytes of md5((16,pad)(n,dhSecret)) with 0x55 for the pad.
      3DESKey2 is the second 8 bytes of md5((16,pad)(n,dhSecret)) with 0x55 for the pad.
      3DESKey3 is the first 8 bytes of md5((16,pad)(n,dhSecret)) with 0xaa for the pad.

      HMACKey is md5((16,pad)(n,dhSecret)) with 0x11 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x22 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x33 for the pad followed by md5((16,pad)(n,dhSecret)) with 0x44 for the pad.

      The initial sendIV and receiveIV are calculated by md5((16,pad)(n,dhSecret)) with 0x99 for the pad. If the connection is an outgoing connection, the initial sendIV is the first 8 bytes and the initial receiveIV is the second 8 bytes. If the connection is an incoming connection, the initial sendIV is the second 8 bytes and the initial receiveIV is the first 8 bytes.

    TCP Message format

    (n,totalLength) (20,SHA1_HMAC) (4,msgNumber) (n,msgLength1) (msgLength1,message) ... (n,pad)

    The totalLength and msgLength fields are sent in compressed format. For values between 0 and 127 (27-1), the value is sent as one byte (with one high zero bit). For values between 128 and 16,383 (214-1), the value is sent as 2 bytes (with two high zero bits). For values between 16,384 and 2,097,151 (221-1), the value is sent as 3 bytes (with three high zero bits). Since the maximum size message is 1,048,576 (220), this encoding covers all the legal messages.

    The totalLength field is the length in bytes of the all the messages including their compressed length field. It does not include the 20 byte Hash Message Authentication Code (HMAC), the msgNumber, the pad, or the length of the totalLength field.

    The HMAC is calculated using SHA1 and the authentication key generated as part of key generation. The HMAC is the result of: SHA1( ((64,MACKey) xor opad) SHA1( (64,MACKey xor ipad) (4,msgNumber) (n,msgLength1) (msgLength1,message) ... )). Where opad is the byte 0x36 repeated 64 times and ipad is the byte 0x5c repeated 64 times.

    The msgNumber field is zero for the first message and is incremented by one for each following message. The msgNumber is considered to be an 4 byte unsigned integer in big endian format for this addition. Note that the sequence number starts over at zero after a suspended connection is resumed.

    After the TCP message is generated as above, it is encrypted using Triple DES EDE in Cypher Block Chaining mode. (See Applied Cryptography by Bruce Schneier for details.) The first Initialization Vector (IV) is calculated as part of key generation. The next TCP message uses the last block of the previous message as an IV.

 
Unless stated otherwise, all text on this page which is either unattributed or by Mark S. Miller is hereby placed in the public domain.
ERights Home elib / distrib / vattp 
Back to: Data Pluribus Overview x On to: Testing Data-Pluribus
Download    FAQ    API    Mail Archive    Donate

report bug (including invalid html)

Golden Key Campaign Blue Ribbon Campaign