Great Scott Gadgets

open source tools for innovative people


Speeding up CRC calculations for Bluetooth Low Energy

Over the past few days Mike Ryan has been working hard to cram as much of the Bluetooth Low Energy (BTLE) functionality as possible in to the Ubertooth firmware. In doing so he plans to relieve the host system of the work involved in finding and processing packets. In time this will allow Ubertooth to monitor and inject packets in to BTLE connections while running from a very low powered host, or possibly without a host system at all.

This has involved some excellent work using the CC2400 chip to automatically detect BTLE packets, a task which it is unfortunately unable to achieve for basic rate Bluetooth. Once we know where a packet starts we are able to handle the packet data as a set of bytes rather than needing to break the data up in to bits before running through the whitening and CRC algorithms.

While Mike worked on the whitening algorithm, he set the CRC as an open challenge, which I gladly took up. I thought that it may make an interesting post to explain how CRC algorithms are implemented and show how to trade off time for memory, or time for space complexity for the computational theorists among us, by using a look up table (LUT). This may be common knowledge to many people and there are automated tools to achieve it, but I wanted to work it out by hand.

This part is, at least in part, for my own reference when I look at the code in a year’s time and ask “who did that? And how o we know it’s correct?”

Linear Feedback Shift Registers

Linear Feedback Sift Registers (LFSRs) are often used for CRC checks, forward error correction or to generate pseudo-random data. They are computationally cheap and simple to implement in hardware if required, so they are perfect for low cost networking chips. Bluetooth uses them to implement data whitening, header error checks, CRCs and forward error correction on packet data.

The LFSR that implements the CRC on BTLE packets looks something like this:

LFSR Light

The LFSR for CRC on BTLE packets as drawn by me. See Vol 6, part B, Section 3.2 of the Bluetooth specification for a better, but non-free version of the diagram. For simplicity we can imagine the LFSR as parts, a shift register and the feedback element, using XOR. Each incoming bit of packet data is XOR’d with the right-most bit of the register, for consistency we’ll assume that the bits are numbered 0-23 from left to right. Bit 23 is XOR’d with the incoming data bit and becomes next_bit. The register is shifted one bit to the right and next_bit is added to the end, becoming bit 0. This is a shift register.

Now for the feedback part, each of those arrows feeding in to the top of the register represents a bit in the register that will be XOR’d with next_bit. T\hat is all you need to know about LFSRs for most usese, in fact it should be trivial to implement one using the above information. Here’s our implementation of the above LFSR:

u32 btle_calc_crc(u32 crc_init, u8 *data, int len) {
    u32 state = crc_init;
    u32 lfsr_mask = 0x5a6000; // 010110100110000000000000
    int i, j;

   for (i = 0; i < len; ++i) {
        u8 cur = data[i];
        for (j = 0; j < 8; ++j) {
            int next_bit = (state ^ cur) & 1;
            cur >>= 1;
            state >>= 1;
            if (next_bit) {
                state |= 1 << 23;
                state ^= lfsr_mask;
            }
        }
    }

    return state;
}

Optimising the LFSR

As you can see, we run through the inner loop for each bit of data, although we only perform the XOR if we next_bit was set. This is a very small optimisation that makes use of the shift operation filling with 0s and the fact that XOR with 0 would have no effect. Logically this process looks a little like this:

CRC Light

The LFSR split in to a shift and a feedback, or XOR, component. The diagram above shows the two stage LFSR, with the second stage containing the different masks to be XOR’d with the register depending on the state of next_bit. This is a two value look up table holding 24 bits od XOR mask.

If we can shift then look up the XOR for one bit, why not more? As long as we shift by the appropriate amount, the XOR result only relies on the incoming data and the state of the register. Even better, there is no feedback in to the lowest byte of the register, so early bits in an incoming byte don’t affect the value of later bits.

Working with Bytes

Taking a byte of input data, we first XOR it with the lowest byte of the register to get next_byte, then we shift the register to the right by a byte and append next_byte. This takes care of the shift.

To finish off we need to apply the eight XOR masks based on the content of next_byte. As the register is shifted for each bit, the masks are XOR’d together with each successive mask shifted by one bit, this is shown in the diagram below.

Mask

The final mask is produced by XORing the mask for each bit of next_byte.

The derived mask is specific to the next_byte value of 01101101, so we are able to store it in a table and retrieve it for future use. If we do this for all 256 values of next_byte we can build a full look up table, and use it to calculate the CRC.

