Lynx Encryption?

[+karri]

I have those sources too. Curt Vendell posted them on AtariAge.

 

By "sources" do you mean the .adf disk images? The zip file from cgexpo.com just contains a bunch of source files and executables. I've tried getting them into UAE but haven't been successful. I'm not sure how to get files from my linux box into an Amiga .adf disk image without an actual Amiga computer. Plus, even if I was able to get the files into Amiga .adf disk images, I have no idea which files go onto which disk image.

 

If you've got the disk images already, I'd love to get them. If not, I'll look up Harry and see if he can help me put together some disk images.

 

Wookie

 

I can help a bit. There are 4 disks. The disks contain the directories named:

- boot

- rsa1

- rsa2

- rsa3

 

This means that the disk labeled rsa1 contains this directory structure:

drwxr-xr-x 2 karri karri 4096 2008-08-10 16:03 c

-r-xr--r-- 1 karri karri 103 2001-01-12 16:30 keyfile.1

drwxr-xr-x 2 karri karri 4096 2008-08-10 16:03 l

drwxr-xr-x 2 karri karri 4096 2008-08-10 16:03 s

 

I do not have the afd images. And I have not yet been able to get the code posted by Curt to work well.

--

Karri

PS. Now you got me interested in this stuff again.

[Wookie]

This is technology archeology at its best. Figuring this out and finally getting the private key, or the algorithm for generating the private key into portable C code is essential for preserving the Lynx as a homebrew platform. Thanks for you help so far.

[+karri]

This is technology archeology at its best. Figuring this out and finally getting the private key, or the algorithm for generating the private key into portable C code is essential for preserving the Lynx as a homebrew platform. Thanks for you help so far.

 

You are welcome. Curts encryption code will not work if compiled on a Litte Endian machine. It has to be something like Motorola Amiga or Power PC.

 

I am half-way in my process to create an endian independent version of the code. But so far it does not work.

 

Inside the Lynx we have a special case. The exponent that we use for decryption is a fixed constant 3 instead of a 51 byte key. This is of course much faster than the generic version. But because of this running the encryption process using the Lynx code is impossible.

 

What I would like to do is to find a person with a Power PC based linux system and run the code attached here on the PowerPC.

 

To compile this type

gcc enctest.c

 

To run this type

./a.out

 

The output should be something like

 

LynxDecrypt fails

Decrypt works

 

The LynxDecrypt part is little endian only

The Decrypt part is big endian only

 

enctest.zip

 

If the Decrypt fails on a big endian system then the algorithm posted by Curt may be faulty.

--

Regards,

 

Karri

Edited September 8, 2009 by karri

[Wookie]

What I would like to do is to find a person with a Power PC based linux system and run the code attached here on the PowerPC.

 

It just so happens I still have a 1.0 GHz PPC PowerBook

 

I'll check it out soon. Just a heads up, my wife is having our second baby tomorrow, so I'll be AFK for the next couple of weeks probably.

 

Wookie

[+karri]

What I would like to do is to find a person with a Power PC based linux system and run the code attached here on the PowerPC.

 

It just so happens I still have a 1.0 GHz PPC PowerBook

 

I'll check it out soon. Just a heads up, my wife is having our second baby tomorrow, so I'll be AFK for the next couple of weeks probably.

 

Wookie

 

Congratulations. I hope everything goes well.

 

And this encryption stuff waits here forever.

 

--

Karri

[+karri]

I found a few more bugs in my code so I upload it here again.

 

Now I have 4 tests included. I hope one of them produces "Decrypt works" when run on PowerPC.

 

enctest.zip

--

Karri

[Wookie]

I found a few more bugs in my code so I upload it here again.

 

Now I have 4 tests included. I hope one of them produces "Decrypt works" when run on PowerPC.

 

enctest.zip

--

Karri

 

Here's the output from running it on my PPC mac:

 

barsoom:Downloads dave$ ./enctest
LynxDecrypt works
Decrypt fails
fdc10d8ee9ee0913e5960c3464dad4bb99ecce4faa8ced65f03270a384c4fca26d3af8774bac9b547d826ff8a5064d7b7755e4
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
35b5a3942806d8a22695d771b23cfd561c4a19b6a3b02600365a306e3c4d63381bd41c136489364cf2ba2a58f4fee1fdac7e79
05ed0d1d6f3191379b88b1bd0953407eee8e30057d63ccd553b50c2161b1d20353440ecf7b589b2ce7238fd350c86c83b6c2b2
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
e455777b4d06a5f86f827d549bac4b77f83a6da2fcc484a37032f065ed8caa4fceec99bbd4da64340c96e51309eee98e0dc1fd
030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
797eacfde1fef4582abaf24c368964131cd41b38634d3c6e305a360026b0a3b6194a1c56fd3cb271d79526a2d8062894a3b535
453f8aa6f54fb19634ba2422966e140b0b360f91e9e67a845348a6f5c71bfeaa72c4e77f75f791765650a3843c8e4d741c496e
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
fdc10d8ee9ee0913e5960c3464dad4bb99ecce4faa8ced65f03270a384c4fca26d3af8774bac9b547d826ff8a5064d7b7755e4
030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
35b5a3942806d8a22695d771b23cfd561c4a19b6a3b02600365a306e3c4d63381bd41c136489364cf2ba2a58f4fee1fdac7e79
01ed23cd999363fabe8ba780abbdb942ede3f80d4dd078e1b5c0fd8e0ab8d38e735102197d0d82c58d74ff97d5fba2ad5ccdae
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
e455777b4d06a5f86f827d549bac4b77f83a6da2fcc484a37032f065ed8caa4fceec99bbd4da64340c96e51309eee98e0dc1fd
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
797eacfde1fef4582abaf24c368964131cd41b38634d3c6e305a360026b0a3b6194a1c56fd3cb271d79526a2d8062894a3b535
056bfa2174722760c08ed87fba37ec4e20db11bbf79e77a43c4c756cf66a13a25e0e453c5ec76c10163eb96747072fd9bf3e00
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0

 

