Conficker, RSA and RC4

I was reading the excellent paper An Analysis of Conficker's Logic and Rendezvous Points from SRI and was surprised to learn that Conficker botnet updates are distributed at its rendezvous points as encrypted and signed binaries using RC4 and RSA (the “R” in both cases here stands for Ron Rivest). Both the A and B variants of Conficker use these checks to ensure that the updates have been created by the Conficker authors – just like any other software vendor issuing updates and patches. The paper depicts the update process as follows

So each Conficker client carries an RSA public key E for signature verification. A Windows binary file F is encrypted and signed as follows

• Hash F to produce a 512-bit hash M
• Encrypt F with RC4 using M as the key
• Sign M using private key D

A Conficker client authenticates the encrypted binary as follows

• Using the embedded public key E, compute the signature verification to recover M
• Decrypt the encrypted binary using RC4 and M as the key
• Verify that the hash of F is in fact M

For Conficker A, the RSA key is 1024-bits and 2048-bits for Conficker B, both of which are listed in the paper. That’s a large public key for Conficker B but it is dwarfed by the 512-bit symmetric key used in RC4. Yes RC4 can support such huge key sizes, and I will explain in a future post how this is possible.