According to the malware authors, only the first 1024 bytes of a file is uploaded to the C&C server in order to search for the matching private key in cases where you lost the public key, which could take up to 24 hours. So it sounds like the C&C uses some brute force method for searching for the key. So what would that do? Try every single private key that it has generated to decrypt the first 1024 bytes until it finds the right one? But how does it know which is the right key after the decryption process? If AES key is truly random, you wouldn't be able to tell just by looking at it what you've decrypted is an actual AES key. In order to tell, you could potentially add some kind of constant bit of data that will show up in the decrypted data once the right private key is used to decrypt it. Or, in a more complex case, you'd have to go a step further and use the supposed AES key you've decrypted to decrypt the actual file header (which I presume might be stored in the first 1024 bytes) and then check if the header looks like a document that might have been originally encrypted on the infected machine.
I'm curious if anyone knows if there is anything else besides the AES key that the CryptoLocker encrypts using the RSA public key that eventually gets stored together with the file?