No such luck. I'll take a look at the code soon and work out the math by hand. I'm sure I can figure it out when I get a chance.

 

Wookie

[+karri]

Thanks Wookie,

 

Could you edit the file and comment out the line

 

#define LITTLE_ENDIAN

 

I forgot to do it.

 

--

Karri

[Wookie]

Thanks Wookie,

 

Could you edit the file and comment out the line

 

#define LITTLE_ENDIAN

 

I forgot to do it.

 

--

Karri

 

 

It looks like the same result after commenting out the #define LITTLE_ENDIAN:

 

barsoom:Downloads dave$ ./enctest
LynxDecrypt fails
Decrypt fails
fdc10d8ee9ee0913e5960c3464dad4bb99ecce4faa8ced65f03270a384c4fca26d3af8774bac9b547d826ff8a5064d7b7755e4
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
35b5a3942806d8a22695d771b23cfd561c4a19b6a3b02600365a306e3c4d63381bd41c136489364cf2ba2a58f4fee1fdac7e79
d1b24b9c2d3db572195cd4fecb4766a990f5a1aeee4094b20a3043f2915f4cd36247c6a595552e478d5bb9a97964337c2c8a6c
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
e455777b4d06a5f86f827d549bac4b77f83a6da2fcc484a37032f065ed8caa4fceec99bbd4da64340c96e51309eee98e0dc1fd
030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
797eacfde1fef4582abaf24c368964131cd41b38634d3c6e305a360026b0a3b6194a1c56fd3cb271d79526a2d8062894a3b535
46d513ed72bb431a924ef11d30102a76665229160a9c8e4d8e96699ec402887e996f80709e81458bd6f5a127499c8f8cc30c1f
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
fdc10d8ee9ee0913e5960c3464dad4bb99ecce4faa8ced65f03270a384c4fca26d3af8774bac9b547d826ff8a5064d7b7755e4
030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
35b5a3942806d8a22695d771b23cfd561c4a19b6a3b02600365a306e3c4d63381bd41c136489364cf2ba2a58f4fee1fdac7e79
99f65b345013eca375e7c3933541712b159afee459942be6c30bbf75ce59f984a2a7904c624dfb120788ac57098c9741b7f56e
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0
Decrypt fails
e455777b4d06a5f86f827d549bac4b77f83a6da2fcc484a37032f065ed8caa4fceec99bbd4da64340c96e51309eee98e0dc1fd
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
797eacfde1fef4582abaf24c368964131cd41b38634d3c6e305a360026b0a3b6194a1c56fd3cb271d79526a2d8062894a3b535
c004f8f6b6239b95179e4765f8127685ed34ad9ce7cf1fdbec21dc816cec0b35ee176c486e2c0f8dd1b4311c8a6f0f388a1f07
8000204f026405e606a9088d8bfd4c4afea200200003a20bbd6d02bc76029900fccad0f49c91fda9048d95fda01fb9002499a0

 

I still haven't had a chance to look at the code closely.

 

Wookie

[GroovyBee]

Just had a quick look at the source. A few comments :-

 

I don't think the BIT #define is correct for big endian. When you compare Intel machines to 68000 machines only the byte order is different and not the bit order within each byte.

 

For arithmetic involving arrays of bytes accessed as individual bytes the resultant number generated by a algorithm using that array must be stored/accessed with a known endianess. You don't need to change the the end of the array that you start processing from.

[+karri]

Just had a quick look at the source. A few comments :-

 

I don't think the BIT #define is correct for big endian. When you compare Intel machines to 68000 machines only the byte order is different and not the bit order within each byte.

 

For arithmetic involving arrays of bytes accessed as individual bytes the resultant number generated by a algorithm using that array must be stored/accessed with a known endianess. You don't need to change the the end of the array that you start processing from.

 

True. But if you look at the for-loop it will treat the data as bits. First it tries to access the most significent bit of the most significent byte. When you flip the byte order you still want to access the same bit. But now the most significent byte is the last byte. The bit you want is not the least significent but the most significent so you need to index it by 7-bit.

 

