Unsolved Problems

Alright team, let’s get cracking:

From www.kottke.org:

Another Wikipedia gem: a list of unsolved problems from a number of different fields, including linguistics, physics, and computer science. (via lone gunman)

I think my favorite problem deals with the existence of one-way functions, also called hash functions1:

From en.wikipedia.org:

Description
One-way functions are easy to compute but hard to invert. Although there are several candidates for which no good (i.e. quick) reverse algorithms are currently known, it hasn’t yet been proven that any function exists for which no such reverse algorithms exist.
Importance
If one-way functions do not exist then public key cryptography is impossible. Their existence would imply that many complexity classes are not learnable, and that P≠NP.
Conjecture
It is assumed but unproven that they do exist. Several encryption systems are based on the assumption that modular exponentiation is a one-way function.

1 Kind of. Hash functions usually return a value of fixed length, which precludes them from being true one-way functions.

3 Replies to “Unsolved Problems”

  1. One way hashing functions are quite interesting indeed. The concept of a fixed length return from the function for ANY possible input yields way to the possibility (read: EXISTENCE) of hash collisions. I have come across various security articles that deal with this type of research.
    The basic concern for this is that for any input x into a hash function, there is a fixed length return sequence H(x).
    If one could find a hash collision for any given input x, let’s call this y; Then they could craft any arbitrary sequence of data y+p, that would return the same hash as x+p. In other words (or expressions 😉 ) H(y+p) = H(x+p)
    This will probably become more relevant in the future once the current one way hashing algorithms (ie: MD5, SHA-1, RIPE-160, etc..) are put under pressure by ever increasing computing power and attacks.

    People will laugh at the security we have currently when CPU speeds increase and multiple cores begin to be utilized more ubiquitously.

    This topic happily coincides with the premise of my favorite nerdcore song:
    http://frontalot.com/media.php/325/MC_Frontalot_SFTF_%2801%29_Secrets_From_The_Future.mp3

  2. Yeah, I know SHA-1 has been under scrutiny for a while now, luckily linux uses salting.
    There are also massive md5 rainbow tables that are being created now.

Leave a Reply

Your email address will not be published. Required fields are marked *