Defcon is the time when I have no business meetings and am quite disconnected with the world. A good time to immerse myself in my own thoughts. Last week during Defcon @ Las Vegas, I was thinking on how difficult it is build a secure system. We get amazed by hacking various stuff but is lot more amazing to think how tough it is to build a secure system.

"Halting problem" makes it practically impossible to build a secure system

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. (Source Wiki)

Now what does it imply? It implies that the halting problem is applicable to our computer programs and we cannot determine if any program will halt with a given input. This further implies that we can model the possibility of the existence of any vulnerability (e.g. a crash while fuzzing) a halting problem. And we cannot determine whether the program will halt unless it does. 

(Read more:  Top 5 Application Security Technology Trends)

Multi-stage attack chaining is a PSPACE complete problem

Well, I worked on this long at "iViZ Security"  long time back when we were researching on how to find all the permutations and combinations of attack paths. My knowledge could be a bit dated but in any case this is a damn "hard" problem.

Imagine if you want to combine multiple vulnerabilities to execute a chain of attacks. You may have obtained partial privilege by exploiting some vulnerability. Then you use privilege escalation. Get root. Sniff. Now that's a multi-stage attack. We researched on finding all the permutations and combinations of attacks. After working on this for a while we got the nasty issue of requirement of space and memory to store the information of states. We found that it is a PSPACE complete problem. 

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. (Source-Wiki)

So the conclusion is that it virtually impossible to find all the permutations and combinations of attack paths. To secure you need to stop all such paths but to break you need to find just one. So making sure that we defend all of them is pretty hard.

(Read more:  How the Heartbleed bug was found by Antti Karjalainen - discoverer ...)