But I may be wrong.

 

I just cannot make this work with Curts algorithm. The algo ripped from the Lynx works ok.

 

Perhaps we should just get the standard RSA algorithm and recompile it for 408 bit keys.

--

Karri

[GroovyBee]

What compiler was the code originally passed through to get the final binary (back when the Lynx was still being developed for)? What size in bits should an "unsigned int" be in this code? Is it 16 bits or 32? If it is sixteen bits change all "unsigned int" to "unsigned short int" for modern compilers.

[GroovyBee]

I'll try and explain myself better. If you have a variable 0x12345678 it is stored in intel (x86 processor) little endian format format as :-

 

0xN+0 = 0x78

0xN+1 = 0x56

0xN+2 = 0x34

0xN+3 = 0x12

 

And big endian (Motorola 68k) :-

 

0xN+0 = 0x12

0xN+1 = 0x34

0xN+2 = 0x56

0xN+3 = 0x78

 

If you look at 0x12 stored in memory in binary on x86 it is :-

 

00010010

 

and on 68k it is :-

 

00010010

 

There are no difference in bit positions in the byte.

 

In "C" language terms :-

 

unsigned char data=0x80;

 

if (data&0x80)

{

...

}

 

is still a true condition on either hardware. Hence my reasoning to say that the BIT #define is not correct.

 

EDIT: Posted too early .

Edited September 15, 2009 by GroovyBee

[+karri]

Thanks. I have spent too much time on this and I am completely blind for my own mistakes.

 

The better approach is to start again and download a good implementation of RSA and try out that one with our known keys.

 

The formula is very simple:

 

A = B ^ C % D

 

A = 51 bytes from the cleartext array

B = 51 bytes from the Harrys encrypted loader

C = 3

D = 51 bytes Lynx public key

 

Once this works using generic RSA code then we should be able to get the real private key using the keyfiles from the Amiga disks.

 

// This is the Atari keyfile.1
// I believe it is the encrypted private key for signing carts
static unsigned char keyfile_1[chunkLength] = {
   0xea, 0x6c, 0xad, 0xb2, 0xab, 0xb1, 0xd3, 0xee,
   0x85, 0x6f, 0xd3, 0x36, 0xc0, 0xc1, 0x16, 0x1d,
   0x31, 0x44, 0x65, 0x1a, 0x22, 0x81, 0xb5, 0xb8,
   0x26, 0xdd, 0xce, 0x0f, 0x8f, 0xbb, 0x25, 0xc8,
   0x1d, 0x34, 0x03, 0x1f, 0xb4, 0xb9, 0xae, 0xda,
   0xcf, 0xde, 0x75, 0xc1, 0xd2, 0xed, 0x35, 0x4b,
   0xcc, 0x11, 0x58
};

// This is the Atari keyfile.2
// I believe it is the exponent for protecting the signing private key
static unsigned char keyfile_2[chunkLength] = {
   0x14, 0xd6, 0x30, 0x08, 0x35, 0x57, 0x28, 0xef,
   0x2b, 0xa3, 0x25, 0xb7, 0x11, 0x8c, 0x62, 0x2d,
   0x16, 0x7a, 0x7d, 0xee, 0x57, 0xe7, 0x37, 0x18,
   0xc9, 0x96, 0xe5, 0xa9, 0x63, 0x49, 0x68, 0x15,
   0xf6, 0x6c, 0x12, 0x8c, 0x9e, 0xeb, 0xda, 0xef,
   0xbd, 0x75, 0x3a, 0x9e, 0x7d, 0x02, 0xe6, 0xe9,
   0xfd, 0xd7, 0x97
};

// This is the Atari keyfile.3
// I believe it is the public key for protecting the signing private key
static unsigned char keyfile_3[chunkLength] = {
   0xdd, 0x74, 0xf0, 0xb7, 0xee, 0xe2, 0x6b, 0x6d,
   0xb7, 0x75, 0xcc, 0xca, 0x1d, 0x65, 0xdc, 0xd4,
   0x35, 0xe2, 0x09, 0xd0, 0x18, 0x46, 0x9b, 0xf5,
   0x96, 0xcc, 0x80, 0xfa, 0x44, 0xea, 0xee, 0x0e,
   0x23, 0xbb, 0x36, 0xfe, 0x68, 0x22, 0xbf, 0xb5,
   0x53, 0x7d, 0xf2, 0xfb, 0x86, 0x82, 0x94, 0x13,
   0xd4, 0x24, 0x6c
};

 

LynxPrivateKey = keyfile_1 ^ keyfile_2 % keyfile_3

 

Once this is known we should be able to run

 

encrypter_loader = plaintext_loader ^ private_key % LynxPublic_key

--

Karri

Edited October 5, 2009 by karri

[Wookie]

Thanks. I have spent too much time on this and I am completely blind for my own mistakes.

--

Karri

 

I have started my own implementation that uses stdint.h data types and the ntoh* and hton* functions for handling endian issues portably. I should get some more time on it today.

 

Wooke

