<p>Consider the example <a href="http://en.wikipedia.org/wiki/Wired_Equivalent_Privacy">Wired Equivalent Privacy</a>, which is no such thing in reality: due to <a href="http://www.isaac.cs.berkeley.edu/isaac/mobicom.pdf">embarrassingly basic theoretical oversights</a> (pdf), WEP is crackable within minutes.</p>

<p>In <a href="http://www.schneier.com/essay-192.html">“Why Computers Are Insecure,”</a> Bruce Schneier quipped</p>

<blockquote>
  <p>Security engineering involves programming Satan's computer.</p>
  
  <p>And Satan's computer is hard to test. </p>
</blockquote>

CC BY-SA 2.5
2010-08-24T00:32:01.000Z
2010-08-24T00:32:01.000Z
Greg Bacon
<p>In a number of ways:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Cryptography" rel="nofollow noreferrer">Cryptography</a> (an enormously broad generalization of information security that ranges from privacy to encryption)</li>
<li><a href="https://en.wikipedia.org/wiki/Formal_verification" rel="nofollow noreferrer">Formal verification of code</a> (also see the <a href="https://web.archive.org/web/20130902044910/http://www.ertos.nicta.com.au/research/sel4/" rel="nofollow noreferrer">seL4 project</a>)</li>
<li><a href="https://en.wikipedia.org/wiki/Fault-tolerant_system" rel="nofollow noreferrer">Fault tolerance</a> and <a href="https://en.wikipedia.org/wiki/Error_detection_and_correction" rel="nofollow noreferrer">error correction</a></li>
<li><a href="https://hal.archives-ouvertes.fr/inria-00115199/en/" rel="nofollow noreferrer">Theoretical ways to prevent malware</a> (<a href="https://rjlipton.wpcomstaging.com/2010/02/26/is-it-time-to-stop-malware-forever/" rel="nofollow noreferrer">another</a>) including <a href="https://en.wikipedia.org/wiki/Code_signing" rel="nofollow noreferrer">code signing</a></li>
<li>Tamperproof Hardware</li>
<li><a href="https://eprint.iacr.org/2010/414.pdf" rel="nofollow noreferrer">Point obfusation</a> (a theoretical approach to information theoretically secure code obfusaction)</li>
<li><a href="https://en.wikipedia.org/wiki/Machine_learning" rel="nofollow noreferrer">Machine learning</a> helps to prevent and alert hack attempts in real time (think <a href="https://doi.org/10.1007/3-540-36415-3_2" rel="nofollow noreferrer">Active Wardens</a> and <a href="https://en.wikipedia.org/wiki/E-mail_filtering" rel="nofollow noreferrer">Spam Filtering</a>).</li>
<li>Much much more.</li>
</ul>

CC BY-SA 2.5
2010-08-24T01:11:10.157Z
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
CC BY-SA 2.5
2010-08-24T01:20:49.310Z
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
CC BY-SA 2.5
2010-08-24T01:30:18.433Z
@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
CC BY-SA 4.0
2010-08-24T00:29:07.447Z
2022-09-19T10:25:02.303Z
2022-09-19T10:25:02.303Z
Ross Snider
<p>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.</p>

<p>Yu Gu, Andrew McCallum, and Don Towsley. <a href="http://portal.acm.org/citation.cfm?id=1251118">Detecting anomalies in network traffic
using maximum entropy estimation.</a> In IMC ’05: Proceedings of the 5th ACM SIGCOMM
conference on Internet measurement, pages 1–6, 2005</p>

CC BY-SA 2.5
2010-10-21T08:43:48.520Z
2010-10-21T08:43:48.520Z
Joshua Brody
<p>Unlike the other answers, this is more along the lines of &quot;things we should worry about when saying something is 'provably secure'&quot; as opposed to places where TCS has been used in security. Thus, it addresses the first question of security concerns when working with theory.</p>
<p>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 '<a href="http://anotherlook.ca/" rel="noreferrer">Another Look</a>' 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.</p>
<p>Some examples (quoting/paraphrasing a few points from their site):</p>
<blockquote>
<ol>
<li><p>A security theorem is conditional — it assumes the intractability of some mathematical problem.</p>
</li>
<li><p>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 &quot;proved&quot;.</p>
</li>
<li><p>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.</p>
</li>
<li><p>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.</p>
</li>
</ol>
</blockquote>

