Black-box cryptanalysis of home-made encryption algorithms: a practical case study
Author: Pierre Capillon
Date: 2016-05-16T18:46:05.593450+00:00
Publisher: STIC

Table of Contents

1 Introduction
2 Exploring file formats
3 Initial intuition, trial and errors
4 Hypotheses, heuristics and validation
5 Instrumentation considerations
6 Final thoughts and industry efforts

Black-box cryptanalysis of home-made encryption algorithms: a practical case study

Pierre Capillon
pierre.capillon@ssi.gouv.fr

Agence Nationale de la Sécurité des Systèmes d’Information
(French Network and Information Security Agency – ANSSI)

Abstract. Product vendors sometimes develop their own cryptographic algorithms to either protect their intellectual property or ensure information confidentiality (data or communications). Many of these algorithms have been proven to contain critical weaknesses which defeat their purpose, weaken security and might expose customer data or systems.

Most research on home-made algorithms is usually done through reverse-engineering of the hardware or software parts implementing these cryptographic primitives. This article tackles a different approach on an unknown and simple algorithm.

During the study of an embedded system firmware, the author was not allowed to tamper with the targeted product. With hardware-based attacks or research out of the equation, this article proposes a first-hand account on how black-box cryptanalysis was performed on a custom algorithm in order to retrieve a 40 MB firmware from an 18 MB compressed and encrypted image.

The author discloses approaches, methods, ideas and tools developed throughout the part-time 6-weeks process, and discusses explored ideas and attacks which proved to be either successful or dead-ends.

Acknowledgement. This work was conducted in 2014, along with

Fabrice Desclaux and Camille Mougey who have provided invaluable help in identifying some key data fields. Cédric Bouhier and Nicolas Vivet have also provided significant contributions to the reverse engineering and implementation of the compression algorithm.

1 Introduction

1.1 Disclaimer

While initially describing the study of obscure systems, cryptanalysis  [9] (as a discipline) has a strong mathematical connotation. This paper does not tackle much of the mathematical challenges the cryptanalysis of modern cryptography poses. It is rather a collection of considerations and techniques used to attack an unknown encryption/scrambling algorithm (an index table may be found at section 6.3).

Therefore, in the context of this article, cryptanalysis shall be viewed as the historical discipline of retrieving cleartexts, whatever the means and however weak the algorithm is. Do not expect a revolutionary attack on a complex cryptosystem, rather a glimpse of a thought process.

The focus of this article is to provide a first-hand account on the effort such a cryptanalysis requires, as well as dismiss claims that attacking custom-made cryptography is infeasible or requires extraordinary resources.

As such, while identifying details were left out, the algorithm principles have been preserved.

1.2 State of the art in black-box cryptanalysis

Nowadays, black-box cryptanalysis is usually performed on ciphertext with prior knowledge of the algorithm. This is mainly due to the various reverse-engineering opportunities of available products, hardware or software. Well-known examples include:

- digital rights management (DVD, etc.);

- access control systems (various NFC technologies);

- Wi-Fi encryption (WEP, WPA+TKIP);

- cellular communications (A5/1 and A5/2 stream ciphers).

Many other examples exist where proprietary cryptography was studied and successfully attacked  [7]. This also includes the recovery of firmware images  [1].

However, all of these examples involved access to the algorithm details before an attack could be performed on ciphertexts.

Historically, ciphertext-only attacks with no prior access to algorithm details have been devised by rival governments when eavesdropping foreign diplomatic communications. While access to algorithm details would still be seeked through various intelligence means, it was not uncommon to attack foreign cryptography on the basis of intercepted communications only. Unlike the well-known case of the Enigma machine, cryptanalysis of the German Lorenz cipher during World War II was made without access to the physical machine  [8]. At approximately the same time, the Japanese Purple code was also broken by the american National Security Agency without needing access to the device itself. A second attempt to break the Purple code with modern techniques was even made by the NSA more recently  [5].

Similarly, early paid television services have had their scrambling mechanism attacked. Some of their scrambling algorithms have even been cryptanalyzed without having access to a legitimate decoder or algorithm details  [2] [3].

This article is an account of a similar attempt on present-day secret proprietary algorithm used for firmware encryption.

1.3 Embedded systems security

Security research is common on current embedded products in order to find and patch vulnerabilities. Such a work may or may not be the result of a collaborative effort with the product vendor. As such, different amounts of information are available to the researcher, who in turn tries to get access to as many information as possible, possibly up to design documents and source codes.

In many cases, source code access is either not possible for multiple reasons or simply not desirable. The researcher often turns to black box analysis to:

- study device communications, via traffic captures and protocol fuzzing;

- study its internal mechanisms, via reverse-engineering of the device firmware.

To protect those, sometimes vendors still consider the development and use of secret, unproven, home-made scrambling systems or cryptography a worthy investment. Beyond firmware encryption/intellectual property protection, it is not uncommon to find this kind of algorithm in proprietary communication protocols. The rising trend in « smart » devices (the « Internet of Things ») brings its round of similar attempts at bogus security measures. Performance considerations worsen the problem, as vendors try to implement « optimized » algorithms to run decently on limited hardware resources.

