So I was just reading this interesting post about the Storm worm and it got me wondering a bit about cryptography. Since the best suggestion people had for tracking down such a worm was to track down computers the worm uses as command and control servers and turn them into honeypots to generate lists of infected machines and maybe track the thing back to it’s source.

Now a clever worm designer could put in some countermeasures like making sure that commands arrive at infected machines along many paths making it tough to figure out what is ‘upstream’ from the recipient. However, by timing the arrival of these messages you could probably defeat most simple schemes of this kind so I got to wondering if it was possible to create a really robust solution to this sort of problem.

Now there is some pretty interesting work on public key steganography. That is systems that let someone embed information in some apparently random noise using a public key so that just detecting the presence of an encoded message is computationally infeasible without the private key. For instance if you needed to pass secret messages to an agent working for another countries embassy you might embed his instructions into random information that accompanies routine communications between the embassies (say the low order bits of timestamps on emails¹) and without his private key his superiors won’t be able to detect that any extra message even existed. However, this isn’t really what you want to run a botnet. It might help avoid detection of control messages through network monitoring but if security researchers find an infected machine they can extract any private keys it contains and figure out what network connections contain secret instructions to the machine.

What would be ideal here is something like reverse public key steganography. That is a system that works as follows. Imagine you have n channels , C1..Cn, each carrying symbols randomly distributed with distribution D1…Dn and that k << n of these channels are controlled by colluding agents who know some private key S. What we want is the property that anyone who knows public key P can apply some operation Decode(C1..Cn, P) to (with very high probability) recover a message that the k agents colluded to send but that it is computationally infeasible for anyone without knowledge of S to determine which channels are being modified by the colluding agents. In other words anyone (knowing P) can figure out what message is being sent but no one can figure out who is sending it.

I kinda suspect that some system like this must have been devised already and I just don’t know how to search for it. In either case not only would it allow for the creation of a nearly perfect botnet control system (you embed control messages in the random information that accompanies DNS requests or TCP connections) but it would also have some interesting applications for P2P systems and anonymous hosting. Basically it would be useful for any situation where you want to let individuals announce things without revealing their identity. Of course it would be even better if k could be reduced to one or if the system would allow some m<

Anyway if anyone knows if such systems are possible I’m curious. It also raises the interesting question about how one would deal with botnets built by really savvy individuals like governments. If something like this works it could be almost impossible to even identify the infected computers or track down the creators using technology (normal police work like following the money would still work).