103 replies to this topic

[Wookie]

I'm attaching my latest version of the lynx decryption code. This is a completely refactored, cleaned up, and commented version of the earlier enctest.c file that was posted. I think my version makes it pretty easy to understand how the decryption process actually happens when the Lynx boots up. Here's the tarball:

 lynxdec.tar.gz   6.92K   73 downloads

To unpack it and build it do the following:

tar -zxvf lynxdec.tar.gz
cd lynxdec
make
./lynxdec

It should unpack and build on any sane Linux/Mac with developers tools installed.

The next steps I'm going to take is to make the decrypt_block function actually loop the number of times specified by the exponent rather than the two times needed to raise data blocks to the 3rd power (which is the Lynx public exponent). Once I make that change, then we'll be able to try decrypting the private key and playing around with encrypting data.

I'm getting really close. The big leap forward happened when I realized there was framing in the encrypted data rather than just being one big block of data.

--Wookie

Edited by Wookie, Wed Oct 28, 2009 3:33 PM.

[Wookie]

karri, on Wed Oct 28, 2009 12:45 PM, said:

You cannot use this algorithm for encryption. The exponent is hard-coded to some value here. The question is if the hard coded exponent is 3 or something else.

The interesting thing is to get the same decrypted result using a generic RSA algorithm. Because we need the generic RSA algorithm for encryption anyway.

--
Karri

The exponent is hard coded by the fact that the montgomery multiplication was being run twice on each block, hence raising each block to the power of three. A * A * A == A^3. I now know enough to decrypt Harry's encrypted loader using a generic RSA algorithm. The trick was figuring out the framing in the encrypted data.

--Wookie

[karri]

Wookie, on Wed Oct 28, 2009 5:16 PM, said:

karri, on Wed Oct 28, 2009 12:45 PM, said:

You cannot use this algorithm for encryption. The exponent is hard-coded to some value here. The question is if the hard coded exponent is 3 or something else.

The interesting thing is to get the same decrypted result using a generic RSA algorithm. Because we need the generic RSA algorithm for encryption anyway.

--
Karri

The exponent is hard coded by the fact that the montgomery multiplication was being run twice on each block, hence raising each block to the power of three. A * A * A == A^3. I now know enough to decrypt Harry's encrypted loader using a generic RSA algorithm. The trick was figuring out the framing in the encrypted data.

--Wookie

Very nice!

The last step could be part of Montgomery multiplication. It has to adjust the data after the process. I don't believe that they had any extra obfuscation step. RSA was sure that the basic algorithm is strong enough.

Kudos to you for finding the framing. This explains many other things to me as well that I had problems with in Handybug.

--
Karri

[karri]

Wookie, on Wed Oct 28, 2009 1:41 PM, said:

Does anybody know why there is a gap in the decoded version? Do we know if the Lynx only decrypts two frames? Do we know if the remaining part of Harry's plaintext loader (bytes 411-506) are actually important? I've made lots of progress but that has created lots of new questions.

--Wookie

The plaintext loader is just a binary dump done by me from the handybug emulator. I don't know anything about the loader. Sage and Harry have the sources for it.

--
Karri

[karri]

Wookie, on Wed Oct 28, 2009 5:16 PM, said:

I now know enough to decrypt Harry's encrypted loader using a generic RSA algorithm. The trick was figuring out the framing in the encrypted data.

--Wookie

I tried this using OpenSSL BN math and the result is still not what I expect. Have you succeeded in doing the decryption using a generic RSA algorithm? My decrypt still fails

Encdata is:
c1, 0d, 8e, e9, ee, 09, 13, e5, 96, 0c, 34, 64, da, d4, bb, 99, ec, ce, 4f, aa, 8c, ed, 65, f0, 32, 70, a3, 84, c4, fc, a2, 6d, 3a, f8, 77, 4b, ac, 9b, 54, 7d, 82, 6f, f8, a5, 06, 4d, 7b, 77, 55, e4, 31, 

Exponent is:
03, 