1.4 Context

As part of security research on a particular embedded system, a team of several people split the task between various efforts, one being focused on the firmware itself.

To obtain the firmware image, multiple paths may be considered. Here are the main options:

- asking the vendor;

- downloading an image file hoping it is not scrambled;

- retrieving the firmware legitimately from the device;

- exploiting a software vulnerability to extract or study the firmware from the device;

- exploiting an hardware vulnerability to extract or study the firmware from the device.

Unfortunately, none of those are available:

- no proprietary information is to be exchanged;

- the device is lent for a short duration by the manufacturer;

- the device cannot be tampered with;

- the device should be returned in pristine and working condition.

These restrictions rule out any kind of hardware manipulations, such as extracting firmware data directly from the NAND flash chips. Yet this specific manipulation was considered, but deemed too risky after seeing how the SoC, flash chips and contact pads are protected under a heavily glued heatsink (see figure 1).

Fig. 1: The target system PCB with a prominent, glued heatsink. Undocumented visible connectors provide no useful signals.

After assembling the unit back together, members of the team go on with fuzzing it, while the author focuses on retrieving the firmware by other means.

For the sake of this article, the different product models can be grouped as follows:

- M1, M2, M3, M5 and M6 form model group A;

- M4, M7 and above form model group B.

Models from the latter group have significant differences in the hardware platform. The available unit is model M6, with later tests done on model M3, whose differences are irrelevant to this paper.

Firmware updates images are available for all models, with five revisions at the time of the study (including a major revision). Downgrading the device to an older revision is officially supported, and the original firmware revision is also available for download. Images for group A are about 18 MB in size, while those for group B are about 50 MB.

It is then decided to have a look at these firmware upgrade files as they stand a good chance of containing the full image.

Unfortunately, these images do not load into reverse-engineering tools as they seem to be encrypted.

1.5 Specific constraints

Modern techniques often involve knowledge of the attacked algorithm and use some of its properties to retrieve information about the plaintext. This information is usually retrieved through reverse-engineering of the software or hardware parts implementing the target algorithm. This approach is not possible due to our constraints.

This paper thus focuses on ideas, approaches, methods and tools developed while attacking the encryption with no prior knowledge:

- the algorithm is entirely unknown;

- the target platform architecture is unknown;

- the hardware configuration is unknown (including possible security modules);

- the software platform seems to include open-source libraries (SSL libraries), as observed by using the product;

- no remote code execution was achieved on the device yet, excluding dynamic analysis or firmware extraction;

- no oracle is available to get feedback from the firmware update process.

The product could very well run an embedded Linux distribution on a general-purpose CPU as well as a bare-bone proprietary operating system on a custom-designed system-on-chip.

1.6 Initial problem and resources considerations

While the practical case on which this article is based ends up being a success, readers shall keep in mind the following considerations:

- the ideas developed in this paper are probably not suitable for strong cryptographic algorithms: a detail feels dangerously off from the beginning, hinting at a weak algorithm;

- even with a weak algorithm, there is no guarantee of succeeding in recovering a plaintext image;

- no knowledgeable help could be obtained;

- what is observable does not necessarily reflect the algorithm designer’s intent: a very complex proprietary algorithm may result in observed properties which were not initially expected.

A particular emphasis is made on the last consideration.

To achieve decryption, the following resources were used:

- six weeks of part-time research amounting to probably 3 weeks of full-time work on the project;

- a single man effort, with contributions from two colleagues;

- a single desktop workstation for computations;

- lots of sweet and caffeine in various forms.

These weeks of effort had a noticeable effect on the author’s health and sanity, with sleeping and eating disorders occurring over an extended period of time.

2 Exploring file formats

The first step in analyzing firmware updates is figuring out the file format:

- Is it a binary file? Is it executed on the device?

- Is it a filesystem? Is it well-known or custom-made?

- Is it compressed? Is it encrypted?

- Does it contain metadata? A digital signature? Parameters?

Immediate actions are to quickly check whether obtaining a usable binary file looks feasible. Two main steps help achieve that:

- entropy analysis of every firmware update available, for all models in case some differences showed up;

- file format and header reconstruction, which helps postulate various hypotheses which would then be tested.

2.1 Entropy

Entropy analysis  [10] is known to help discriminate various types of data (text, binary code, images), as well as their possible status (plaintext, encrypted, compressed). The compression algorithm may sometimes be identified by this method  [4].

Figure 2 shows the result on firmware updates from both product model groups.

Fig. 2: Binwalk entropy analysis on the first 17 MB of the update file for model M6 (group A, bottom) and M7 (group B, top).

Group B models exhibit a very high and uniform entropy average (around 0.98), possibly indicating the use of strong cryptography or compression. However, group A models exhibit a far lower average entropy (0.78) with clear fluctuations. Two areas near the end of the file have a higher entropy, possibly revealing the use of compression or encryption on some parts of the firmware. Also, the beginning and the end of the file show more fluctuations than the largest area between the 10% and 80% filelength marks.