[ThomH]

I'm not in the slightest bit confident about this, but assuming the big numbers posted are big endian, I wrote the following quick program on top of the arbitrary-precision arithmetic support in OpenSSL (whichever version came with Mac OS X v10.6):

#include <stdlib.h>
#include <openssl/bn.h>

#define BIGNUM_BIGENDIAN

#ifdef BIGNUM_BIGENDIAN

BIGNUM *load_number(unsigned char *buffer, int numbytes)
{
BIGNUM *r1 = BN_new();
BIGNUM *r2 = BN_new();

while(numbytes--)
{
	BN_lshift(r2, r1, ;
	BN_add_word(r2, *buffer); buffer++;

	BIGNUM *t = r1; r1 = r2; r2 = t;
}

BN_free(r2);
return r1;
}

void print_number(BIGNUM *number)
{
BIGNUM *printCopy = BN_new(), *pc2 = BN_new();
BN_copy(printCopy, number);

unsigned char *tempBuffer;
tempBuffer = (unsigned char *)calloc(BN_num_bytes(number), 1);

int arrayPointer = BN_num_bytes(printCopy)-1;

while(!BN_is_zero(printCopy))
{
	tempBuffer[arrayPointer] = BN_mod_word(printCopy, 256);
	arrayPointer--;

	BN_rshift(pc2, printCopy, ;

	BIGNUM *t = pc2; pc2 = printCopy; printCopy = t;
}

BN_free(printCopy);
BN_free(pc2);

for(int c = 0; c < BN_num_bytes(number); c++)
{
	printf("%02x, ", tempBuffer[c]);
}
printf("\n\n");

free(tempBuffer);
}

#endif

int main (int argc, const char * argv[]) {

static unsigned char keyfile_1[] = {
	0xea, 0x6c, 0xad, 0xb2, 0xab, 0xb1, 0xd3, 0xee,
	0x85, 0x6f, 0xd3, 0x36, 0xc0, 0xc1, 0x16, 0x1d,
	0x31, 0x44, 0x65, 0x1a, 0x22, 0x81, 0xb5, 0xb8,
	0x26, 0xdd, 0xce, 0x0f, 0x8f, 0xbb, 0x25, 0xc8,
	0x1d, 0x34, 0x03, 0x1f, 0xb4, 0xb9, 0xae, 0xda,
	0xcf, 0xde, 0x75, 0xc1, 0xd2, 0xed, 0x35, 0x4b,
	0xcc, 0x11, 0x58
};

static unsigned char keyfile_2[] = {
	0x14, 0xd6, 0x30, 0x08, 0x35, 0x57, 0x28, 0xef,
	0x2b, 0xa3, 0x25, 0xb7, 0x11, 0x8c, 0x62, 0x2d,
	0x16, 0x7a, 0x7d, 0xee, 0x57, 0xe7, 0x37, 0x18,
	0xc9, 0x96, 0xe5, 0xa9, 0x63, 0x49, 0x68, 0x15,
	0xf6, 0x6c, 0x12, 0x8c, 0x9e, 0xeb, 0xda, 0xef,
	0xbd, 0x75, 0x3a, 0x9e, 0x7d, 0x02, 0xe6, 0xe9,
	0xfd, 0xd7, 0x97
};

static unsigned char keyfile_3[] = {
	0xdd, 0x74, 0xf0, 0xb7, 0xee, 0xe2, 0x6b, 0x6d,
	0xb7, 0x75, 0xcc, 0xca, 0x1d, 0x65, 0xdc, 0xd4,
	0x35, 0xe2, 0x09, 0xd0, 0x18, 0x46, 0x9b, 0xf5,
	0x96, 0xcc, 0x80, 0xfa, 0x44, 0xea, 0xee, 0x0e,
	0x23, 0xbb, 0x36, 0xfe, 0x68, 0x22, 0xbf, 0xb5,
	0x53, 0x7d, 0xf2, 0xfb, 0x86, 0x82, 0x94, 0x13,
	0xd4, 0x24, 0x6c
};

BIGNUM *keyFile1, *keyFile2, *keyFile3, *result;

keyFile1 = load_number(keyfile_1, 51);
keyFile2 = load_number(keyfile_2, 51);
keyFile3 = load_number(keyfile_3, 51);

BN_CTX *ctx = BN_CTX_new();
result = BN_new();

BN_mod_exp(result, keyFile1, keyFile2, keyFile3, ctx);

printf("Result is:\n");
print_number(result);

BN_free(result);
BN_free(keyFile1);
BN_free(keyFile2);
BN_free(keyFile3);
BN_CTX_free(ctx);

   return 0;
}

I've never used OpenSSL before and couldn't find a definitive reference on the intended usage patterns for BIGNUMs, hence the slightly awkward means of byte stuffing and retrieval — though if you insert something like a print_number(keyFile1) then you get exactly the same byte pattern back as you put in, so I'm confident they're correct.

 

Anyway, output is:

90, 53, a4, ab, bd, 77, c6, b3, c6, 58, 5a, 41, 2d, d9, ce, 60, 47, 10, e3, 66, ab, 6b, 90, d8, 1e, ce, 3c, 05, de, 7b, 4f, 9f, 03, b7, 75, 12, 83, 2f, bd, 93, 81, 39, 1a, 41, 50, 34, b5, f8, 9c, 51, dc, 

 

Obviously this will be completely incorrect if the 51 byte numbers given are intended to be little endian, in which case you'll need to modify load_number and print_number. Or just reverse the order of the numbers in the arrays then reverse the order of the numbers in the output.

 

Hope I've understood!

[+karri]

I'm not in the slightest bit confident about this, but assuming the big numbers posted are big endian, I wrote the following quick program on top of the arbitrary-precision arithmetic support in OpenSSL (whichever version came with Mac OS X v10.6):

 

Hope I've understood!

 

You understood it perfectly. This was exactly what I hoped to do some day.

 

The keys are definitely in big endian as it is the standard way of representing them. I just have to try out the key you found. Perhaps it works for encrypting stuff.

 

--

Thanks,

 

Karri

[+karri]

I ran this on Intel and the result is identical to the Mac output.

 

The only problem is that the result is different from what it should be .

 

Perhaps the Lynx is not RSA after all. There may be some small twist to the algorithm.

 

What we know from the code is that:

 

static unsigned char LynxExponent[] = {
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x03
};

static unsigned char LynxPublicKey[] = {
   0x35, 0xB5, 0xA3, 0x94, 0x28, 0x06, 0xD8, 0xA2,
   0x26, 0x95, 0xD7, 0x71, 0xB2, 0x3C, 0xFD, 0x56,
   0x1C, 0x4A, 0x19, 0xB6, 0xA3, 0xB0, 0x26, 0x00,
   0x36, 0x5A, 0x30, 0x6E, 0x3C, 0x4D, 0x63, 0x38,
   0x1B, 0xD4, 0x1C, 0x13, 0x64, 0x89, 0x36, 0x4C,
   0xF2, 0xBA, 0x2A, 0x58, 0xF4, 0xFE, 0xE1, 0xFD,
   0xAC, 0x7E, 0x79
};

 

I also know that the first chunk of the loader produces this output:

static unsigned char HarrysEncryptedLoader[] = {
   0xFD, 0xC1, 0x0D, 0x8E, 0xE9, 0xEE, 0x09, 0x13,
   0xE5, 0x96, 0x0C, 0x34, 0x64, 0xDA, 0xD4, 0xBB,
   0x99, 0xEC, 0xCE, 0x4F, 0xAA, 0x8C, 0xED, 0x65,
   0xF0, 0x32, 0x70, 0xA3, 0x84, 0xC4, 0xFC, 0xA2,
   0x6D, 0x3A, 0xF8, 0x77, 0x4B, 0xAC, 0x9B, 0x54,
   0x7D, 0x82, 0x6F, 0xF8, 0xA5, 0x06, 0x4D, 0x7B,
   0x77, 0x55, 0xE4
};

// This is Harrys miniloader in plaintext
static unsigned char HarrysPlaintextLoader[] = {
   0x80, 0x00, 0x20, 0x4f, 0x02, 0x64, 0x05, 0xe6,
   0x06, 0xa9, 0x08, 0x8d, 0x8b, 0xfd, 0x4c, 0x4a,
   0xfe, 0xa2, 0x00, 0x20, 0x00, 0x03, 0xa2, 0x0b,
   0xbd, 0x6d, 0x02, 0xbc, 0x76, 0x02, 0x99, 0x00,
   0xfc, 0xca, 0xd0, 0xf4, 0x9c, 0x91, 0xfd, 0xa9,
   0x04, 0x8d, 0x95, 0xfd, 0xa0, 0x1f, 0xb9, 0x00,
   0x24, 0x99, 0xa0
};

 

Unfortunately the OpenSSL library produced

Encdata is:
fd, 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, 

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:
2a, 65, 8a, e0, e5, aa, aa, 86, 36, 72, 72, 0b, 42, ed, dd, a7, 4a, a0, 5c, 6e, af, 42, 4f, 54, 40, 13, f8, 5c, 11, 21, ec, c3, c1, a5, fb, a5, b0, 8f, fa, b3, 6f, 8b, 29, ce, f8, 74, 14, 39, e3, 74, cb, 

 

Sigh...

 

I also found out that the key produced from the keyfiles don't work backwards with the exponent 3. So back to the drawing board...

 

--

Karri

Edited October 5, 2009 by karri

[Wookie]

Sigh...

 

I also found out that the key produced from the keyfiles don't work backwards with the exponent 3. So back to the drawing board...

 

Not entirely. We do have a working LynxDecrypt implementation in the enctest. I'm assuming, by the terrible C code, that it was reverse engineered from the Lynx firmware code. I haven't tried too hard to clean it up and figure out exactly why it is working. If we can better understand that algorithm, then we'll be heading in the right direction.

[+karri]

Sigh...

 

I also found out that the key produced from the keyfiles don't work backwards with the exponent 3. So back to the drawing board...

 

Not entirely. We do have a working LynxDecrypt implementation in the enctest. I'm assuming, by the terrible C code, that it was reverse engineered from the Lynx firmware code. I haven't tried too hard to clean it up and figure out exactly why it is working. If we can better understand that algorithm, then we'll be heading in the right direction.

 

True. The basic stuff was created by Harry Dodgson. Cleanup is by me.

 

What happens here is that the Lynx uses Montgomery multiplication for solving the equation.

 

There are two parts that should be understood.

 

1) The LynxMont routine is not what it says in the comment. It does a lot more - why.

 

2) The LynxMont is first run on the data alone. Then the result is run through LynxMont again.

 