CC BY-SA 3.0
2011-07-10T09:37:50.493Z
2011-07-10T09:37:50.493Z
2020-06-17T09:38:08.363Z
Artem Kaznatcheev
<p>Theorem provers have been used to some extent for proving correctness of software, hardware and protocols. See, for example, <a href="http://afp.sourceforge.net/" rel="nofollow">here</a> or <a href="http://en.wikipedia.org/wiki/Isabelle_%28theorem_prover%29#Usage" rel="nofollow">here</a>.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Non-interference_%28security%29" rel="nofollow">here</a>.</p>

CC BY-SA 2.5
2010-10-21T10:25:41.790Z
2010-10-21T10:25:41.790Z
Raphael
<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-21T10:16:41.977Z
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
CC BY-SA 2.5
2010-10-22T08:39:35.757Z
@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
CC BY-SA 2.5
2010-10-22T14:18:06.720Z
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
CC BY-SA 2.5
2010-08-24T00:04:45.930Z
2010-08-24T00:11:04.190Z
2010-08-24T00:11:04.190Z
matus
<p>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</p>

<p>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.</p>

<p>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. </p>

CC BY-SA 2.5
2010-08-24T00:08:00.497Z
2010-08-24T00:08:00.497Z
Aaron Roth
<p>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?</p>

CC BY-SA 2.5
2010-08-24T00:38:04.903Z
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
<cr.crypto-security><big-picture>
How does Theoretical Computer Science relate to security?
The Rook
# How does Theoretical Computer Science relate to security?

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** cr.crypto-security, big-picture

> **Comments:**
> **username_1**: 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.  

---

## 7 answers

### Answer by username_9 on 2010-08-24. Score: 20 | Accepted answer

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 by username_1 on 2010-08-24. Score: 15

In a number of ways:

* [Cryptography](https://en.wikipedia.org/wiki/Cryptography) (an enormously broad generalization of information security that ranges from privacy to encryption)
* [Formal verification of code](https://en.wikipedia.org/wiki/Formal_verification) (also see the [seL4 project](https://web.archive.org/web/20130902044910/http://www.ertos.nicta.com.au/research/sel4/))
* [Fault tolerance](https://en.wikipedia.org/wiki/Fault-tolerant_system) and [error correction](https://en.wikipedia.org/wiki/Error_detection_and_correction)
* [Theoretical ways to prevent malware](https://hal.archives-ouvertes.fr/inria-00115199/en/) ([another](https://rjlipton.wpcomstaging.com/2010/02/26/is-it-time-to-stop-malware-forever/)) including [code signing](https://en.wikipedia.org/wiki/Code_signing)
* Tamperproof Hardware
* [Point obfusation](https://eprint.iacr.org/2010/414.pdf) (a theoretical approach to information theoretically secure code obfusaction)
* [Machine learning](https://en.wikipedia.org/wiki/Machine_learning) helps to prevent and alert hack attempts in real time (think [Active Wardens](https://doi.org/10.1007/3-540-36415-3_2) and [Spam Filtering](https://en.wikipedia.org/wiki/E-mail_filtering)).
* Much much more.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_3**: @username_0: 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.  

---

### Answer by username_2 on 2010-08-24. Score: 12

Consider the example [Wired Equivalent Privacy](http://en.wikipedia.org/wiki/Wired_Equivalent_Privacy), which is no such thing in reality: due to [embarrassingly basic theoretical oversights](http://www.isaac.cs.berkeley.edu/isaac/mobicom.pdf) (pdf), WEP is crackable within minutes.

In [“Why Computers Are Insecure,”](http://www.schneier.com/essay-192.html) Bruce Schneier quipped

> Security engineering involves programming Satan's computer.
>
> And Satan's computer is hard to test.


---

### Answer by username_4 on 2010-10-21. Score: 10

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.](http://portal.acm.org/citation.cfm?id=1251118) In IMC ’05: Proceedings of the 5th ACM SIGCOMM
conference on Internet measurement, pages 1–6, 2005


---

### Answer by username_5 on 2011-07-10. Score: 8

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](http://anotherlook.ca/)' 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 by username_6 on 2010-10-21. Score: 6

Theorem provers have been used to some extent for proving correctness of software, hardware and protocols. See, for example, [here](http://afp.sourceforge.net/) or [here](http://en.wikipedia.org/wiki/Isabelle_%28theorem_prover%29#Usage).

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](http://en.wikipedia.org/wiki/Non-interference_%28security%29).


---

### Answer by username_7 on 2010-08-24. Score: 3

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.

> **Comments:**
> **username_6**: 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.  
> **username_8**: @username_6: 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.  
> **username_6**: 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).  

---

