Defcon, Turing Machine & Halting Problem: "Why is it easier to hack than to defend?"

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 ...)

Views: 975

Join the Discussion ...

You need to be a member of CISO Platform to join the discussion!

Join CISO Platform


CISO as an enabler

Started by Maheshkumar Vagadiya Jul 30, 2020. 0 Replies

Share the instances where you were able to convince the Executive management /board that CISO function is enabler rather then a hindrance.Thanks youMaheshContinue

Has Anyone Evaluated Digital Signature (like Docusign)?

Started by CISO Platform. Last reply by Yogesh Nov 19, 2020. 2 Replies

(question posted on behalf of a CISO member)Has anyone evaluated digital signature (like Docusign), any specific risk/ security areas to be looked into while finalising a vendor? Any and all inputs will be very much appreciated.Continue

What are your strategies for using Zoom in your organization after recent vulnerabilities in news about Zoom platform?

Started by CISO Platform. Last reply by ANAND SHRIMALI May 20, 2020. 4 Replies

(question posted on behalf of a CISO member)What are your strategies for using Zoom in your organization after recent vulnerabilities in news about Zoom platform?Related Question: …Continue

[Please Suggest] Corona Virus: Security advisory for work from home

Started by CISO Platform. Last reply by Bhushan Deo Mar 20, 2020. 12 Replies

(question posted on behalf of a CISO member)Due to CORONA virus most of the organizations are allowing their employees to work form home.Has any one issued security advisory for work from home ?Continue

Tags: #COVID19

Follow us

Contact Us


Mobile: +91 99002 62585

InfoSec Media Private Limited,First Floor,# 48,Dr DV Gundappa Road, Basavanagudi,Bangalore,Karnataka - 560004

© 2021   Created by CISO Platform.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service

/* */