General hints for newbie cryptanalysis
Ray Ingles
"Aliens versus Predator". I've managed to add a few things to the Linux
port and I'm working on a few others.
One irritating thing is that the files are stored encrypted on the
install CD, and the Windows install executable (that does the
decryption) doesn't easily work under Linux. You need to use VMWare or
a real Windows box to install the files. After that you can copy the
game data to Linux, but installation is a bit of a pain.
I've been looking into how hard it would be to break the encryption on
these files. (Note: I am *not* trying to violate copyright. I'm just
trying to make it possible to install these files from a valid CD under
Linux.) Since I have decrypted versions of these files from a Windows
install, it becomes basically a known-plaintext attack.
I've done some (very) simple checks - e.g. some simple XORs of the
encrypted and plaintext versions, by byte or short or integer. No
trivial solutions, but it's clear that it's not a complex algorithm -
comparing a plot of the plain file vs. the encrypted one, you can see
that different 'regions' of the files look different.
By good fortune one of the (unencrypted) files has a long sequence that
basically looks like a sawtooth when plotted - and the 'encrypted'
version appears to follow that pattern, only the values are spread into
'clouds' that have similar (but not identical) internal patterns. They
are of slightly varying lengths - 16 to 18 integers long.
Given that (skimpy) info, any suggestions for likely means of attack?
Suggestions for further reading?
--
Sincerely,
Ray Ingles sorce...@gmail.com
"These modern kids don't know the simple joy of saving four bytes of
page-0 memory on a 6502 box." - isomeme
Phil Carmody
> By good fortune one of the (unencrypted) files has a long sequence that
> basically looks like a sawtooth when plotted - and the 'encrypted'
> version appears to follow that pattern, only the values are spread into
> 'clouds' that have similar (but not identical) internal patterns. They
> are of slightly varying lengths - 16 to 18 integers long.
Look at the trigrams containing 2 identical bytes in the plaintext.
("ABB"). Is there any relationship between E(B_1) and E(B_2)? If so,
does it seem to depend on B, or on E(A_1). For 'dependency', just
throw tallies into buckets, and see if there's a trend.
Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.
Joseph Ashwood
news:slrnelf16m....@grayswandir.ingles.homeunix.org...
Keeping in mind that this is probably still illegal, and so if you do this
you really are on your own. Decompile the windows installer, it will have
the algorithm and the key.
Joe
Luc The Perverse
news:slrnelf16m....@grayswandir.ingles.homeunix.org...
> basically looks like a sawtooth when plotted - and the 'encrypted'
> version appears to follow that pattern, only the values are spread into
> 'clouds' that have similar (but not identical) internal patterns. They
> are of slightly varying lengths - 16 to 18 integers long.
>
> Given that (skimpy) info, any suggestions for likely means of attack?
> Suggestions for further reading?
Even a simple XOR RAND() wouldn't yield this.
It sounds like you are describing some sort of simple bit (or byte) shuffle.
Your best bet is probably decompilation (and it sounds from your description
of the problem that this is likely within your realm of expertise.)
If you are doing this for fun - then I would try bit counting. See if there
are bit boundaries which yield consistantly equal numbers of bits from the
"decrypted" and and "encrypted" versions.
Still though - a bit/byte shuffle using a cryptographically secure PRNG
would probably not be "crackable" without the key. Your best bet is
decompilation.
If you are lucky the obfuscation/decryption code will be contained in a
simple function that will be easy to identify.
--
LTP
:)
TC
Ray Ingles wrote:
> One irritating thing is that the files are stored encrypted on the install CD,
Why do you say that the files are encrypted? There'd be little point in
doing that, because the decryption key would have to be stored on the
CD. So that scheme would be easily cracked. It's far more likely that
the files are just compressed - not encrypted.
> By good fortune one of the (unencrypted) files has a long sequence that
> basically looks like a sawtooth when plotted - and the 'encrypted'
> version appears to follow that pattern,
This suggests that the file is /not/ encrypted. Typically, an encrypted
file will not show any patterns at all; the data will look totally
random.
HTH,
TC (MVP MSAccess)
http://tc2.atspace.com
TC
TC wrote:
> Ray Ingles wrote:
>
> > One irritating thing is that the files are stored encrypted on the install CD,
>
> Why do you say that the files are encrypted? There'd be little point in
> doing that, because the decryption key would have to be stored on the
> CD. So that scheme would be easily cracked. It's far more likely that
> the files are just compressed - not encrypted.
PS. My comment about the decryption key was based on the assumption
that you did -not- have to enter a key when you installed the CD. Hmm,
I'm not sure why I made that assumption! However, even if you -did-
have to enter a key, this still doesn't say that the files are
encrypted. In the installer programs that I know, the list of valid
serial #s (within the installer exe) is encrypted, but the other files
(within that exe) are not encrypted - they're only compressed.
sorce...@gmail.com
> Ray Ingles wrote:
> > One irritating thing is that the files are stored encrypted on the install CD,
> Why do you say that the files are encrypted?
Because they are *precisely* the same length as the files that are
eventually stored on the hard drive, but contain different data. I
should have mentioned that before.
> There'd be little point in
> doing that, because the decryption key would have to be stored on the
> CD. So that scheme would be easily cracked. It's far more likely that
> the files are just compressed - not encrypted.
I suspect that the scheme was not intended to be forever uncrackable,
just to be annoying enough to throw up an obstacle to casual copying.
To elaborate a bit, the normal install procedure is as follows:
1. Insert install CD, run install excutable.
2. Upon prompting, swap out the install CD for the second CD, an
(apparently standard) audio CD that contains the in-game music. Some
kind of CD-check is done at this point - one that doesn't work under
WINE.
3. Restore install CD, continue installing.
> > By good fortune one of the (unencrypted) files has a long sequence that
> > basically looks like a sawtooth when plotted - and the 'encrypted'
> > version appears to follow that pattern,
>
> This suggests that the file is /not/ encrypted. Typically, an encrypted
> file will not show any patterns at all; the data will look totally
> random.
As I stated, I strongly suspect the 'encryption' scheme is
unsophisticated - obviously it's not any kind of block cypher. It may
be as simple as storing the bytes out-of-order. But I have little
experience cracking encryption schemes, even crude ones, so I was
hoping to get some suggestions to narrow my search, thinking that
perhaps my descriptions might sound similar to a scheme someone had
encountered before.
Sincerely,
Ray Ingles (313) 227-2317
"Economies don't like step functions." - Dr. Leonard Bieman
TC
sorce...@gmail.com wrote:
> TC wrote:
> > Ray Ingles wrote:
> > > One irritating thing is that the files are stored encrypted on the install CD,
> > Why do you say that the files are encrypted?
>
> Because they are *precisely* the same length as the files that are
> eventually stored on the hard drive, but contain different data. I
> should have mentioned that before.
But how do you know the length of each file *inside the installer exe*?
I don't see how you could know that, unless you knew the detailed
structure of the relevant portions of that exe file.
Are you absolutely certain that the total size of the extracted files,
is not greater than the size of the installer exe? Because if it *is*
greater, then, the installer exe must be using some compression.
sorce...@gmail.com
> sorce...@gmail.com wrote:
> > Because they are *precisely* the same length as the files that are
> > eventually stored on the hard drive, but contain different data. I
> > should have mentioned that before.
>
> But how do you know the length of each file *inside the installer exe*?
Ah, I see the confusion. They are not *inside* an "installer exe".
There is a "setup.exe" executable, but there are also directories with
files, layed out exactly as they are when installed. I should have made
that clear before.
E.g., on the CD, there is a directory called "fastfile". Inside that
directory, there are a bunch of files like "Tex1.FFL", "Tex2.FFL", etc.
Here's a series of commands:
cd /media/cdrom/fastfile
ls -l Tex1.FFL
-r-xr-xr-x 1 sorceror sorceror 375580 2000-02-08 09:00 Tex1.FFL
ls -l ~/projects/avp/game/fastfile/tex1.ffl
-rwxr-xr-x 1 sorceror sorceror 375580 2000-02-08 13:00
/home/sorceror/projects/avp/game/fastfile/tex1.ffl
diff Tex1.FFL ~/projects/avp/game/fastfile/tex1.ffl
Binary files Tex1.FFL and
/home/sorceror/projects/avp/game/fastfile/tex1.ffl differ
cd ..
ls -l SETUP.EXE
-r-xr-xr-x 1 sorceror sorceror 60416 1998-01-22 17:08 SETUP.EXE
So, the files after install are exactly the same size as on the CD,
but they are different internally, and the installer executable is far
too small to contain the actual game data, which on-disk is ~500MB.
For the example file I picked:
The 'encrypted/encoded' version:
od -x Tex1.FFL | head
0000000 c89c e8f4 c1c5 c9cd f1a5 f9fd e946 e9ed
0000020 f2d4 9989 8185 898d ae3d b9bd ebdb eb28
0000040 fff7 8fc3 74d7 8783 b783 cbb7 efe3 83e3
0000060 abab 504f 2ccf 09db 2ea4 393d d7a7 292d
0000100 1b4b 1b5b 6f67 1873 c0a0 101c 001c 4400
0000120 2878 3c20 5439 a0b4 b891 8554 adb3 b5b5
0000140 a009 a5b9 97c7 97d7 fbf3 8bcf 70d3 838f
0000160 b38f f7b3 bf97 43af 7b83 cf50 db2c 3509
0000200 c3a2 2525 d3a3 d429 0777 0747 6b63 0458
0000220 ccac 1c18 0c18 400c 1c68 3918 b454 91a0
The 'unencrypted', installed version:
od -x ~/projects/avp/game/fastfile/tex1.ffl | head
0000000 4652 4c46 0000 0000 0014 0000 02d8 0000
0000020 b830 0005 0000 0000 c522 0000 7267 7061
0000040 6968 7363 435c 6d6f 6f6d 5c6e 6161 665f
0000060 6e6f 2e74 4952 004d c524 0000 4360 0000
0000100 7267 7061 6968 7363 435c 6d6f 6f6d 5c6e
0000120 7562 6e72 522e 4d49 4900 004d 0884 0001
0000140 431e 0000 7267 7061 6968 7363 435c 6d6f
0000160 6f6d 5c6e 6c63 756f 7964 522e 4d49 0000
0000200 4ba4 0001 4360 0000 7267 7061 6968 7363
0000220 435c 6d6f 6f6d 5c6e 6765 2e67 4952 004d
Some interesting patterns with the "0000" bytes there, but they don't
seem to hold further on. Ah, well.
Sincerely,
Ray Ingles (313) 227-2317
"If these aliens are so magically powerful, how come you
never see any forest circles? Or mountain circles?" - Me
TC
sorce...@gmail.com wrote:
> TC wrote:
> > But how do you know the length of each file *inside the installer exe*?
>
> Ah, I see the confusion. They are not *inside* an "installer exe".
> There is a "setup.exe" executable, but there are also directories with
> files, layed out exactly as they are when installed.
Ok, I see now.
It might be interesting to see if you can find another installation CD,
& install it on another PC. Are the "input" files identical on the two
CDs, and are the "output" files identical on the two PCs? Perhaps that
would shed some light on it.
I also found a reference to someone else's linux port of this game. Ask
Mr Google for more information :-)
TC
sorce...@gmail.com wrote:
> E.g., on the CD, there is a directory called "fastfile". Inside that
> directory, there are a bunch of files like "Tex1.FFL", "Tex2.FFL", etc.
Maybe these would help with the FFL files:
http://groups.google.com/groups?hl=en&lr=&q=%22Aliens%20versus%20Predator%22%20%20ffl
http://www.google.com/search?hl=en&lr=&q=%22Aliens%20versus%20Predator%22%20%20ffl
Ray Ingles
<sll_noSpamli...@cc.usu.edu> wrote:
> "Ray Ingles" <sorc...@grayswandir.ingles.homeunix.org> wrote in message
> news:slrnelf16m....@grayswandir.ingles.homeunix.org...
I think it may be some of that and some very simple additive noise.
> Your best bet is probably decompilation (and it sounds from your description
> of the problem that this is likely within your realm of expertise.)
Well, I may resort to that, but I have a hunch the algorithm is pretty
simple, and I'm looking to further my education by stretching my knowledge
a bit.
> If you are doing this for fun - then I would try bit counting. See if there
> are bit boundaries which yield consistantly equal numbers of bits from the
> "decrypted" and and "encrypted" versions.
Hmmm. I will give that a shot. Thanks for the suggestions!
Ray Ingles
> It might be interesting to see if you can find another installation CD,
> & install it on another PC. Are the "input" files identical on the two
> CDs, and are the "output" files identical on the two PCs? Perhaps that
> would shed some light on it.
I can probably at least get some md5sums of the files and see if they
match.
> I also found a reference to someone else's linux port of this game. Ask
> Mr Google for more information :-)
Yup, that's what I'm working with. I've added the in-game music and I'm
working on getting the in-game movies going (getting my head around
libavcodec). Being able to write a Linux installer would pretty much
make the game feature-complete. Thanks for your suggestions!
bill...@gmail.com
typical encryption algorithm (and which one).
http://peid.has.it/