Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I know it might seem a bit too much theoretical, but I was wondering if there was some list of known open problems in security?

In a similar way that there are open problems in Theoretical Computer Science: http://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science, it would be interesting to get a similar list in security, especially for research purposes.

Note that I am particularly interested in theoretical/research problems, rather than concrete usage or implementation problems, as those given in this list: What are the biggest unsolved problems in IT Security?.

Any idea/suggestion/comment is welcome, this is just question that came up to my mind after a panel discussion at a security conference.

EDIT: As pointed out by Thomas, I'm more interested here on non-crypto problems, such as those involving policies, enforcement mechanisms, etc.

share|improve this question
If you want the theoretical problems, you should try on the crypto site. –  Thomas Pornin Feb 8 '12 at 21:27
Well, actually, I'm more interested in non-crypto problems, as they already have quite well defined problems. Thanks for pointing this out, I will update my question! –  Charles Morisset Feb 8 '12 at 21:30
@RoryAlsop Yes, I actually cite this question already in my question, and I'm rather interested in theoretical/research problems, while it seems (but I might be wrong) that this question focuses more on concrete implementation problems. It also seems that the answers given for this question show unsolvable problems rather than open ones. –  Charles Morisset Feb 8 '12 at 21:38
Ah - gotcha. Interesting topic - hope you get some good answers. –  Rory Alsop Feb 8 '12 at 21:43
I think you'll find several questions have already looked at some of the open problems such as this one. –  logicalscope Feb 8 '12 at 22:07

1 Answer 1

Covert channels and side channels are hard to eliminate.

Additionally, many of the open problems in computer science have implications for security.

There is a need for formal ways to specify software, and there is a need for formal ways to specify security requirements.

The difficulty we have proving program correctness for critical programs the size of operating systems, means that it is difficult to prove that widely used security critical code (IP stacks, OpenSSL) is correct.

The inability to efficiently check for ambiguity in a grammar, means it is hard to prove that an authority carrying message will exercise only the authority intended.

The inability to prove halting for a broad and interesting subset of programs makes it hard to reason about denial of service and resource hogging.

The inability to tightly bound aliasing statically means it's hard to statically prove that data does not leak from one part of a program to another.

share|improve this answer
Thanks, you make a very good point by relating security problems to more "traditional" software problem. However, correct me if I'm wrong, but it seems that most problems you mention are not really open, but just hard. For instance, the halting problem is not open: we know that it's undecidable to know whether a program (including security programs) stops or not. Similarly, we know that in general, because of aliasing, an assignment may have a different effect according to the context. Unless you were thinking about something more specific, which would be very interesting to discuss! –  Charles Morisset Feb 9 '12 at 3:47
@CharlesMorisset, Sorry. I chose poor examples and I interpreted "open" not as "there exists no proof that answers the question Q" to "there is no solution or good heuristics for problem P, therefore C.S. practitioners lack good tools/methodologies for producing code with property R." –  Mike Samuel Feb 9 '12 at 4:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.