One-way function question…

[rabit]

I read an article about securing databases. One of the methods that were described was a one-way function. Since f(x) is supposed to be "almost" impossible to convert back to x, this will make the database searchable & transparent @ the same time. Can someone pls clear up for me how is it guaranteed that the one-way function output [ f(x) ] is always unique. If f(x) is used as a search index is must be unique. What are the math techniques that make this happen?

[SonofGalen]

The function may not always be unique in the fact that it is the first time it will be used, in fact, that may happen more times than we'd like to admit.

However, it can be unique in the fact that it will often be based off of prime numbers, many discovered by the Mercin(SP) Prime Number Project, which many people participate in. The use of prime numbers will help insure the fact that it will be original and it can only be correctly translated one way.

For further understanding, I would do some study into the nature of functions.

I hope this helps.

[Maestr0]

I think in the case of a database you're probably using a one-way hash function, which is slighty different but works well because a one-way hash funtion takes a variable sized message for input compresses it a produces a fized size digest. This works well for a database by being a fixed length and using less overhead than a one way function based on a trap door. Putting the same value into a hash function will produce the same digest, since the digest is a fixed length there must exist another value(s) other than the initial which when put through the hash funciton will produce an identical digest. That is to say that somewhere H(X) = H(Y). This is called a collision and finding one could make it possible to retrive the original message. Doing this is needless to say difficult. How difficult you ask? Well popular hash functions today are MD5,SHA and RIPEMD. Each creates a different sized digest and vary in the level of collision resistant properties but most of these are very difficult although not impossible to crack, most attacks against them would likely be brute force or dictionary so ensuring the original message is difficult to guess will help. And as far as using them for a primary key, I believe that although not mathematically unique you should be able to find a key which should work fine, something like H(Username + Password)?

-Maestr0

[SonofGalen]

I believe doing some encryption research could help clarify this. Pick up a good book, or just check-out the Tutorial section here.

[Tim_axe]

Man, this took so long to write I'm no longer #2...

I don't know which one way functions are used in a database, but I doubt they are used in places other than authentication or storing a username / password database. If you use it to encrypt content (news, articles, etc), then you wouldn't be able to decrypt it to display it, much less search through it, unless you type the entire thing in, run it through that one way function, and wait for the "found" alert...all the while hoping you didn't misspell that one word... So probably only usable in username / password databases. Correct me if I'm wrong here. (and as has been mentioned, isn't always 100% unique, but is unique enough from similar and dissimilar inputs that it can reliably be used to make sure that a file you downloaded wasn't modified during download)

Some examples of a one way (hash) function:
MD5 - http://www.spitzner.net/md5.html
SHA - http://home.ecn.ab.ca/~jsavard/crypto/mi060501.htm http://home.ecn.ab.ca/~jsavard/crypto/mi0605.htm

How do these one-way functions work?
You find a function f( x ) where there is no inverse g( x ) or f^-1( x ), so there is no g( f(x) ) that gets you x. This can be done in programs by dropping data, or by combining data in a way that you can't seperate it. Either way you lose the original data. For example, adding up all of the ASCII values in a text file gives you one huge number, but using that huge number you can't get the original data since the length of the file, the order of values in that file, and the values themselves are not stored in that one big number. That is an example of a one way function, albit simple.



Now I'll toss in some info on finding the inverse of basic functions just for fun, and so you can see some math in action; but it isn't used like this in one way functions like in encryption to my (limited) knowledge, these are just concepts. Note that for other functions (such as sin, cos, tan, etc) you can find the inverse of those functions (arcsin, arccos, arctan) but there are special rules you have to follow because the inverse functions aren't always *functions.* I also have a link if my examples completely throw you off, which they probably will given the fact that I decided to just sponatneously do that...

Link: http://www.sosmath.com/algebra/invfunc/fnc1.html - read this if I completely lose you here.

To find the inverse of a function (regular algebra math now), you swap the x and y in the equation, and solve for y. This is because essentially you mirror the values over x=y. For example, the inverse of "y = 2x + 1" -> "x = 2y + 1" -> "x - 1 = 2y" = "y = ( x-1 ) / 2".

Now, in some cases you can't have an inverse function for ALL values. Take "y = x / ( x-1)" -> "x = y / ( y-1)" -> "x * (y-1) = y" -> "xy - x = y" -> (subtract y from both sides, add x to both sides) -> "xy - y = x" -> (factor left side) -> "y * (x-1) = x" -> (divide by x-1) -> "y = x / ( x-1 )" Since you can't divide by zero, x can't equal 1, because if it did, you would get "f(1) = 1 / ( 1-1 )" = "1 / 0"! But for any other value, you can get an inverse.

[rabit]

Thanx guys keep it coming...

[VictorKaum]

Originally posted here by Maestr0
I think in the case of a database you're probably using a one-way hash function, which is slighty different but works well because a one-way hash funtion takes a variable sized message for input compresses it a produces a fized size digest. This works well for a database by being a fixed length and using less overhead than a one way function based on a trap door. Putting the same value into a hash function will produce the same digest, since the digest is a fixed length there must exist another value(s) other than the initial which when put through the hash funciton will produce an identical digest. That is to say that somewhere H(X) = H(Y). This is called a collision and finding one could make it possible to retrive the original message. Doing this is needless to say difficult. How difficult you ask? Well popular hash functions today are MD5,SHA and RIPEMD. Each creates a different sized digest and vary in the level of collision resistant properties but most of these are very difficult although not impossible to crack, most attacks against them would likely be brute force or dictionary so ensuring the original message is difficult to guess will help. And as far as using them for a primary key, I believe that although not mathematically unique you should be able to find a key which should work fine, something like H(Username + Password)?

-Maestr0

the chances to find H(X) = H(Y) are not so small using new bruto force attack techniques. One of those is based on the known principle of the birthday paradox reducing the number of guesses from 2^n to 2^n/2

[VictorKaum]

Tim_axe: perhaps this gives some more background.
http://202.115.65.116/Cipher/HTML/PDF/E89/75.PDF