ctrl-alt-Development

Your hotkey to alternative software development

Mandatory Movies

I love movies, especially if they have a dystopian theme to it. Some of the best:

Liberating Encrypted TPS Files

The Clarion TPS Encryption algorithm explained.
Appeared first on blog.42.nl

Liberating Encrypted TPS Files

My previous article on Clarion TPS files left one big question unanswered: how do encrypted TPS files work and is it possible to decrypt them. In this post I will dissect the encryption algorithm and explain how it works. It involves quite a bit of binary arithmetic and hexadecimal numbers, so take a deep breath before diving in!

First there is the password. It is passed as a parameter to the TPS driver. Oddly enough it is called the ‘owner’ parameter. With the password a key is generated which is used to encrypt and decrypt the data. The effect is pretty dramatic.

A close look at TPS files.

What are the differences between an encrypted and decrypted file?

The block below is the header of an unencrypted TPS file, easily identified by its tOpS identifier at position 0x0E. Also notice the repetitive nature of the data after position 0×0030 – this is the jump table for data areas in the file.

              
00000000h: 00 00 00 00 00 02 00 06 00 00 00 06 00 00 74 4F ; ..............tO
00000010h: 70 53 00 00 00 00 00 12 49 00 00 00 00 00 00 00 ; pS......I.......
00000020h: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ; ................
00000030h: 00 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000040h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000050h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000060h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000070h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000080h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
00000090h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
000000a0h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................
000000b0h: 04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00 ; ................

              

The second block is encrypted data. It looks pretty random. However. If you look more closely you will notice that it is repeating every 0×40 bytes. For example, the data at 0×0040 is the same as at position 0×0080. Identical data leads to identical encrypted data every 64 bytes. Thus the encryption works in blocks of 64 bytes that use the same key (so no key progression or block chaining, fortunately).

              
00000000h: B4 DC 3C 92 90 BC DF 78 B0 5B AF FF A0 F8 30 41 ; ................
00000010h: 00 AE FF D8 F0 BF EF A2 E0 DC FA 57 F7 BF FB B3 ; ................
00000020h: A8 54 DA C0 70 6D 7D EA 30 E9 FD 7A D0 7A FD F4 ; ................
00000030h: D8 FF FE F1 50 F9 BE C1 E4 D3 77 E3 F4 7A FF F1 ; ................
00000040h: B4 DC 5C 92 94 BC DF 78 B4 59 AF F9 A4 F8 DC FA ; ................
00000050h: E4 5D FF D9 E4 BC EF B1 A4 DC FA 73 F4 BF FB 53 ; ................
00000060h: AC 54 DA C0 74 6D FD AA 34 E9 BD FA D4 7A FD D4 ; ................
00000070h: DC FF 7E E1 54 F9 FE C1 E4 D3 77 E3 F4 7A BF F1 ; ................
00000080h: B4 DC 5C 92 94 BC DF 78 B4 59 AF F9 A4 F8 DC FA ; ................
00000090h: E4 5D FF D9 E4 BC EF B1 A4 DC FA 73 F4 BF FB 53 ; ................
000000a0h: AC 54 DA C0 74 6D FD AA 34 E9 BD FA D4 7A FD D4 ; ................
000000b0h: DC FF 7E E1 54 F9 FE C1 E4 D3 77 E3 F4 7A BF F1 ; ................

              

I spent quite some time tinkering with XOR schemes, but there is no fixed relation between the bits and their position in the block. Some pretty clever bit shifting is going on. Time to bring out the big guns: IDA Pro . The Free version worked perfectly on the ancient TPSCOPY tool so I spent some evenings stepping through the assembly. Let me tell you what I found.

Step one: Building the Key from the owner string.

The first step is to convert the owner string (the password) to a 64 byte block that will be the encryption and decryption key. The password is treated as a C string, so a 0×00 is at the end. Funnily enough it starts building this key from the 2nd character in the password, not the first.

Filling the block is done by filling out the block in steps of 0×11 bytes, adding the index to the current value and starting at offset 1:

              
key[(index * 0x11) & 0x3f] = index + password[(1 + index) % password.length]

              

For a short and simple password of ‘a’ this leads to:

              
0000 : 00 92 22 74 04 96 26 78 08 9a 2a 7c 0c 9e 2e 80 ................
0010 : 10 62 32 84 14 66 36 88 18 6a 3a 8c 1c 6e 3e 90 ................
0020 : 20 72 02 94 24 76 06 98 28 7a 0a 9c 2c 7e 0e a0 ................
0030 : 30 82 12 64 34 86 16 68 38 8a 1a 6c 3c 8e 1e 70 ................

              

Notice how the first value is 0×00 (the end of the C string) and the first character at 0×0011 is 0×62 which is ‘a’ + 1. The next value is at 0×0022 and is 0×00 + 2 and so on and so on.