These fluctuations could indicate that more diverse data types are located at these locations, while a single type lies in the largest chunk.

Also, a 0.78 average entropy could be characteristic of executable code, which may suggest that the firmware is not strongly encrypted.

2.2 Header identification

Opening the firmware update in any hexadecimal editor reveals plaintext data, suggesting the presence of a formatted header (see figure 3).

Fig. 3: Header fields identified visually. Chunk sizes and hashes can be seen overlayed in green and red (darkest colors).

The relevant model part number is mentionned a few times, as well as a copyright string, both in plaintext form. They might help the update program determine whether the proper update is being flashed to the device.

Also, four 6-character field names have two occurrences each. Their first occurrence is preceded by 8 bytes for each. Four of these bytes turn out to be the size of the data section following their second occurrence.

The first two data sections contain short plaintext data or are simply empty. The last section is identified as a signature, sits at the end of the firmware update and is sufficiently long to hold a MAC value, but not much more. The bulk of the firmware is thus located in the third data storage section, which begins immediately.

2.3 Main data storage section

The main data section starts with 92 unknown bytes, yet they do not vary across firmware revisions nor models. The following section contains weird ASCII values, ending with a long string of 0x2D values. This section is actually a build timestamp/release string obfuscated with a ROT13 pass. The actual purpose of the ROT13 use is still unknown.

Right after this ROT13 section, 120 bytes of data look much different from the next ones, which have far more null values that the rest of the header. Among those 120 bytes, a sharp eye can identify the 32-byte SHA256 hash value of an empty string (e3b0c44298fc1c14 9afbf4c8996fb924 27ae41e4649b934c a495991b7852b855). The four bytes immediately preceding the hash are NULL, which may reveal a new size field.

As three SHA256 hashes fit in 120 bytes, with 24 bytes left, there is room for a 32-bit size field and an additional 4-byte value. Indeed, the other 4-byte values fit the description of a size field: adding all three fields gives precisely the size in bytes of the remainder of the main data section.

Therefore, these three data chunks seem to be stored in the main data section of the firmware update file, with the last chunk being empty. Notably, this chunk of data is not empty among models from group B.

Unfortunately, those SHA256 hashes do not match any subset of the stored data.

Fig. 4: Header fields as retrieved from the manual file analysis. Bold text highlights variable contents between revisions and models.

From this manual analysis, many parts of the firmware update header can be reconstructed. Figure 4 shows the resulting documentation. A few fields are identified by reverse-engineering the firmware update application, but the software does not parse them further than the first 144 bytes (0x90), while some can be identified further along. Parsing of those fields is probably done on the device itself.

Identified fields are then compared across product models and firmware revisions, to help mark fields whose values are either static or changing. Some fields have their value depend solely on the firmware revision, sharing it across models. Some other fields have their value change completely between models, even from the same group.

2.4 Hypotheses and initial thoughts

A summary of firmware update c.01 for model M6 is shown in figure 5.

Fig. 5: Firmware update file format summary. Firmware image is expected to be found within chunk #2.

Two interesting data chunks are identified: a very small one, and a large one occupying the bulk of the firmware update file. The latter is likely to contain the firmware image.

Analysis with automated tools, such as binwalk, does not identify a known compression algorithm or data type.

Consequently, the recovery efforts then focus on firmware updates for models from group A, as they do not seem strongly encrypted.

At this point, a few hypotheses are formulated on the identified data chunks:

- one of the chunks must contain executable code, as well as other plaintext data we should obtain by using the device (GUI strings, web pages);

- the chunks could be flashed « as-is », as there seems to be strong integrity mechanisms in place;

- identified SHA256 hashes must correspond to the output after properly processing data chunks, indicative of either (or both) compression or encryption;

- downgrading ability, format similarities and varying header values across firmware revisions must mean the update file is self-sufficient, and that the updater software is backward compatible.

We were then left with two data chunks, of which we assumed to have the SHA256 values of their corresponding plaintext. The recovery efforts then focus on each chunk, as recovering the smallest one could eventually help recovering the largest chunk.

Up to this point, the recovery efforts lasted for a single day.

3 Initial intuition, trial and errors

3.1 Finding code patterns

Not knowing whether the binary data is in plaintext, compressed, or somehow encrypted form, a colleague suggested to try and match code patterns.

Finding instruction opcodes

A statistical analysis can be performed on byte groups of varying length, to match the results to those of typical CPU architecture instruction sets.

This task is quite difficult, especially with variable-length instruction sets.

Although it was briefly explored, initial results proved too uncertain to properly match any given architecture.

Function calls

Byte sequences related to function calls/returns or function prologue/epilogues can be searched for, and matched against those of known architectures. A match would also help identify the underlying CPU architecture. One would find roughly the same proportion of call instructions than that of return instructions. The same goes for prologue/epilogue patterns (matching combinations of push/pop instructions).

While data entropy is somewhat similar to that of binary code from various architectures, this approach proved unsuccessful.

3.2 One more hypothesis

After failed attempts at directly identifying executable code, a new hypothesis is tested.

