Progress... A detour into big numbers and encrypted headers.

[Blade]

Okay, so we recently wrote a MapClass implementation as part of our drive to get map drawing done. This handles the cell grid and a bunch of stuff relating to it and with a bit of glue code it might be enough to get a basic map renderer on the go. In the game its one of the lower classes in a hierarchy of inherited classes that control all the aspects of the in game UI, so to get something basic drawing as it does in the game, there is still a bit of work ahead. After that we've taken a change of pace into some code that we previously investigated, but struggled to get a working implementation going.

 

The code in question is the internal "Multi Precision Integer" library that is used to do the RSA part of the mix header encryption. Now we have header decryption working as it is using an embedded library, but if we stay with that library we are bound to its license terms so really we wanted our own version of the games internal "XMP" library. In fact the code everyone and their dog uses to handle the encrypted headers, the XCC decryption code, is pretty much already the code from the game reversed to C. It has problems however, for a start, GCC seems to hate compiling it with optimizations. Secondly, its not big endian friendly which might harm future attempts to port the code to systems other than x86.

 

For all these reasons we started writing our own implementations and its pretty straight forward like doing long addition, subtraction, multiplication and such like you learned at school only with each "place" in the number being a 32bit int rather than 0-9. It all went well until we got to the "modular" operators, specifically modular multiplication.

 

If you've ever looked into the XCC code, this is done by a function called calc_a_bignum there, but its really the Thad Smith Modular Multiplication algorithm as far as we can tell. In fact it looks like the WW coders were heavily influenced in their algorithm choice by the PGP algorithms (presumably as that was one of the few crypto libraries with available source at the time). It does some crazy bit shift magic to speed up calculating this value and even in the PGP code it is hard to follow, much less the XCC code version. So crazy in fact that currently we still can't get a fully 32bit version to work, we've had to resort to a simpler algorithm based on long division to calculate the modulo of the multiplication result. Its not as fast, but it does mean that we finally have a home grown "Multiple Precision" library that can decode mix file headers.

 

Now, back to those scenario hierarchy classes....

 

Edit:

I've managed to implement an alternative to the Thad Smith algorithm that is still fast, so another external library dependency is definitely eliminated.

[Allen262]

Don't have clue what this means but as long as your making progress it is all good!

[CCHyper]

Don't have clue what this means but as long as your making progress it is all good!

 

TL;DR - We did use a public, open source library for RSA (The encryption the mix files use), now we have our own implimentation that OmniBlade has written based on research. Now this is complete, we are no longer tied to any other external librarys and/or licenses!

[Allen262]

Why would you want to lock the mix files?

[CCHyper]

Why would you want to lock the mix files?

 

We don't want to encrypt them within RA++, but need to be able to read/open them, as the original RA did.

 

But it also allows OmniBlade to extend he's tool to make encrypted MIX files the same way WW would have.

[Blade]

Yeah, its Westwood that wanted to lock the mix files to make it harder to retrieve the individual files out of them. We've just had to implement these algorithms to unlock the already locked content. As I mentioned, XCC has had code to do this for a long time now but its messy and pretty much impossible to know what its doing from looking at it.

[Nyerguds]

Just kick out the encryption

[CCHyper]

_

Edited November 17, 2020 by CCHyper

[Nyerguds]

Re-save them all with XCC in advance XD

[SiRaLeX]

The code in question is the internal "Multi Precision Integer" library that is used to do the RSA part of the mix header encryption.

 

Can anyone explain what that means to us mere mortals?! 

 

 

P. S.: I have decrypted mix files through some sort of "known plaintext" attacks before. 

 

P. P. S.: I'd also not really consider it "encryption". I mean you can easily "decrypt" it without knowing any sort of key, so does the game.

 

 

 

[Blade]

Multi precision integers are basically arbitrarily large integers that can be used for calculations that don't fit into the CPU word size. Internally they are normally represented by an array of ints that match the word size for the CPU and the maths is done something akin to the long addition, subtraction, multiplication and division you may have learned in school. It only gets complicated when it needs to do these operations efficiently and using more complicated maths (such as used by RSA which is modular exponentiation).

 

Decrypt the mix files headers? I doubt it unless you already knew the index that the header decrypts to (in which case what was the point again). Note that the body is not encrypted at all, you can read any file directly from it if you know its start an size. Its only that information that is encrypted.

 