Modulo is:
35, b5, a3, 94, 28, 06, d8, a2, 26, 95, d7, 71, b2, 3c, fd, 56, 1c, 4a, 19, b6, a3, b0, 26, 00, 36, 5a, 30, 6e, 3c, 4d, 63, 38, 1b, d4, 1c, 13, 64, 89, 36, 4c, f2, ba, 2a, 58, f4, fe, e1, fd, ac, 7e, 79, 

Result is:
1b, 36, 5a, 57, 0a, 02, 2d, c0, de, bf, e0, 12, 39, a7, a0, 28, 18, ee, dd, 77, ed, 4c, 4b, 5e, 46, de, c4, 4d, 2b, 5d, 3c, d9, 7a, d5, eb, 29, 55, e3, 30, de, 03, fa, 80, 5b, 55, b2, 01, 1e, 26, a7, 88, 

[karri]

OMG!!!! We are almost there!!!!

I removed the last step that you thought was obfuscation and now the result is:

karkak@karkak-rd:~/Desktop/lynxdec$ ./lynxdec 
    0x80, 0x80, 0x20, 0x2f, 0xb3, 0x62, 0xa1, 0xe1, 
    0x20, 0xa3, 0x5f, 0x85, 0xfe, 0x72, 0x4f, 0xfe, 
    0xb4, 0xa4, 0x5e, 0x20, 0xe0, 0x03, 0x9f, 0x69, 
    0xb2, 0xb0, 0x95, 0xba, 0xba, 0x8c, 0x97, 0x67, 
    0xfc, 0xce, 0x06, 0x24, 0xa8, 0xf5, 0x6c, 0xac, 
    0x5b, 0x89, 0x08, 0x68, 0xa3, 0x7f, 0x9a, 0x47, 
    0x24, 0x75, 0x07, 
LynxDecrypt fails

Then I inverted the Harrys encrypted loader and ran it through OpenSSL RSA.

Encdata is:
31, e4, 55, 77, 7b, 4d, 06, a5, f8, 6f, 82, 7d, 54, 9b, ac, 4b, 77, f8, 3a, 6d, a2, fc, c4, 84, a3, 70, 32, f0, 65, ed, 8c, aa, 4f, ce, ec, 99, bb, d4, da, 64, 34, 0c, 96, e5, 13, 09, ee, e9, 8e, 0d, c1, 

Exponent is:
03, 

Modulo is:
35, b5, a3, 94, 28, 06, d8, a2, 26, 95, d7, 71, b2, 3c, fd, 56, 1c, 4a, 19, b6, a3, b0, 26, 00, 36, 5a, 30, 6e, 3c, 4d, 63, 38, 1b, d4, 1c, 13, 64, 89, 36, 4c, f2, ba, 2a, 58, f4, fe, e1, fd, ac, 7e, 79, 

Result is:
15, 75, 24, 47, 9a, 7f, a3, 68, 08, 89, 5b, ac, 6c, f5, a8, 24, 06, ce, fc, 67, 97, 8c, ba, ba, 95, b0, b2, 69, 9f, 03, e0, 20, 5e, a4, b4, fe, 4f, 72, fe, 85, 5f, a3, 20, e1, a1, 62, b3, 2f, 20, 80, 80, 

The result is almost identical. Only the first byte 15 should be 07.

Now I am sure that Harrys Encdata needs to be reversed when you feed it into the RSA algorithm. Also the result comes out reversed.

You did it!!!!

The obfuscation step needs to be understood next.

--
Karri

[karri]

Here is the OpenSSL version.

Compile it with

gcc lynxdecrypt.c -lssl

 lynxdecrypt.tar.gz   2K   76 downloads

--
Karri

[Wookie]

Alright, I'm claiming victory on the generic rsa decryption front. Here's my latest tarball that includes both my lynxdec (which is the cleaned up and refactored reverse engineered version of the Lynx ROM algorithm) and a new app called rsadec that demonstrates how to use the OpenSSL bignum library to do the RSA decryption successfully:

 lynxdec.tar.gz   7.74K   73 downloads

Karri, you missed a crucial detail that you only process 50 bytes from the result of each RSA block decryption. That stray 0x15 byte is thrown away. For each 51 byte encrypted block, we get 50 bytes of decrypted data out. So with that detail in mind, I wrote rsadec to use the BN_mod_exp(), loading each block of encrypted data backwards, and then reversing, trimming, and accumulating the resulting data into the output buffer.