The plaintext data is likely to be either some form of binary executable code, some data files, or parameters. Such data is likely to be structured: common executable formats have a well-defined header, whose structure and values do not vary that much between compilations. The same is true for other data types.

Therefore, we are likely to find a format header or container structure which probably does not vary much between firmware updates.

3.3 Initial discovery

After the firmware update header, data from chunk #1 immediately shows a lot of null values, as can be seen in figure 6: chunk #1 data starts at 0x1E0.

Additionally, most bytes have a very low number of bits set. This seems to confirm the previous hypothesis that data might be structured and have bitfield values or flags stored first.

Fig. 6: Chunk #1 binary data differences between consecutive minor revisions of model M6. Note how the same number of bits are set in each 4-byte word.

Binary differences between two consecutive minor revisions reveal another interesting detail: there is the same number of bits set for each corresponding 4-byte group.

This observation leads to a major discovery: if the stored data is actually structured, it is unlikely that the format markers differ by much. Bits should then be stored at the same position. Since it is not the case, there are yet precisely the same number of bits set for each 4-byte group, the content has probably been scrambled at least by a bitwise rotation of some sort.

This is first verified manually by calculating bitwise rotations differences on little-endian 4-byte words, as shown on figure 7.

Fig. 7: Whiteboard with initial discovery of bit-shifting similarities across firmware revisions.

So the scrambling system is likely to use bitwise rotations to obfuscate data from chunk #1, as we are able to get perfect matches of the first data bytes by applying a specific rotation to an update revision compared to another.

Up to this point, two days of effort had been spent in the analysis.

3.4 Comparing update revisions

The previous finding means that one might be able to match some if not all data from an update revision to another, by simply applying the same bitwise rotation to each 4-byte word.

Comparing SHA256 hashes from the update headers between various models and revisions reveals that chunk #1 data could be the same within the same major firmware revision. Figure 8 shows that all minor revisions of the b.xx and c.xx branches respectively have identical hashes.

Fig. 8: SHA256 hashes found in headers from update files for different versions and models.

Therefore, if our earlier hypothesis—that SHA256 hashes are those of cleartext data—is true, it should be possible to perfectly match chunk #1 data found among those minor revisions, both in cleartext and encrypted form.

Ciphertext match does not necessarily mean the encryption has been broken yet, as the bitwise rotation may be applied as a final pass. However, if this is the only pass, it is then possible to fully decrypt the data. In any case, being able to match ciphertext from an update to another can still prove useful.

Figure 9 shows what the decryption approach would be in such an event.

Fig. 9: Decryption approach for chunk #1 in the event bitwise rotation is the only scrambling pass.

Unfortunately, applying the same bitwise rotation to the full chunk #1 data only yields a partial match: data ceases to match after an arbitrary length (see figure 10).

Fig. 10: Block boundary detection in chunk #1 at 0x1F018 due to a sudden content mismatch.

The bitwise rotation distance changes after a given length, hence revealing that the scrambling process works with 4-byte aligned blocks of arbitrary sizes. Repeating the bitwise rotation allows identification of 4 blocks of different sizes with different rotation parameters for the full chunk.

Note that the first two blocks include large amounts of consecutive NULL bytes. As these NULL bytes are insensitive to bitwise rotation, it is impossible to determine how many blocks span across those.

3.5 Bruteforce

Testing all 31 possible bitwise rotations on chunk #1 finally reveals some plaintext, indicating that no other scrambling has been applied to data. The first block reveals the ELF magic value, while the last block reveals ELF section names and some compilation string artefacts.

As shown in figure 11, two blocks are left with no identifiable plaintext in any of their rotated counterpart. This leaves 31^2 = 961 combinations (compared to the initial 31^4 = 923521 combinations), allowing a bruteforce attack on chunk #1 to recover the plaintext. Candidate plaintexts would be tested against the SHA256 hash found in the update header, granted our initial hypothesis is correct.

Fig. 11: Block decryption bruteforce for chunk #1.

All 961 candidates are generated with their SHA256 hash, and a match is found for chunk #1, validating all previously stated hypotheses.

A valid ELF binary follows a small, custom header. This also reveals that the underlying architecture is a MIPS CPU.

3.6 Chunk #1 analysis

Reverse-engineering the recovered chunk #1 ELF reveals interesting details. The binary has three main modes of operation:

- parsing headers with a format matching the one found before the ELF magic;

- uncompressing a blob to an arbitrary memory location, with a variant of an LZ compression algorithm;

- acting as an ELF image loader and jumping to its entry point.

Oddly enough, it looks like this binary is executed on the device and gets the decrypted chunk #2 as an input, decompresses and runs it. The binary could act as a bootloader and be used to load the firmware image into memory.

The compression algorithm is then reimplemented to mimic the binary implementation, including corner cases and error conditions. However, the chunk #2 data needs to be fully decrypted before being able to fully uncompress it.

3.7 Trial and error

While bruteforce was an option for chunk #1 (even with the initial 923521 combinations), this seems a very unlikely possibility on chunk #2 due to the potentially large number of blocks. A rough estimate gives more than 2000 blocks with the observed mean block size of 8 KB.

