ALICE: I would learn to fly an airplane so I could discover new mountain ranges. What about you?
PAUL: Some might say that is what I do. My friends might add that they pay for the fuel. But really, I just try to keep the SF’s score low. How can we create mnemonics that are not vulnerable to your attack?
ALICE: Well, I guess the first thing to do is create a keypad layout that uses zero and one.
PAUL: Yes, but my academic sibling Pólya would say that we first need to understand the problem. Ideally, we want a keypad layout that produces an injective mapping from the six-letter English words into the natural numbers from zero to one million.
ALICE: Injective?
PAUL: Such that no two words produce the same code number.
ALICE: Is that even possible?
PAUL: I do not know. I believe this is an instance of the multiple subset sum problem, related to the knapsack problem.
ALICE: Ah yeah, I remember that from my algorithms class. It’s NP-Complete, right?
PAUL: Yes, and likely intractable for problems even as small as this one. The total number of possible keypad mappings is 100 million billion billion. But it is easy for us to check the pigeons.
ALICE: Huh?
PAUL: The pigeonhole principle. For any subset of m letters within a word, there can be at most 106–m words that have that pattern of letters. If there are more, then there must be a collision, no matter the mapping we choose.
ALICE: Ah, I see. That’s easy enough to check! [Typing.]
So, there are fourteen five-letter suffixes like “inder,” “aggle,” and “ingle” that will all produce at least one collision. I guess there’s no way to make a perfect mapping.
PAUL: Gelfand advised Endre Szemerédi. This problem is reminiscent of Szemerédi’s use of expander graphs in pseudorandom number generation. What we want to do is take a relatively small set of inputs (being the six-letter English words) and use an expander graph as an embedding into the natural numbers between one and a million, such that the resulting distribution mimics uniformity.
ALICE: That sounds ... difficult.
PAUL: Constructing expander graphs is extremely difficult. But I think Szemerédi would agree that interesting things rarely happen in fewer than five dimensions.
ALICE: I am a pragmatist. How about we use a genetic algorithm to evolve a near optimal mapping?
PAUL: Such a solution would not be from The Book, but it would provide you with a mapping.
ALICE: What book?
PAUL: The Book in which the SF keeps all of the most beautiful solutions.
ALICE: Well, I think I’ll try my hand at a scruffy genetic algorithm. I need a decent mapping if I ever want to publish this in PoC‖GTFO!
PAUL: What is PoC‖GTFO?
ALICE: It’s... I guess it’s a sort of bible.
PAUL: Then the only difference between your Book and mine are the fascists who created them. Maybe we will continue tomorrow ... if I live.
ALICE: [Looking up from her keyboard.] Can I buy you a drink? [Paul has vanished.]
PASTOR: The moral of the story, dear neighbors, is not that these locks are inherently vulnerable; if used properly, they are in fact incredibly secure. We must remember that these locks are only as secure as the codes humans choose to assign to them. Using a phone keypad mapping on six-letter English dictionary words is the physical security equivalent of a website arbitrarily limiting passwords to eight characters.
13:7 Reversing the LoRa PHY
by Matt Knight
It’s 2016, and everyone’s favorite inescapable buzzword is IoT, the Internet of Things. The mere mention of this phrase draws myriad reactions, depending on who you ask. A marketing manager may wax philosophical about swarms of connected cars eradicating gridlock forever, or the inevitability of connected rat traps intelligently coordinating to eradicate vermin from midtown Manhattan,22 while a security researcher may just grin and relish in the plethora of low-power stacks and new attack surfaces being applied to cyber-physical applications.
IoT is marketing speak for connected embedded devices. That is, inexpensive, low power, resource constrained computers that talk to each other, possibly on the capital-I Internet, to exchange data and command and control information. These devices are often installed in hard to reach places and can be expected to operate for years. Thus, easy to configure communication interfaces and extreme power efficiency are crucial design requirements. While 2G cellular has been a popular mechanism for connecting devices in scenarios where a PAN or wired technology will not cut it, AT&T’s plans to sunset 2G on January 1, 2017 and LTE-M Rel 13’s distance to widespread adoption presents an opportunity for new wireless specifications to seize market share.
LoRa is one such nascent wireless technology that is poised to capture this opportunity. It is a Low Power Wide Area Network (LPWAN), a class of wireless communication technology designed to connect low power embedded devices over long ranges. LoRa implements a proprietary PHY layer; therefore, the details of its modulation are not published.
This paper presents a comprehensive blind signal analysis and resulting details of LoRa’s PHY, chronicles the process and pitfalls encountered along the way, and aspires to offer insight that may assist security researchers as they approach their future unknowns.
Casing the Job
I first heard of LoRa in December 2015, when it and other LP-WANs came up in conversation among neighbors. Collectively we were intrigued by its advertised performance and unusual modulation, thus I was motivated to track it down and learn more. In the following weeks, I occasionally scanned the spectrum near 900 MHz for signs of its distinctive waveform (more on that soon), but searches in the New York metropolitan area, Boston, and a colleague’s search in San Francisco yielded no results.
Sometime later I found myself at an IoT security meetup in Cambridge, MA that featured representatives from Senet and SIGFOX, two major LPWAN players. Senet’s foray into LoRa started when they sought to remotely monitor fluid levels in home heating oil tank measurement sensors to improve the existing process of sending a guy in a truck to read it manually. Senet soon realized that the value of this infrastructure extended far beyond the heating oil market and has expanded their scope to becoming a IoT cellular data carrier of sorts. While following up on the company I happened upon one of their marketing videos online. A brief segment featured a grainy shot of a coverage map, which revealed just enough to suggest the presence of active infrastructure in Portsmouth, NH. After quick drive with my Ettus B210 Software Defined Radio, I had my first LoRa captures.
First Observations and OSINT
LoRa’s proprietary PHY uses a unique chirp spread spectrum (CSS) modulation scheme, which encodes information into RF features called chirps. A chirp is a signal whose frequency is increasing or decreasing at a constant rate, and they are unmistakable within the waterfall. A chirp-based PHY is shown in Figure 13.10.
Contrasted with FSK or OFDM, two common PHYs, the differences are immediately apparent.
Modulation aside, visually inspecting a spectrogram of LoRa’s distinct chirps reveals a PHY structure that is similar to essentially all other digital radio systems: the preamble, start of frame delimiter, and then the data or payload.
Since LoRa’s PHY is proprietary, no PHY layer specifications or reference materials were available. However, thorough analysis of open source and readily available documentation can greatly abbreviate reverse engineering processes. When I conducted this investigation, a number of useful documents were available.
First, the Layer 2+ LoRaWAN stack is published, containing clues about the PHY.
Second, several application notes were available for Semtech’s commercial LoRa modules.23 These were not specs, but they did reference some PHY-layer components and definitions.
Third, a European patent filing from Semtech described a CSS modulation that could very well be LoRa.
Finally, neighbors who came before me produced open-source prior a
rt in the form of a partial rtl-sdrangelove implementation and a wiki page,24 but this attempt was piecemeal and neglected, with only high level observations on the wiki. These were not enough to decode the packets that I had captured in New Hampshire.
Demodulation
OSINT gathering revealed a number of key definitions that informed the reverse engineering process. A crucial notion is that of the spreading factor (SF): the spreading factor represents the number of bits packed into each symbol. A symbol, for the unordained, is a discrete RF energy state that represents some quantity of modulated information (more on this later.) The LoRaWAN spec revealed that the chirp bandwidth, that is the width of the channel that the chirps traverse, is 125 kHz, 250 kHz, or 500 kHz within American deployments. The chirp rate, which is intuitively the first derivative of the signal’s frequency, is a function of the spreading factor and the bandwidth: it is defined as bandwidth/2(spreading_factor). Additionally, the absolute value of the downchirp rate is the same as the upchirp rate.25
Back to the crucial concept of symbols. In LoRa, symbols are modulated onto chirps by changing the instantaneous frequency of the signal; the first derivative of the frequency, the chirp rate, remains constant, while the signal itself “jumps” throughout its channel to represent data. The best way to intuitively think of this is that the modulation is frequency-modulating an underlying chirp. This is analogous to the signal alternating between two frequencies in a 2FSK system, where one frequency represents a 0 and the other represents a 1. The underlying signal in that case is a signal of constant frequency, rather than a chirp, and the number of bits per symbol is 1. How many data bits are encoded into each frequency jump within LoRa? This is determined by the spreading factor.
The first step to extracting the symbols is to de-chirp the received signal. This is done by channelizing the received signal to the chirp’s bandwidth and multiplying the result against a locally-generated complex conjugate of whichever chirp is being extracted. A locally generated chirp is shown in Figure 13.11.
Since both upchirps and downchirps are present in the modulation, the signal should be multiplied against both a local up-chirp and downchirp, which produces two separate IQ streams. Why this works can be reasoned intuitively, since waves obey superposition, multiplying a signal with frequency f0 against a signal with frequency —f0 results in a signal with frequency 0, or DC. If a chirp is multiplied against a copy of itself, it will result in a signal of 2f0, which will spread its energy throughout the band. Thus, generating a local chirp at the negative chirp rate of whichever chirp is being processed results in RF features with constant frequency that can be handled nicely.
In Figure 13.12, the left image shows de-chirped upchirps while the right shows de-chirped downchirps.
This de-chirped signal may be treated similarly to MFSK, where the number of possible frequencies is M = 2(spreading_factor). The Fast Fourier Transform (FFT) is the tool used to perform the actual symbol measurement. Fourier analysis shows that a signal can be modeled as a summed series of basic periodic functions (i.e., a sine wave) at various frequencies. A FFT decomposes a signal into the frequency components that comprise it, returning the power and phase of each component present. Each component to be extracted is colloquially called a “bin;” the number of bins is specified as the “FFT size” or “FFT width.”
Thus, by taking an M-bin wide FFT of each IQ stream, the symbols may be resolved by finding the argmax, which is the bin with the most powerful component of each FFT. This works out nicely because a de-chirped CSS symbol turns into a signal with constant frequency; all of the symbol’s energy should fall into a single bin.26
With the signal de-chirped, the remainder of the demodulation process can be described in three steps. These steps mimic the process required for essentially all digital radio receivers.
First, we’ll identify the start of the packet by finding a preamble. Then, we’ll synchronize with the start of the packet, so that we may conclude in demodulating the payload by measuring its aligned symbols.
Figure 13.10: Spectrogram of a LoRa packet.
Figure 13.11: Locally Generated Chirp
Figure 13.12: De-chirped Upchirps (left) and Downchirps (right)
Finding the Preamble
A preamble is a feature included in modulation schemes to announce that a packet is soon to follow. By visual inspection, we can infer that LoRa’s preamble is represented by a series of continuous upchirps. Once de-chirped and passed through an FFT, all of the preamble’s symbols wind up residing within the same FFT bin. Thus, a preamble is detected if enough consecutive FFTs have the same argmax.
Synchronizing with the SFD
With our receiver aware that it’s about to receive a packet, the next step is to accurately synchronize with it so that symbols can be resolved accurately. To facilitate this, modern radio systems often advertise the start of the packet’s data unit with a Start of Frame Delimiter, or SFD, which is a known symbol distinct from the preamble that receivers are programmed to look for. For LoRa, this is where the downchirps come in.
The SFD is composed of two and one quarter downchirps, while all the other symbols are represented by upchirps. With preamble having been found, our receiver should look for two consecutive downchirps to synchronize against.
Accurate synchronization is crucial to properly resolving symbols. If synchronization is off by enough samples, when FFTs are taken each symbol’s energy will be divided between two adjacent FFTs. Until now, the FFT process used to resolve the symbols processed 2(spreading_factor) samples per FFT with each sample being processed exactly once, however after a few trial runs it became evident that this coarse synchronization would not be sufficiently accurate to guarantee good fidelity.
Increasing the time-based FFT resolution was found to be a reliable method for achieving an accurate sync. This is done by shifting the stream of de-chirped samples through the FFT input buffer, processing each sample multiple times, to “overlap” adjacent FFTs. This increases the time-based resolution of the FFT process at the expense of being more computationally intensive. Thus, overlapping FFTs are only used to frame the SFD; non-overlapped FFTs with each sample being processed exactly once are taken otherwise to balance accuracy and computational requirements.
Technically there’s also a sync word that precedes the SFD, but my demodulation process described in this article does not rely on it.
Demodulating the Payload
Now synchronized against the SFD, we are able to efficiently demodulate the symbols in the payload by using the original non-overlapping FFT method. However, since our receiver’s locally generated chirps are likely out of phase with the chirp used by the transmitter, the symbols appear offset within the set range [0 : 2(spreading_factor) – 1] by some constant. It was surmised that the preamble would be a reliable element to represent symbol 0, especially given that the sync word’s value is always referenced from the preamble. A simple modulo operation to normalize the symbol value relative to the preamble’s zero-valued bin produces the true value of the symbols, and the demodulation process is complete.
Figure 13.13: The top is pre-sync and non-overlapped, middle is pre-sync overlapped, bottom is synchronized and non-overlapped.
Decoding, and its Pitfalls
Overall, demodulation proved to not be too difficult, especially when you have someone like Balint Seeber feeding you advice and sagely wisdom. However, decoding is where the fun (and uncertainty) really began.
First, why encode data? In order to increase over the air resiliency, data is encoded before it is sent. Thus, the received symbols must be decoded in order to extract the data they represent.
The documentation I was able to gather on LoRa certainly suggested that figuring out the decoding would be a snap. The patent application describing a LoRa-like modulation described four decoding steps that were likely present. Between the patent and some of Semtech’s reference designs, there were documented algorithms or detailed descriptions of
every step. However, these documents slowly proved to be lies, and my optimism proved to be misplaced.
OSINT Revisited
Perhaps the richest source of hints was Semtech’s European patent application.27 The patent describes a CSS-based modulation with an uncanny resemblance to LoRa, and goes so far as to walk step-by-step through the encoding elements present in the PHY. From the encoder’s perspective, the patent describes an encoding pipeline of forward error correction, a diagonal interleaver, data whitening, and gray indexing, followed by the just-described modulation process. The reverse process would be performed by the decoder. The patent even defines an interleaver algorithm, and Semtech documentation includes several candidate whitening algorithms.
The first thing to try, of course, was to implement a decoder exactly as described in the documentation. This involved, in order:
Undoing gray coding applied to the symbols.
Dewhitening using the algorithms defined in Semtech’s documentation.
Deinterleaving using the algorithm defined in Semtech’s patent.
Processing the Hamming forward error correction hinted at in Semtech’s documentation.
First, let’s review what we have learned about each step listed above based on open-source research, and what would be attempted as a result.
Gray Indexing Given the nomenclature ambiguity in the Semtech patent, I also decided to test no gray coding and reverse gray coding in addition to forward gray coding. These were done using standard algorithms.
PoC or GTFO, Volume 2 Page 38