To build and run it, do the following (you have to have the OpenSSL development libraries installed, on a debian-based system just run "sudo apt-get install libssl-dev"):

tar -zxvf lynxdec.tar.gz
cd lynxdec
make all
./rsadec

So now, that we have a generic decryption algorithm that works. We need to start trying to reverse engineer the encryption algorithm. Here's what we know:

• The block decryption uses standard RSA modular exponentiation so we know the encryption uses the same.
  
• The block decryption takes 51 bytes of encrypted data and produces 50 bytes of plaintext data. The encryption step will take 50 bytes of plaintext and produce 51 bytes of encrypted data.
  
• Since there is a reversing and accumulation step at the end of decrypting each block, I thing we should expect there to be a reversing and reverse-acculumation on the data going into the block encryption step. This is probably how we go from 50 bytes of plaintext to the 51 bytes that go into the modular exponentiation encryption step. Modular exponentiation, by its very nature, will not change the number of bytes.
  
• We know how to format the encrypted blocks into two frames with frame count bytes so that the Lynx can decode it.

--Wookie

[Wookie]

karri, on Wed Oct 28, 2009 11:06 PM, said:

Kudos to you for finding the framing. This explains many other things to me as well that I had problems with in Handybug.

--
Karri

I'm really interested in looking at a fully encrypted rom dump and a memory dump of the decrypted data from an emulator so that I could devise the full details of the framing encoding scheme. There is evidence to suggest that there is a maximum of 5 blocks per frame and that each frame decodes to each 256 byte boundary. Since there is only a block count and not some "destination memory" offset/index/pointer to tell the decryption process where to put the decrypted data, the destination has to be hard coded and/or calculated using some algorithm.

Since Harry's loader has two frames with the first decoding to memory offset 0 and the second decoding to memory offset 256, that suggests that each frame decodes to each 256 byte boundary (i.e. frame 1 goes to offset 0, frame 2 goes to offset 256, frame 3 goes to offset 512, etc).

I'd need more encrypted data along with a memory dump of the decrypted version of the same data to be sure. I can decode each frame and then look for where it decoded to in the memory dump of the decrypted data. That would tell me how the destination location is determined.

--Wookie

Edited by Wookie, Thu Oct 29, 2009 9:30 AM.

[Wookie]

Are all of the commercial Lynx ROMs fully encrypted or is it just their boot loaders?

Edited by Wookie, Thu Oct 29, 2009 9:33 AM.

[Wookie]

So I'm now certain that the reversing/accumulation step is some sort of obfuscation. Now that we've proven that the OpenSSL bignum library can decrypt encrypted blocks using standard modular exponentiation, we know that the reversing/accumulation step afterwards isn't reversing some encoding necessary to make Montgomery multiplication work. It is an obfuscation step, plain and simple.

After carefully analyzing what the de-obfuscation algorithm is doing, I've figured out how to take plaintext and obfuscate it. The obfuscation must be done in reverse starting with the last byte of each frame and proceeding to the first byte of the frame. The obfuscation algorithm is simple:

int tmp;
unsigned char obfuscated[CHUNK_LENGTH];  /* receives the obfuscated data */
unsigned char plaintext[CHUNK_LENGTH];   /* assume it has a block of plaintext data */
unsigned char * p = obfuscated;

(*p) = 0x15;
p++;
for(int i = CHUNK_LENGTH - 1; i > 0; i--)
{
    if(plaintext[i] < plaintext[i-1])
    {
        tmp = (0x100 + plaintext[i]) - plaintext[i-1];
        *p = (unsigned char)(tmp & 0xFF);
    }
    else
        *p = plaintext[i] - plaintext[i-1];

    p++;
}

/* calculate the last byte */
tmp = 0x100 - plaintext[0];
*p = (unsigned char)(tmp & 0xff);

There is one caveat. This has to run from the end of one frame of plaintext to the beginning. That means for the 1st frame of Harrys loader, we obfuscate the 3rd block, then the 2nd block, then the 1st block. There is carry over between blocks so really, this should be run over the full frame of plaintext data and then the obfuscated output should be chunked into blocks.

--Wookie

[karri]

