Copy Link

Add to Bookmark

Report

The Middle Message (“Friday 13th Attack”) SHA-1 Block problem

@xbox

Published in

xbox

· 10 months ago

Summary

In this document I describe a novel method to avoid issuing the original encryption key with code that performs a third party decryption action. This was conceived as a way to allow the Xbox Linux team issue code performing such an action while being able to keep their code free of any significant literals from the original BIOS.

Background

The X-Box Hard Drive (HDD) is supplied with the ATA security features in use. This causes the drive not to respond to most requests from reset until an unlock code is sent to the drive.

Microsoft chose to give each HDD a different unlock code. To allow the X-Box to unlock its drive for normal operation, they stored an encrypted version of the unlock code in EEPROM on the X-Box motherboard. The native BIOS in the X-Box reads the EEPROM data, performs some crypto involving a 16-byte 'key', and sends the result to the HDD in a SECURITY UNLOCK ATA command.

To be even more restrictive, other ingredients in the encrypyion algorithm include the HDD model and serial numbers, the intention being to make it impossible for one X-Box to use the drive of another.

This restrictive process posed a problem for the Xbox Linux team, who are working on a replacement BIOS for the X-Box, containing only clean code, which needs to be able to boot from the HDD. Although Speedbump had written working code for the unlock action, it was considered undesirable to have to issue the code with the original 16-byte key in it as a literal. Debate about how best to handle this continued until Friday 13th September 2002....

Notes:

1) Since the whole point of this effort was to cleanly avoid having to distribute the actual key, the Key used in this document is:

unsigned char key[16] = { 
         0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08, 
         0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,0x10 
};

You can probably guess that this was not the actual key used by MS :-)

2) Speedbump has written a detailed description of the HDD unlock code encryption algorithm available at http://xbox-linux.sf.net/articles.php?aid=2002224023814 which will be useful in understanding the following.

The SHA-1 algorithm

Here is a part of Speedbump's original code which performs the decryption action

HMAC_SHA1(key_hash, 
          EEPROMKey, 16, 
          (unsigned char *)data_hash, 20, 
          NULL, 0); 

rc4_prepare_key(key_hash,20,&RC4_key); 

//decrypt data (from eeprom) with generated key 

rc4_crypt(data1,8,&RC4_key); 
rc4_crypt(data2,20,&RC4_key);

If you look at the sequence, you can see that the Eeprom key - EEPROMKey- itself is not actually used for the calculation. Instead, key_hashis computed from the hashed result of EEPROMKey and data_hash - this consisting of a block of data taken from the Eeprom of the Xbox - that goes on to be used in the rest of crypto algorithm. The EEPROM data that makes up data_hash is different for each xbox, and so because key_hash depends on this unique data_hash, it too has a different value depending on which xbox it is computed on.

key_hash is the “crypt_key”, which is subsequently prepared by rc4_prepare_key and then used in the rest of the crypto sequence.

So, our goal is to find a way in the HMAC_SHA1() system to somehow no longer need EEPROMKey.

HMAC_SHA1() explored

So, what does the HMAC_SHA1() actually do?

HMAC_SHA1(key_hash, 
          EEPROMKey, 16, 
          (unsigned char *)data_hash, 20, 
          NULL, 0);

key_hash is the result array, EEPROMKey we know is the magic key we are trying to lose, 16 bytes being its length. The next two arrays are the inputs to the function, first a pointer to the array and then the length of the array.

In this particular case, only one input array data_hash is used, and this is always 20 bytes. The second input array being NULL, it can be ignored. (Later the function is called again with two input arrays, but we can ignore it for now)

Here is the actual code inside HMAC_SHA1():

void HMAC_SHA1( unsigned char *result, 
         unsigned char *key, int key_length, 
         unsigned char *text1, int text1_length, 
         unsigned char *text2, int text2_length ) 
{ 
      unsigned char state1[0x40]; 
      unsigned char state2[0x40+0x14]; 
      int i; 

      for(i=0x40-1; i>=key_length;--i) state1[i] = 0x36; 
      for(;i>=0;--i) state1[i] = key[i] ^ 0x36; 

Seq1  quick_SHA1 ( &state2[0x40], 
                state1, 0x40, 
                text1, text1_length, 
                text2, text2_length, 
                NULL ); 

       for(i=0x40-1; i>=key_length;--i) state2[i] = 0x5C; 
       for(;i>=0;--i) state2[i] = key[i] ^ 0x5C; 

Seq2   quick_SHA1 ( result, 
                 state2, 0x40+0x14, 
                 NULL ); 
}

