512/513 bytes tables discovery - DSLR Hack development - CHDK Forum
« previous next »
Pages: [1] 2   Go Down

512/513 bytes tables discovery

  • 13 Replies
  • 10205 Views
*

Offline lorenzo353

  • *
  • 39
512/513 bytes tables discovery
« on: 06 / March / 2010, 16:28:59 »
Advertisements
Hi,

do we know how xor decoding tables were found ?

- 300d/10d tables was found by Alex Berstein, 10 Dec 2003, (http://wiki.alexbernstein.com/FirmwareDecrypterUnpacker)
- 20d/350d/30d/400d/5d tables, 21 Jan 2008, see http://chdk.setepontos.com/index.php/topic,134.msg2461.html#msg2461
- 40d tables, 4 May 2008,  http://chdk.setepontos.com/index.php/topic,111.msg11400.html#msg11400

is the only way to find them is the one mx3 have done for the 40D ?

Lorenzo
« Last Edit: 10 / March / 2010, 06:15:33 by lorenzo353 »
Logged
*

Offline mx3

  • ****
  • 372
Re: 512/513 bytes tables discovery
« Reply #1 on: 07 / March / 2010, 04:31:51 »
Quote from: lorenzo353 on 06 / March / 2010, 16:28:59
is the only way to find them is the one mx3 have done for the 40D ?
actually I did not decode tables for new unknown file.
someone already had them. I don't know where did they come from.
my tool just can recreate tables from pure encryption stream which is without data.
I do not know how to guess this stream for unknown file.
well I have some idea but it requires alot of computing power.
Logged
skype: max_dtc. ICQ: 125985663, email: win.drivers(at)gmail, eVB decompiler
*

Offline mx3

  • ****
  • 372
Re: 512/513 bytes tables discovery
« Reply #2 on: 08 / March / 2010, 00:24:47 »
Code: [Select]
#define CRYPT1_SIZE 512
#define CRYPT2_SIZE 513

  while ((val = fgetc(in)) != EOF) {
    fputc(val ^ crypt1[i] ^ crypt2[j], out);
    i++;
    j++;
    if (i >= CRYPT1_SIZE) i=0;
    if (j >= CRYPT2_SIZE) j=0;
  }
as you see value from input data stream does not affect indexes of crypt1 / crypt2 tables.
what actually crypt1[ i ] ^ crypt2[ j ] mean? why not to use only one table ?
if we see this (crypt1[ i ] ^ crypt2[ j ]) operation independently from input data stream we can see that it generates repeatable sequence of pseudo random bytes.

that sequence is a real key which is used for data XORing: seq[ i ] = tbl512[ i % 512 ] ^ tbl513[ i % 513 ];
effective not repeatable length of this sequence is 512*513 = 262656
because this sequense is not random really it is possible from these 262656 bytes to restore initial tables.

as you can see
Code: [Select]
seq[0]   = tbl512[0] ^ tbl513[0];
seq[512] = tbl512[0] ^ tbl513[512];
seq[1024] = tbl512[0] ^ tbl513[511];
then
Code: [Select]
tbl512[0] = seq[0] ^ tbl513[0];
tbl512[0] = seq[512] ^ tbl513[512];
tbl512[0] = seq[1024] ^ tbl513[511];
tbl512[0] = seq[1536] ^ tbl513[510];
which also means
Code: [Select]
seq[0] ^ tbl513[0] = seq[512] ^ tbl513[512];
seq[0] ^ tbl513[0] = seq[1024] ^ tbl513[511];
seq[0] ^ tbl513[0] = seq[1536] ^ tbl513[510];
but hey. we assume we have all 262656 values for seq.
it means if we know tbl513[0] then we have full tbl513, right?
Code: [Select]
tbl513[512] = seq[0] ^ tbl513[0] ^ seq[512] ;
tbl513[511] = seq[0] ^ tbl513[0] ^ seq[1024] ;
tbl513[510] = seq[0] ^ tbl513[0] ^ seq[1536] ;
but if we have tbl513 restored then what?
Code: [Select]
tbl512[0] = seq[0] ^ tbl513[0];
tbl512[1] = seq[1] ^ tbl513[1];
tbl512[2] = seq[2] ^ tbl513[2];
tbl512[3] = seq[3] ^ tbl513[3];
it seems we have a problem in "if we know tbl513[0]".
but wait. does this big ugly thing depends on single byte??????
hm. what will be if we use any random byte for initialization?
actually due to consistense of equations we will get tables wich in turn can be used to reqreate original 262656 bytes sequence.
it seems like magic but there it is - good tables.
any random byte =[0..255]
it means there are 256 possible combinations of tables to recreate the same unique stream.

that is all about recreating tables for pseudo random stream.

**********************************************************

further guess what :-)
how to guess pseudo random encryption stream from unknown file?
Code: [Select]
decrypted_file[0] = seq[0] ^ encrypted_file[0];
decrypted_file[262656] = seq[0] ^ encrypted_file[262656];
decrypted_file[525312] = seq[0] ^ encrypted_file[525312];
which in turn means
Code: [Select]
decrypted_file[0] ^ encrypted_file[0] = decrypted_file[262656] ^ encrypted_file[262656];
decrypted_file[1] ^ encrypted_file[1] = decrypted_file[262657] ^ encrypted_file[262657];
decrypted_file[2] ^ encrypted_file[2] = decrypted_file[262658] ^ encrypted_file[262658];
and
Code: [Select]
decrypted_file[0] = decrypted_file[262656] ^ encrypted_file[262656] ^ encrypted_file[0];
decrypted_file[1] = decrypted_file[262657] ^ encrypted_file[262657] ^ encrypted_file[1];
decrypted_file[2] = decrypted_file[262658] ^ encrypted_file[262658] ^ encrypted_file[2];
well suppose we know there should be a big chunk of bytes in encrypted file which we know (guess what: jpg file:-).
I would say let's slide-xor it with encrypted file.

