Hello. Just a quick message to show the progress in finding the encryption key used for the RT85 firmware.
Cypher UsedA quick look at the firmware files shows the cipher is some kind of block cipher with a 32-bit block size. Thanks to andynvkz, who was able to get a Bootloader Toolkit from SinONE (the microcontroller manufacturer) we can confirm the cipher used is TEA, the Tiny Encryption Algorithm, in the 32-bit block size / 64-bit key version.
You can find a working code of the algorithm used at:
https://github.com/0x000000AC/Tiny-Encryption-Algorithm/blob/master/tea16.cInteresting to note the Bootloader Toolkit includes a tea library for the Keil compiler to be used with your bootloader. This means it is very probable the firmware was compiled also with the Keil 8051 C Compiler.
EndiannessThe endianness used is the native one from the 8051 microcontroller. Let's call a the byte at address n, b the byte at address n+1, c the byte at address n+2 and d the byte at address n+3. These four bytes creates the 32-bit word ( a << 24 ) | ( b<<16 ) | ( c << 8 ) | d
Because the TEA algorithm divides the 32-bit word into two 16-bit chunks, we have V0 = ( a << 8 ) | b , and V1 = ( c << 8 ) | d
Cleartext / ciphertext pairsIf you are not familiarized with the 8051 microcontroller this is the most difficult part to understand. Getting pairs of cleartext / ciphertext was the most difficult part, because the entire firmware files are encrypted, but because it is code for a 8051 microcontroller, some information can be extracted from the first bytes, where the interrupt vector table resides. For example, these are the first bytes from one firmware file:
file: A_UV88V1_09_20190929.bin
00000000: d298fb36 e1628796 f8ce2d23 d389995d ...6.b....-#...]
00000010: e1628796 e1628796 f8ce2d23 5c8948c3 .b...b....-#\.H.
00000020: f8ce2d23 94f7c212 e1628796 e1628796 ..-#.....b...b..
00000030: e1628796 e1628796 e1628796 e1628796 .b...b...b...b..The first 8051 interrupt vectors are:
Address Interrupt
======= ===========
0x0000 Reset
0x0003 INT0
0x000B Timer 0
0x0013 INT1
0x001B Timer1
0x0023 SerialThe Reset vector is located at address 0x0000. Almost every 8051 compiler places a LJMP instruction there pointing to the start of the code, so we know the first byte is 0x02, the LJMP opcode, followed by the jump address (two bytes).
The next interrupt vector (INT0) is located at address 0x0003, and virtually any 8051 compiler places there a LJMP instruction (0x02) followed by the jump address in every used interrupt vector. In this case this will take bytes at address 0x0003, 0x0004 and 0x0005. The same for all the other interrupts: a LJMP opcode followed by the jump address.
There are 8 bytes between interrupt vector addresses, and only three bytes are used (LJMP + address). The unused bytes usually are filled with zeros and we know the Keil compiler fills all these unused bytes with zeros. We also see for addresses over 0x0028 the same 32-bit sequence is repeated over and over: 0xE1628796. It is simple to deduce this is the encrypted version of 0x00000000.
Now let's see the addresses 0x000B (Timer0), 0x001B (Timer1) and 0x0023 (serial) They all are inside a 32-bit block with value 0xF8CE2D23 and all of them correspond to the "23" part of it. All these blocks are followed by no zero blocks, this means they are used interruptions vectors, so we can asume they contain a LJMP as last byte. And analyzing the bytes before it, it is easy to see they are zero filled bytes.
With all this information we can "partially decode" the first bytes of the firmware:
00000000: 02xxxx00 00000000 00000002 xxxx0000
00000010: 00000000 00000000 00000002 xxxx0000
00000020: 00000002 xxxx0000 00000000 00000000
00000030: 00000000 00000000 00000000 00000000So we can get the following correspondences:
E1628796 ---> 00000000
F8CE2D23 ---> 00000002And the following partial correspondences:
D298FB36 ---> 02xxxx00
D389995D ---> xxxx0000
94F7C212 ---> xxxx0000If you analyze some firmware files you will find many partial correspondences, but unfortunately only these two full ones.
In few words: the goal is to find a 64 bit key that translates 0xE1628796 into 0x00000000
and 0xF8CE2D23 into 0x00000002.
Breaking TEA
This is the funniest part. A simple web search and you will find some people saying a 32-bit block cipher is insecure or even that TEA is broken. Well... it is obvious they have never tried to break a real world TEA cipher.
Some even dare to publish papers and code that are supposedly capable of breaking TEA but when you read it you discover they are breaking a one round TEA version (something that is trivial to break). The real TEA uses 32 rounds: they are trying to demonstrate how to open a safe breaking a cardbox shoe box.
Some "serious" papers describe a method to guess the key that requires the key (!). This is the case of a description about related key attack on TEA that requires to cipher a number of cleartexts under the unknown key (how? It is unknown) and a related key, constructed using some math to the original key (how? it is unknown). Then comparing both ciphertexts they affirm the original key can be deduced. The problem is you need the original key to cipher some plaintexts, and also you need it to created the related key. If you have the original key, what is the point?
An interesting paper talks about the relationship between the bitsum of the key and the bitsum of the chiper text under certain keys with a defined pattern. The bitsum of a binary number is just the number of ones in its binary representation. I made a lot of tests and I can't see this bitsum relation using "normal real world keys"
My findings: The only property of TEA I have tested and confirmed is the equivalent key problem, which reduces the keyspace from 2^64 to 2^62 keys. It is a nice reduction, but not enough.
It is really easy to find a key that decodes E1628796 into 00000000. With a 32-bit block size and 64-bit key a first guess is there must be about 2^32 keys that decodes E1628796 into 00000000 but hopefully there must be only ONE (four) that decodes E1628796 into 00000000
*AND* F8CE2D23 into 00000002. Only one, but because of the equivalent key disadvantage of TEA, there are four equivalent ones.
To check this premise I used a version of TEA using 16-bit blocks and 32-bits keys and encoded 0000 and 0002 under a random 32-bit key. Then I tried all possible 32-bit keys (a few seconds under a modern CPU) and got a little bit over 2^16 keys that decoded into 0000 and only four (all of them equivalent) that decoded both values into 0000 and 0002. The numbers seems to hold.
As today, I have nearly 150000 keys that decodes E1628796 into 00000000, for example
[0064B606046603F0] - 00000000 - 992C0C2D
[04EF5C0C4B8A75A6] - 00000000 - 5D4A3022
[0E8D27E935CCC071] - 00000000 - C92F088D
[1491C6DF16B59162] - 00000000 - 9F5B9947
[17D3D83E1D93A685] - 00000000 - C9FDAC48
[17F81BC445CB28D2] - 00000000 - 8D629136
[38745F2A5F977378] - 00000000 - BBE93F6C
[48BE1F274F7248A5] - 00000000 - 2D7245B7
[48ED01B045A21972] - 00000000 - 0FA130C1
[4D38672B39CF522C] - 00000000 - D3FEA581
[59FE42152BAD1DF3] - 00000000 - DF51694F
[650200426E037BA9] - 00000000 - 8C775878
[6631656D23F90172] - 00000000 - AC5D320F
[6F27895A728A6299] - 00000000 - 64397638
[770B11DC0B13CD0B] - 00000000 - E603E976
First column is the key in order K0:K1:K2:K3. Second column is the decoding of E1628796, and third column is the decoding of F8CE2D23. You can use these values as test vectors. The "best" matches I have found yet are:
[4EB3C5686AC86E10] - 00000000 - 0000D7E2
[63B710B5194C7EF3] - 00000000 - 000088F3
[5D0816A177F3A33E] - 00000000 - A10C0002And, if bitsum is a thing with real world TEA, this one is also interesting:
[00E20E084977C31D] - 00000000 - 11804000Although promising, they can't be used as a starting point to find the real key because the smallest change in the key and everything in the output changes a lot. TEA is a really powerful random number generator.
Any idea? Any expert in cryptography out there? Any clue or algorithm to reduce the search space way down from 2^64 (2^62)?
I started using the CPUs, and later, motivated by andynvkz I switched to GPU but still my worst case scenario is a bit over 500 years. Just too much
Any idea will be welcomed.
andynvkz: I wrote you but your inbox is full, so I got the messages back.
" alt="" class="bbc_img" />
(Attachment Link) " alt="" class="bbc_img" />