Wookie, on Thu Oct 29, 2009 10:49 AM, said:

There is one caveat. This has to run from the end of one frame of plaintext to the beginning. That means for the 1st frame of Harrys loader, we obfuscate the 3rd block, then the 2nd block, then the 1st block. There is carry over between blocks so really, this should be run over the full frame of plaintext data and then the obfuscated output should be chunked into blocks.

--Wookie

I have a faint memory that the idea was that the entire cart was signed by the encryption scheme. This may have meant that the obfuscation step was run over the entire cart and only the loader was encrypted.

42Bastian found some cart where they made a mistake with checking the content. He then created a trojan (INSERT.O in the BLL-toolkit) based on this. In this way it became possible to write homebrew stuff for the Lynx.

But I do not know if this is true or not. It is something I heard years ago from someone.

--
Karri

[karri]

One more thing!

After the encrypted loader every cart needs two mandatory directory entries in plaintext. The first entry points to the title sprite that will also be in plaintext and the second entry points to the first executable that is also in plaintext.

So only the loader can be encrypted. It is usually bigger than 410 bytes. I could skim through my ROM collection to grab different encrypted loaders and corresponding plaintext versions from RAM.

--
Karri

[Wookie]

karri, on Thu Oct 29, 2009 12:51 PM, said:

So only the loader can be encrypted. It is usually bigger than 410 bytes. I could skim through my ROM collection to grab different encrypted loaders and corresponding plaintext versions from RAM.

--
Karri

That would be helpful. After looking at Harry's encryption tutorial again, it appears that either he encrypted his miniloader when generating the screenshots or the encryption only applies to the boot loader and boot loaders are always in 2 frames, 3 blocks in the 1st and 5 blocks in the 2nd. If you look at Harry's screenshots, they match what I've confirmed about the framing and the blocks.

That said, I'm afraid that your assumptions about the keyfiles are wrong. I just wrote up a simple app that tries a bunch of different things. It uses known good input and output blocks to the mod_exp RSA step. It first verifies that decrypting the known good block of encrypted data into the known good (obfuscated) plaintext data using the lynx public exponent and modulus. Once it is established that the decryption works, we know that we should be able to encrypt the known good (obfuscated) plaintext data using the public modulus and the private exponent and get the known good block of encrypted data.

With that understanding, I first tried using each of the keyfiles as the private exponent as is and didn't get any matches. I then ran all permutations of the three key files where each one is either the encrypted private key, private exponent, or private modulus to decrypt the encrypted private exponent as you suggested. None of the decrypted private exponents could successfully encrypt the known good plaintext.

Since we've had issues with reversing the data blocks, I also tried all of the permutations but added code to reverse the encrypted private key before trying to decrypt it. None of those generated keys worked out either.

Here's my latest tarbal:

 lynxdec.tar.gz   9.31K   62 downloads

At this point, I'm stumped. Until we know how the keyfiles are used, we can't reverse engineer the encryption process. My next approach was to disassemble the "realbig" amiga app that reads in the keyfiles and does the encryption. My only problem is that I can't seem to find a good 68K disassembler for linux. Any ideas? I know 68K assembly pretty well, but there's going to be system/kernel calls to read files/disk data that will be hard for me to pin down. All I really need is a disasm dump of that realbig executable and I could probably work out what each key file is used for. I've been staring at RSA mod exp code for so long it would be obvious what is going on.

If somebody can convert the realbig app into 68K asm for me, that would be a big help. Either that or point me at a free 68K disassembler. I wrote a 68K disassembler in 68K assembly once but it has to run in a 68K emulator to work. I suppose I could dig that out if we get desperate.

--Wookie

Edited by Wookie, Thu Oct 29, 2009 1:56 PM.

[Wookie]

Here's the realbig executable:

 realbig.tar.gz   5.13K   48 downloads

This is a 68K amiga executable. When executed, it prompts the user to put the keyfile.1 disk in the disk drive, then keyfile.2 disk, then keyfile.3 disk and lastly, the disk with the lynx rom to encrypt.

There are different possible uses for the three key files. One possibility is that the private exponent is itself encrypted and the other two key files are the exponent and modulus for decrypting the private key. Another possibility is that they are components used to calculate the private key as per the RSA system.

