The Middle Message
(“Friday 13th Attack”)
SHA-1
Block problem
Public release
© by Lehner Franz (franz@caos.at / franz@lehner.at ) Friday, 13.9.2002
Revision by Andy (andy@warmcat.com) Sunday, 15.9.2002 (English correction)
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 availble 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 orignal 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_hash is 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 dependingon 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 tosomehow 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 maually
built up the second message and performed the necessary computation.
At this point we have precooded 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 similiar 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)