PoC or GTFO, Volume 2
Page 39
Data Whitening Data whitening was a colossal question mark while looking at the system. An ideal whitening algorithm is pseudorandom, thus an effective obfuscator for all following components of the system. Luckily, Semtech appeared to have published the algorithm candidates in Application Note AN1200.18. Entitled “Implementing Data Whitening and CRC Calculation in Software on SX12xx Devices,” it describes three different whitening algorithms that were relevant to the Semtech SX12xx-series wireless transceiver ICs, some of which support LoRa. The whitening document provided one CCITT whitening sequences and two IBM methods in C++. As with the gray indexing uncertainty, all three were implemented and permuted.
Interleaver Interleaving refers to methods of deterministically scrambling bits within a packet. It improves the effectiveness of Forward Error Correction, and will be elaborated on later in this text. The Semtech patent application defined a diagonal interleaver as LoRa’s probable interleaver. It is a block-style non-additive diagonal interleaver that shuffles bits within a block of a fixed size. The interleaver is defined as
Symbol(j, (i + j)%PPM) = Codeword(i, j)
where 0 <= i < PPM and 0 <= j < 4 + RDD. In this case, PPM is set to the spreading factor (or spreading_factor — 2 for the PHY header and when in low data rate modes), and RDD is set to the number of parity bits used by the Forward Error Correction scheme, ranging [1 : 4].
There was only one candidate illustrated here, so no iteration was necessary.
Forward Error Correction The Semtech patent application suggests that Hamming FEC be used. Other documentation appeared to confirm this. A custom FEC decoder was implemented that originally just extracted the data bits from their standard positions within Hamming(8,4) codewords, but early results were negative, so this was extended to apply the parity bits to repair errors.
Using a Microchip RN2903 LoRa Mote, a transmitter that was understood to be able to produce raw frames, a known payload was sent and decoded using this process. However, the output that resulted bore no resemblance to the expected payload. The next step was to inspect and validate each of the algorithms derived from documentation.
After validating each component, attempting every permutation of supplied algorithms, and inspecting the produced binary data, I concluded that something in LoRa’s described encoding sequence was not as advertised.
Taking Nothing for Granted
The nature of analyzing systems like this is that beneath a certain point they become a black box. Data goes in, some math gets done, RF happens, said math gets undone, and data comes out. Simple enough, but when encapsulated as a totality it becomes difficult to isolate and chase down bugs in each component. Thus, the place to start was at the top.
How to Bound a Problem
The Semtech patent describes the first stage of decoding as “gray indexing.” Gray coding is a process that maps bits in such a way that makes it resilient to off-by-one errors. Thus, if a symbol were to be measured within ±1 index of the correct bin, the gray coding would naturally correct the error. “Gray indexing,” ambiguously referring to either gray coding or its inverse process, was initially understood to mean forward gray coding.
The whitening sequence was next in line. Data whitening is a process applied to transmitted data to induce randomness into it. To whiten data, the data is XORed against a pseudorandom string that is known to both the transmitter and the receiver. This does good things from an RF perspective, since it induces lots of features and transitions for a receiver to perform clock recovery against. This is functionally analogous to line coding schemes such as Manchester encoding, but whitening offers one pro and one con relative to line coding: data whitening does not impact the effective bit rate as Manchester encoding does,28 but this comes at the expense of legibility due to the pseudorandom string.
At this point, it is important to address some of the assumptions and inferences that were made to frame the following approach. While the four decoding stages were thrown into question by virtue of the fact that at least one of the well-described algorithms was not correct, certain implied properties could be generalized for each class of algorithm, even if the implementation did not match exactly.
I made a number of assumptions at this point, which I’ll describe in turn.
First, the interleaver in use is non-additive. This means that while it will reorder the bits within each interleaving block, it will not cause any additional bits to be set or unset. This was a reasonable assumption because many block-based interleavers are non-additive, and the interleaver defined in the patent is non-additive as well. Even if the interleaver used a different algorithm, such as a standard block interleaver or a different type of diagonal interleaver, it could still fit within this model.
Second, the forward error correction in use is Hamming FEC, with four data bits and one to four parity bits per codeword. FEC can be thought of as supercharged parity bits. A single parity bit can indicate the presence of an error, but if you use enough of them they can collectively identify and correct errors in place, without re-transmission. Hamming is specifically called out by the European patent, and the code rate parameter referenced throughout reference designs fits nicely within this model.
The use of Hamming codes, as opposed to some other FEC or a cyclic coding scheme, was fortuitous because of a property of the Hamming code words. Hamming codeword mapping is deterministic based on the nybble that is being encoded. Four bits of data provide 16 possible codewords. When looking at Hamming(8,4) (which is the inferred FEC for LoRa code rate 4/8), 14 of the 16 codewords contain four set bits (1s) and four unset bits (0s). However, the code words for 0b0000 and 0b1111 are 0b00000000 and 0b11111111, respectively.
Thus, following on these two assumptions, if a payload containing all 0x00s or 0xFFs were sent, then the interleaving and forward error correction should cancel out and not affect the output at all. This reduces our unknown stages in the decoding chain from four to just two, with the unknowns being gray indexing and whitening, and once those are resolved then the remaining two can be solved for!
Since “gray indexing” likely refers to gray coding, reverse gray coding, or no coding should it be omitted, this leaves only three permutations to try while solving for the data whitening sequence.
The first step was to take a critical look at the data whitening algorithms provided by Semtech AN1200.18. Given the detail and granularity in which they are described, plus the relevance of having come straight from a LoRa transceiver datasheet, it was almost a given that one of the three algorithms would be the solution. With the interleaver and FEC effectively zeroed out, and “gray indexing” reduced to three possible states, it became possible to test each of the whitening algorithms.
Testing each whitening algorithm was fairly straightforward. A known payload of all 0x00s or 0xFFs (to cancel out interleaving and FEC) was transmitted from the Microchip LoRa Technology Mote and then decoded using each whitening algorithm and each of the possible “gray indexing” states. This resulted in nine permutations. A visual diff of the decoded data versus the expected payload resulted in no close matches. This was replaced with a diff script with a configurable tolerance for bits that did not match. This also resulted in no matches as well. One final thought was to forward compute the whitening algorithms in case there was a static offset or seed warm-up, as can be the case with other PRNG algorithms. Likewise, this did not reveal any close matches. This meant that either none of the given whitening algorithms in the documentation were utilized, or the assumptions that I made about the interleaver and FEC were not correct.
After writing off the provided whitening algorithms as fiction, the next course of action was to attempt to derive the real whitening algorithm from the LoRa transmitter itself. This approach was based on the previous observations about the FEC and interleaver and a fundamental understanding of how data whitening works. In essence, whitening is as simple as XORing a payload against a static pseudorandom string, with the same string used by both the trans
mitter and receiver. Since anything XORed with zero is itself, passing in a string of zeroes causes the transmitter to reveal a “gray indexed” version of its whitening sequence.
This payload was received, then transformed into three different versions of itself: one gray-coded, one unmodified, and one reverse gray-coded. All three were then tested by transmitting a set of 0xF data nybbles and using each of the three “gray indexing” candidates and received whitening sequence to decode the payload. The gray coded and unmodified versions proved to be incorrect, but the reverse gray coding version successfully produced the transmitted nybbles, and thus in one fell swoop, I was able to both derive the whitening sequence and discern that “gray indexing” actually referred to the reverse gray coding operation. With “gray indexing” and whitening solved, I could turn my attention to the biggest challenge: the interleaver.
The Interleaver
At this point we’ve resolved two of the four signal processing stages, disproving their documentation in the process. Following on this, the validity of the interleaver definition provided in Semtech’s patent was immediately called into question.
A quick test was conducted against a local implementation of said interleaver: a payload comprised of a repeated data byte that would produce a Hamming(8,4) codeword with four set and four unset bits was transmitted and the de-interleaved frame was inspected for signs of the expected codeword. A few other iterations were attempted, including reversing the diagonal offset mapping pattern described by the patent and using the inverse of the algorithm (i.e., interleaving the received payload rather than de-interleaving it). Indeed, I was able to conclude that the interleaver implemented by the protocol is not the one suggested by the patent. The next logical step is to attempt to reverse it.
Within a transmitter, interleaving is often applied after forward error correction in order to make the packet more resilient to burst interference. Interleaving scrambles the FEC-encoded bits throughout the packet so that if interference occurs it is more likely to damage one bit from many codewords rather than several bits from a single codeword. The former error scenario would be recoverable through FEC, the latter would result in unrecoverable data corruption.
Block-based interleavers, like the one described in the patent, are functionally straightforward. The interleaver itself can be thought of as a two-dimensional array, where each row is as wide as the number of bits in each FEC codeword and the number of columns corresponds to the number of FEC codewords in each interleaver block. The data is then written in row-wise and read out column-wise; thus the first output “codeword” is comprised of the LSB (or MSB) of each FEC codeword. A diagonal interleaver, as suggested in the patent, offsets the column of the bit being read out as rows are traversed.
Understanding the aforementioned fundamentals of what the interleaver was likely doing was essential to approaching this challenge. Ultimately, given that a row-column or row-diagonal relationship defines most block-based interleavers, I anticipated that patterns that could be revealed if approached appropriately. Payloads were therefore constructed to reveal the relationship of each row or codeword with a corresponding diagonal or column. In order to reveal said mapping, the Hamming(8,4) codeword for 0xF was leveraged, since it would fill each row with eight contiguous bits at a time. Payloads consisting of seven 0x0 codewords and one 0xF codeword were generated, with the nybble position of 0xF iterating through the payload. See Figure 13.14.
As one can see, by visualizing the results as they would be generated by the block, patterns associated with each codeword’s diagonal mapping can be identified. The diagonals are arbitrarily offset from the corresponding row/codeword position. One important oddity to note is that the most significant bits of each diagonal are flipped.
While we now know how FEC codewords map into block diagonals, we do not know where each codeword starts and ends within the diagonals, or how its bits are mapped. The next step is to map the bit positions of each interleaver diagonal. This is done by transmitting a known payload comprised of FEC codewords with four set and four unset bits, then looking for patterns within the expected diagonal.
Figure 13.14: Symbol Tests
Reading out the mapped diagonals results in this table.
T
Bot
D
1
0
1
0
0
0
0
1
E
0
1
1
1
0
1
0
0
A
0
1
0
1
1
0
0
0
D
1
0
1
1
0
0
0
0
B
1
1
0
0
0
0
1
0
E
0
1
1
1
0
1
0
0
E
0
1
1
1
0
1
0
0
F
1
1
1
1
1
1
1
1
While no matches immediately leap off the page, manipulating and shuffling through the data begins to reveal patterns. First, reverse the bit order of the extracted codewords.
B
Top
D
1
0
0
0
0
1
0
1
E
0
0
1
0
1
1
1
0
A
0
0
0
1
1
0
1
0
D
0
0
0
0
1
1
0
1
B
0
1
0
0
0
0
1
1
E
0
0
1
0
1
1
1
0
E
0
0
1
0
1
1
1
0
F
1
1
1
1
1
1
1
1
And then have a look at the last nybble for each of the highlighted codewords.
B
Top
D
1
0
0
0
0
1
0
1
E
0
0
1
0
1
1
1
0
A
0
0
0
1
1
0
1
0
D
0
0
0
0
1
1
0
1
B
1
0
0
0
0
1
1
E
0
0
1
0
1
1
1
0
E
0
0
1
0
1
1
1
0
F
1
1
1
1
1
1
1
1
Six of the eight diagonals resemble the data embedded into each of the expected FEC encoded codewords! As for the first and fifth codewords, it is possible they were damaged during transmission, or that the derived whitening sequence used for those positions is not exact. That is where FEC proves its mettle, as applying Hamming(8,4) FEC would repair any single bit errors that occurred in transmission. The Hamming parity bits that are expected with each codeword are calculated using the Hamming FEC algorithm, or can be looked up for standard schemes like Hamming(7,4) or Hamming(8,4).
While the most standard Hamming(8,4) bit order is: p1, p2, d1, p3, d2, d3, d4, p4 (where p are parity bits and d are data bits), after recognizing the above data values we can infer that the parity bits are in a nonstandard order. Looking at the diagonal codeword table and the expected Hamming(8,4) encodings together, we can map the actual bit positions:
Bot
p1
p2
p4
p3
d1
d2
d3
Top
d4
D
1
0
0
0
0
1
0
1
E
0
0
1
0
1
1