# How does Theoretical Computer Science relate to security?

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?

-
The perspective of CS Theory presented is subjective and very arguable and is also not required to pose the question. The question seems to focus specifically on hacking, which is a broad subject in and of it self (ranging all the way to social engineering techniques) and does not come close to what "being secure" entails. For these reasons I have downvoted. However, I feel like the question is coming from a good place and has some interesting aspects to it so I have answered below. – Ross Snider Aug 24 '10 at 0:38

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.

-

In a number of ways:

-
I honestly don't believe you have ever found a vulnerability, patched a single piece of code or have even seen the inner workings of a real world vulnerability. – The Rook Aug 24 '10 at 1:11
Using OllyDbg I patched my gdi dll to fix the (second) cursor vulnerability (obviously without source code) before Microsoft's patch Tuesday. Again using OllyDbg I patched a closed source emulator to make it cheat proof for (embarrassingly) a Pokemon competition. I found a 0day in a webcam project and have scored reasonably high on a large number of wargames (including Blacksun, which has ASLR and PaX enabled). I won't mention some of the more nefarious things I've done.... Shrug; Why would it matter if I had or had not? Please don't flame. – Ross Snider Aug 24 '10 at 1:20
@The Rook: If you believe Ross's list has little connection to the actual practice of software security, then say so. Maybe even giving some examples would be helpful, or adding an answer of your own detailing just how far away TCS security research is from actual security practice (which I think would be very interesting to read). But there's no need to demean Ross. – Joshua Grochow Aug 24 '10 at 1:30

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.

-

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

-

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.

-

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.

-

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.

-
Any proper high level language (read: other than C[++]) does not give the programmer control over memory access, so I would consider this problem solved. – Raphael Oct 21 '10 at 10:16
@Raphael: Given that a vast amount of software is still written in C and C++, this problem cannot simply be considered solved. Furthermore, techniques for addressing code injection attacks on Javascript, for example, are still in their infancy. There's a lot to be done. – Dave Clarke Oct 22 '10 at 8:39
The fact that certain environments ignore existing solutions (sometimes for good reasons) does not make the problem (here: accessing forbidden memory addresses) less solved. Some things that are hard to check can be easily circumvented by appropriate invariants. You can, for example, demand formal proof of termination from your programmer (cf Isabelle/HOL). – Raphael Oct 22 '10 at 14:18