One-way function question…
Results 1 to 8 of 8

Thread: One-way function question…

  1. #1
    Banned
    Join Date
    Nov 2003
    Posts
    127

    One-way function question…

    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?

  2. #2
    Senior Member
    Join Date
    Nov 2003
    Posts
    247
    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.
    www.ADigitalPimp.com
    There is a ghost in the machine, and he is my friend.

  3. #3
    Senior Member Maestr0's Avatar
    Join Date
    May 2003
    Posts
    604
    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
    \"If computers are to become smart enough to design their own successors, initiating a process that will lead to God-like 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

  4. #4
    Senior Member
    Join Date
    Nov 2003
    Posts
    247
    I believe doing some encryption research could help clarify this. Pick up a good book, or just check-out the Tutorial section here.
    www.ADigitalPimp.com
    There is a ghost in the machine, and he is my friend.

  5. #5
    Senior Member
    Join Date
    Oct 2001
    Posts
    786
    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.

  6. #6
    Banned
    Join Date
    Nov 2003
    Posts
    127
    Thanx guys keep it coming...

  7. #7
    Senior since the 3 dot era
    Join Date
    Nov 2001
    Posts
    1,542
    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

  8. #8
    Senior since the 3 dot era
    Join Date
    Nov 2001
    Posts
    1,542
    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
  •