Chunk #2 also displays a valid ELF header at the beginning, after a similar custom header. However, identifiable data quickly surfaces in the few kilobytes immediately after the ELF header:

- large data areas padded with 0xFF values;

- an embedded filesystem image, with structures similar to directory entries;

- corrupted web content (HTML pages and GIF images).

Binwalk successfully identifies a very limited number of images, though they are split across multiple storage blocks of the filesystem and are not yet fully recoverable.

The chunk #2 data is still compressed at this point. Due to how LZ compression works, early bytes will probably be left unaffected before the compression dictionnary fills with enough context. However, control bytes are inserted every 8 bytes, corrupting contents.

Quickly enough, the compression mechanism is sufficiently active to deter naive recovery attempts. Also, block boundaries for the encryption algorithm become less and less clear as binary data is much more difficult to identify. It is then required to recover all block boundaries as well as the rotation distance for each of these blocks before being able to uncompress the firmware.

As could be expected, contrary to the chunk #1 data, no two firmware updates share identical SHA256 hashes. Identifying block boundaries is not feasible using the same comparison technique.

About two weeks of part-time work had been spent on recovering the chunk #1. The next sections will cover how the actual recovery was performed on the 18 MB chunk #2.

4 Hypotheses, heuristics and validation

Two major parameters are still unknown:

- how the bitwise rotation distance is chosen;

- how the block size is determined.

Given the size of the chunk #2 data, these parameters cannot be guessed by bruteforce alone.

4.1 Refining hypotheses and using them to find strong heuristics

Given the previous findings regarding the chunk #1 executable, one can safely assume compressed, cleartext chunk #2 data is processed by a similar (if not identical) binary running on the device itself. The following hypotheses may then be formulated:

- decryption must occur before any further processing;

- downgrade support means the decryption binary must either apply a common algorithm for every revision or identify the target revision;

- firmware update files must be self-sufficient to yield correct decryption parameters.

Careful comparison between update revisions and across different models reveals the following facts:

- rotation distance varies based on version number only, as the same values are used for chunk #1 data across different models;

- block sizes vary by both version number and model; however as no identical SHA256 is found across models, the latter may be unimportant;

- block sizes do not vary between minor firmware revisions for the same chunk #1 data.

Therefore, block sizes and rotation distances could be determined by:

- two hard-coded, data- and version-dependent lists of values;

- a value generation algorithm seeded by information within the update file header;

- the cleartext data itself, or a value derived from the cleartext data (possibly its hash value).

It is highly unlikely that hardcoded lists of values are used for each version, as they should be either determined from the start of the product lifecycle, or pushed in advance for upcoming upgrades by the previous ones. This process seems very unlikely for a device with both downgrade support and the ability to skip major revisions.

The next efforts are focused on recovering how both block sizes and rotation distances are determined. At that point, only a handful of these values have been determined: 4 blocks for chunk #1 data, and only 2 blocks for chunk #2 data.

4.2 Expanding the sample size

To get a better idea of the various block sizes and rotation parameters, it is useful to gather as much actual values as possible, sorted by revision number and model.

Fortunately, chunk #1 data for model M1 is 560 KB long. As multiple versions share the same data, the same comparison technique can be used between minor revisions to identify block boundaries.

Within two minor revisions 22 and 24 blocks can be identified, with confirmed lengths varying between 128 and 15712 bytes (blocks starting or ending in byte arrays neutral to bitwise rotation are ignored as their boundary cannot be precisely determined). No obvious correlation pattern can be identified with such a small sample size.

Rotation parameters to fully decrypt chunk #1 cannot not be bruteforced. Indeed, only five blocks are recovered based on string values, leaving 17 to 19 unknown parameters, far too much to guess accurately. Again, the sample size for both block size and rotation parameter is insufficient to detect any noticeable correlation.

As the comparison method cannot be reliably used on chunk #2 data because of varying contents between revisions, other ways of confirming block boundaries are developed.

4.3 Instrumenting compression

The decompression algorithm will fail if it encounters certain particular invalid control bytes or empty dictionary entries.

This allows using the decompression algorithm to validate its own input: incoherent data will not be decompressed correctly. This implies:

- bitwise rotation on 4-byte words will corrupt or shift control bytes at incorrect positions;

- decompression dictionary will slowly fill with incorrect contextual data, leading to decompression errors later on, sometimes very far from the current position, depending on data duplicity.

If wrong block sizes or rotation parameters are guessed, decompression is likely to fail. This fact can be exploited to validate guessed values, by trying to uncompress the data and having the decompression routine display offsets where errors have been encountered.

4.4 Finding multiple reliable checks

Block boundaries will end in the middle of stored data, which may be used as a validity check:

- if an executable binary is located around suspected block boundaries, disassembling instructions should yield a coherent output, rather than corrupted or uncommon instructions;

- if a filesystem is discovered, its structure could be reverse-engineered to help validate coherence of guessed block boundaries and rotation parameters;

- if files of known format are discovered, they can be used to validate the decompression output.

Various data are found that could be used to validate block boundaries after guessing block size and bitwise rotation distance:

