Kerberos HMAC-RC4

Martyr

I've been thinking about this now and then for couple of months, pondering the possibility, but haven't yet bothered investigating it much.

Since Windows 2000, we've had active directory, the default authentication method on a domain being kerberos and it uses RC4-HMAC for encryption, described very well in RFC 4757

Lets say an attacker captures the AS-REQ packet which has the encrypted timestamp.

We already know the year,month and day..even the time packet was sent.
In the format: YYYYMMDDHHMMSSZ

The only thing we can't be certain of exactly is the SS and MM (minutes) values which might be off a little - unless both client/servers are synchronised with same time server in the domain.

But anyway, thats still 11 bytes of plaintext we are certain of..15 if we are absolutely sure.

The key used to encrypt the client-nonce and timestamp will always be 16 bytes.

So, can anyone see a way of recovering the 16-byte RC4 key just knowing the plaintext?

If you've studied RC4, the state table of 256 bytes, is simply mixed with the key, then XOR'd against the plaintext.

If we XOR'd the ciphertext by the known plaintext, we'd have some of the state table - just wondering if its possible to recover the entire key like this..

Coincidently while searching about RC4 vulnerabilities, there was this interesting article by Eli Biham and Yaniv Carmeli.

Efficient Reconstruction of RC4 Keys from Internal States

In this paper we present an efficient algorithm for the retrieval of the RC4 secret key, given an internal state. This algorithm is several orders of magnitude faster than previously published algorithms. In the case of a 40-bit key, it takes only about 0.02 seconds to retrieve the key, with success probability of 86.4%. Even if the algorithm cannot retrieve the entire key, it can retrieve partial information about the key.

So using the algorithms mentioned in this paper, it is possible to recover the RC4 key knowing the internal key state, but what about knowing only some of the key state?

"Even if RC4 key could be recovered, we'd still have to crack this aswell, since its calculated from the client key using HMAC-MD5" - you might argue.(see attached)

But eliminating RC4 from the computation would still accelerate recovery of client keys..because we could reverse half the normal process of HMAC-MD5 which uses a checksum of the "plaintext" in PA_DATA

Additionally, its possible to pre-compute tables of the client NTLM hash processed with HMAC-MD5, in the end, all our attack would require is 1 round of MD5!!
By recovering the RC4 key, its possible to eliminate almost all of the real time encryption..which would make passwords very easy to recover.

AES is now supported in Windows 2008/Vista, but XP/wk3 systems won't be disappearing anytime soon, so its still vulnerable to MITM attacks.

For anyone interested in the way PA_ENC_TIMESTAMP packet is decrypted normally, see attached.

Martyr

This is for the "expert" who asked me for proof.

Obviously, I can't prove its possible to recover the RC4 key knowing only some of the plaintext, because there is no research
There is article by biham..etc which re-constructs the key from known key state.

But most of you who read my post, know this..except for that expert in computing who can't understand it.

here is some code

[PHP]int main(int argc, char *argv[])
{
u8 K[16], K1[16], K2[16], K3[16];

u32 T = 1; // Message type..for PA-ENC-TIMESTAMP should always be 1

RC4_KEY data_key;

// 1. K=MD4(Little_endian(UNICODE(pwd))
ntlm1_password("fr2beesgr", K);
dump("K",K);

// 2. K1=MD5_HMAC(K,1); // with 1 encoded as little endian on 4 bytes (01000000 in hexa);
hmac_md5((u8*)&T,4,K,16,K1);
dump("K1",K1);

// 3. K3=MD5_HMAC(K1,checksum);
hmac_md5(ts_checksum,16,K1,16,K3);
dump("K3",K3);

// 4. clear_data = RC4(K3,encrypted_data);
RC4_set_key(&data_key,16,K3);

// decrypt the data
RC4(&data_key,sizeof(enc_data),enc_data,clear_data);[/PHP]


1.
[PHP]ntlm1_password("fr2beesgr", K);[/PHP]

This is MD4(UNICODE($PASSWORD))

2.
[PHP]hmac_md5((u8*)&T,4,K,16,K1);[/PHP]

4 rounds of MD5 using 0x01 as text parameter to HMAC-MD5 and the NTLM hash as key.

We can pre-compute up to this point and save results in file.

3.
[PHP]hmac_md5(ts_checksum,16,K1,16,K3);[/PHP]

This uses checksum of plaintext to generate RC4 key.

Its not possible to pre-compute this part because we can't know every checksum.

in the RC4 encryption is the PRGA function

[PHP] for(int i = 0,j = 0;i < data_len;i++)
{
t = sbox[i+1];
j += t;

j &= 255;
s = sbox[j];

sbox[j] = t;
sbox = s;

t += s;
t &= 255;

data ^= sbox[t];
}[/PHP]

its just an xor, which means you could recover part of the internal key state.
and perhaps using the algorithms in bihams text, you could recover the entire key, which would mean breaking the whole HMAC-RC4 kerberos system.