How does Theoretical Computer Science relate to security?

Question

When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker. So in a sense securing software is the process of making software less useful. In Theoretical Computer Science you aren't working with the real world. So are there any security concerns when working with pure theory? Or the other side of the coin, does Theoretical Computer Science affect the real world of people getting hacked? If so, what security topics are considered Theoretical?

Answer 1

Your intuition that "insecurity" is due to software that is "too useful" is correct, in a sense. There is a large and growing theoretical literature on "differential privacy" that formalizes your intuition. See for example, here: research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf

Here, we think of the input to an algorithm as being a "database", and the algorithm is "insecure" if it reveals too much information about any one person's data in the database. An algorithm is $\epsilon$-differentially private if the algorithm's output does not depend much on any one input: specifically, changing a single entry in the input database should only change the probability of any output of the algorithm by at most an $e^\epsilon$ factor.

Of course, making an algorithm private makes it less useful: a $0$-differentially private algorithm produces outputs that aren't even a function of the inputs at all! But it turns out you can try and carefully balance the tradeoff between privacy and utility, and can get very private algorithms that nevertheless are very non-trivially useful.

Answer 2

Consider the example Wired Equivalent Privacy, which is no such thing in reality: due to embarrassingly basic theoretical oversights (pdf), WEP is crackable within minutes.

In “Why Computers Are Insecure,” Bruce Schneier quipped

Security engineering involves programming Satan's computer.

And Satan's computer is hard to test.

Answer 3

In a number of ways:

• Cryptography (an enormously broad generalization of information security that ranges from privacy to encryption)
• Formal verification of code (also see the seL4 project)
• Fault tolerance and error correction
• Theoretical ways to prevent malware (another) including code signing
• Tamperproof Hardware
• Point obfusation (a theoretical approach to information theoretically secure code obfusaction)
• Machine learning helps to prevent and alert hack attempts in real time (think Active Wardens and Spam Filtering).
• Much much more.

Answer 4

There's a lot of real-world motivation for the study of streaming algorithms that comes from network intrusion detection. The paper below uses streaming algorithms for empirical entropy to detect anomolies in your network traffic.

Yu Gu, Andrew McCallum, and Don Towsley. Detecting anomalies in network traffic using maximum entropy estimation. In IMC ’05: Proceedings of the 5th ACM SIGCOMM conference on Internet measurement, pages 1–6, 2005

Answer 5

Unlike the other answers, this is more along the lines of "things we should worry about when saying something is 'provably secure'" as opposed to places where TCS has been used in security. Thus, it addresses the first question of security concerns when working with theory.

As hackers say, theoretical results are often tangential to real-world security. This sort of argument has been made more theoretical, scientific, and precise by Alfred Menezes and Neal Koblitz in their series of 'Another Look' papers (warning: the site seems a little confrontational to me, but I think the basic idea of questioning assumptions is very important). They point out weaknesses in standard assumptions in cryptography, even in seminal papers.

Some examples (quoting/paraphrasing a few points from their site):

1. A security theorem is conditional — it assumes the intractability of some mathematical problem.

2. Often the intractability assumption is made for a complicated and contrived problem: in some cases the problem is trivially equivalent to the cryptanalysis problem for the protocol whose security is being "proved".

3. Sometimes a proof has a large tightness gap, but parameter sizes are still recommended as if the proof had been tight. In such cases the proof usually gives a useless lower bound on the running time of a successful attack. Further, an asymptotic result does not necessarily provide any assurance of security for parameters in the range used in practice.

4. A security theorem uses a certain model of security. Certain attacks — especially side-channel attacks — are very hard to model, and the models that have been proposed are woefully inadequate.

Answer 6

Theorem provers have been used to some extent for proving correctness of software, hardware and protocols. See, for example, here or here.

The problem of data flowing in undesired ways through programs (an thus causing a potential leak) has been modelled theoretically using the notion of (non-)interference; get pointers here.

Answer 7

Decidability is a central concern in programming language research. That is, much effort is being invested in constructing programming languages which only accept code which satisfies certain properties. Typical static languages only provide weak guarantees, like rejecting a program if certain methods do not exist, but imagine if the language could also throw out programs which, for instance, improperly use mutexes, or attempt to read beyond the end of memory regions. It is clear that decidability issues come in quickly (simplest scenario: specify that your compiler should only accept terminating programs), and certainly, there are efficiency concerns (the ML type-checker has doubly exponential cases).

In any case, the PL research community is very interested in security (do you trust your browser to run arbitrary foreign code?!), and their questions lead into many classical CS theory questions.