Out of these two topics it should be possible to understand what the exponent really is. It may be something else than 3.

 

Or could the two runs through LynxMont just mean that the algorithm is run twice on the data.

 

--

Karri

[Wookie]

Or could the two runs through LynxMont just mean that the algorithm is run twice on the data.

 

That could be how Montgomery multiplication works, but I think your guess might be right. I also noticed that it appears to start on byte 1, not byte 0 the first time through the algorithm. I'll see if I can take a closer look at it this weekend. We need a clean, function based (no globals) implementation of that code before we can get anywhere with this. So far we've seen one failed modular exponentiation using the OpenSSL library. My own bignum library came up with the same failed result independently and I wasn't using any tricks, just straight forward long hand algorithms.

 

Wookie

[Wookie]

I've been slowly picking at the enctest.c file, trying to clean it up, understand it and reorganize it so that I can try running other data through it. One of the things I noticed was that the decryption process doesn't really need lots of code. Here's the call tree that is generated by cflow:

 

main() <int main (int argc,char *argv[]) at enctest.c:502>:
   LynxDecrypt() <void LynxDecrypt (const unsigned char encrypted_data[]) at enctest.c:389>:
       convert_it() <void convert_it () at enctest.c:322>:
           sub5000() <void sub5000 (int m) at enctest.c:307>:
               Copy() <void Copy (unsigned char *A,unsigned char *B,int m) at enctest.c:71>
               LynxMont() <void LynxMont (unsigned char *L,unsigned char *M,unsigned char *N,const unsigned char *PublicKey,int m) at enctest.c:246>:
                   Clear() <void Clear (unsigned char *A,int m) at enctest.c:53>
                   Double() <void Double (unsigned char *B,int m) at enctest.c:80>
                   add_it() <void add_it (unsigned char *BB,unsigned char *FF,int m) at enctest.c:230>:
                   Adjust() <int Adjust (unsigned char *BB,const unsigned char *NN,int m) at enctest.c:95>:
                       Copy() <void Copy (unsigned char *A,unsigned char *B,int m) at enctest.c:71>
   Compare() <bool Compare (unsigned char *A,const unsigned char *B,int m) at enctest.c:445>:
   printf()

 

