December 6, 2017 at 14:50Huffman table recovery in Intel ME 11.x
Today Positive Technologies expert Dmitry Sklyarov at the Black Hat conference in London will talk about how the file system is arranged on which part of Intel CSME / ME version 11.x and some files for this system are located. We present to your attention his article on restoring Huffman tables in Intel ME 11.x.
As you know , many Intel ME 11.x modules are stored in Flash-memory in a packed form, and two algorithms are used for compression - LZMA and Huffman Encoding . There is a public implementation for LZMAwhich can be used for unpacking, but for Huffman everything is more complicated. Huffman Encoding unpacker in ME is implemented at the hardware level, and building equivalent program code is a complex and non-standard task.
After reviewing the source code that is part of the unhuffme project , it is easy to see that for previous versions of ME there are two sets of Huffman tables and each set contains two tables. The presence of two tables (one for the code and one for the data) is probably due to the fact that the statistical properties of the code and the data are very different.
The following properties are also noteworthy:
It can be assumed that in the Huffman tables for ME 11.x the last three properties are also observed. Then, to fully restore the tables, you need to find the following:
To obtain information about individual modules, you can use existing knowledge about the internal structures of the firmware .
Having examined the Lookup Table, which is part of the Code Partition Directory, it is easy to determine for which modules Huffman coding is applied, where their packed data begins and what size the module will have after unpacking.
Having examined the Module Attributes Extension for a particular module, it is easy to find the size of the compressed and decompressed data and the SHA256 from the decompressed data.
After a quick analysis of several firmware for ME 11.x, it is easy to see that the data size after unpacking by Huffman is always a multiple of the page size (4096 == 0x1000 bytes). At the beginning of the packed data is an array of four-byte integer values. The number of array elements corresponds to the number of pages in the unpacked data.
For example, for a module of size 81920 == 0x14000 bytes, an array will occupy 80 == 0x50 bytes and consist of 20 == 0x14 elements.
The two high-order bits of each of the Little-Endian values store the table number (0b01 for code and 0b11 for data). The remaining 30 bits store the offset of the beginning of the compressed page relative to the end of the offset array. The snippet above describes 20 pages:
It is noteworthy that the offsets of the packed data for each page are sorted in ascending order, and the size of the packed data for each page in explicit form does not appear anywhere. In the above example, the packed data for each particular page starts at the border multiple of 64 = 0x40 bytes, and the unused areas are filled with zeros. But for other modules, it can be established that alignment is not required. This suggests that the unpacker stops when the data size of the unpacked page reaches 4096 bytes.
Since we know the total size of the packed module (from the Module Attributes Extension), we can divide the packed data into separate pages and work with each page separately. The beginning of the packed page is determined from the offset array, and the size is determined by the offset of the beginning of the next page or the total size of the module. In this case, after the packed data, an arbitrary number of insignificant bits can go (these bits can have any values, but in practice they are usually zero).
The screenshot shows that the last compressed page (starting at offset 0xFA40) consists of byte 0xB2 == 0b10110010, followed by 273 bytes with the value 0xEC == 0b11101100, and then only zeros. Since the bit sequence 11101100 (or 01110110) is repeated 273 times, we can assume that it encodes 4096/273 == 15 identical bytes (most likely with values 0x00 or 0xFF). Then the bit sequence 10110010 (or 1011001) encodes 4096-273 * 15 == 1 byte.
This is in good agreement with the assumption that each code sequence encodes an integer number of bytes (from 1 to 15 inclusive). However, it is not possible to completely restore Huffman tables in this way.
As shown earlier , in different firmware versions for ME 11, modules with the same names can be packed with different algorithms. If you parse the Module Attributes Extension for the modules of the same name, packed both by LZMA and Huffman, and extract the SHA256 values for each module, you will not find a single pair of modules packed with different algorithms and having the same hash values.
But if you remember that for modules packed with LZMA, SHA256 is usually calculated from the compressed data, and count SHA256 for modules after unpacking LZMA, you will find quite a few suitable pairs. And for each such “paired” module, we will immediately receive several pairs of pages - packed in Huffman and unpacked.
The presence of a large set of pages in compressed and open form (separately for code and data) allows you to restore all code sequences used in these pages. The solution to the problem is at the junction of linear algebra and search engine optimization. Probably, you can build a rigorous mathematical model that takes into account all the limitations, but since the task is a one-time task, it turned out to be faster to do some of the work manually, and some to automate.
The most important thing is to at least roughly determine the Shape (points of change in the lengths of code sequences). For example, that 7-bit sequences have values from 1111111 to 1110111, 8-bit sequences from 11101101 to 10100011, etc. Since Canonical Huffman Coding is used, knowing Shape allows you to determine the length of the next code sequence (the shortest sequence consists only of units , the longest is only of zeros, and the smaller the value, the longer the sequence).
Since we do not know the exact size of the compressed data, it is possible to erase from the “tail” all sequences consisting of only zero bits (since they are the longest, and the appearance of the rarest code sequence in the last position is unlikely).
When each compressed page can be represented as a set of code sequences, we can begin to determine the lengths of the values encoded by them. The sum of the lengths of the encoded values for each page should be 4096 bytes. This allows you to create a system of linear equations where the lengths of the encoded values are unknown, the coefficients are the number of occurrences of the corresponding code sequence in a compressed page, and 4096 is always in place of a free term. Pages of code and data can be processed together, since for identical code sequences the lengths of the encoded values must match.
Given a sufficient number of pages (and equations), the only solution to the system is easily found by the Gauss method. And having plain text, knowing the length of each value and the order of their sequence, it is easy to obtain the correspondence of the code sequences and the values encoded by them.
After processing all the available “paired” pages, it will be possible to find out the values for approximately 70% of the sequences from the code table and 68% of the sequences from the data table. Lengths will be known for approximately 92% of the sequences. And there will be some uncertainty in the Shape: in some places either one value of a shorter length or two values of a longer length can be used, and it is impossible to determine the boundary until one of the values is found in the packed data.
Now you can begin to restore values for code sequences that are found only in modules for which there are no plaintexts.
If a sequence with an unknown length is encountered, another line is added to the equation system, and this allows you to quickly determine the length. But how to determine the meaning without having a clear text?
Fortunately, SHA256 from the unpacked module is stored in the metadata. And if we correctly guess the value of all unknown code sequences in all the pages that make up the module, the calculated SHA256 value should match the SHA256 value from the Module Attributes Extension.
When the total length of the unknown sequences is 1 or 2 bytes, the unknown bytes are elementarily found by frontal enumeration. You can also deal with 3 or even 4 unknown bytes (especially if they are located close to the end of the module), but it can take from several hours to several days to search on one core (it is easy to parallelize it on several cores or machines). Attempts to enumerate 5 or more bytes were not made.
Thus, it is possible to recover several more code sequences (and several modules). But then there are only modules in which the total volume of unknown bytes exceeds the capabilities of brute-force-selection.
However, the presence of a large number of modules, slightly differing from each other, allows the use of various heuristics and with their help to find the values of unknown code sequences.
Since there are two Huffman tables in the unpacker, the compressor tries to compress the data of each of them, and leaves the version that takes up less space. As a result, the division into "code" and "data" is conditional. And when you change part of the page, another table may be more effective. That is, looking at other versions of the same module, you can find identical fragments that were packed in another table, and so restore unknown bytes.
When one code sequence occurs many times in one (or different) modules (for example, in code and in data), it is often easy to determine what restrictions are imposed on unknown values.
In the field of these modules, constants and offsets are quite common (for example, to text strings or functions). Constants can be common for different modules (for example, for hashing functions and encryption algorithms), and offsets are unique for each version of the module, but must refer to the same (or very similar) pieces of data or code. And their values are very easy to recover.
Some fragments of ME code were obviously borrowed from open-source projects (for example, wpa_supplicant), and fragments of text strings are easily guessed by context and by peering into the source.
Having looked at the source and found the text of the function, for the compiled code of which several bytes are unknown, you can work as a compiler and guess what values are suitable in this place.
Since there should not be strong differences in different (but close) versions of one module, sometimes it is enough to find an equivalent function in a module of another version and understand by its code what should be in unknown bytes.
If the code is not taken from public sources, some fragment is unknown in all available versions of the module, and is not found in any other module (namely, it was with the amt module), you can find the same place (for example, in ME 10), find out the logic functions, and then project it to an unknown place in ME 11.x.
Starting with modules in which there were fewer unknown sequences, and combining various heuristics, it was possible to step by step increase the known part of Huffman tables (each time checking the correctness of the assumptions by calculating SHA256). With increasing coverage, the modules, where initially the number of unknown sequences were measured in dozens, were not so intimidating. The process looked convergent, but everything ran into amt.
This module is the largest in size (about 2 megabytes, about 30% of the total), contains many code sequences that are not found in any other module, but are found in all versions of amt. It is possible to guess several sequences with high probability, but the only way to verify the assumption is to guess all of them (so that SHA256 matches). Thanks to the invaluable help of Maxim Goryachy, we managed to overcome this barrier, as a result of which we were able to unpack any of the modules contained in our firmware and packed with the Huffman algorithm.
Over time, new firmware appeared, and they came across codewords not previously seen. But each time one of the heuristics worked, the module was successfully unpacked and the coverage of the tables increased.
By mid-June 2017, we were able to recover approximately 89.4% of the sequences for the code table and 86.4% of the sequences for the data table. But the chances of building a 100% table coverage in a reasonable time through the analysis of new modules are very weak.
On June 19, fragments of Huffman tables covering 80.8% of sequences for a code table and 78.1% of sequences for a data table were published on GitHub by a user with the nickname IllegalArgument . Probably, the author (or authors) used a similar approach based on an analysis of existing firmware. And in the published tables there was nothing new.
And on July 17, Mark Ermolov and Maxim Goryachy got the opportunity to find out the unpacked values for any compressed data. We prepared 4 compressed pages (two for code and two for data), and restored all 1519 sequences for both tables .
At the same time, one incomprehensible place was discovered. In the Huffman table for data, the value 00410E088502420D05 corresponds to both the sequence 10100111 (8 bits long) and the sequence 000100101001 (12 bits long). This is a clear redundancy, but most likely it is due to a random error.
The resulting Shape is as follows:
Posted by Dmitry Sklyarov, Positive Technologies
As you know , many Intel ME 11.x modules are stored in Flash-memory in a packed form, and two algorithms are used for compression - LZMA and Huffman Encoding . There is a public implementation for LZMAwhich can be used for unpacking, but for Huffman everything is more complicated. Huffman Encoding unpacker in ME is implemented at the hardware level, and building equivalent program code is a complex and non-standard task.
Previous versions of ME
After reviewing the source code that is part of the unhuffme project , it is easy to see that for previous versions of ME there are two sets of Huffman tables and each set contains two tables. The presence of two tables (one for the code and one for the data) is probably due to the fact that the statistical properties of the code and the data are very different.
The following properties are also noteworthy:
- For different sets of tables, the length ranges of codewords differ (7–19 and 7–15 bits inclusive).
- Each code sequence encodes an integer number of bytes (from 1 to 15 inclusive).
- Both sets use Canonical Huffman Coding (this allows you to quickly determine the length of the next code word when unpacking).
- Within one set, the lengths of the encoded values for any codeword are the same in all tables (Code and Data).
Formulation of the problem
It can be assumed that in the Huffman tables for ME 11.x the last three properties are also observed. Then, to fully restore the tables, you need to find the following:
- range of codeword lengths;
- boundaries of values of code words having the same length (Shape);
- lengths of encoded sequences for each codeword;
- encoded values for each codeword in both tables.
Separate compressed data into separate pages
To obtain information about individual modules, you can use existing knowledge about the internal structures of the firmware .
Having examined the Lookup Table, which is part of the Code Partition Directory, it is easy to determine for which modules Huffman coding is applied, where their packed data begins and what size the module will have after unpacking.
Having examined the Module Attributes Extension for a particular module, it is easy to find the size of the compressed and decompressed data and the SHA256 from the decompressed data.
After a quick analysis of several firmware for ME 11.x, it is easy to see that the data size after unpacking by Huffman is always a multiple of the page size (4096 == 0x1000 bytes). At the beginning of the packed data is an array of four-byte integer values. The number of array elements corresponds to the number of pages in the unpacked data.
For example, for a module of size 81920 == 0x14000 bytes, an array will occupy 80 == 0x50 bytes and consist of 20 == 0x14 elements.
The two high-order bits of each of the Little-Endian values store the table number (0b01 for code and 0b11 for data). The remaining 30 bits store the offset of the beginning of the compressed page relative to the end of the offset array. The snippet above describes 20 pages:
It is noteworthy that the offsets of the packed data for each page are sorted in ascending order, and the size of the packed data for each page in explicit form does not appear anywhere. In the above example, the packed data for each particular page starts at the border multiple of 64 = 0x40 bytes, and the unused areas are filled with zeros. But for other modules, it can be established that alignment is not required. This suggests that the unpacker stops when the data size of the unpacked page reaches 4096 bytes.
Since we know the total size of the packed module (from the Module Attributes Extension), we can divide the packed data into separate pages and work with each page separately. The beginning of the packed page is determined from the offset array, and the size is determined by the offset of the beginning of the next page or the total size of the module. In this case, after the packed data, an arbitrary number of insignificant bits can go (these bits can have any values, but in practice they are usually zero).
The screenshot shows that the last compressed page (starting at offset 0xFA40) consists of byte 0xB2 == 0b10110010, followed by 273 bytes with the value 0xEC == 0b11101100, and then only zeros. Since the bit sequence 11101100 (or 01110110) is repeated 273 times, we can assume that it encodes 4096/273 == 15 identical bytes (most likely with values 0x00 or 0xFF). Then the bit sequence 10110010 (or 1011001) encodes 4096-273 * 15 == 1 byte.
This is in good agreement with the assumption that each code sequence encodes an integer number of bytes (from 1 to 15 inclusive). However, it is not possible to completely restore Huffman tables in this way.
Finding “compressed text - plaintext” pairs
As shown earlier , in different firmware versions for ME 11, modules with the same names can be packed with different algorithms. If you parse the Module Attributes Extension for the modules of the same name, packed both by LZMA and Huffman, and extract the SHA256 values for each module, you will not find a single pair of modules packed with different algorithms and having the same hash values.
But if you remember that for modules packed with LZMA, SHA256 is usually calculated from the compressed data, and count SHA256 for modules after unpacking LZMA, you will find quite a few suitable pairs. And for each such “paired” module, we will immediately receive several pairs of pages - packed in Huffman and unpacked.
Shape, Length, Value
The presence of a large set of pages in compressed and open form (separately for code and data) allows you to restore all code sequences used in these pages. The solution to the problem is at the junction of linear algebra and search engine optimization. Probably, you can build a rigorous mathematical model that takes into account all the limitations, but since the task is a one-time task, it turned out to be faster to do some of the work manually, and some to automate.
The most important thing is to at least roughly determine the Shape (points of change in the lengths of code sequences). For example, that 7-bit sequences have values from 1111111 to 1110111, 8-bit sequences from 11101101 to 10100011, etc. Since Canonical Huffman Coding is used, knowing Shape allows you to determine the length of the next code sequence (the shortest sequence consists only of units , the longest is only of zeros, and the smaller the value, the longer the sequence).
Since we do not know the exact size of the compressed data, it is possible to erase from the “tail” all sequences consisting of only zero bits (since they are the longest, and the appearance of the rarest code sequence in the last position is unlikely).
When each compressed page can be represented as a set of code sequences, we can begin to determine the lengths of the values encoded by them. The sum of the lengths of the encoded values for each page should be 4096 bytes. This allows you to create a system of linear equations where the lengths of the encoded values are unknown, the coefficients are the number of occurrences of the corresponding code sequence in a compressed page, and 4096 is always in place of a free term. Pages of code and data can be processed together, since for identical code sequences the lengths of the encoded values must match.
Given a sufficient number of pages (and equations), the only solution to the system is easily found by the Gauss method. And having plain text, knowing the length of each value and the order of their sequence, it is easy to obtain the correspondence of the code sequences and the values encoded by them.
Unknown sequences
After processing all the available “paired” pages, it will be possible to find out the values for approximately 70% of the sequences from the code table and 68% of the sequences from the data table. Lengths will be known for approximately 92% of the sequences. And there will be some uncertainty in the Shape: in some places either one value of a shorter length or two values of a longer length can be used, and it is impossible to determine the boundary until one of the values is found in the packed data.
Now you can begin to restore values for code sequences that are found only in modules for which there are no plaintexts.
If a sequence with an unknown length is encountered, another line is added to the equation system, and this allows you to quickly determine the length. But how to determine the meaning without having a clear text?
Verifier and brute-force
Fortunately, SHA256 from the unpacked module is stored in the metadata. And if we correctly guess the value of all unknown code sequences in all the pages that make up the module, the calculated SHA256 value should match the SHA256 value from the Module Attributes Extension.
When the total length of the unknown sequences is 1 or 2 bytes, the unknown bytes are elementarily found by frontal enumeration. You can also deal with 3 or even 4 unknown bytes (especially if they are located close to the end of the module), but it can take from several hours to several days to search on one core (it is easy to parallelize it on several cores or machines). Attempts to enumerate 5 or more bytes were not made.
Thus, it is possible to recover several more code sequences (and several modules). But then there are only modules in which the total volume of unknown bytes exceeds the capabilities of brute-force-selection.
Heuristics
However, the presence of a large number of modules, slightly differing from each other, allows the use of various heuristics and with their help to find the values of unknown code sequences.
Using a Second Huffman Table
Since there are two Huffman tables in the unpacker, the compressor tries to compress the data of each of them, and leaves the version that takes up less space. As a result, the division into "code" and "data" is conditional. And when you change part of the page, another table may be more effective. That is, looking at other versions of the same module, you can find identical fragments that were packed in another table, and so restore unknown bytes.
Reusable
When one code sequence occurs many times in one (or different) modules (for example, in code and in data), it is often easy to determine what restrictions are imposed on unknown values.
Constants and tables with offsets
In the field of these modules, constants and offsets are quite common (for example, to text strings or functions). Constants can be common for different modules (for example, for hashing functions and encryption algorithms), and offsets are unique for each version of the module, but must refer to the same (or very similar) pieces of data or code. And their values are very easy to recover.
String constants from open libraries
Some fragments of ME code were obviously borrowed from open-source projects (for example, wpa_supplicant), and fragments of text strings are easily guessed by context and by peering into the source.
Code from open libraries
Having looked at the source and found the text of the function, for the compiled code of which several bytes are unknown, you can work as a compiler and guess what values are suitable in this place.
Similar functions in modules of another version
Since there should not be strong differences in different (but close) versions of one module, sometimes it is enough to find an equivalent function in a module of another version and understand by its code what should be in unknown bytes.
Similar features in previous versions of ME
If the code is not taken from public sources, some fragment is unknown in all available versions of the module, and is not found in any other module (namely, it was with the amt module), you can find the same place (for example, in ME 10), find out the logic functions, and then project it to an unknown place in ME 11.x.
Process convergence
Starting with modules in which there were fewer unknown sequences, and combining various heuristics, it was possible to step by step increase the known part of Huffman tables (each time checking the correctness of the assumptions by calculating SHA256). With increasing coverage, the modules, where initially the number of unknown sequences were measured in dozens, were not so intimidating. The process looked convergent, but everything ran into amt.
This module is the largest in size (about 2 megabytes, about 30% of the total), contains many code sequences that are not found in any other module, but are found in all versions of amt. It is possible to guess several sequences with high probability, but the only way to verify the assumption is to guess all of them (so that SHA256 matches). Thanks to the invaluable help of Maxim Goryachy, we managed to overcome this barrier, as a result of which we were able to unpack any of the modules contained in our firmware and packed with the Huffman algorithm.
Over time, new firmware appeared, and they came across codewords not previously seen. But each time one of the heuristics worked, the module was successfully unpacked and the coverage of the tables increased.
Final touch
By mid-June 2017, we were able to recover approximately 89.4% of the sequences for the code table and 86.4% of the sequences for the data table. But the chances of building a 100% table coverage in a reasonable time through the analysis of new modules are very weak.
On June 19, fragments of Huffman tables covering 80.8% of sequences for a code table and 78.1% of sequences for a data table were published on GitHub by a user with the nickname IllegalArgument . Probably, the author (or authors) used a similar approach based on an analysis of existing firmware. And in the published tables there was nothing new.
And on July 17, Mark Ermolov and Maxim Goryachy got the opportunity to find out the unpacked values for any compressed data. We prepared 4 compressed pages (two for code and two for data), and restored all 1519 sequences for both tables .
At the same time, one incomprehensible place was discovered. In the Huffman table for data, the value 00410E088502420D05 corresponds to both the sequence 10100111 (8 bits long) and the sequence 000100101001 (12 bits long). This is a clear redundancy, but most likely it is due to a random error.
The resulting Shape is as follows:
Posted by Dmitry Sklyarov, Positive Technologies