Code: [Select]
[-- --------262656------][----------262656------][----------262656------][----------262656------][----------262656------]
^
  [known data chunk]      [decrypted new data]    [decrypted new data]    [decrypted new data]    [decrypted new data]  
how to know this jpg is at right offset?
cross xor it in all others 262656 sections and analize data after XORing.
if you see there text - you won.
if you see there 0xEX every fourth byte - you won it.

same relates to text strings but the bigger chunk size the better.
« Last Edit: 08 / March / 2010, 00:38:46 by mx3 »
Logged
skype: max_dtc. ICQ: 125985663, email: win.drivers(at)gmail, eVB decompiler
*

Offline lorenzo353

  • *
  • 39
Re: 512/513 bytes tables discovery
« Reply #3 on: 09 / March / 2010, 16:45:11 »
yes, very clever. we need a know plain text of 262656 bytes...
Logged
*

Offline lorenzo353

  • *
  • 39
Re: 512/513 bytes tables discovery
« Reply #4 on: 09 / March / 2010, 16:45:43 »
I'm continuing travelling back into time ...

- 30d and 20d tables comes from user "ruevs", in 21 / January / 2008
http://chdk.setepontos.com/index.php/topic,134.msg2461.html#msg2461
which tells a similar encryption is used in IXUS camera.

- see this post from "GrAnd", 10 / December / 2007
talking about .fir format
http://chdk.setepontos.com/index.php/topic,134.msg810.html#msg810
from Powershot s300 for example: http://web.canon.jp/imaging/dc/ELIX300_1002-e.exe

at that time, the upgrade was done using USB or serial cable. thus Win32 exe that does the decryption must have been studied in details...

and when appeared fi2 format ?
Logged
*

Offline lorenzo353

  • *
  • 39
Re: 512/513 bytes tables discovery
« Reply #5 on: 09 / March / 2010, 16:47:04 »
do we know when and where appeared the .fir decoder "GrAnd" is talking about ?
Logged
*

Offline lorenzo353

  • *
  • 39
Re: 512/513 bytes tables discovery
« Reply #6 on: 09 / March / 2010, 16:50:00 »
I also noticed that the 2nd updater of 7d version 109 and 110 are identical. Suppose we do not know the 512/513 tables, can we guess them knowing only these 2 differently encrypted updaters we know the plain text version is identical ?
« Last Edit: 09 / March / 2010, 16:52:00 by lorenzo353 »
Logged
*

Offline ewavr

  • ****
  • 1057
  • A710IS
Re: 512/513 bytes tables discovery
« Reply #7 on: 09 / March / 2010, 18:40:53 »
-
« Last Edit: 09 / March / 2010, 18:43:59 by ewavr »
Logged
*

Offline lorenzo353

  • *
  • 39
Re: 512/513 bytes tables discovery
« Reply #8 on: 10 / March / 2010, 05:10:26 »
Quote from: lorenzo353 on 09 / March / 2010, 16:47:04
do we know when and where appeared the .fir decoder "GrAnd" is talking about ?
here first, in CHDK SVN :
Vitalyb, 24 feb 2007, https://tools.assembla.com/chdk/log/branches/vitalyb/tools/pakwif.c

Vitalyb found in  Sept 2006 how to dump powershot firmware:
http://wiki.alexbernstein.com/CanonHackingHistory

