Solving Problems with Unknown Constraints

“Software constraints are only confining if you use them for what they’re intended to be used for” 

— David Byrne (Of the Talking Heads)

I recently had an ongoing conversation that spanned several days about the subject of solving mazes. A friend casually mentioned the “Same Wall Rule”, (also known as the “Right Hand Rule”), for solving a maze. This is where if you want to find the exit of a maze you should pick a wall and follow it, with the assumption that you will eventually find the exit this way.

Same Wall Rule for Solving a Maze

I pointed out that while this rule generally works, you can’t count on it as it can fail spectacularly. For example, what if you start out next to a free-standing wall?

Same Wall Rule Failing Horribly

After that our conversation turned to other things but the next day my friend came back and said “I found the problem! The Same Wall Rule will work, but you have to start at the beginning of the maze! Then you can be guaranteed that you won’t hit a free-standing wall”.

Which is true in most cases, but what if what you are looking for an exit in a free-standing section of the maze? For example what if the treasure is in the middle or you are dealing with a 3-dimensional maze?

Same Wall Rule Failing to Find Treasure

This reminded me of a paper that Cormac Herley recently wrote titled: Justifying Security Measures. I highly recommend reading it. It points out that in the security community we often say:

Security(X) > Security(~X)

When we really mean:

Outcome(X|ABCD) > Outcome(~X|ABCD).

Which is a fancy way of showing that when we say doing X is more secure than not doing X, there usually is a large number of assumptions, (ABCD….), that we’re leaving out. Where this directly relates to the main topic of this blog, (password security), is that Herley specifically calls out the password field for the practice of ignoring constraints in our security advice. Or, to quote his paper:

“Passwords offers a target-rich environment for those seeking tautologies and
unfalsifiable claims.”

Now back to the issue of maze solving, the same problem often arises. When we make a maze solving algorithm, we’re making certain assumptions about the rules of the game. For example, the next iteration of a mapping algorithm might involve marking rooms that you have been in before to detect loops. Well there is a certain fairy-tale where that approach failed due to the marks being destroyed by a 3rd party actor:

Hansel and Gretel showing that marks aren’t always permanent

Even assuming you can safeguard your marks in the maze, that approach may still not be effective if the maze moves while you are traversing it.

I’ve never seen such an amazing premise turned into such a boring book

Note, these assumptions go both ways. For example if you are designing a super hard maze, a snarky player can often do something completely unexpected.

Seriously, why would you want to go through the maze?

I’d argue that coming up with a perfect maze solver that works for all mazes with no constraints is a near impossible problem. If you can design an algorithm, chances are someone else can come up with a situation where it will fail. On the plus side, the same goes for maze designers. If you come up with a maze with constraints, someone probably can solve it even if it’s not how you expected the maze to be solved.

*** This is a Security Bloggers Network syndicated blog from Reusable Security authored by Matt Weir. Read the original post at: https://reusablesec.blogspot.com/2017/08/solving-problems-with-unknown.html