I know why the convert_it algorithm starts at byte 1 instead of 0. Montgomery multiplication works backwards in a sense and thus can carry over into the first byte. I'm slowly wrapping my head around this. It looks like that once i get this cleaned up, I'll be able to run the private keys through this to decrypt the encrypted private key and then use the private key to encrypt Harry's plaintext loader. I think I'm getting pretty close.

Edited October 27, 2009 by Wookie

[Wookie]

OK, I think I've made some major progress forward. I've been slowly cleaning up the enctest.c file, figuring out what it is doing in each step and renaming variables and restructuring the code. I've refactored all of the global variables so that they are now parameters to the functions. I've trimmed all of the cruft and I've wrapped my head around the whole algorithm.

 

The reason that using bignum libraries to do decryption hasn't worked is that there is primitive framing in the encrypted data. If you take the value of the very first byte and subtract it from 256, you get the number of encrypted blocks to process. For instance, the first byte in Harry's encrypted loader is 0xFD (253). If you subtract that from 256 - 253 = 3 blocks in the "frame" to process. The blocks start immediately following the count byte and are 51 bytes long, the same size as the keys. Once you process the next 3 * 51 bytes of data, there is another block count byte. In Harry's encrypted loader, that byte is 0xFB (251) meaning that there is another 5 blocks of encrypted data in that frame.

 

So if you want to make decryption work using another bignum library, you'll have to read the first byte, calculate how many encrypted 51 byte blocks there are to process and then for each 51 byte block after that, multiply it by itself three times (raise it to the third power) and then mod it by the Lynx public key and you should get the result you're looking for.

 

What is most interesting about this is we now know the following:

 

1. How to decrypt the private encryption key for encrypting data for the lynx.

2. How to use the decrypted private key to encrypt data for the lynx.

 

I'm currently restructuring the enctest.c code so that we can pass any lynx-encrypted data streams through it. That will let me try decrypting the encrypted private key used for encrypting data for the lynx.

 

I'm getting so close to having generic Lynx encrypt/decrypt tools written in C that I can taste it.

 

--Wookie

[+karri]