- a data structure first attributed to a NAND flash image format (however, this turned out to be misleading);

- a proprietary filesystem derived from FAT-like structures;

- a few web pages;

- a few PNG and GIF images;

- multiple X.509 certificates for HTTPS support.

This « almost known » cleartext data helps provide reliable checks to confirm candidate block boundaries and rotation parameters: either check for consistency or simply compare with a copy obtained from the embedded web server. GIF files, web pages and certificates are used in that regard.

4.5 Unreliable data

A block boundary ends up within an SSL certificate for a different model, which is still present in the image[1] . Due to the random nature of such data, and unavailability of the relevant model, it is impossible to fully validate this block boundary.

Furthermore, the embedded filesystem image seems to contain forensic artefacts of deleted data within the web root, which is confusing as these files could not be retrieved by accessing the web server (as if the filesystem image had been generated and updated on an actual device).

These uncertainties lead to the decompression progressing or failing in similar ways given multiple different candidate block boundaries. This quickly increased combinatorial complexity.

This type of error becomes more and more common as the decompression progresses through binary input data which is not easily identifiable/verifiable. Indeed, the decompression dictionary quickly fills, leaving less and less empty entries, which results in less and less decompression failures (even from incorrect data).

4.6 Combining steps to discard branches

Fig. 12: Chunk #2 decryption approach.

As described in figure 12, the recovery process outline then becomes as follows:

1. guess rotation parameter for the first block, using the ELF magic value, or bruteforce the rotation distance ;

2. run instrumented decompression on candidate cleartext chunk. Decompression failure occurs at or after the actual block boundary: decompression should then have advanced significantly if the parameters were guessed correctly;

3. check validation heuristics on candidate uncompressed chunk;

4. try the next candidate rotation parameter or block boundary if validation fails. Go on to the next block if validation passed.

Advancing decompression along with guessing attempts provides the following benefits:

- bitwise rotation distance is bruteforced for each subsequent block sequentially instead of trying every combination for multiple consecutive blocks. Doing so contained combinatorial explosion within acceptable limits;

- compression control codes may be checked for coherence before attempting decompression, effectively reducing the number of combinations;

- decompression can be attempted on multiple candidate block boundaries, with candidates advancing the output further likely being the correct ones;

- multiple, different heuristic checks may be tested against the last few uncompressed candidates.

This approach limits computational requirements progressively by running the most CPU-intensive tasks on less candidates as they are being discarded along the way.

4.7 Initial results

This approach yields very interesting results. As shown in figure 13, multiple block boundaries and rotation parameters can be retrieved.

It becomes evident that the rotation distance comes from a cyclic list of 24 values. This list is shared across all revisions and models. Only the starting index differs and it is determined by the version number within the update file header.

This discovery enables full decryption of model M1 chunk #1, which ends up having no helpful difference with respect to chunk #2 data recovery.

At this point however, block boundaries do not seem to be shared between models or revisions, nor do they look cyclic.

Uncertainties in block boundaries, as well as decompressed data ambiguity lead to finding new ways of validating our guesses, as discussed in subsection 4.9.

Fig. 13: Chunk #2 identified block boundaries and repeating bitwise rotation pattern.

4.8 Implementation

Fig. 14: Developed tool for block boundary and bitwise rotation parameter discovery.

A small tool is developed specifically to implement our approach (figure 14):

- given an initial rotation distance, it will guess the next block boundaries recursively by running decompression attempts on multiple candidate boundaries;

- decompression is reimplemented in C (from our initial ruby implementation), to accommodate for some performance issues;

- rotation parameter guessing is reimplemented using the discovered hardcoded values to speed up boundary discovery and eliminate unreliable guesses.

The tool is obviously very specific to the attacked algorithm and firmware update format.

4.9 Analyzing revision-specific differences

While different firmware revisions contain different data, one could assume minor revisions would not differ by much.

Even if parts of the executable code change to reflect patches, most static resources and code will remain the same. This means one should be able to find identical data within two consecutive minor revisions, granted the build process is streamlined and produces a similar content layout for each revision.

Therefore, an attempt is made to recover two consecutive firmware revisions in parallel. The rationale behind this effort is as follows: as different versions have different block sizes, block boundaries are likely to end up in different parts of their contents. This means that for any given data block, one will probably be longer than the block containing the same data from the other revision. It is then possible to leverage this length difference to cross-validate block boundaries by comparing contents from candidate blocks of one revision to the longer block from the other revision.

Fig. 15: Chunk #2 mutual validation approach.

Proceeding this way enables cleartext recovery by alternating the reference block used for validation between two consecutive firmware revisions: whichever block ends at the farthest output offset will be used as reference. This « mutual validation » approach is described in figure 15.

4.10 Final results

The mutual validation between consecutive revisions proves successful enough to enable the recovery of several hundreds of data blocks.

During the manual recovery of these block boundaries, some statistics are kept. It becomes obvious that their sizes are also following a cyclic pattern of 31 values (see figure 16), although they are different for every firmware revision. Like block boundaries of the chunk #1, it is thought that the values do not depend on revision numbers, but only data contents.