The following code implements the CRC using a LUT:

u32 crcgen_lut(u32 crc_init, char *payload, int len)
{
    u32 state = crc_init;
    int i;
    u8 key;
   
    for (i = 0; i < len; ++i) {
        key = payload[i] ^ (state & 0xff);
        state = (state >> 8) ^ crc_lut[key];
    }
    return state;
}

The LUT itself consists of 256 32bit values, so is too large to reproduce here, but it can be found on Github.

While it is possible to write code to that builds the LUT from shifted masks for each value of next_byte, it was easier to use the known good implementation of the CRC algorithm given earlier to provide the final state of the register for all one byte payloads and then XOR it with the pre-mask state, as shown below.

LUT

The XOR mask for each key is calculated and then stored in the LUT. After looking at the code, Michael Ossmann pointed out that leaving the key byte blank while building the LUT would yield the same result and avoid a pointless shift operation in the final algorithm. It seems that no matter how nerdy you try to be, someone will out-geek you.


Motivating the Problem

One of the most difficult aspects of talking to people about Bluetooth packet sniffing is what my university supervisor called “motivating the problem”. What he meant by this was trying to convince others that the problem which you were trying to solve was really as hard as you know it to be.

Sniffing Bluetooth is Hard

Over the past five years we have dedicated a lot of time to motivating the problem when we give presentations on Bluetooth security, often resulting in glazed looks from some audience members. This post is intended to go some way towards explaining the challenges facing our project and to encourage anyone interested to participate.

Bluetooth packet sniffing falls foul of the motivation problem because it is so often compared to other wireless protocols that appeared at around the same time, such as 802.11 and Zigbee, which had promiscuous packet sniffing solutions available, using commodity hardware, soon after their release.

Another reason that Bluetooth sniffing is hard to discuss is the set of terms that need to be defined before we can even begin to describe the problems involved. At a minimum, the following are useful to know before entering in to a discussion about Bluetooth packets:

Piconet - A personal area network with one master device connected to potentially many slave devices.

Master device - The device that defines a piconet, often but not always the “smartest” device, e.g. a PC or phone.

Slave device - The device being connected to the master, e.g. a keyboard, mouse or headset.

Bluetooth Device Address - A 48 bit unique device address, usually shown in the same format as IEEE 802 MAC addresses and issued from the same address space. It is common for smartphones to have consecutive Bluetooth device and wifi MAC addresses.

NAP - Non-significant Address Part. The first two bytes of the device address.

UAP - Upper Address Part. The third byte of the device address. Forms the organizationally unique identifier when combined with the NAP.

LAP - Lower Address Part. The lower three bytes of the device address, assigned by the manufacturer.

CLK27 - A 27 bit counter that increments 3200 times per second and wraps in slightly less than 24 hours. Every device maintains an internal clock value, although we are mostly concerned with the master device’s clock. Often referred to as “the clock”.

CLKN - The upper 26 bits of CLK27. This is a clock that ticks 1600 times per second, once per packet “slot”.

AFH Map - Adaptive Frequency Hopping allows Bluetooth connections to avoid using noisy channels, such as channels that overlap nearby wireless networks. The map specifies which channels are available for a given connection.

The feature of Bluetooth that makes packet sniffing so hard is frequency hopping. Originally designed to ensure robust connections, it causes more problems and confusion for packet sniffers than any other feature. The pseudo-random hopping sequence that all devices within a piconet share is determined by the LAP, UAP and CLKN of the master device. To have any chance of extracting useful data from a Bluetooth connection we need to know these three values.