I need to peek at the realbig assembly to figure out how the keyfiles are used.

--Wookie

[karri]

Wookie!

There is another approach. We could go back to the encryption sources posted by Curt Vendel. These sources were given to Atari to do the encryption. Perhaps these sources include something more than just the RSA algorithm?

Look at this assembly listing below.
--
Karri

 LYNXE.TXT   20.88K   81 downloads

Edited by karri, Thu Oct 29, 2009 2:14 PM.

[Wookie]

karri, on Thu Oct 29, 2009 2:09 PM, said:

There is another approach. We could go back to the encryption sources posted by Curt Vendel.
--
Karri

Do you have the Curt Vendel sources? Are they somewhere on this board?

--Wookie

[Wookie]

karri, on Thu Oct 29, 2009 2:09 PM, said:

Look at this assembly listing below.
--
Karri

LYNXE.TXT

What is this assembly listing of?

--Wookie

Edit: wait, nvrmnd...it appears to be the original assembly listing for realbig. Thanks! I'll have to dust off my 68K assembly book now My initial pass through the code shows that the magic seems to be happening on lines 158-197. There is a comment there that says "now combine the key disks"...hrm...

Edited by Wookie, Thu Oct 29, 2009 2:45 PM.

[Wookie]

So after taking a closer look at the assembly, it is pretty clear to me that this is for a 68K Atari machine rather than an Amiga machine. The way I know is that it is using trap #1 to make OS calls for opening files, reading files, and closing files. After some research into Amiga DOS, they never used traps for interfacing with the OS. Instead they provided a symbols file that let you call into the OS runtime directly using branching rather than traps. You could use traps on an Amiga but that was for running your own code. I saw examples of doing sound output through custom traps.

So armed with this new knowledge, I need to go grep the web for docs on the Atari 68K machines and their OS trap interface before I can move forward. I may not get back to this for a while, the last few day's hacking chewed up my brain a bit.

--Wookie

Edit: my guess is it was written for the Atari ST and its GEMDOS operating system. Another bit of evidence supporting this is that on line 26 of the assembly source there is a comment that says "for m_shrink". While browsing the Atari Compendium programmers reference for GEMDOS I came across this line: "An application should use the basepage information to decide upon the amount of memory it actually needs and Mshrink() to return the rest to the system." Is the m_shrink in the assembly the same as the Mshrink() C function referred to in the quote? My guess is yes. I'm willing to bet that function $4a of trap #1 is the m_shrink routine of GEMDOS.

Edited by Wookie, Thu Oct 29, 2009 4:43 PM.

[Wookie]

Ok, I'm certain that this assembly program was written for GEMDOS running on an Atari ST computer. I found an example assembly app that shows how to call GEMDOS, XBIOS, and BIOS system calls on an Atari ST. The example looks like this:

GEMDOS equ 1
BIOS equ 13
XBIOS equ 14
.text
* .... other stuff ...
* Terminate program and release our memory to the system
clr.1 -(sp) * Term, GEMDOS function 0
trap #GEMDOS * Perform GEMDOS trap
.end

GEMDOS functions are called using trap #1. The above code calls GEMDOS function 0 to terminate the application. Now, at the bottom of the assembly program for doing lynx encryption there is the following:

 clr.w   -(sp)
 trap    #1

This is using trap #1 to call the OS function 0 to terminate. Hrm, that matches GEMDOS. Ok, now I can move forward. Does anbydoy have a good GEMDOS assembly reference somewhere? I need a reference on the trap functions and what parameters get passed in the registers/stack. I've found where the keyfiles get opened and read into memory. I need the trap reference to figure out where they are written to memory and figure out how they are used.

--Wookie

Edit: found one GEMDOS Reference

Edited by Wookie, Thu Oct 29, 2009 5:24 PM.

[karri]

Wookie, on Thu Oct 29, 2009 2:31 PM, said:

karri, on Thu Oct 29, 2009 2:09 PM, said:

There is another approach. We could go back to the encryption sources posted by Curt Vendel.
--
Karri

Do you have the Curt Vendel sources? Are they somewhere on this board?

--Wookie

Yes. here

[Wookie]

