Malicious Cryptography: Exposing Cryptovirology

Chapter 8

Coping with Malicious Software

This chapter is likely to seem quite out of place in this book. Nevertheless, after dedicating so many chapters of this book towards malicious software attacks we felt obliged to present some results on how to defend against these attacks. This chapter is not a how-to manual to recover from a viral infection. Rather, a number of proactive and reactive security measures are given to combat the spread of self-replicating malware. Antiviral heuristics are presented along with their counter-heuristics, their counter-counter-heuristics, and so forth, to illuminate the challenges facing viral containment. The chapter also includes heuristics for identifying cryptoviruses and cryptotrojans wherever they may reside. These heuristics are based on the fact that cryptoviruses and cryptotrojans must contain a public key which has certain mathematical properties.

8.1 Undecidability of Virus Detection

A number of real-world problems that would be nice to be able to solve are in fact not solvable. For instance, it would be useful to be able to determine algorithmically if on input¹ M and w, where M is an arbitrary given Turing machine and w is an arbitrary given input string, whether or not M accepts² w. This is known as the halting problem. It is a decision problem since the answer comes in the form of yes or no. To solve this problem it would be necessary ...