
November 24th, 2003, 04:40 AM
#1
Banned
Oneway function question…
I read an article about securing databases. One of the methods that were described was a oneway 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 oneway 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?

November 24th, 2003, 04:43 AM
#2
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.

November 24th, 2003, 06:31 AM
#3
I think in the case of a database you're probably using a oneway hash function, which is slighty different but works well because a oneway 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
\"If computers are to become smart enough to design their own successors, initiating a process that will lead to Godlike omniscience after a number of ever swifter passages from one generation of computers to the next, someone is going to have to write the software that gets the process going, and humans have given absolutely no evidence of being able to write such software.\" Jaron Lanier

November 24th, 2003, 06:36 AM
#4
I believe doing some encryption research could help clarify this. Pick up a good book, or just checkout the Tutorial section here.

November 24th, 2003, 06:38 AM
#5
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 oneway 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 = ( x1 ) / 2".
Now, in some cases you can't have an inverse function for ALL values. Take "y = x / ( x1)" > "x = y / ( y1)" > "x * (y1) = y" > "xy  x = y" > (subtract y from both sides, add x to both sides) > "xy  y = x" > (factor left side) > "y * (x1) = x" > (divide by x1) > "y = x / ( x1 )" Since you can't divide by zero, x can't equal 1, because if it did, you would get "f(1) = 1 / ( 11 )" = "1 / 0"! But for any other value, you can get an inverse.

November 24th, 2003, 07:58 PM
#6
Banned
Thanx guys keep it coming...

December 28th, 2003, 01:03 PM
#7
Originally posted here by Maestr0
I think in the case of a database you're probably using a oneway hash function, which is slighty different but works well because a oneway 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

December 30th, 2003, 01:01 PM
#8
Tim_axe: perhaps this gives some more background.
http://202.115.65.116/Cipher/HTML/PDF/E89/75.PDF
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

