XOR (Scrambler) key extraction
Author: Chris Sampson, TRC Data Recovery
Most modern flash based device controllers utilise a scrambler pattern for the data that they write to their flash memory. This scrambler is often unique to the controller manufacturer and occasionally to the individual controller model.
Recovery of data from devices that are scrambled in this way is only possible if the scrambling pattern is known (or can be determined), as the scrambled data will not be usable without the scrambling pattern first being removed.
Scrambler implementation is similar to basic encryption, where an exclusive-or herein XOR) operation is conducted on the data, by the controller. This happens prior to it being written to the flash memory using the controller’s Linear-Feedback Shift Register.
Unlike true encryption, scrambling patterns are not designed for security reasons and are therefore easy to identify, extract and then use for data recovery.
Using Visual Nand Reconstructor, we are able to identify and extract new or unidentified Xor scrambler patterns in a (normally) relatively straight forward way. We do this using a little knowledge of the flash memory chip architecture which we then combine with the bitmap viewer component of VNR.
Before beginning to extract the key, it is helpful to make a note of some of chip parameters that we have used to create the dumps of our flash memory.
To start with we will need:
– the Page size for the NAND chip
– the Block size for the chip
Why? Xor scrambler keys tend to be multiples of the size of block. They use a repeating pattern which is easily visible when we set the bitmap viewer to the size of exactly one page. When it comes to the importance of the Block size, the entire key tends to be the exact length of 1 block, 1/2 of block, 1/6 of block of the flash memory chip. We will use this fact later to make the process of extraction simpler.
1. Identifying and setting the structure for the flash memory
We should start by determining the structure of our NAND chip with which we can easily determine the data area (which is likely to be XORed), the spare area markers and the ECC code. Later we will certainly need to remove the manufacturer’s spare area markers and the ECC too as these areas are not XORed and will not need to be un-xored by our process. Sometimes the spare area markers are XORed too, this is not common but can occur.
An explanation of the purpose, identification and structure generation of NAND chips using VNR can be found in the article.
2. Identifying the key
If you have already spent some time with your case and have been unable to identify the usual, readable, data structures that you would expect, it is likely that the data is scrambled or encrypted. For most devices available on the market, encryption is not supported or implemented.
Where XOR scramblers are implemented, patterns can normally be found in the flash dumps. These patterns are often easy to identify, a guide to identification of these patterns can be found in the article.
To view the kind of identifiable results that are shown in the “Xor key visual recognition” article, linked to above, we need to set our bitmap viewer to the size of one page if it’s not set by default. Once we have done this we can scroll through the NAND dump and attempt to locate a pattern such as those linked to above, with which to start our extraction.
3. Determining the start and end of the key
There is another way to navigate through the dump which may prove to save time and prevent fiddly manual setting of start and end offsets for the key. We can do this by setting the Page size to exactly one block of the flash memory (this is one of the values that we recorded earlier).
VNR allows us to then set the hex editor to Page View and step through the dump at increments of exactly one block in size. This will help us later too as the hex editor will also display exactly one block, we can extract the entire XOR key very simply and then save it too.
Open the ‘Phy Image’ that you wish to work on by selecting it within the main VNR interface and then clicking on the Dump Viewer item from the Toolbar. This will allow us to open the dump viewer display of VNR. In the Toolbar menu of Dump Viewer, you should ensure that both Hex View and Bitmap View are selected. Also, click on hex view and make sure that ‘Page View’ is selected.
You should now have a Window that looks like the following:
Now for the final UI configuration steps:
1. Go to the Bitmap Viewer tab
At the top left, you will see a field that is labelled ‘Page Size’ with an icon to the right of it consisting of a P and two green arrows. Clicking this icon will set our bitmap view to the Page size that we used in our NAND chip configuration.
2. In Hex Viewer, set the Page Size to the NAND chip ‘Block Size’ that we noted earlier.
3. Now you can do progress in 2 different ways, you can either:
– Use the Slider and arrows to step through 1 block at a time until you locate your key
– Use the scroll bar to the right of the Bitmap View and try to locate a pattern this way
When the key and architecture are unknown (as is common with new and/or unsupported devices), there is no exact science to locating a key however, there are some things to bear in mind. Normally the device’s controller utilises the blocks at the very start of the flash memory to store firmware code. This area may include info pertaining to the logical layout of the data on the flash, translator tables and a whole host of other information. Skipping through this 1 block at a time can be time consuming. Often, we jump 32 blocks, if there is no data, we jump to block 64, then 128 and so on. Once we have located a persistent area of data we can revert to stepping through at a block per time until we find the key.
In the image below we have been lucky, we have two consecutive blocks containing the Xor key, this is very useful when it comes to extracting a ‘clean’ key.
Things can become more complex with certain controllers. Phison, for example, do not always use keys that are exactly 1 block in size. When this scenario is encountered it becomes necessary to use the bitmap viewer to identify the repetition period for the key. This process is a little less precise than the one that we use to determine a full block XOR key.
This should not prove to be too much of a problem as the block size is wholly divisible by the XOR key size, so we can still use a full block as our key, it is just that the key will be larger than it needs to be.
4. Extraction of multiple copies of the key
Having found 1 copy of the key, we are left with a problem. There is a chance that our extracted block contains a whole uncompromised key however, this is not likely.
We have a few things that we still need to consider:
– The key may contain areas that have been corrupted by data, so far we have no way to tell if the key is pure XOR key or whether it is just an area with a high concentration of 0x00 (zeros) or 0xFF.
– We have not considered ECC,the extracted key is likely to contain bit errors and we have not considered this in our extraction either.
– There is still the possibility (however, it is unlikely) that this is an area that was written with a pattern that was not as simple as 0x00 or 0xFF. This pattern may repeat the same byte over the entire key area or it may be 2 bytes or more that are repeated.
To stand the best chance of mitigating the above issues, we need to extract three copies of the key from different areas of the dump. If we know that the dump contains a specific dataset, we may choose three consecutive blocks – if we cannot be sure about that, it is always better to try to find three blocks that are from different locations on the NAND.
Once we have located our key, we can select the entire block within the hex editor (This can be done by clicking and dragging or by using Ctrl+A). In the ‘Dump viewer’ tab use ‘Save selected’ to save the key to your case folder, repeat this process for the second and third areas, as shown on the picture below.
Once we have our 3 areas, we can then begin the process of cleaning the key. The key can be cleaned regardless of ECC as the likelihood of bit errors, even on TLC memory, that affect the exact same bit as on the two other versions that we have extracted is minimal to negligible, that said, it is not entirely impossible for this to happen, so be aware of it. If the ECC type is available and usable within VNR, it is ideal to work on a green coloured block, this reduces one of the unknowns from the equation by eliminating the possibility of ECC errors within our extracted keys. Ideally, blocks from the ECC map that are red should be avoided wherever possible.
5. Bit verificator
Now that we have our samples of the XOR key, we can clean them. Often, particularly if we have enabled ECC through VNR, our key will already be pretty clean however, we cannot rule out that actual data exists in the key area which would corrupt the extracted key. If the key is completely new to us, we cannot rule out that there may be data of a specific pattern hidden beneath the pattern – what we can do is minimise the likelihood of either bit errors or occasional character existing within the key, corrupting the extracted version.
For this we use the ‘Bit Verification’ feature of VNR. Bit verificator takes inputs and compares them. Where two of the three inputs contain identical data and a third is not consistent, bit verificator ignores the inconsistent element and works with the other two. This process is not fool-proof however, it is very reliable in practice, particularly when combined with ECC.
Now open the extracted keys from the VNR Workspace. Use the ‘Open physical images’ menu item, you can select all three at the same time, they will be added to the VNR workspace. We can now verify them.
To use Bit Verificator, you do the following:
A. Add the Bit Verificator ‘V’ element to the VNR workspace
B. Check that the number of elements is set to the number of versions of the key that you have extracted
C. Join each extracted key to the Verificator
You should be left with the following:
6. Removal of Marker structures and ECC
In most cases the Xor scrambler pattern applies only to the data area of the flash memory, some controllers also implement it over the spare area as well but this is less common. For this example we only need to remove the scrambler from the data area. We will remove the ECC, and spare areas from the extracted keys entirely. As we have already defined the structure of the flash, this process is simple:
A. Right click on a dump that has a defined structure and choose ‘Copy structure to buffer’
B. Right click on the ‘Bit verify’ element and choose ‘Paste structure from buffer’
C. Add the ‘Data area’ element and join it to ‘Bit verify’, set Structure dump to ‘Data Area’ as below.
7. Saving the ‘Clean’ Xor key
In the above steps we have removed the SA and ECC structures from our key. We now need to save the key, with the Data area element selected, choose the Dump viewer menu item and then choose Save all. The naming conventions for Xor keys are laid out in Visual NAND Reconstructor Book Part 2. Software
You can now apply the Xor key by setting it as the source file of the Xor element in the VNR workspace.
8. Creating a XOR key extraction device
In certain circumstances, sometimes for research, other times when it has not proven possible to locate a XOR key using the above method, it becomes necessary to locate a flash memory device which can be used for key extraction.
The best way of achieving this is to use a hex editor to fill a working device with a known pattern, 0x77. 0x77 creates an asymmetric binary pattern on the flash media which is easy to identify and remove later.
Once filled we should see a repeating pattern however, this IS NOT the XOR key, IT IS the XOR key XORed with 0x77. If you follow the above process for extraction and save the key, you can later XOR it by 0x77 with any good hex editor or binary file manipulation tool to obtain the original XOR key.
After the key is applied, I cannot find any file system metadata
Often this is due to the flash being inverted, add an invert ‘I’ element to the Xor element and try again, if this process fails it could be that the extracted key was not from an area containing 0x00 or 0xFF. If this is the case you may need to search for the key again or extract the key from a matching, working device which you have first written a known test pattern (eg. 0x77) to.
When I apply the Xor key there are lots of errors and I cannot extract usable data
This could be a combination of problems, the most likely ones are:
• The Xor Key is not quite correct which is leading to uncorrectable ECC errors – you should try to re-extract the key and check that you have cleaned it with Bit verify – try try to find keys from another area of the flash or another dump if possible
• There are simply too many bit errors within the dump, please see this article
• The image has not be reconstructed properly, check out the case sample here
The dumps appear to be XORed but I cannot locate a key
This happens sometimes, please check whether an existing key will fit, these should be in your VNR install folder, if not, they can be downloaded from the Client Portal
When I try to select an entire block in the hex editor VNR crashes
This can happen on rare occasions and is normally a result of the chip’s structure being defined incorrectly. You should follow this guide and try the case sample to familiarise yourself with the process. This can also happen if you have migrated your dump files form another application.
- Examine the case. Follow all steps of Xor extraction and and check all parameters.
- Remove all elements except PhyImage, then analyze dump in bitmap/hex, and exctract Xor (Scrambler) key.
- Apply the Xor key and find data patterns in bitmap.