answer :
* 31 may 2005 (alex_polushin), 20d encryption
http://tech.groups.yahoo.com/group/canondigicamhacking/message/5726

* 20 dec 2007 (soldeersmurfje), 40D firmware decryption
http://tech.groups.yahoo.com/group/canondigicamhacking/message/7883
« Last Edit: 13 / March / 2010, 06:52:23 by lorenzo353 »
Logged
*

Offline Yarvieh

  • *
  • 26
Re: 512/513 bytes tables discovery
« Reply #9 on: 14 / April / 2010, 10:57:20 »
Actually you can recover the xor keys with a little bit more then 512+513 = 1025 (+ some extra) bytes of continuous plain text at a random location in the file.

For fun and games let us assume that the plain text we know are all 0x00 (there's a couple of 7 and 10kb blobs of those in the 500d firmware, perfect!)

now to explain how this works, lets scale it down and assume a keysize of 3 for key1 and a keysize of 4 for key2 and data bits between 0 and 3 (keeps brains from exploding)

The cypher stream is 1 1 3 2 3 3 3 0 1 3 1 2

lets map this out in a neat little table mapped to the position in the xor tables key2 vertiaclly key1 horizontaly . is for cypher bits, ? for key bits,
the first byte uses 1,1 as key indexes, second 2,2 etc etc etc

Code: [Select]
1 . . ?   
. . . ?   
. . . ?   
. . . ?   
? ? ?     

1 . . ?   
. 1 . ?   
. . . ?   
. . . ?   
? ? ?                                         

1 . . ?   
. 1 . ?   
. . 3 ?   
. . . ?   
? ? ?     

1 . . ?   
. 1 . ?   
. . 3 ?   
2 . . ?   
? ? ?     

1 3 . ?
. 1 3 ?
. . 3 ?
2 . . ?
? ? ?   etc etc   



and we end up with (I went though enough data to fill the table, but you need a minimum of 2 numbers in every row/column)

Code: [Select]
1 3 1 ?
3 1 3 ?
3 1 3 ?
2 0 2 ?
? ? ?

So lets figure this thing out, lets start in the upper left, assuming all plain text is 0, we get 0 ^ some number ^ some other number is 1,
lots of options here, but here's the fun part, it doesn't really matter!! just guess one and the beauty of this is, you don't have to be right!

lets pick 3 for the first byte in key 2

Code: [Select]
1 3 1 3
3 1 3 ?
3 1 3 ?
2 0 2 ?
? ? ?

now lets fill in some unknowns in key 1 based on the new information we just pulled out of our *ss :)

let start with the first column : some number ^ 3 = 1 so, some number = 3 ^ 1 , so first byte of key1 = 2,

Code: [Select]
1 3 1 3
3 1 3 ?
3 1 3 ?
2 0 2 ?
2 ? ?

second column 3^3 = 0, so second one is 0

Code: [Select]
1 3 1 3
3 1 3 ?
3 1 3 ?
2 0 2 ?
2 0 ?

third column 1^3 is 2 again

Code: [Select]
1 3 1 3
3 1 3 ?
3 1 3 ?
2 0 2 ?
2 0 2

awesome we just recovered key 1, lets see what else we fill in now, we see that in the second row , last column that key2 pos 2 must be 2 ^ 3 = 1

Code: [Select]
1 3 1 3
3 1 3 1
3 1 3 ?
2 0 2 ?
2 0 2

same goes for pos 3

Code: [Select]
1 3 1 3
3 1 3 1
3 1 3 1
2 0 2 ?
2 0 2

and finally 2 ^ 2 = 0

Code: [Select]
1 3 1 3
3 1 3 1
3 1 3 1
2 0 2 0
2 0 2

Hey look at that, all recovered and the fact that the iniital number we guessed might not be the original number doesn't even matter, and we didn't need all the data in the table either (just 2 values on each row/column) :)

now how to decrypt the flasher without knowing the keys or plaintext? by hoping for a large block of 0x00's :)

Step 1 start at offset 0, feed keysize1+keysize2 bytes of data to the key recovery algo.
step 2 at offset 0 decrypt (keysize1*2)+keysize2 bytes using the just recovered keys
step 3 if the decrypted data is all zero's we're done and have got the final keys, if not move to offset 1 and go back to step 1

Attached a small C# app that eats its way though the 500d firmware not the prettiest code ever but it does the job, sadly the 550d lacks the 00's,  uses a different algo or keylength so came up empty handed on that one but hey it was still a fun excercise :)

Logged
Pages: [1] 2   Go Up
« previous next »
 

Related Topics


SimplePortal © 2008-2014, SimplePortal