8

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

I'm more interested here on non-crypto problems, such as those involving policies, enforcement mechanisms, etc.

Community
  • 1
Charles
  • 446
  • 4
  • 8
  • If you want the theoretical problems, you should try on the [crypto site](http://crypto.stackexchange.com/). – Thomas Pornin Feb 08 '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 Feb 08 '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 Feb 08 '12 at 21:38
  • Ah - gotcha. Interesting topic - hope you get some good answers. – Rory Alsop Feb 08 '12 at 21:43
  • 1
    I think you'll find several questions have already looked at some of the open problems such as [this one](http://security.stackexchange.com/q/698/6249). – logicalscope Feb 08 '12 at 22:07
  • @RoryAlsop Thanks! I hope too, I was actually talking with some colleagues, and we realized that we couldn't think immediately at some known open problems, so that's why I hope some people here can hep :) – Charles Feb 08 '12 at 22:16
  • @logicalscope Thanks, but as I mention above, I'm more interested in research topic, that is "open problem in the sense that there might exist a solution, but we don't know it yet", rather than "hard problems that we can't solve efficiently". – Charles Feb 08 '12 at 22:17
  • Users and IT people :-) – AaronS Feb 09 '12 at 07:36
  • I'm not sure it's a duplicate question, but certainly related: http://security.stackexchange.com/questions/698/what-are-the-biggest-unsolved-problems-in-it-security – Steve Feb 09 '12 at 17:45

1 Answers1

9

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.

Mike Samuel
  • 3,873
  • 18
  • 25
  • 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 Feb 09 '12 at 03: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 09 '12 at 04:47