Revision as of 13:28, 24 October 2013

Timing Based Key Agreement Protocol

Introduction

A paper from Maurer & Gander , ‘On the Secret-Key Rate of Binary Variables’, which expanded on Claude Shannon’s work revealed to us when the encryption operators used by Bob and Alice are independent – the secrecy rate is zero. A new approach was take in the project - as the previous method of attempting to do two independent rotations would clearly not work. This new method was using the round trip times between the sender and recipient as the way to generate a key. The round trip times are generated as shown in the image below.

Once the round trip times are generated, they are turned into a bit stream by using the formula shown.

Due to the fact that the internet is not a perfect communication channel, the round trip times observed by the sender and recipient are going to be different - hence the bit streams generated are going to be different. Therefore, as of yet we cannot use these as a secure key. If we consider the situation from an eavesdropper, say Eve's, perspective, we notice that while Alice and Bob are able to communicate and directly generate their respective round trip times, Eve is only able to estimate the round trip times. Due to the randomness of the internet, and any further timing delays which occur when the packets actually reach the sender/recipient, Eve will never have the same quality of information as the Alice and Bob.

The next step is to reconcile Bob and Alice's bit streams - but do this in such a way that we further extend our advantage over Eve. This is done through a process called advantage distillation, and our chosen advantage distillation protocol was called the bit pair iteration protocol. During this process, Alice and Bob directly communicate with each other, and through parity checks determine which bits are correct or incorrect. Consider Eve, if is in the channel eavesdropping as shown in the diagram above, when the bit pair iteration protocol takes place, she is able to eavesdrop on which packets are deemed as being incorrect by Alice and Bob. However, even though these packets are incorrect for Alice and Bob, if we recall the fact that due to the randomness that all of the bit streams will be different, there is no guarantee that they are incorrect for her. This can result in her keeping incorrect bits, and discarding correct bits. Therefore, in theory, Eve's bit error rate should not drop as quickly as Bob and Alice's bit error rate. An example is shown below.

Imagine the three bit streams below are obtained:
Alice: 11001001
Bob:   01101001
Eve:   10000111
Say Alice and Bob perform Bit Parity Checks - we notice that the first and second bit pairs will be thrown out due to the parity check failing
Now if we imagine Eve is listening to these Bit Parity Checks - she would respond by throwing out the first and second bit pairs.
However, in Eve's case - the first and second bit pairs would have been consistent.

Alice Reconciled Bit Stream: 10
Bob Reconciled Bit Stream:   10
Eve Reconciled Bit Stream:   01

In this case, the bit error rate between Bob and Alice is 0 %
Meanwhile, the bit error rate between Eve and Alice is  100 %

Program

A python program was created. This program had two operating modes - client and server (equivalent to Alice and Bob) - and automated the whole process described previously. That is, the program records the round trip times, generates the bit streams, and performs the reconciliation process. An example of the programs output is shown below.

This program, in conjunction with several python scripts, available here and here were used to conduct the testing. The testing process and results are described below.

Testing

The verify the theoretical claims made above, there needed to be several tests done. The main tests done, and the rationale behind the tests is listed below.

Eavesdropping

The protocol which was created aims to provide us with a means of secure communications. That is, two parties A and B must be able to communicate over a channel and if there is an eavesdropper in this channel, he is not able to recover the same key that A and B do. A series of tests were done, which involved changing the physical position of the eavesdropper, as well as other small tests such as changing the number of iterations, and even the precision of the recorded round-trip times.

Alice, Bob, Eve all on separate networks

The first course of testing was done where Alice, Bob and Eve were all on separate networks. This was the simplest test to conduct, as well as the simplest situation in theory. If we examine the situation, we realise that the variation in the round trip times observed by Alice, Bob and Eve is going to be reasonably high. This is due to the fact that every leg of the trip is done over an imperfect, noisy communication channel. The variation in the round trip times means that the protocol operates under the best circumstances. Consider a scenario, the worst case scenario, where there is no variation or noise in the channel, this would mean that the round trip times observed by all three parties would be the same, and the protocol would not function. This is the opposite of that scenario. The results are shown below.

The test results can be found on Timing Based Encryption: Test Case 1

Alice, Bob, Eve all on the same network

The second course of testing was a situation where Alice, Bob and Eve were all on the same LAN network. While this case may seem like it is the polar opposite of test case 1, it is rather similar. If we consider the situation in a little more detail, we realise that it is merely a scaled example of test case 1. That is, where in test case 1, where the protocol works to maximum efficiency because the noise in the channel is large, the protocol should work at high efficiency in this situation as well because although the noise is low, the round trip times are extremely low (<1ms) so that the variation in the round trip times appears to be just as large as in the external network case, if not bigger.

The test results can be found on Timing Based Encryption: Test Case 2

Eve on the same network as either Alice and Bob

This test was the ultimate test of the protocols efficiency. Considering this situation, if Eve is on the same LAN network as either Bob or Alice, the difference in the round trip times observed by Eve and either Bob/Alice is going to be extremely minimal (<1ms). This means of all the test cases we run, this is the case in theory where eavesdropping the bit parity checks will be most useful for Eve.

The test results can be found on Timing Based Encryption: Test Case 3

Program Output

In addition to running tests which confirmed the security of the protocol from an eavesdropper, the output of the program also needed to be tested. That is, having a protocol which is secure from an eavesdropper is excellent, however we need to confirm that the protocol can actually generate something of use from Alice and Bob. The testing was divided up into two cases, both consisting of sub cases. Each is described below.

Program Output: Alice and Bob on same network

The first and simplest test which was to be run was running the physical layer security program on two computers which were on the same LAN network. In theory, the very small round trip times provides us with fast operation, and the lack of noise should also provide us with accurate results.

The test results can be found on Timing Based Encryption: Test Case 4

Program Output: Alice and Bob on different networks

The more conclusive test for the program output was a situation where the two parties were on separate networks. The noise of the communication channel as well as some of the randomness produced could provide us with slightly less accurate results. Combine this with other small errors which are bound to occur such as packet loss/timeouts/duplicate packets, the results which we recover here could be less convincing than the LAN network results.

The test results can be found on Timing Based Encryption: Test Case 5

Summary of Results

The main conclusion which we can reach from the test results is simply: the protocol works. However, we did learn some things about the protocol when conducting our testing

• The protocol is most effective when there is some additional noise and variety present in the communication channel - such as the internet connections of the sender and recipient being heavily used
  • It appears to be equally effective whether it be over LAN, or the internet. Maybe slightly more effective over LAN
• The effectiveness of the protocol does not seem to be effected by the number of round trip times gathered
  • Obviously, we want this number to be high enough for the eavesdropper to have a significant amount of errors though - atleast over 2500
• The protocol is least effective when the eavesdropper is on the same network as either the sender or the recipient
  • This is due to what we previously noted, that due to the relatively tiny time it takes for the eavesdropper to forward to the sender or recipient over the LAN, the round trip times which he and they observe will be almost identical.
  • In this case, the results we received were rather random - however the protocol functioned correctly all of the time, but with varied effectiveness
• A sender and recipient can securely generate a key using the timing based key generation protocol

Back to Main Page

Secure_communications_without_key_exchange?_2013