28c3: The Science of Insecurity

Download high quality version: http://bit.ly/uSJPUL
Description: http://events.ccc.de/congress/2011/Fa...

Meredith L. Patterson, Sergey: The Science of Insecurity

Why is the overwhelming majority of common networked software still not secure, despite all effort to the contrary? Why is it almost certain to get exploited so long as attackers can craft its inputs? Why is it the case that no amount of effort seems to be enough to fix software that must speak certain protocols?

The answer to these questions is that for many protocols and services currently in use on the Internet, the problem of recognizing and validating their "good", expected inputs from bad ones is either not well-posed or is undecidable (i. e., no algorithm can exist to solve it in the general case), which means that their implementations cannot even be comprehensively tested, let alone automatically checked for weaknesses or correctness. The designers' desire for more functionality has made these protocols effectively unsecurable.

In this talk we'll draw a direct connection between this ubiquitous insecurity and basic computer science concepts of Turing completeness and theory of languages. We will show how well-meant protocol designs are doomed to their implementations becoming clusters of 0-days, and will show where to look for these 0-days. We will also discuss simple principles of how to avoid designing such protocols.

• Category

  Science & Technology

[beatsnbleeps]

Unfunny troll is unfunny. Go rate more kawasaki movies pls. We need your expertise there.

[Sampo Syreeni]

Uhm, a fixed width length field most certainly does not make a protocol context sensitive, but only blows up the (D)FA needed to recognize it. On the other hand I'm reasonably sure context sensitive grammars won't cut something like Elias codes. Otherwise, Patterson's ideas are a beautiful formalization of what I've been saying for the longest time: validate first, then compute with minimal checks. Kudos!

[vytemagic]

i came here about being insecure in public.

[Kurtis Rainbolt-Greene]

S-expressions don't need to use brackets. She specifically suggests using wrapping characters *that wont exist in the sub-language of the value*.

[Evi1M4chine]

Okay, now I’m booting Linux on that Turing-complete Rule 110 machine implemented in HTML5+CSS3. See you in A BILLION YEARS! ;)

[Evi1M4chine]

So how exactly do you use S-expressions to completely avoid escaping *and* length fields? I mean what about a string with a bracket inside? You can’t escape it. And you can’t skip it because you don’t have a length field. So it *will* end up as a ordered pair Sexpression or a parse error. And the only alternative is not to have any brackets in string at all. Which is nonsense.

How do you do this?

[Evi1M4chine]

“If you haven’t recognized it, don’t goddamn process it!” → Uuum, recognition itself is a form of processing. So we end up with a catch-22 problem of infinite recursion. Meaning this is not solution. No?

[Evi1M4chine]

Hmm… Isn’t a stack also a context? I can’t think of any way it isn’t a context.

[Evi1M4chine]

I just wrote a turing-complete ICMP echo implementation. XD

[sleeplessNerd]

Introducing a delimiter would decrease the usable range of one symbol to 255/256's to there is a linear loss in efficiency. This can be reduced by escaping though.

But it is the only safe solution as far as I can tell. Mostly because the places where this stuff is operated upon are very simple and can't introduce complex parsing (e.g. latching on a preamble of frames in an asic)

[sleeplessNerd]

Best talk in a long time. She is really awesome.

Scientific Hackery while drinking Club Mate. Science makes it better. (To quote xkcd "it works bitches")

You need a CS degree to really grasp it - It is a surprisingly simple message. - I kind of implement it partially already.

@ssyreeni: I think the DFA will blow up exponentially. Or how would you recognize the input length while using loops in the transition graph? - A PDA could do it maybe by pushing n markers on the stack or something.