Fig. 16: Chunk #2 identified block boundaries across firmware update revisions.

Using both the block size and rotation distance lists to decrypt the firmware results in a clear text image matching the SHA256 hash found in the update file header.

This concludes the six weeks of research, with most advances always occurring only a few days apart. The lack of long period without significant breakthroughs supported arguments in favor of continuing the cryptanalysis effort.

5 Instrumentation considerations

5.1 Planned evolutions, areas of research

While further development was not required, a few evolutions and areas of research were discussed internally, in case the manual and mutual validation approach proved insufficient:

- automating the mutual validation process;

- automating binary disassembly as a dedicated validation check;

- spending more effort reverse-engineering the proprietary filesystem to develop efficient validation heuristics;

- using a third data source for validation, across either three consecutive minor revisions or between identical revisions for different product models;

- instrumenting decompression to provide dictionary hit and miss statistics, and devise heuristics based on expected behaviour.

5.2 On multithreading

The developed tools used for bruteforce or block boundary discovery are not multithreaded.

The author believes spending time on properly multithreading the process would have shifted focus on irrelevant matters, rather than finding clever ways of attacking the problem. To an extent, the author recommends performance issues not be resolved by multithreading before any other option has been fully explored.

However, some critical steps may hit performance issues, as was the case with our initial ruby implementation of the decompression algorithm. One should take extra time to consider whether multithreading would lift a significant bottleneck or help advance to an ulterior step.

A basic attempt was still made to make use of the Open MP multithreading library, although performance was not ultimately an issue for our needs.

5.3 Statistical methods for data analysis

While simple analysis of block sizes and rotation parameters helped identify cyclic patterns, a true statistical analysis was not relevant for our data set.

However, this method should always be considered, and the author purposedly kept track of various observed properties in case a statistical study would be required later on.

6 Final thoughts and industry efforts

6.1 Recovered algorithm and data

The efforts succeeded in recovering a plaintext firmware image from the update files only. The result is a 42.2 MB ELF file recovered from the initial 18.1 MB firmware update. The file loads properly in IDA and finally reveals a custom-designed, proprietary real-time operating system running on a MIPS architecture.

The encryption algorithm resulted in bitwise rotation performed on 4-byte words, with parameters shared within data blocks of varying sizes ranging from 128 bytes to 16 KB. Bitwise rotation distance is taken from a cyclic list of 24 values, shared accross all firmware versions, with a starting value depending solely on the firmware update version. Block sizes vary with 31 possible values, also taken from a cyclic list, whose values vary depending on the firmware update chunk content.

The reader should keep in mind the observed resulting algorithm may not necessarily reflect the designer’s intent, but might as well be the result of unintended consequences of an improper design.

Reverse engineering of the discovered firmware revealed enormous, unrolled routines implementing cryptographic primitives believed to participate in the update process. Multiple debug symbol names reveal the algorithm was actually thought as a cryptosystem, with decryption and encryption routines being explicitly named as such.

6.2 Required effort and resources

As stated in subsection 1.6, the effort spanned over six weeks of part-time work for a single researcher.

Coworker contributions included reverse-engineering of the ELF binary contained in the first chunk as well as a reimplementation of the decompression routine in both Ruby and C, in addition to various tool optimizations.

The developed tools helped us figuring out block boundaries, which allowed recovery of plaintext images in less than half an hour of manual checking. Computations were single-threaded and performed on a Dell T5500 workstation with 12 GB of RAM and dual Xeon X5650 (6 cores/12 threads each, 2.67 GHz).

In preparation for a similar attempt, the author would like to give readers the following advices:

- take detailed notes of everything: wikis are great for that;

- take regular breaks, sometimes for extended periods of time;

- step back and go over your approach on a regular basis to avoid getting lost in your own misconceptions;

- try to find ways to refine and/or validate hypothesis;

- have your ideas cross-examined by coworkers who are not involved in your project, keep notes of every suggestion;

- do not take a path without having considered at least one or two other possible options in case of failure.

6.3 Summary of discussed techniques and ideas

The following tables provide a summary of analysis techniques and ideas discussed in this article, along with their relevance to the recovery of our firmware data.

File format identification

Technique/Idea

Ref.

Comments/Relevance

Entropy analysis

2.1

Helped identify compressed and weakly encrypted data

Field delimiter identification

2.2

Helped recover data-container structure

Well-known value identification

2.2

Helped identify hashes, timestamps, sizes, etc.

Size-field identification

2.2

Helped delimit raw data chunks

Static/variable data identification

2.3

Helped delimit fields, identify value significance, devise hypotheses

Encryption scheme identification

Technique/Idea

Ref.

Comments/Relevance

Finding instruction opcodes

3.1

Unsuccessful attempt at finding executable code

Matching calling conventions

3.1

Unsuccessful attempt at finding code-like patterns in case the encryption kept symbols alike

Bitwise binary differences

3.3

Helped locate bitfields, headers, parameters, etc.

Comparing multiple samples

3.4

Helped identify static data BLOBs, enable statistical analysis, exploit potential similarities

