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

Votes: 0
E-mail me when people leave their comments –

You need to be a member of CISO Platform to add comments!

Join CISO Platform

Join The Community Discussion

CISO Platform

A global community of 5K+ Senior IT Security executives and 40K+ subscribers with the vision of meaningful collaboration, knowledge, and intelligence sharing to fight the growing cyber security threats.

Join CISO Community Share Your Knowledge (Post A Blog)
 

 

 

CISO Platform Talks : Security FireSide Chat With A Top CISO or equivalent (bi-monthly)

  • Description:

    CISO Platform Talks: Security Fireside Chat With a Top CISO

    Join us for the CISOPlatform Fireside Chat, a power-packed 30-minute virtual conversation where we bring together some of the brightest minds in cybersecurity to share strategic insights, real-world experiences, and emerging trends. This exclusive monthly session is designed for senior cybersecurity leaders looking to stay ahead in an ever-evolving landscape.

    We’ve had the privilege of…

  • Created by: Biswajit Banerjee
  • Tags: ciso, fireside chat

CISO Meetup at BlackHat Las Vegas 2025

  • Description:

    We are excited to welcome you to the CISO Meetup during BlackHat USA 2025 in Las Vegas! Join us for an exclusive networking, meaningful conversations, and community building with top CISOs and cybersecurity leaders from around the globe. 

    Meetup Details:

    Location: Mandalay Bay, Las Vegas …

  • Created by: Biswajit Banerjee
  • Tags: ciso, black hat, black hat 2025, black hat usa

6 City Playbook Round Table Series (Delhi, Mumbai, Bangalore, Pune, Chennai, Kolkata)

  • Description:

    Join us for an exclusive 6-city roundtable series across Delhi, Mumbai, Bangalore, Pune, Chennai, and Kolkata. Curated for top cybersecurity leaders, this series will spotlight proven strategies, real-world insights, and impactful playbooks from the industry’s best.

    Network with peers, exchange ideas, and contribute to shaping the Top 100 Security Playbooks of the year.

    Date : Sept 2025 - Oct 2025

    Venue: Delhi, Mumbai, Bangalore, Pune,…

  • Created by: Biswajit Banerjee