In this post, I’ll suggest some more algorithms and strategies that could be used as part of a PKLITE-compressed EXE decompression utility.
For an introduction to PKLITE, and a list of the other posts in this series, see Part 1.
This post uses some of the EXE jargon defined in my post on DOS EXE format.
Scope of this post
Suppose you want to write a robust static PKLITE decompressor, that will support almost all qualifying PKLITE-compressed DOS EXE files.
Some such files have deliberately disguised by one of a number of PKLITE “protector” utilities, and others have been hacked by hand. You want your decompressor to support most such files, perhaps without even being aware that they were supposed to be protected.
There are also some “white hat” PKLITE patchers which, for example, fix bugs in PKLITE. You want to support such patched files.
There are some “special” versions of PKLITE-compressed files, usually labeled as v1.10 or v1.20. I won’t cover those files, because (for one thing) I don’t know how to decompress them.
I won’t cover the 1.00beta version of PKLITE. While it’s pretty easy to deal with, I think it would be better to cover its differences in a separate post.
I won’t offer a good, efficient way to detect whether a file is PKLITE-compressed. However, if the file turns out not PKLITE-compressed, or is not a supported PKLITE variant, the strategy I’m suggesting should eventually fail gracefully, as opposed to producing garbage.
I won’t offer a way to determine the precise version of PKLITE that compressed the file.
Overview of strategy
The decompression strategy will consist of these steps:
- Read the outer EXE header, to find the special offsets of the file (entry point, etc.).
- Figure out the compression parameters. That’s mainly what this post is about.
- Decompress the compressed code image, to a memory buffer. (Refer to Part 3.)
- Decompress the compressed relocation table, to a memory buffer.
- Read the footer.
- Determine if the copy-of-original-EXE-header is available. If not, construct a header.
- Write the decompressed file.
There are just a few compression parameters that you always need to determine:
- The offset of the compressed code image
- Whether the compression mode is “large”, or “small”
- Whether “extra” compression is used
- Whether the file was made by the beta version of PKLITE
In a previous post, I suggested you might need to know whether the “uncompressed region” feature was used. I now think you don’t need to know that in advance. But I still don’t know how to decompress such files (and I’ve never encountered one).
Notes on identification
Although identification of PKLITE-compressed files isn’t the goal, here are a few things to consider. I would suggest, though, that a dedicated PKLITE decompressor should not be too quick to screen out files that violate these norms.
The IP register field (in the outer EXE header) is normally 256, and CS is −16. But in MEGALITE files (more on that later), both are 0.
The number of relocation table entries (in the outer EXE file) is normally either 0 or 1. But I found one (presumably hacked) file in which it is 2.
The entry point is equal to the start of the code segment. I haven’t found any exceptions to this rule, other than the beta version.
EXE files are supposed to start with signature bytes “MZ”, but for some reason MS-DOS tolerates “ZM” as well. PKLITE will only compress files that start with “MZ”, and the files it generates always start with “MZ”. But there are multiple PKLITE protector utilities that change the signature to “ZM”, so a good decompressor needs to tolerate “ZM”.
The bytes at the entry point match the pattern B8 ?? ?? BA or 50 B8 ?? ?? BA for all pristine files, and for low-tech protected files. But there exist high-tech protection utilities (e.g. UN2PACK and MEGALITE) for which this is not the case.
Diagrams
Here’s an annotated partial hex dump of a typical file compressed with PKLITE v1.15:
Here’s the same file, compressed with the “extra compression” option:
The “\\\” shaded region shows the bytes that are “scrambled”, and will be different in every file.
When to read the inner EXE header
Normally, PKLITE-compressed files that don’t use extra compression contain a copy of the original EXE header (DOS header and custom-data-1 section). In a previous post, I may have suggested using some information from that header during decompression. It can be helpful to know the expected size of the decompressed data, and the size of the relocation table.
But I think that is a bad idea when writing a robust decompressor. The problem is that there are a lot of files in which some or all of the original header has been corrupted or erased.
It’s a chicken-and-egg problem. To decide whether the original header is valid, you really need to decompress the file first. Then you will know what some of the fields in it should be, and can better decide whether to trust it. Since you can’t know if it is trustworthy until after you finish decompression, you can’t use it as part of your decompression routine.
The “shape” of the decompressor
It is sometimes important to know the version, or version range, of PKLITE that seems to have created the file. I think of this as the “shape” of the embedded decompressor.
There are a number of different ways to go about this. The one I’m suggesting here is to fingerprint the bytes starting at the entry point.
At some point, you’ll have to detect files made by the beta version. There are several ways to do that, and it’s hard to pick one. I guess I’ll just say that if bytes at the entry point start with 2E 8C, then you should stop, unless you support the beta version.
v1.00beta: 2E 8C
The rest of this step can be deferred until you determine that it would provide useful information. But it’s logical to do it now.
Look at up to 36 bytes starting at the entry point, and test them against the patterns below. For some versions of the format, the “Not enough memory” error message begins in this range. In those cases, the patterns are designed to disregard the bytes that would make up the error message, as they can’t be trusted.
The ?? bytes are to be treated as wildcards.
v1.00-1.05: B8 ?? ?? BA ?? ?? 8C DB 03 D8 3B 1E 02 00 73 1D 83 EB 20 FA 8E D3 BC 00 02 FB 83 EB ?? 8E C3 53 B9 ?? ?? 33 v1.12-1.13: B8 ?? ?? BA ?? ?? 05 00 00 3B 06 02 00 73 1A 2D 20 00 FA 8E D0 FB 2D ?? 00 8E C0 50 B9 ?? ?? 33 FF 57 BE 44 v1.14-1.15: B8 ?? ?? BA ?? ?? 05 00 00 3B 06 02 00 72 1B B4 09 BA 18 01 CD 21 CD 20 v1.50-2.01: 50 B8 ?? ?? BA ?? ?? 05 00 00 3B 06 02 00 72 ?? B4 09 BA ?? ?? CD 21 B8 01 4C CD 21 MEGALITE: B8 ?? ?? BA ?? ?? 05 00 00 3B 2D 73 67 72 1B B4 09 BA 18 01 CD 21 CD 90
If the file matches one of these patterns, remember which one it matches, for future reference. If it doesn’t match any of the patterns, that’s okay — keep going.
These patterns are undoubtedly not as good as they could be. It’s difficult to decide exactly how strict to be.
MEGALITE is evidently a hacked version of PKLITE v1.14. You probably won’t encounter any files made by it, but it’s relatively easy to support. It just requires a bit of special handling.
Search for the “tables” section
If you look at a PKLITE-compressed file in a hex editor, you’ll probably see a distinctive pattern of bytes that looks something like this:
03 00 02 0A 04 05 00 00 00 00 00 00 06 07 08 09 01 02 00 00 03 04 05 06 00 00 00 00 00 00 00 00 07 08 09 0A 0B 0C 0D
Or this:
04 00 05 06 07 00 00 00 00 00 08 09 0A 0B 0C 19 00 00 00 00 00 0D 0E 0F 10 11 12 00 00 00 00 00 13 14 15 16 17 18 01 02 00 00 03 04 05 06 00 00 00 00 00 00 00 00 07 08 09 0A 0B 0C 0D
I don’t know what these bytes are for, but I’d guess that they are lookup tables that are a critical part of the decompressor. I’ll call it the “tables” section.
The first pattern appears in files that use “small” compression, and the second is for “large” compression. In both cases, it ends with the same 23 bytes:
01 02 00 00 03 04 05 06 00 00 00 00 00 00 00 00 07 08 09 0A 0B 0C 0D
Searching for this 23-byte sequence seems like a good idea, for a number of reasons:
- The bytes are distinctive enough that they shouldn’t accidentally occur in a non-PKLITE file.
- It would presumably be very difficult for a troublemaker to modify them, and have the file still work.
- The bytes occur right before the compressed code section, the location of which is a critical piece of knowledge that you’ll need.
- The byte just before the
01 02sequence tells you, with virtual certainty, whether the compression mode is “small” (09), or “large” (18). - Cases where tables section can be found correlate well with the types of PKLITE files that I know how to decompress.
So far, so good. Unfortunately, there are some issues:
- In v1.14+ with extra compression, the tables section is in a part of the decompressor that is “scrambled”. So, if you don’t find the tables section initially, you need to descramble the part of the file in which it might occur, and search again. See the “Descrambling” section below for how to do that.
- V1.50+ without extra compression has an extra
90byte after the0Dbyte. I don’t know if this byte is significant, or is just an unused artifact of some sort. - V1.14 with extra compression, and only this version, is (after descrambling) missing the final two bytes (
0C 0D). I have no explanation for this. I wonder if it could be a bug.
Because of v1.14/extra, you should only search for these 21 bytes:
01 02 00 00 03 04 05 06 00 00 00 00 00 00 00 00 07 08 09 0A 0B
Call this the “signature string”. If you can’t find the signature string, the file is most likely one of the special “v1.20” versions that I don’t know how to decompress, or it is not a PKLITE-compressed file at all.
The problem with these inconsistencies is that it makes it hard to be sure where the table ends. And finding the end of it is important.
In all of the files I’ve looked at, I find that it’s safe to assume the length, starting with the 01 02 bytes, is 23 bytes. (24 bytes also works.). Unfortunately, I can’t be sure that’s true for all PKLITE-compressed files in existence.
So, where exactly in the file should you search for the signature string? I can’t say precisely, but I think it’s good enough to start at entry_point+336, and search through entry_point+850.
Suppose you find the signature string starting at offset N. Add 23 to N, then (if that is not already a multiple of 16) round up to the next multiple of 16. Call this the “compressed code offset”.
Descrambling
In v1.14+ with extra compression, the bulk of the decompressor is scrambled, to make it more difficult to analyze. (You could say it’s encrypted, though that might be an overstatement.) This is alluded to in the release notes:
- Changes have been made to make this version more resistant to "disliting".
The scrambling key/seed seems to be derived from the system clock. Compressing the same file twice results in two different compressed files.
The descrambling algorithm is simple: To descramble the byte at file offset N, XOR it with the (scrambled) value of the byte at offset N−2.
[Edit: It turns out that this descrambling algorithm is not correct, though it’s close enough. See my follow-up post on descrambling.]
The nice thing about this algorithm is that you can descramble starting at any position. You don’t have to know where the scrambled section starts. If you don’t know exactly where it ends, then you will get some trailing garbage, but that isn’t really a problem.
Detecting extra compression
It is critical to accurately detect whether extra compression is used. If you mis-detect it, decompressing the code section will seem to go smoothly, but the decompressed data will be garbage. (Decompressing the relocation table, on the other hand, can sometimes go detectably wrong. For example, you may reach the end of the file prematurely.)
If the tables section was scrambled, set extra=true, and you’re done.
If the decompressor is shaped like v1.14-1.15, v1.50-2.01, or MEGALITE, then set extra=false (because otherwise, the tables section would have been scrambled).
If the decompressor is shaped like v1.00-1.05 or v1.12-1.13, look at the two ?? bytes that matched the B9 ?? ?? 33 part of the fingerprint pattern. If they are C3 00, C4 00, 22 01, or 23 01, then extra=false. If they are C7 00, C8 00, 25 01, or 26 01, then extra=true.
If you still don’t know the answer, you’ll have to fall back on methods that are less reliable.
If the start-of-DOS-code-image value calculated from the outer EXE header is 80 or 96, then it’s a good guess that extra=true. If it is 112 or higher, then extra=false.
If the start-of-DOS-code-image is less than 80, then this is apparently a kind of hacked file that I’m not familiar with. Guessing that extra=false might be the best option, but who knows? Another option is to trust the “info bits” field, i.e., the 0x10 bit from the byte at offset 29 from the beginning of the file.
Putting it together
You now have what you need to decompress the main part of the file, find the compressed relocation table, decompress that, find the footer, and read that.
After that, it’s time to write out the decompressed file. If the compressed file contains a copy of the original header, that makes it easier. But deciding if this copy is trustworthy is a nontrivial problem. I suggest verifying that all the fields in the footer are identical to the corresponding fields in the copy. You could also verify that the size of the relocation table matches what you decompressed, that the decompressed code image size matches what the copy implies.
Write the headers
If you have a valid copy-of-original-EXE-header:
Determine the size of the copy by peeking inside it to read the start-of-relocation-table field. Subtract 2, to account for the missing “MZ” signature. Make sure the size is valid before you do anything with it — it must be at least 26, and not so large that it overlaps the code image segment of the outer EXE file.
Also validate that the decompressed relocation table won’t overlap the decompressed code image segment.
- Write an “MZ” signature.
- Copy the copy-of-original-EXE-header to the new file.
- Write the decompressed relocation table.
- Write enough padding bytes (can be zero valued) to get to the start-of-DOS-code-image position indicated by the copy.
If you don’t have a valid copy-of-original-EXE-header:
Decide where you’re going to put the new relocation table. Generally, it should be at offset 28.
Decide where you’re going to put the new code image segment. It can go at any position after the relocation table that is a multiple of 16 bytes. You can use the lowest such position. Another non-silly option is to round up to the next multiple of 512 bytes, as was often done in the DOS era (though I don’t know if there’s a good reason for this).
At this point, I’m going to assume knowledge of the format of the standard 28-byte DOS EXE header. Search the internet if you need something to refer to.
The “checksum” or “checknum” field (offset 18) and the “overlay index” field (offset 26) can be set to 0.
Considering the fields supplied by the footer, you can now calculate the value of all the fields in the new 28-byte DOS header, except for min-memory-needed (offset 10) and max-memory-requested (offset 12). Reconstructing these fields as accurately as possible is, I think, a very difficult problem, and I don’t have the answer to it. No two PKLITE decompressors seem to do it quite the same. However, getting these fields just right is not particularly important, especially in the year 2022. You can get something that’s probably good enough just by copying them from the outer EXE header of the PKLITE-compressed file.
- Write the newly constructed 28-byte header.
- Write the decompressed relocation table. (Write padding first, if you chose an offset larger than 28.)
- Write enough padding bytes to get to the start-of-DOS-code-image position you selected.
Write the rest of the file
- Write the decompressed code segment.
- If there’s anything in the “overlay” segment, copy it unchanged to the new file.
This completes the decompression process.
Entropymine 