I've been slowly picking at the enctest.c file, trying to clean it up, understand it and reorganize it so that I can try running other data through it. One of the things I noticed was that the decryption process doesn't really need lots of code. Here's the call tree that is generated by cflow:

 

main() <int main (int argc,char *argv[]) at enctest.c:502>:
   LynxDecrypt() <void LynxDecrypt (const unsigned char encrypted_data[]) at enctest.c:389>:
       convert_it() <void convert_it () at enctest.c:322>:
           sub5000() <void sub5000 (int m) at enctest.c:307>:
               Copy() <void Copy (unsigned char *A,unsigned char *B,int m) at enctest.c:71>
               LynxMont() <void LynxMont (unsigned char *L,unsigned char *M,unsigned char *N,const unsigned char *PublicKey,int m) at enctest.c:246>:
                   Clear() <void Clear (unsigned char *A,int m) at enctest.c:53>
                   Double() <void Double (unsigned char *B,int m) at enctest.c:80>
                   add_it() <void add_it (unsigned char *BB,unsigned char *FF,int m) at enctest.c:230>:
                   Adjust() <int Adjust (unsigned char *BB,const unsigned char *NN,int m) at enctest.c:95>:
                       Copy() <void Copy (unsigned char *A,unsigned char *B,int m) at enctest.c:71>
   Compare() <bool Compare (unsigned char *A,const unsigned char *B,int m) at enctest.c:445>:
   printf()

 

I know why the convert_it algorithm starts at byte 1 instead of 0. Montgomery multiplication works backwards in a sense and thus can carry over into the first byte. I'm slowly wrapping my head around this. It looks like that once i get this cleaned up, I'll be able to run the private keys through this to decrypt the encrypted private key and then use the private key to encrypt Harry's plaintext loader. I think I'm getting pretty close.

 

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

[Wookie]

So there is one other interesting observation I just made. Harry's plaintext loader has 410 bytes in it but the result data block is declared to be 600 bytes long in enctest.c. I noticed that there are two distinct encrypted blocks of data in the encrypted loader. What tipped me off was the block count framing that I described above. The lynx decryption algorithm decodes the first frame consisting of three encrypted 51 byte blocks into the base of the loader memory; in our case index 0 of the result data block. The second frame is decoded into memory starting at byte 256 after the base of the loader memory.

 

So what struck me as odd is that the first frame is only 3 blocks of 51 bytes of encrypted data but the second frame is 5 blocks of 51 bytes of encrypted data. Let me show you why that is odd. If you do the math for the encrypted loader data it makes sense:

 

       1 byte  (first frame block count)
  3 * 51 bytes (three blocks of encrypted data)
       1 byte  (second frame block count)
+  5 * 51 bytes (five blocks of encrypted data)
===============
     410 bytes (encrypted loader)

 

But the math for the plaintext loader doesn't make sense. For each 51 byte block, we get 50 bytes of decrypted data. What is odd is that the second frame of 5 blocks is decrypted to the 256th byte of the result memory instead of the 151st byte. If the two frames were meant to be decrypted contiguously into memory then the second frame would be decrypted to the 151st byte since 3 * 50 bytes = 150. Since it is decrypted to the 256th byte, that creates a gap of 106 bytes.

 

What that means to me is that the plaintext loader isn't 410 bytes long, it is actually 506 bytes long. We know that we're going to get 400 bytes of decrypted data (8 * 50 = 400). But we also know that there is a gap of 106 bytes in between the two blocks of decrypted data, so the whole decrypted loader is really 400 + 106 = 506 bytes.

 

Armed with that knowledge, I dumped out the entire decrypted result and here is the true plaintext version of Harry's encrypted loader:

 