The situation gets even worse for encrypted links. To have any chance of sniffing the pairing process, and using the extracted data to find the pin (see: http://www.eng.tau.ac.il/~yash/shaked-wool-mobisys05/index.html ), we must know these three values before the target devices begin to communicate.

One solution to this is to begin sniffing all traffic in a target piconet on the assumption that a new device will be paired with it in the future. In many ways it is good that this is not a practical attack vector, however it makes research and investigation in to Bluetooth authentication and encryption a harder task.

Devices that support Bluetooth v2.0+ also support adaptive frequency hopping (AFH), which adds an additional variable to the list that we have to find before we can monitor a connection.

The Ubertooth tools passively monitor each channel in turn to find piconets and build up information on the LAP, UAP, CLKN and AFH map, this behaviour can be seen in the Kismet plugin. Ubertooth-follow is the one exception to this method as it uses a Bluetooth dongle to acquire the values that the Ubertooth needs to follow a hopping pattern.

Hopefully this has provided a crash course in Bluetooth packet sniffing for anyone who wants to get involved or try out the Ubertooth tools. We’re working hard to improve the amount of data that we are able to collect as well as adding features such as packet injection, Bluetooth Low Energy support, integration with external tools such as Wireshark and Kismet and support for more low cost embedded platforms such as ARM (raspberryPi, BeagleBone) and Android.


So You Want to Track People with Ubertooth ...

I am contacted frequently by people who want to use Ubertooth One to track the movements of vehicles or pedestrians on highways, at airports, in shopping malls, etc. This is a FAQ.

Q: Can Ubertooth One be used to monitor movements of people carrying Bluetooth devices?

A: Yes. With multiple Ubertooth Ones covering different locations, you can determine the time that a particular target device is present at each location. This could allow you to compute average travel times on highways, wait times in queues, etc.

Q: We currently track Bluetooth devices by using standard Bluetooth adapters performing frequent inquiries. This only detects discoverable devices. Ubertooth One could be used to track non-discoverable devices, right?

A: Yes. However, Ubertooth One only detects devices when they are actively transmitting. An idle target device, discoverable or not, will not be detected by Ubertooth One in passive monitoring mode. Inquiry detects discoverable devices whether or not they were active before inquiry; passive monitoring detects active devices whether or not they are discoverable.

Q: So an optimal solution to identify the largest number of devices would incorporate both inquiry and passive monitoring?

A: To identify the most devices possible, you should use both inquiry and passive monitoring. Additionally you could perform paging or partial paging. Paging is the process used when a Bluetooth device connects to another. Once you have identified a non-discoverable Bluetooth device address with passive monitoring, you can page for that address. This determines whether or not the target device is present even if the device has become inactive.

Q: How is partial paging different than normal paging?

A: The normal paging procedure involves several packets transmitted back and forth between the master (the paging device) and the slave (the paged device). The first packet is transmitted by the master and contains the slave’s address. The second packet is transmitted by the slave in response to the master. It is possible for the master to stop the paging procedure at this point before fully opening the connection. The first slave response packet is sufficient to determine the slave’s presence. (This is analogous to a TCP SYN scan.) This partial paging procedure would be faster than a complete paging procedure. I don’t know of any implementations, but Ubertooth One would be a good platform for developing such a thing.

Q: Could partial paging be used to conduct a brute force search for all possible LAPs (Bluetooth Device Address Lower Address Parts)?

A: Yes, but it would take a while. Even with some optimizations, I estimate that an exhaustive brute force LAP search by partial paging with a single Ubertooth One would take on the order of 100 hours. This is considerably faster than previous implementations but is probably too slow to be useful for tracking applications.

Q: Could packets transmitted by paging or partial paging be misinterpreted by a nearby passive monitor, indicating presence of a device that is not there?

A: Yes. If you implement both paging and passive monitoring, you must take care to ignore the packets transmitted by your own system.

Q: We’re tracking Bluetooth devices anonymously.

A: No, you’re not.

Q: No, really! We are! Aren’t we?

A: Unless your system has been designed carefully for anonymity and has been audited thoroughly for anonymity by an information security professional, it is highly unlikely that you are tracking people anonymously. If you store BD_ADDRs (Bluetooth Device Addresses) of target devices, you are storing individually identifiable information about the owners of those devices. The same is true if you store hashes of BD_ADDRs or encrypted BD_ADDRs unless great care has been taken to irrevocably destroy encryption keys. If you delete stored data without an audited secure erasure procedure, you should assume the data are easily recoverable. Most importantly, if you tell people that their information is being anonymized without properly anonymizing it, you are a bad person.

Q: Are you interested in building a tracking system for us?

A: I am interested, from an academic standpoint, in tracking the movements of Bluetooth devices, and I believe that people have a right to know how they can be tracked by transmissions from wireless communication devices they carry. I would be willing to develop special purpose hardware and software for such applications so long as I am permitted to publish everything I produce under an open source license.

Q: We would like to pay you to develop a proprietary tracking system and grant us exclusive distribution. Will you do it?

A: I develop only open source hardware and software.


Discovering Bluetooth Devices

In July 2011 Michael Ossmann wrote a blog post entitled “Discoverability is Not a Mitigating Factor” which discussed the Bluetooth security advice being given about discoverable devices by people and organisations that should know better. It is worth reading his post in full, but I’ll quote two important parts here:

“LAP sniffing is easy. Spill and Bittau showed how to sniff LAPs with a USRP for about $1000. Now it can be done with an Ubertooth One for about a tenth of that price. It can even be done using Travis Goodspeed’s method for promiscuous sniffing with lower cost platforms.”

“The UAP is only slightly more difficult for an attacker to learn. Project Ubertooth and gr-bluetooth include software that implements automatic UAP determination based on passive observation of just a few packets.”

I completely agree with Michael on this, the methods for retrieving the LAP and UAP are easy and well known, but we still hear advice suggesting that turning off the discoverable setting for your device will protect it from being found by malicious attackers. So, taking in to account Wright’s law:

“Security will not get better until tools for practical exploration of the attack surface are made available.” -Josh Wright

I wrote a tool that would initiate a standard Bluetooth device scan, but also add devices discovered with the Ubertooth. I call the tool “ubertooth-scan” and it’s available from the master branch of the Ubertooth git repository.

Ubertooth-scan requires an Ubertooth and a standard Bluetooth device on a host with libbluetooth (bluez) installed. First we use the Bluetooth device to perform an HCI scan, this is the same as running “hcitool scan” from the command line. The second part of the tool uses the Ubertooth to promiscuously sniff for Bluetooth packets, retrieving the LAP and UAP values before handing them over to libbluetooth to query the device name. Most non-discoverable devices respond to name inquiries.

ubertooth-scan

I’ve also added an extended query (triggered by the -x option) which will check the device for supported features, chipset version and clock offset from the local device.

Using a dongle to get the clock offset for a remote device allows us to calculate the clock value of the target and use that to hop along with the piconet, dumping packet data to screen as we go. Here’s a quick snippet of the code in action, apologies for the low quality video:

Note from 2022: The video that was in this post is no longer available.

I’ll be presenting this in more detail, along with other recent developments in the Ubertooth project, at Ruxcon this weekend. If you are in Melbourne or are already planning to attend Ruxcon, and would like more detail, please come to my presentation at 2pm on Sunday in track 1.


Ubertooth and libbtbb Release 2012-10-R1

The latest release of the Ubertooth software is now available. The 2012-10-R1 release contains numerous bug fixes and minor improvements as well as some large architectural changes.

The host code for both Ubertooth and libbtbb is now easier to compile, with major simplifications to the process for the btbb Wireshark plugin. Build instructions can be found on the Ubertooth website.

As development has shifted from a subversion repository to a git repository, we no longer have sequential revision numbers to use for release naming. All future releases will be named using the year and month of release.

When using the latest release it is necessary to update the firmware on your Ubertooth. Binary firmware images can be found in the release package, and flashed to the Ubertooth using the ubertooth-dfu tool (ubertooth-dfu –write <image-filename.dfu> –detach). The host code needs to be built and installed before updating firmware images. Alternatively firmware images can be built using the ARM embedded variant of gcc.

The release notes for the ubertooth 2012-10-R1 release are as follows:

Release Notes

The Ubertooth host utilities in this release require libbtbb-2012-10-R1 or greater, it can be found at https://sourceforge.net/projects/libbtbb/files/.

These are just the highlights. For a complete list of changes since the previous release, see the git log.

  • libubertooth

The core Ubertooth functions are now packaged as a library, which allows us to have some independence between the core ubertooth functions and the tools that use them, such as ubertooth-* and the kismet plugin. This should also help with future binary packaging.

  • Firmware flashing

The ubertooth-dfu tool now attenpts to identify Ubertooth devices and put them in to firmware upgrade mode. Multiple arguments can also be passed to ubertooth-dfu and will be executed in the order specified ont he commandline. To flash firmware on to an ubertooth device, use the following command: ubertooth-dfu –write <firmware_image.dfu> –detach

  • Bluetooth Low Energy (Experimental)

Bluetooth Low Energy (Bluetooth Smart) sniffing is experimentally supported by the bertooth-btle tool. The tool can be used to sniff the connection setup procedure between devices; promiscuous sniffing is available but is extremely experimental. Credit for this achievement goes to Mike Ryan.

  • Ubertooth-follow

Ubertooth-follow has been added to the set of Ubertooth commandline tools. It retrieves the clock value from a local device using libbluetooth (bluez) and uses the Ubertooth to hop in time with the piconet. To build ubertooth-follow use “make clock_debug=true”.

  • Git

Since the last release we have moved the source repository from SVN to Git. This should not affect the released code, but makes life easier for those of us working on the code.


subscribe to GSG feed