A Collision Too-Perfect

Cheeky executables, both MD5 and SHA1 hashes are equal , different run output (“Eat more hashes” Challenge Write-Up)

Licensed cc-by Anonymous http://openwalls.com/image?id=399

Shortly after the first practical SHA1 collision attack was made public, a somewhat short-and-to-the-point challenge was up in the air, a team member that is fully aware of my addictive nature towards challenges with a twist unleashed it at me (thanks, Oren) and, understandably, I had to comply.

The premise is simple — two PE executables, same MD5 and SHA1 hashes against each other BUT as promised — with a twist. Once run, they have a whole different output.

Same hash values, different output. (Screengrab from challenge’s blogpost)

Magic, that’s the only explanation, right?

Right off the bat — you can imagine I tested it on my own environment by a built-in tool, certutil.exe, to confirm this claim. Realizing that’s a solid hash calculation direct us to talk on what can be happening here.

Obviously, both executables are equal in byte-to-byte comparison, but run-time is what makes them different — that brings us to the inevitable conclusion that something extra, probably file metadata (which wouldn’t affect hash sum) is in play.

Let’s take a look at it’s delivery mechanism — it’s a 7z archive. What’s important to note about 7z together with other archiving schemes is that they preserve some of the properties and attributes of files contained within them.

In the given archive case it is not suitable to preserve security information, such as permissions (ACE/ACLs on Windows and any permission scheme appropriate to other environments) on compressed files. Several important metadata sustained throughout (de)compression is Modify/Access dates and of course — file names.

“Bit-Banging” File Properties (excuse the misuse)

To drive a challenge home until solution you would like to save time, and “playing it dirty” is fair game, generally speaking so we start with trying out some probable solutions when we follow the logic above.

So we start by changing the names — unfortunately nothing is changed on output, that doesn’t negate a different process flow altogether, but judging by “proof of the pudding “— it wasn’t affecting anything.

Next, let’s look at those dates side-by-side.

By comparing, we can spot a difference in times, so the assumption will be that changing those dates to fit one another will result in the other’s proper control flow.

Another important fact is that file times are all malleable.

Now, if you just try many of the off-the-shelf tools that you might find over the internet and try to match those times you are mostly destined to fail. I tried like 6 different solutions and none of them have been able to accomplish the task.

Matching times try-out using Nirsoft’s File Date Changer

Luckily, I knew what is the problem but was too lazy to start with the obvious choice of writing my own tool to accomplish it.

You are missing a tick

You can’t miss what you never realized you never had

The thing is the Windows FILETIME structure:

typedef struct _FILETIME {DWORD dwLowDateTime;DWORD dwHighDateTime;} FILETIME, *PFILETIME;

Every file on NTFS adheres to that elaborate time structure, that makes exactly 100 nanoseconds a tick, it is a 64-bit value that can be separated to two DWORD (32-bits on x86-Windows), High and Low, so the granular data is there, you just don’t need it on most processes that the file undergoes.

So, the control flow is not only affected by the general date and time but you need to be more exact as it is testing to see the lower, nanosecond defining, bits as well.

The final solution to this problem was concluded by just setting a short PowerShell script, as I’m not too comfortable with that damn scripting language, I wasn’t too eager to go ahead and use it right from the beginning.

And finally —the challenge was solved. I had a blast, thank you Kinine for this beautiful and insightful riddle. Looking forward for the next one.

Both files are going through the same control flow. WIN!