You are wrong though, it does involve keys and is actually quite a sophisticated system. When a mix file was created by the original Westwood makemix tool, a random 448bit Blowfish (56 bytes) key was generated. This was then encrypted using the private Westwood RSA key and saved as an 80byte block in the mix header followed by the mix index encrypted by blowfish using the generated key.

 

The game then reverses this, it decrypts the 80byte block using the Westwood public key that corresponds to the private key to regenerate the Blowfish key and then proceeds to decrypt the index so it can work out where files start and end as well as what their ID is so it can find them by name.

 

How then do we have tools that can create encrypted mix files given that Westwood has a private key? Well XCC cheats, it loads an existing encrypted mix and saves its blowfish key in both forms and simply writes the encrypted block unchanged, it makes no attempt to encrypt the blowfish key and its decryption is just reverse engineered from the game as far as I can tell, using the hard coded public key. Olaf wasn't even aware it was RSA to my knowlege. However Westwood also goofed up and with TS released a mix containing a file called keys.ini which as luck would have it, contains the key pair. We've also since discovered that EDWIN also has the private key embedded in it. This went unused until a few years ago when I put some effort into really understanding the mix encryption and now its possible to create mix files with new keys (though not yet with XCC).

[SiRaLeX]

Thanks blade, that's an excellent explanation! Frank "zzattack" told me that MIX files use Blowfish a couple of days ago. But of course your explanation and knowledge of MIX files is much more in-depth and contemporary.

 

So everyone with the WW pub key can unencrypt decrypt the blowfish key used to encrypt the contents of the MIX. Now, the problem is obviously that if you don't have the original WW key pair you cannot generate encrypted MIX files with a blowfish key of your desire. I don't know what EDWIN is. Is it a tool?

 

I've also seen Olaf's blowfish class. The algorithm itself is quite simple. I've particularly had a good laugh at his byte swapping function: https://github.com/OmniBlade/xcc/blob/7b5459984276e84c670a7343bb3fb1a05a976b6e/misc/blowfish.cpp

 

Fun fact: there's an instruction called "bswap" that does all the work for you.

 

Anyways, here's what Frank "zzattack" told me about MIX:

[20.06.2016 12:17:46] SiRaLeX: Hey Frank

[20.06.2016 12:18:05] SiRaLeX: Let me riddle you a ditty, it's just an itty bitty, little thing on my mind

[20.06.2016 15:38:44] zzattack: oo

[20.06.2016 15:46:08] SiRaLeX: BTW, do you know how MIX file encryption works ?!

[20.06.2016 15:46:20] SiRaLeX: Is it actually "encryption" that uses a key

[20.06.2016 15:46:29] SiRaLeX: Or is it just some sort of wild scrambling

[20.06.2016 15:46:39] SiRaLeX: As in

[20.06.2016 15:46:52] SiRaLeX: Does it use a well known and recognized crypto algorithm ?!

[20.06.2016 15:47:11] SiRaLeX: The FOW (fog of war) file from the original foghack was encrypted

[20.06.2016 15:47:17] SiRaLeX: But I've easily unencrypted it

[20.06.2016 15:47:36] zzattack: it uses blowfish

[20.06.2016 15:47:39] SiRaLeX: Right

[20.06.2016 15:47:46] zzattack: it's encryption with a key yes

[20.06.2016 15:47:53] zzattack: but obviously it's fully cracked

[20.06.2016 15:47:54] SiRaLeX: Nice

[20.06.2016 15:48:00] SiRaLeX: Well, yeah

[20.06.2016 15:48:21] SiRaLeX: The way I got ahold of the foghack shp is by just dumping it from memory

[20.06.2016 15:48:44] SiRaLeX: Ain't no need to blow that fish for me

[20.06.2016 15:48:52] zzattack: yea

[20.06.2016 15:49:10] zzattack: did u know stuff in mix files doesnt even have filename

[20.06.2016 15:49:20] SiRaLeX: nah

[20.06.2016 15:49:31] SiRaLeX: I looked at mix file structure once

[20.06.2016 15:49:34] zzattack: its true

[20.06.2016 15:49:37] SiRaLeX: And I know there is an encrypted flag

[20.06.2016 15:49:47] SiRaLeX: And I think each file is prepended with a file name

