narrowing the hop search

Dominic Spill has been kind enough to correspond with me about my recent work on reversing the Bluetooth hopping sequence. He pointed out some interesting ideas he had proposed last May. One essential idea I had overlooked is that 6 bits of clock can be recovered along with the partial address from (almost) any frame. These clock bits can be used to narrow the search space of possible clock values.

In my original analysis, I looked at the hopping algorithm and assumed that an observer is somehow able to accurately measure the intervals between frames captured on one or more channels. I also assumed that the observer has partial knowledge of the master's address, but I did not consider partial knowledge of the master's clock.

How can the observer measure intervals between frames? The method Dominic proposed (and I overlooked) is to decode the 6 bits of the master's clock from each frame. Differences from one frame to the next reveal information about the interval between frames. Unfortunately, the six bits of clock only describe 64 different time slot intervals, yet there is an average of 79 slots between two frames on a single channel. When observing a single channel, a difference of 47 might indicate an interval of 47 slots, but it could also represent an interval of 111 slots (47 + 64). A more direct approach would be to count the number of samples between observed frames. Perhaps the best method would be to combine direct measurement with confirmation by decoded clock values.

No matter how the intervals are determined, the 6 decoded clock bits can be used to narrow the search space. My first simulations included a search through 134217728 possible clock values. Taking advantage of the 6 known clock bits, it is possible to reduce the search space to 2097152 possible values. I ran a new set of simulations to find out how much this helps.

In order to have 95% chance of a unique match, we could observe all 79 channels for 3/8 of a second (30 channel seconds processed). Alternatively, we could observe a single channel for 3/5 of a second (3/5 channel seconds processed).

When narrowing the search space by the 6 known clock bits, the observation time required when observing all 79 channels changes very little, but the time required when observing a single channel changes considerably. This result strengthens support of my conclusion that the most efficient method to reverse the hopping sequence is to monitor a single channel.