const unsigned char HarrysFullPlaintextLoader[506] = {
   0x80, 0x00, 0x20, 0x4f, 0x02, 0x64, 0x05, 0xe6, 
   0x06, 0xa9, 0x08, 0x8d, 0x8b, 0xfd, 0x4c, 0x4a, 
   0xfe, 0xa2, 0x00, 0x20, 0x00, 0x03, 0xa2, 0x0b, 
   0xbd, 0x6d, 0x02, 0xbc, 0x76, 0x02, 0x99, 0x00, 
   0xfc, 0xca, 0xd0, 0xf4, 0x9c, 0x91, 0xfd, 0xa9, 
   0x04, 0x8d, 0x95, 0xfd, 0xa0, 0x1f, 0xb9, 0x00, 
   0x24, 0x99, 0xa0, 0xfd, 0x88, 0x10, 0xf7, 0x8a, 
   0x9d, 0x00, 0x24, 0xe8, 0xd0, 0xf9, 0x4c, 0x49, 
   0x03, 0x00, 0x7a, 0x02, 0x00, 0x24, 0x40, 0x1c, 
   0x07, 0xba, 0x02, 0x00, 0x04, 0x64, 0x60, 0xa2, 
   0x1f, 0x9e, 0xa0, 0xfd, 0xca, 0x10, 0xfa, 0xa9, 
   0x04, 0x8d, 0x8c, 0xfd, 0xa9, 0x0f, 0x8d, 0x01, 
   0x02, 0x60, 0xa0, 0x10, 0xad, 0xb2, 0xfc, 0x95, 
   0x36, 0xe8, 0x88, 0xd0, 0xf7, 0x60, 0x01, 0x20, 
   0x04, 0x00, 0x01, 0x00, 0x00, 0x24, 0x20, 0x91, 
   0x92, 0x09, 0x08, 0x90, 0x04, 0x06, 0x11, 0x10, 
   0x28, 0x2a, 0x47, 0x39, 0x00, 0x9d, 0x11, 0x8f, 
   0x5e, 0xd9, 0x87, 0x94, 0x5e, 0xa7, 0x4e, 0xff, 
   0xe7, 0x05, 0xba, 0xd1, 0x55, 

   /* frame one ends here and the gap begins */

                                 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

   /* gap ends here and the second frame begins */

   0x20, 0x62, 0x02, 0xe6, 0x3c, 0xe6, 0x3d, 0xa5, 
   0x36, 0x20, 0x00, 0xfe, 0xa6, 0x37, 0xe8, 0xa4, 
   0x38, 0xc8, 0x20, 0x42, 0x03, 0x38, 0xa6, 0x37, 
   0xa5, 0x38, 0xe9, 0x04, 0xa8, 0xc6, 0x3c, 0xd0, 
   0x04, 0xc6, 0x3d, 0xf0, 0x19, 0xad, 0xb2, 0xfc, 
   0x92, 0x3a, 0xe6, 0x3a, 0xd0, 0x02, 0xe6, 0x3b, 
   0xe8, 0xd0, 0xea, 0xc8, 0xd0, 0xe7, 0xe6, 0x36, 
   0x64, 0x37, 0x64, 0x38, 0x80, 0xc9, 0x60, 0xad, 
   0xb2, 0xfc, 0xca, 0xd0, 0xfa, 0x88, 0xd0, 0xf7, 
   0x60, 0xa9, 0x12, 0x85, 0x33, 0xa5, 0x33, 0x4a, 
   0x4a, 0xe5, 0x33, 0x4a, 0x2e, 0x82, 0x02, 0x2e, 
   0x83, 0x02, 0x66, 0x33, 0xa5, 0x33, 0x6d, 0x82, 
   0x02, 0x4d, 0x83, 0x02, 0xa8, 0xbd, 0x00, 0x24, 
   0x48, 0xb9, 0x00, 0x24, 0x9d, 0x00, 0x24, 0x68, 
   0x99, 0x00, 0x24, 0xe8, 0xd0, 0xd7, 0xce, 0xf5, 
   0x03, 0xd0, 0xd2, 0xa2, 0x32, 0x74, 0x00, 0xca, 
   0xd0, 0xfb, 0xa5, 0x31, 0x20, 0x00, 0xfe, 0xad, 
   0xb0, 0xfc, 0xf0, 0x03, 0x20, 0x4f, 0x02, 0xa9, 
   0x10, 0x85, 0x32, 0x38, 0xa2, 0x10, 0xad, 0xb2, 
   0xfc, 0xa0, 

   /* the enctest.c plaintext loader ended here */
   /* but there is actually more data that gets */
   /* decrypted which follows */

               0x03, 0x6d, 0xb2, 0xfc, 0x88, 0xd0, 
   0xfa, 0x95, 0x20, 0xca, 0xd0, 0xf0, 0x4e, 0xf4, 
   0x03, 0xd0, 0x2a, 0xa9, 0x02, 0x85, 0x46, 0x8a, 
   0x64, 0x00, 0x18, 0xa2, 0x1f, 0x75, 0x11, 0x95, 
   0x11, 0x65, 0x00, 0xa8, 0xb9, 0x00, 0x24, 0xe6, 
   0x00, 0xca, 0x10, 0xf1, 0xc6, 0x46, 0xd0, 0xeb, 
   0xa2, 0x10, 0xb5, 0x00, 0x55, 0x10, 0x95, 0x00, 
   0x95, 0x10, 0xca, 0xd0, 0xf5, 0xc6, 0x32, 0xd0, 
   0xba, 0xe6, 0x31, 0xd0, 0xa5, 0xa2, 0x08, 0xb5, 
   0x3e, 0x95, 0x36, 0xca, 0xd0, 0xf9, 0xea, 0xea, 
   0xea, 0x20, 0x4f, 0x02, 0xea, 0xea, 0x20, 0x03, 
   0x03, 0x6c, 0x42, 0x00, 0xff, 0x08, 0x00, 0x00, 
   0x00, 0x00, 
};

 

So this explains that we have to be smarter about how we encrypt things. We can't just encrypt one big block and have the Lynx decrypt it into memory. If the enctest.c file is a fully reverse engineered version of the Lynx ROM, then we know that the Lynx expects there to be two frames of encrypted data. One frame to be decrypted to the base of loader memory and the second frame to be decoded into memory starting at the 256th byte of loader memory.

 

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

Edited October 28, 2009 by Wookie