Obviously this key is not nearly random enough. The next step is some interesting bit re-shuffling. It works in 32 bit little endian words, so 4 bytes at a time in reverse order. There are 16 of such words in the key. For each position in the key it takes that word (a) and another indexed by the least significant 4 bits of that word (b). Then it performs the following computation:

              
a' = a + a & b
b' = a + a | b

              

For the first position in the key this means that:

              
a = word[0] = 0x74229200
b = word[0x74229200 & 0x0F] = word[0] = 0x74229200
And thus:
a' = 0x74229200 + 0x74229200 & 0x74229200 = 0xE8452400
b' = 0x74229200 + 0x74229200 | 0x74229200 = 0xE8452400

              

So the first word in the key is replaced by 0xE8452400. Not very spectacular but once the b index is different it becomes quite messy. This shuffle operation is performed twice. Once it is done the key formed from the humble ‘a’ password is unrecognizable, although there are still some patterns visible:

              
0000 : 80 a4 52 70 90 18 dd 68 a0 48 ab f1 a0 f8 dc 48 ................
0010 : a0 5c ee 90 60 b8 ed 21 a0 d4 f8 51 f0 ba fb 10 ................
0020 : 40 22 74 e0 30 69 2d aa 20 e9 ac 72 d0 78 fd c0 ................
0030 : 98 2c 6e 60 50 d1 32 c1 e0 d1 72 e1 b0 7a 3c d1 ................

              

This block of data is used to encrypt and decrypt the tps file and thus forms the Key.

Step 2: Encrypting a block.

Now we have a key, we can attempt to encrypt a block. The encryption algorithm is quite similar to the shuffling algorithm and works indexed as well.

              
k = key[index]
a = block[index]
b = block[k & 0x0F]

a' = k + (!k & b | k & a)
b' = k + ( k & b | !k & a)

block[index] = a'
block[k & 0x0F] = b'

              

It takes two words, one at the current index and one at the index pointed at by the 4 least significant bits of the key value at that position. Then half of the bits of a and half of the bits of b (according to the key mask) are added to the key and assigned to a’. The other half of the bits are added to the key and assigned to b’. Then the values are written back.

Let me show an example on how this works:

              
key = 0xF0F0F0F0
a = 0xFFFF0000
b = 0x0000FFFF

a' = 0xF0F0F0F0 + ( 0x0F0F0F0F & 0x0000FFFF | 0xF0F0F0F0 & 0xFFFF0000)
b' = 0xF0F0F0F0 + ( 0xF0F0F0F0 & 0x0000FFFF | 0x0F0F0F0F & 0xFFFF0000)

a' = 0xF0F0F0F0 + ( 0x00000F0F | 0xF0F00000)
b' = 0xF0F0F0F0 + ( 0x0000F0F0 | 0x0F0F0000)

a' = 0xF0F0F0F0 + 0xF0F00F0F = 0xE1E0FFFF
b' = 0xF0F0F0F0 + 0x0F0FF0F0 = 0x0000E1E0

              

Ok this explains by my XOR tricks didn’t work out. Its much more like the RC5 algorithm as it uses addition for encryption and as we’ll see subtraction for decryption.

Step 3 : Decrypting a block

Decrypting is done in reverse order than encrypting, so the index starts at 0x0F and ends at 0×00 as it has to produce the bit distribution in exact the reverse order. The algorithm is as follows:

              
a' = ( key & (a - key)) | (!key & (b - key))
b' = (!key & (a - key)) | ( key & (b - key))

              

Yes, that is exactly the opposite of the encryption. As it should be of course.

The example below takes the results from the previous encryption example and reverses the process:

              
key = 0xF0F0F0F0
a = 0xE1E0FFFF
b = 0x0000E1E0

a - key = 0xF0F00F0F
b - key = 0x0F0FF0F0

a' = 0xF0F0F0F0 & 0xF0F00F0F | 0x0F0F0F0F & 0x0F0FF0F0
b' = 0x0F0F0F0F & 0xF0F00F0F | 0xF0F0F0F0 & 0x0F0FF0F0

a' = 0xF0F00000 | 0x0F0F0000 = 0xFFFF0000
b' = 0x00000F0F | 0x0000F0F0 = 0x0000FFFF

              

And the original values are back!

This is how the encrypting and decrypting works for a single key entry. This process is repeated for all 16 key words. Forwards for encrypting and backwards for decrypting as the same block words need to be selected for the process to be reversible.

Conclusion

The TPS encryption algorithm is remarkably elegant and fast to run while it provides good enough encryption to stop most amateurs. I have implemented the algorithm in my tps-parse library and tps-to-csv tool so that they now support the encrypted files as well. You still have to know the password of course!