Subject: [multipathtcp] Feedback on sha1/key exchange for MPTCP inter-op with FreeBSD

From: Nigel Williams <[email-masked]>
Date: Tue, 16 Oct 2012 15:14:07 +1100

Dear Christoph,

I'm currently doing some interop testing between the Linux MPTCP 
implementation (built from the git repository as of October 10) and the 
FreeBSD implementation that I am working on. I have some 
questions/comments. I've cc'd the mailing list as some of this might be 
of interest to others. Please let me know if I've missed something obvious!

(1) Endianess and the sha1 hashing of local and remote keys: I initially 
had some trouble matching keys and idsns with the Linux implementation. 
Having a look through the linux code (function mptcp_key_sha1(local_key) 
in mptcp_ctrl.c) it looks like the output of sha_transform is converted 
into big-endian, and the token and idsn are then assigned (as big-endian).

Once the mptcp_key_sha1() function returns, 'idsn = ntohll(idsn) + 1;' 
is called (returning the idsn to host order). The idsn is then typcast 
as a u32 and this value is used for tcb->seq (which is the starting dseq 
value of DSN mappings). All this was calculated from 'local_key', which 
is stored locally in host order.

The problem arises then that the local_key is put onto the wire in host 
byte order, when we were expecting to receive it in network byte order. 
Is there a reason why the key is not transmitted in network byte order?

Also, is it possible to do the conversion to host order of the idsn and 
token within mptcp_key_sha1(), rather than on return? A quick glance at 
the function does not make it immediately obvious that the values should 
be converted into host order on return. Some comments in this function 
would be useful (for instance the FreeBSD sha1 returns the hash in 
network order, while Linux does not).

(2) Perhaps as a general comment/feedback, it might be worth detailing a 
little more explicitly in the implementers guide the conversions 
occurring in this process, as it is currently a little ambiguous and I 
needed to dig through the linux code in order to make my implementation 
compatible on the wire.

As far as I can tell, the process should be along the lines of:

1. generate 64-bit key (store in host order)
2. sha1 hash of key (byte order is implementation specific)
3. choose the most significant 4 bytes for the token, and least 
significant 8 bytes, taking into account the byte order of the sha output.
4. store token and idsn locally in host order.
5. get the lower portion of the idsn with an unsigned 32-bit typecast
6. when transmitting the local_key/remote_key, do so in network order. 
(currently Linux transmits in host order?)

As we need to be sure that different implementations are exchanging keys 
correctly during the handshake, it would be nice to have this 
information documented, making the endianess of things clear for 
implementers. It would also be helpful in the future to add some more 
comments to the Linux code, as it isn't always clear as why things are 
being done a certain way.

regards,
nigel

---

From: Christoph Paasch <[email-masked]>
Date: Tue, 16 Oct 2012 08:32:16 +0200

Hello Nigel,

> Is there a reason why the key is not transmitted in network byte order?

the key is not stored in host-byte order. When generating the random bits we 
simply store them in a u64 and send them on the wire. Thus, the keys are in 
network byte-order.

The endianness conversion in mptcp_key_sha1 is part of the SHA-1 algorithm. 
SHA-1 does an endianness conversion on the input (done by sha_transform in 
lib/sha1.c).
When returning the final output another conversion is done in sha1_final 
(crypto/sha1_generic.c), part of the generic crypto-library of the linux 
kernel.

However, in MPTCP we don't use the crypto-library (thus, don't call 
sha1_final) because we want to spare some CPU cycles. So, we have to do the 
endianness conversion at the end of mptcp_key_sha1 by hand.

>From what I see in 
http://www.leidinger.net/FreeBSD/dox/crypto/html/d2/d24/sha1_8c_source.html

the sha-1 algorithm in FreeBSD is also endianness-agnostic. Meaning, if you 
call sha1_result at the end, he will also do an endianness conversion so that 
your output matches the endianness of the input.

> needed to dig through the linux code in order to make my implementation

I will try to add more comments in the implementation.

> 1. generate 64-bit key (store in host order)

In a certain sense, the endianness of the key doesn't matter. Because, no 
arithmetic operations are done on the key.
The key is just a sequence of bits, and this sequence of bits should be sent 
that way on the wire and applied to the hashing algorithm. And it is the 
hashing algorithm that handles the endianness in order to produce the same 
results on big-endian and little-endian machines. (as SHA-1 is doing)

> being done a certain way.

There have been done tests with the Linux Kernel implementation on a big-
endian client and a little-endian server. And it was working after we fixed 
one bug.

I believe the endianness is now correctly handled in Linux.

Cheers,
Christoph

-- 
IP Networking Lab --- http://inl.info.ucl.ac.be
MultiPath TCP in the Linux Kernel --- http://mptcp.info.ucl.ac.be
Université Catholique de Louvain
--

---

From: Nigel Williams <[email-masked]>
Date: Tue, 16 Oct 2012 19:44:06 +1100

Hi Christoph,

Thanks for the response, it's clear where the misunderstanding is now.

> endianness conversion at the end of mptcp_key_sha1 by hand.

What caused the confusion is that the Linux key is considered to be in 
network order after it is generated. I don't recall the draft specifying 
what order the key is to be in when hashed, and it is apparent that it 
should.

I would argue in favour of hashing in host order for semantic reasons:
- It seems non-standard behaviour to not perform a network-to-host byte 
order conversion on arriving options.
- Maintains consistency with other stack variables which are kept in 
host byte order for simplicity of arithmetic (or other things)

> your output matches the endianness of the input.

Okay. Misunderstood what the Linux code was doing (we thought the 
FreeBSD code was doing something different to Linux, and this is not the 
case).

> arithmetic operations are done on the key.

As the endianness of the key will change the hash output, it does matter.

cheers,
nigel

---

From: Christoph Paasch <[email-masked]>
Date: Tue, 16 Oct 2012 11:01:02 +0200

> what order the key is to be in when hashed, and it is apparent that it 

You should not look at the key as a 64-bit integer. It is rather a sequence of 
8 bytes. When hashing, the key has to be in the same order as it was seen on 
the wire. SHA-1 algorithm makes sure that the hash produces as a result the 
same bit-sequence on little-endian and big-endian machines.

If we would convert the key to host-byte-order, the bit-sequence input to the 
sha-1 algorithm will be different on little-endian and big-endian machines. 
Thus SHA-1 won't produce the same result anymore.

> host byte order for simplicity of arithmetic (or other things)

Actually they are only stored in host-byte order if arithmetic operations are 
performed on them.

TCP-MD5-options are not converted. For the same reason why the MPTCP-key is 
not converted, because we are working on a sequence of bits/bytes.
Same for TCP Cookie extensions.

Christoph