In the first, seq1, call to quick_SHA1(), we can see it is effectively (as we are calling HMAC_SHA1() with text 2 as NULL):

quick_SHA1 ( output, 
             state1, 0x40, 
             text1, 20, 
             NULL );

The SHA-1 algorithm is designed for 64 byte blocks, so the code deals with the first 64 bytes and then the remaining 20 bytes, as two separate SHA-1 actions.

The first SHA-1 block state is generated from the RC4 key, with the padding bytes set to 0x36.

Examining the first SHA-1 sequence

The first SHA-1 block is started with the original SHA-1 reset variables (found in sha1.c)

      for(i=0x40-1; i>=key_length;--i) state1[i] = 0x36; 
      for(;i>=0;--i) state1[i] = key[i] ^ 0x36; 

Blk 1   Start: 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 
                       (Original Reset Values) 

        37343532 3330313E 3F3C3D3A 3B383926 key^0x36 
        36363636 36363636 36363636 36363636 
        36363636 36363636 36363636 36363636 
        36363636 36363636 36363636 36363636 
        Result : F67C8ECD 6FAB0899 1BCDD028 5881C1BF 174EC320

(This Result is constant, and we store it, as it is the same in every Xbox)

Blk 2.  Start: F67C8ECD 6FAB0899 1BCDD028 5881C1BF 174EC320 
        528D987A 953F2E71 D82DDC29 66F20C6A // Text1[20] 
        E3F248C8 80000000 00000000 00000000 + SHA padding 
        00000000 00000000 00000000 00000000 
        00000000 00000000 00000000 000002A0 + SHA lenght 
        Result : 9CFFBB94 78CD99C3 88815462 9B48EFFF 29E46715

( REMEMBER THIS KEY for NEXT sequence !!)

The result of the computation for the first block is used as the starting state for the second block operation.

The result of the first block is a constant, and does not depend on the EEPROM data.
So I created a new function HMAC1Reset(&context); which is able to directly initialize the SHA-1 state for Block2 computation to this result without having to compute it with the key.

Some further information about the second block:

The first 20 bytes of the second block contain the EEPROM data_hash value. The 0x80 at byte 20 in the second block is the SHA-1 Block end signal and the final 0x02a0 is the SHA-1 length variable.

So I only took the result of the first SHA-1 block , stored in a Reset value, and then manually built up the second message and performed the necessary computation.

At this point we have precoded the result state of the first key computation seen earlier, which contains no information specific to the X-Box it was executing on, and does not contain the original RC4 key.

Examining the second SHA-1 sequence

The second sequence is very similar to the first, except the different XOR seed.

       for(i=0x40-1; i>=key_length;--i) state2[i] = 0x5C; 
       for(;i>=0;--i) state2[i] = key[i] ^ 0x5C; 

Blk 1    Start with: 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 
                        (Original Reset Values) 
         5D5E5F58 595A5B54 55565750 5152534C 
         5C5C5C5C 5C5C5C5C 5C5C5C5C 5C5C5C5C 
         5C5C5C5C 5C5C5C5C 5C5C5C5C 5C5C5C5C 
         5C5C5C5C 5C5C5C5C 5C5C5C5C 5C5C5C5C

Result : AE44CF97 9819A09B CB5F99BB 651405C6 C7D7FBD3 (This Result is constant, and we store it, as it is the same in every Xbox)

Blk2     Start with: AE44CF97 9819A09B CB5F99BB 651405C6 C7D7FBD3 
         9CFFBB94 78CD99C3 88815462 9B48EFFF // SHA1 result 
         CC57F495 80000000 00000000 00000000 // we remembered 
         00000000 00000000 00000000 00000000 
         00000000 00000000 00000000 000002A0 

         Result : 4E354E86 47D29C9B 36532003 17783316 EBF5DB32

And this is the RC4 key, we acutally use in the RC4 key sequence.

So, we can again store the result from block 1, as it never changes. This is stored in the HMAC2Reset(&context); function. However... examine the Blk 2 contents in the table above. The message 9C . . . . is the SHA-1 result of the Block 2 from the first SHA-1 sequence shown earlier.

The Result is the RC-4 key, from which the RC_4 intermediate key is calculated.

The sha1_keyvalidation() function is slightly more complex as there are two messages involved. But is is no different in principle and in fact uses the same values.

Conclusion

The end result of this analysis is that the X-box Linux team were able to issue their code without including the original key, yet are able to unlock the HDD. The improved decryption code also has the advantage of running 30-40% faster than the original, as the CPU-intensive SHA-1 algorithm is executed only twice instead of the previous four times.

Franz (franz@caos.at)