Bruteforce

3.5

Helped recover data without known/identifiable plaintext

Reverse-engineering

3.6

Helped identify and implement the compression algorithm, helped find useful error/corner cases

Binary data fingerprinting

3.7

Unsuccessful attempt at recovering complete files from firmware image

Data recovery

Technique/Idea

Ref.

Comments/Relevance

Devising strong heuristics

4.1

Helped develop data validation routines used for automating exploration

Keeping statistics and numbers

4.2

Helped identify patterns, cyclic values, helped prepare further analysis

Chaining decryption with other processing

4.3

Helped validate decryption, block boundaries, decompression input

Instrumenting compression

4.3

Helped discard incoherent compression control bytes

Validating data formats

4.4

Helped validate successful decompression, helped discard corrupted bruteforced/guessed candidate blocks

Chaining data validation

4.6

Helped limit combinatorial complexity

Cross-comparison between multiple source data versions

4.9

Helped exploit similarities across data revisions, helped derive validation heuristics

Multithreaded tools

5.2

Unused

Statistical methods for data analysis

5.3

Unused, though it was strongly considered and prepared for

Thought process

Technique/Idea

Ref.

Comments/Relevance

Taking long breaks

6.2

Proved essential to keeping clear thoughts, ideas and goals

Peer review, suggestions and rubber duck debugging

6.2

Proved essential to validate and find ideas, helped ensure the implemented methods were appropriate and correct

6.4 On the use of home-made cryptography

Most researchers would not bother trying to attack the algorithm directly when they could afford attacking the hardware directly.

While it is widely recognized that security by obscurity is not a viable option in the long term, the successful efforts presented herein are a strong reminder that custom-made cryptography is not a strong deterrent to reverse-engineering. Even worse, the development and use of such algorithms tend to provide vendors with a false sense of security, which ultimately is fatal in environments where security is key.

Hiding firmwares to deter reverse-engineering ultimately results in the security community failing to analyze products and get vulnerabilities fixed through responsible disclosure, while leaving resourceful, malicious actors able to spend the required effort to succeed. These actors usually have no incentive to publish their findings or get bugs fixed, leaving legitimate customers vulnerable.

All of these considerations hold even without considering the fact that designing a secure cryptographic system can prove very difficult  [6].

References

1.    Dominic Chen. Firmware deobfuscation utilities. https://github.com/ddcc/drive_firmware/, 2015. [Online; accessed 22-January-2016].

2.    Technical Zone Experiment. Codage et décodage des chaines analogiques de 1984 à 2010 (partie 1). http://wintzx.fr/blog/2014/01/codage-_et-_decodage-_des-_chaines-_analogiques-_en-_1984-_partie-_1/, 2014. [Online; accessed 22-January-2016] (French).

3.    Technical Zone Experiment. Codage et décodage des chaines analogiques de 1984 à 2010 (partie 2). http://wintzx.fr/blog/2014/02/codage-_et-_decodage-_des-_chaines-_analogiques-_de-_1984-_a-_2010-_partie-_2/, 2014. [Online; accessed 22-January-2016] (French).

4.    Craig Heffner. Differentiate encryption from compression using math. http://www.devttys0.com/2013/06/differentiate-_encryption-_from-_compression-_using-_math/, 2013. [Online; accessed 18-January-2016].

5.    NSA. Red and purple: A story retold. Cryptologic Quarterly, Vol. 3(n°3-4):63–80, 1984-1985. NSA analysts’ modern-day attempt to duplicate solving the Red and Purple ciphers.

6.    Bruce Schneier. Security pitfalls in cryptography. 1998. https://www.schneier.com/essays/archives/1998/01/security_pitfalls_in.html.

7.    Roel Verdult. The (in)security of proprietary cryptography. PhD thesis, Radboud University Nijmegen and KU Leuven, Netherlands, 2015.

8.    Wikipedia. Cryptanalysis of the lorenz cipher — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Cryptanalysis_of_the_Lorenz_cipher&oldid=695707661, 2015. [Online; accessed 29-December-2015].

9.    Wikipedia. Cryptanalysis — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Cryptanalysis&oldid=692497875, 2016. [Online; accessed 18-January-2016].

10.    Dennis Yurichev. Analyzing unknown binary files using information entropy. http://yurichev.com/blog/entropy/, 2015. [Online; accessed 18-January-2016].

1  The fact that generic SSL certificates are shared and hardcoded is a worrying fact on its own.

Table of Contents

- Introduction
- Exploring file formats
- Initial intuition, trial and errors
- Hypotheses, heuristics and validation
- Instrumentation considerations
- Final thoughts and industry efforts
- 9
- 6.3
- 7
- 1
- 8
- 5
- 2
- 3
- 10
- 4
- 6
- 11
- 12
- 13
- 4.9
- 14
- 15
- 16
- 1.6
- 2.1
- 2.2
- 2.3
- 3.1
- 3.3
- 3.4
- 3.5
- 3.6
- 3.7
- 4.1
- 4.2
- 4.3
- 4.4
- 4.6
- 5.2
- 5.3
- 6.2