[20.06.2016 15:50:07] zzattack: to find a file by its original filename, you need to look for the hash of its first 12 or so characters

[20.06.2016 15:50:26] zzattack: the header contains only the hash of the filename

[20.06.2016 15:50:39] SiRaLeX: nice

[20.06.2016 15:50:47] SiRaLeX: Makes for fast lookup, now, init

[20.06.2016 15:50:47] SiRaLeX:

[20.06.2016 15:50:48] zzattack: that's what the "local mix database" file is for

[20.06.2016 15:50:51] SiRaLeX: Sweet-heart

[20.06.2016 15:50:56] zzattack: true that

[20.06.2016 15:51:09] SiRaLeX: Nice tech-niques

[20.06.2016 15:51:14] zzattack: i mean like the file xcc mixer adds

[20.06.2016 15:51:28] zzattack: to every mix after saving

 

 

 

 

 

[Allen262]

EDWIN is the stock map maker for RA1.

[Chad1233]

Off topic but I always wondered if Westwood used a editor built inside C&C/RA1 for mission/mp map making. I know what they used allowed them to place terrain without clearance check unlike edwin.

[Blade]

Off topic but I always wondered if Westwood used a editor built inside C&C/RA1 for mission/mp map making. I know what they used allowed them to place terrain without clearance check unlike edwin.

 

To my knowledge they did. EDWIN was created by stripping out unneeded parts of the game, while the game stripped out much of the editor code. The original editor would obviously have had more features such as being able to place units and buildings, set facings and health and so on.

[Iran]

Yeah they did, it's why there's still a function in the game to write scenario files from the in-game memory. They did the same thing for Tiberian Sun, there are screenshots for it.

 

It's also the reason why you have a few of those debug keys related to 'map' in the exe.

[Nyerguds]

P. S.: I have decrypted mix files through some sort of "known plaintext" attacks before. 

 

P. P. S.: I'd also not really consider it "encryption". I mean you can easily "decrypt" it without knowing any sort of key, so does the game.

 

So everyone with the WW pub key can unencrypt decrypt the blowfish key used to encrypt the contents of the MIX. Now, the problem is obviously that if you don't have the original WW key pair you cannot generate encrypted MIX files with a blowfish key of your desire.

It's not the mix contents that are encrypted. It's just the header containing the files list. So yes, you can dump it in a hex editor and find rules.ini, and sure, someone could create a scanner that looks for SHP file headers to see which data in the mix block are separate files, but being able to read the actual files table in the header sure is a lot handier, even if the filenames in it are just hashes.

 

[SiRaLeX]

It's not the mix contents that are encrypted. It's just the header containing the files list. So yes, you can dump it in a hex editor and find rules.ini, and sure, someone could create a scanner that looks for SHP file headers to see which data in the mix block are separate files, but being able to read the actual files table in the header sure is a lot handier, even if the filenames in it are just hashes.

 

Not encrypting the MIX contents doesn't make any sense. Anyone with half a brain and basic understanding of common file formats can easily make out where a file starts, ends and therefore where the next one starts - as you noticed.

 

Why bother encrypting at all? If it's true then this whole thing relies solely on keeping SHP and the other formats secret.

 

Lol, I just checked this, Nyerguds. You're right. The contents aren't encrypted at all. Funny shit. I expected better from WestWood  :ranting:  nevermind, I realize the MIX I was looking at was created with "XCC by Olaf van der Spek", can't verify if encrypted Westwood MIX files also don't have their contents encrypted, but I'm taking your word.  :puppydog:

 

 

[Nyerguds]

It's really just the headers, yes. See, Red Alert 1 was the first game to have its mix files encrypted, but it took a lot longer for people to actually read these encrypted RA1 mix files' file tables than it took for people to find rules.ini inside the files.

 

In fact I think XCC is the first tool that managed it; the old RAMIX could open the mix archives, and would show the files inside them, but it never even knew about the mixfile-inside-mixfile structure. The creator had just scanned the mix files, found files, and hardcoded tables of the stuff he found into his tool.

[Blade]

I think the idea was to make it harder to enumerate the locations of the files within the mix and make it a bit harder to mod the game, but because it didn't enforce encrypted headers, the normal header format works fine and so new mixes could still be made with the old tool.