Alright, after looking at the assembly you gave me yesterday, I know for a fact that the keyfiles, which are ascii hex, are loaded, converted from ascii hex to their numeric value, and then the code xor's each byte of the second keyfile with the first keyfile, and then it xor's each byte of the third keyfile with each byte of that.

So that answers the question of why three keyfiles. There is more that gets done with the key data before the encryption that I'm working out now. I just thought you'd like to know the xor'ing bit.

--Wookie

[Wookie]

VICTORY!! VICTORY!! VICTORY!!

Gentlemen, (and ladies), I present to you, the Lynx encryption private exponent:

// This is the known private exponent generated by xor'ing
// the three keyfile blocks below together
const unsigned char lynx_private_exp[CHUNK_LENGTH] = { 
    0x23, 0xce, 0x6d, 0x0d, 0x70, 0x04, 0x90, 0x6c, 
    0x19, 0xb9, 0x3a, 0x4b, 0xcc, 0x28, 0xa8, 0xe4, 
    0x12, 0xdc, 0x11, 0x24, 0x6d, 0x20, 0x19, 0x55, 
    0x79, 0x87, 0xab, 0x5c, 0xa8, 0x18, 0xa3, 0xd3, 
    0xc8, 0xe3, 0x27, 0x6d, 0x42, 0x70, 0xcb, 0x80, 
    0x21, 0xd6, 0xbd, 0xa4, 0x29, 0x6d, 0x47, 0xb1, 
    0xe5, 0xe2, 0xa3
};

You get it by xor'ing the keyfile data together like I said in my previous post. I finally traced out the rest of the encryption assembly code and figured out that it was just running a standard RSA step (r = (d ^ e) mod m) without doing anything else to the key generated by xor'ing the data.

Once I got there, I wrote a tiny program to calculate the private exponent by xor'ing the keyfiles together so that I could use it in some tests. My very first test with the calculated private exponent worked!! The above data is the Lynx private exponent.

So here is my latest tarball. It contains a key.h file that has the public exponent and modulus, the keyfile data, and the calculate private exponent in it. It also has source for a program called privatedkeytest that first decrypts the first block of the encrypted loader using a generic RSA step (using the OpenSSL bignum library) with the public exponent and modulus. The output is checked against the know good output to show the decryption worked. It then takes the output and feeds it back through the generic RSA step with the private exponent and the public modulus. The output from that is the first block of the encrypted loader!!!

Here's the tarball:

 lynxdec.tar.gz   17.63K   78 downloads

I am so satisfied. Now that we have all the pieces, we can write a generic C app that uses the OpenSSL bignum library to do a generic RSA encryption process on our ROMs. I'll bang that out pretty soon.

--Wookie

Edited by Wookie, Fri Oct 30, 2009 12:50 PM.

[GroovyBee]

Not that I'm a Lynx developer but anything that makes development easy for our retro platforms of choice is a good thing.

[karri]

Wookie, on Fri Oct 30, 2009 12:46 PM, said:

VICTORY!! VICTORY!! VICTORY!!

Gentlemen, (and ladies), I present to you, the Lynx encryption private exponent:

// This is the known private exponent generated by xor'ing
// the three keyfile blocks below together
const unsigned char lynx_private_exp[CHUNK_LENGTH] = { 
    0x23, 0xce, 0x6d, 0x0d, 0x70, 0x04, 0x90, 0x6c, 
    0x19, 0xb9, 0x3a, 0x4b, 0xcc, 0x28, 0xa8, 0xe4, 
    0x12, 0xdc, 0x11, 0x24, 0x6d, 0x20, 0x19, 0x55, 
    0x79, 0x87, 0xab, 0x5c, 0xa8, 0x18, 0xa3, 0xd3, 
    0xc8, 0xe3, 0x27, 0x6d, 0x42, 0x70, 0xcb, 0x80, 
    0x21, 0xd6, 0xbd, 0xa4, 0x29, 0x6d, 0x47, 0xb1, 
    0xe5, 0xe2, 0xa3
};

--Wookie

Amazing. I will celebrate tonight! This is a BIG step for the Lynx hobby scene.

--
Karri

Edited by karri, Fri Oct 30, 2009 2:46 PM.