LBP, or Logi-Box-Protocol, describes communication for a set of devices which are geographically spread with one central point of information like a GIS system, i.e. for monitoring and logging purposes in tracking and tracing in logistics.
It is designed to be as lean as possible, because such communication often uses very expensive networks (GSM, UMTS, Satellite Phones, etc.) or very low bandwidth, and many devices are sending information at the same time.
Such communication has to be secure, because the information transported (geographical position) is confidential. So LBP includes rules to apply cryptography.
• LBP is transported as binary code via datagrams, binary stream or ASCII text. The transporting connection has to be bi-directional.
• LBP is a stateful protocol. It is asynchronous, but not completely connectionless. LBP matches the client-server pattern.
• LBP is an encrypted protocol. The encryption algorithms used are Twofish and SHA1.
If datagrams are used, the binary code is transported as payload. Every LBP message must be coded into one single datagram. The problem of fragmentation of datagrams has to be solved in network layers below LBP.
If binary stream is used (i.e. binary terminal or TCP socket), the code 0xff is the message separator, 0x1b is the escape. To send ff, send 1b ff instead. To send 1b, send 1b 1b instead. Using binary stream, every message has to be terminated by the message separator.
If ASCII text is used for this purpose (i.e. SMS or text terminal), the binary code is uuencoded. The filenames `L' or `LBP' must be used. The binary code to be uuencoded is coded exactly as for binary stream.
For limited text message protocols like SMS, text can mean concatenating text messages. Also more than one LBP message can be encoded into one single text message. Uuencode comprises a big overhead, but the message size of LBP messages is calculated to fit every uuencoded message into one single SMS, so an implementation of LBP may or may not support overlapping and distributed LBP messages in different text messages.
If UDP is used to transport datagrams with LBP, the server should use port 423. Since LBP messages are very lean, it is very unlikely that an LBP message is larger than the MTU on the way; however, it is more beautiful to confirm this using MTU discovering (but that costs in expensive networks!). Different clients with the same IP address must use different ports.
It is possible to mix all transport possibilities, even for one single LBP connection the transport may consist of a system of transports (it does not need to though, i.e. using one single transport like SMS is enough).
If a system of transports is used, a system of transport addresses is needed, so that each BOX has a unique address on each transport.
The states an LBP connection can have are:
|
• UNREGISTERED • REQUESTED • REGISTERED |
However, for LBP is an asynchrony protocol, client and server detect those states independently, and may be out of sync.
LBP is a client-server based protocol. The client is called BOX and the server is called SERVER.
In a SET there are up to 2^32-1 BOXes and one SERVER. Every BOX that exists has one connection to the SERVER, which can have the states of 1.3.
BOXes are identified by their BOXID. The BOXID is a 32bit unsigned integer, which is not zero, represented by four octets, building the integer by coding big endian. BOXIDs must be unique in a SET of BOXES communicating with the same SERVER.
Usually, LBP connections are identified by IDs of the underlying transports.
Using datagram oriented network protocols, the ID for a client connection endpoint of those protocols is used to identify an LBP connection. If not available, the transport ID for a client is used to identify an LBP connection, for there is only one connection per client needed for an LBP SET.
I.e., using UDP over IP, the pair IP address and sender port are used to identify an LBP connection, for that identifies a client connection endpoint.
Using connections without datagram based network protocols over a telephony network, the network number of the client (say: it’s phone number) is used to identify an LBP connection.
I.e., using SMS, connections are identified by the phone number of the sender.
Using LBP over other transports, if there is a method to have a unique ID for an LBP connection by using or combining IDs of the transport, this is used.
Only if an LBP message is sent over a transport, which does not support identifying connections nor senders, an optional CONNECTIONID is supported.
The CONNECTIONID only is implemented if there are such transports in an LBP implementation, otherwise it must be omitted.
If a CONNECTIONID is needed, the CONNECTIONID is the first four octets of the SHA1 hash of the BOXID. Because CONNECTIONIDs have to be unique for all BOXes, there may be no collisions in CONNECTIONIDs; if there are collisions with two different BOXIDs in the first four octets of their SHA1 hashes, the higher BOXID is illegal.
CONNECTIONIDs are there, because BOXIDs may include a system for sorting or grouping BOXes, so CONNECTIONIDs are required as pseudonyms without such a system.
The encryption is done using Twofish in OFB mode.
Every BOX has it’s own 32k (pseudo) random data. The SERVER knows all (pseudo) random data the BOXes store.
Random data is used only once. If random data is exhausted, negotiating a new Twofish key negotiates new pseudo random data between BOX and SERVER by encrypting the old (pseudo) random data with this key.
The result is the new (pseudo) random data, which is then used until it is exhausted. Then again a new Twofish key is negotiated and so on.
The quality of that random data is of course very important for security purposes. But one should mention, that when the random data is exhausted, then only pseudo random data is generated, using Twofish.
So perhaps, if the 32k block of random data is used for more than one BOX, it must be crypted with Twofish initially, using different Twofish keys for each BOX. That will not decrease overall security.
A fixed size of data beginning at the first octet of the (pseudo) random data is reserved for encrypting the initializing handshake. See 2.1.1 REGISTER and 2.1.2 REQUESTHEARD. Therefore, the first sizeof(REGISTER) + 57 (the size of the fixed part of REQUESTHEARD) octets of the 32k (pseudo) random data are only used for encrypting those both messages.
In the unregistered state of communication the BOX may initialize communication. Therefore is the command:
As a parameter, the BOX sends its BOXID and the TRADDRESSLIST. At last it sends the first five octets of the SHA1 hash of the whole data before in this message.
TRADDRESSLIST is transport specific binary data. It can be used by the underlying transport implementation to assign one BOXID to one single address, if there is only one transport, or to a set of addresses, if there is a system of underlying transports. TRADDRESSLIST has fixed size for any transport implementation.
The BOX does not send that data unencrypted; instead of that, all params it XORs with the octets of the random data beginning at the first octet of the random data. The message number octet, 0x2a, is sent plain.
After a timeout of 15 sec. without receiving a REQUESTHEARD message from the SERVER, the BOX repeats sending the REGISTER. After a timeout of 30 sec., the BOX repeats sending the REGISTER. The timeout from now on doubles every unsuccessful REGISTER, until it is longer than one day. Than it stays at 65535 sec.
If the SERVER receives a REGISTER message, the SERVER answers by sending REQUESTHEARD (0x17).
As parameters it sends BOXID and KEY optionally followed by newly encryptet CARRIERINFO. At last it sends the SHA1 hash of the whole data before in this message.
KEY is a 256bit Twofish key that was never used in another communication. If such key management is not wanted in the SERVER’s implementation, also the SERVER can send a KEY, which was very likely never used in another communication.
KEY must consist of random data; if pseudo random data is used, KEYs used for different BOXes must not depend on each other.
CARRIERINFO is user defined ASN.1/BER or ASN.1/PER encoded data.
The SERVER does not send this data unencrypted; instead, it crypts as following:
It crypts CARRIERINFO with new (pseudo) random data, which it creates with the new KEY out of old random data. The SHA1 hash is created summing BOXID, KEY, and the newly encrypted CARRIERINFO. Then it crypts BOXID, KEY and the SHA1 hash using XOR with the old random data. It does not crypt the already encrypted CARRIERINFO with the old random data again.
The server does not send different Twofish keys to one BOX in UNREGISTERED state. Instead of that, it repeats the same REQUESTHEARD again and again if requested to send REQUESTHEARD as an answer to a REGISTER message.
To determine if a REQUESTHEARD contains a CARRIERINFO param, use the message length. If it is 57, there is no CARRIERINFO. If it is > 57, there must be CARRIERINFO.
After the SERVER sends REQUESTHEARD, it changes state to REQUESTED for the connection. The SERVER creates new random data by using the new Twofish key; it does hold the old random data, though.
If a BOX receives REQUESTHEARD, it changes the state of the connection to REGISTERED. It then encrypts the random data with the received Twofish key. For furthermore communication, the BOX uses that new pseudo random data. The BOX never uses the old random data again. The BOX then immediately starts to send POSINFO messages, sending the first POSINFO immediately after receiving REQUESTHEARD.
In REQUESTED state the SERVER accepts REGISTER messages (see 2.1.1) from the BOX, which use the old random data for encryption as well as the new random data.
Receiving a POSINFO (see 2.3.1) from the BOX encrypted using the new random data the SERVER changes state to REGISTERED. It from now on never uses the old random data again.
In REGISTERED State the BOX sends POSINFO messages.
A POSINFO has as parameters a 16bit OFFSET into the random data. If a CONNECTIONID is needed for the transport, then the CONNECTIONID follows here. Then a GEOPOINT struct is sent. It can optionally be extended by BOXINFO. After that, the first five octets of the SHA1 hash of the parameters (from OFFSET to GEOPOINT, or to BOXINFO if there is one) are sent.
A GEOPOINT struct is the geographical length encoded as an 32bit big endian signed integer, representing the mantissa of a fixed point number with an offset of 1,000,000, followed by an 32bit big endian signed integer for the geographical width, encoded exactly as the length is. The sign for the geographical length is positive for eastern coordinates and negative for western coordinates. The sign for the geographical width is positive for the northern hemisphere and negative for the southern hemisphere.
That means, divide the number of the length by 1,000,000 and you’ll have the real geographical length, and do so also for the width.
BOXINFO is user defined ASN.1/BER or ASN.1/PER encoded data.
To determine if a REQUESTHEARD contains a BOXINFO param, use the message length. If it is 16 (or 20 if a CONNECTIONID is used), there is no BOXINFO. If it is > 16 (or > 20 if a CONNECTIONID is used), there must be BOXINFO.
The parameter data (not including the leading message number 0xaa, and not including the OFFSET, and if there is a CONNECTIONID, not including the connection ID) is not send plain, but is XORed with the random data beginning at OFFSET.
A BOX must use different offsets for random data each message, except multiple REGISTER messages (see 2.1.1). It must increment the offsets by the message length each time it uses random data.
If the SERVER receives a valid REGISTER message for a BOX in REGISTERED state, it changes state for that connection to UNREGISTERED and proceeds as in 2.1.1.
If a BOX runs out of random data, it changes state to UNREGISTERED. It then immediately sends a REGISTER message as in 2.1.1.
If a BOX changes its address for one or more transports, it changes state to UNREGISTERED. It then immediately sends a REGISTER message as in 2.1.1.
Volker Birk, vb@x-pie.de , Wettgasse 7, 88339 Bad Waldsee, Germany. Phone +49 (7524) 996806 Fax +49 (7524) 996807
Please send comments to the author.
As Bruce Schneier does a very good job an algorithm of him is preferred.
The cryptography of LBP was discussed in de.comp.security.misc first; see the thread starting at <bpofdh$m9v$07$1@news.t-online.com>.
I wish to thank the people of de.comp.security.misc for their help in discussing the cryptography of this protocol: Andreas Beck, Bernd Eckenfels, Bjoern Wunschik, Bodo Eggert, Carsten Krueger, Christian Forler, Christoph Bartoschek, Florian Weimer, Harald Laabs, Jakob Creutzig, Jens Grivolla, Klaus Pommerening, Lutz Donnerhacke, Markus Brueckner, Markus Schaaf, Michail Bachmann, Ralf Muschall, Rene Moehring, Sebastian Posner, Thomas Unger, Urs Traenkner.