RC4 Is Still Considered Harmful

Kerberos is an old authentication protocol that is still used all over the place. The core security concept is using encryption to prove knowledge of user credentials. In the handshake process for this, the user can specify what encryption protocols they support. This is a blessing to make it usable everywhere but a curse because of security. Modern Windows versions disable DES and prefer AES. However, lurking below the surface is another symmetric algorithm - RC4. The stream cipher is known to have many security issues, such as known plaintext attacks. In the RFC for Kerberos in 2006, a modification of RC4 is used in order to work around the known weaknesses of the algorithm. What are the changes? The encrypted data is protected by a keyed MD5 hash, which is used to prevent tampering. The key (confounder) is a 8 byte value. The key is derived from the hash and its base key used in the hash. The previous key and the confounder make sure that the same key is never reused for encryption. The base key is NOT the user key but is derived from a MD5 HAMC keyed with the user's key. The generation of the user key for RC4 Kerberos has historic principles that make it the worst part of the algorithm. When trying to migrate from NTLM authentication (which transfers MD4 hashed passwords), they decided the best course of action was simply using this hash as the RC4-HMAC Kerberos key. They creates a few problems: If an attacker has access to the ciphertext of the RC4-HMAC key, they can attempt to brute force the password. The key isn't random - it's the output of MD4. Kerberoasting can be used here as well. This is the process of requesting a ticket from the Ticket Granting Service (TGT), which is encrypted with this key. Using a known plaintext attack, we can attempt to brute force the key as well. There is a variant of this called AS-REP Roasting as well. Everything prior to this was background. The author was simply trying to understand on the Windows Defender Credential Guard (CG) implements the various Kerberos encryption schemes. They started reverse engineering the DLL CRYPTDLL.DLL. Although this interface is undocumented, the DLL had to export functions and they were easy to work with. While doing this, they noticed there were several private types for encryption they wanted to dive into. One of these algorithms was RSADSI RC4-MD4. This stood out to them for a few reason: The key is 16 bytes but only the first 8 are used. The derived session key is only 5 bytes of randomness. The rest of it is 0xAB repeated. There's no key blinding. Practically, this means that ciphertext can be duplicated between two messages. No cryptographic hash to protect tampering with the ciphertext. With RC4 being a stream cipher, this is particularly bad. The first thought on exploitation was brute forcing the 40 bit key - but we can do better. A message to the Key Distribution Center (KDC) can be forced to return an error message with an encrypted timestamp. Since the timestamp is known, a plaintext attack can be used to recover the key! In particular, plaintext byte XOR timestamp byte = key byte. Additionally, the AS-REP is encrypted with the same session key. Since we know the bytes for the keystream of RC4 from the timestamp, this can be used on the AS-REP message as well. Unfortunately, the overlap of the timestamp and other known values is only 4 bytes of the 5 byte key in the AS-REP structure. Of course, we can brute force the final byte by requested encrypted data and attempting to decrypt it. This attack does require a proxy in order to MitM the request being made to the KDC. Can we do this without a privileged network position? If pre-authentication is disabled, then anybody can make a request to get the TGT for a user and specify the RC4-MD4 encryption algorithm. With this, KDC sends back the encrypted AS-REP structure. The very beginning of this structure is DER encoded data, which should be consistent. So, we can use a plaintext attack once again to derive the streamkey for RC4. At this point, we still don't know the 40 bit key that we're trying to obtain or the streamkey for those bytes. With this much information, we are able to successfully encrypt a timestamp to send back to the KDC though. Now, it's time for the magic and hacker mindset... the timestamp is an ASCII string that is null terminated. If the string is NOT null terminated, then an error message is sent back. If it is, then a success message is sent back. Using this information, we can determine when the plaintext is null. Since we have the encrypted byte we created and know this is a nullbyte, we can recover the keystream for this. The trick above can be used for each byte in the timestamp in order to recover each keystream byte to decrypt the AS-REP structure! There's a second trick that must be used in order to keep writing nullbytes though... A quirk of the DER formats long form can be used to continue reading bytes past the point of the actual timestamp. Since we have 28 possibilities for each byte and 5 bytes to get, a total of 1280 requests are required. Not bad compared to the 240 from before. Overall, an absolutely amazing post for Project Zero. A few lessons learned from this: RC4 is bad and stream ciphers are hard to use properly. Don't compromise when writing a protocol for cryptography. Everything should be designed with as much consideration as possible; from strong algorithms to large keys. Tricks may require the addition of another trick! This is seen with the nullbyte padding attack requiring the DER format attack. I commonly think of a trick and if the trick doesn't work, I move on; I should consider this attack in future work.