|
|
|
|
Blessed are the Geeks, for they shall internet the earth |
Internet Security
Joseph Ritchey
A hash function H is a transformation that takes a variable-size input m and
returns a fixed-size string, which is called the hash value h (that is, h = H(m)).
Hash functions with just this property have a variety of general computational
uses, but when employed in cryptography the hash functions are usually chosen to
have some additional properties.
The basic requirements for a cryptographic hash function are:
- the input can be of any length,
- the output has a fixed length,
- H(x) is relatively easy to compute for any given x ,
- H(x) is one-way,
- H(x) is collision-free.
(If you are already bored at this point, you may want to visit www.frenchmaidtv.com and then return.)
Hash anything in the database that you wouldn't want a malicious person to get their hands on, but you will only be able to compare two hashed string to each other, you will not be able to reverse the hash to get the string back. Well, can't a hashed phrase be cracked with a brute force attack? Yes and there are even hash dictionaries out there. (By the way if you have a text dictionary of common words making your own hash dictionary is not that difficult.) So what the hell is the point of hashing the damn thing in the first place? That is where salt comes in. I know now you're thinking, he needs to stay away from the brownies. But no it true the technique is called salt and salt is basically the process of tagging on extra information before you hash your information. Like this is snippet from the php world:
<?php
$my_text = "My clear text";
echo sha1($my_text ."salt") ."\n";
?>
But in a real world situation I wouldn't use "salt", what you would
want to do is create a long paraphrase of about 64 characters. Then add your
paraphrase somewhere to your text to be hashed. Strings can be played with in
all sorts of ways tagging extra text at the end or the beginning of the string
is just for simplicity. As with any other paraphrase, you must keep it secret.
For the critics out there yes is a supposed faster than brute force attack
against SHA-1. SHA-1 produces a 160-bit hash. That is, every message hashes down
to a 160-bit number. Given that there are an infinite number of messages that
hash to each possible value, there are an infinite number of possible
collisions. But because the number of possible hashes is so large, the odds of
finding one by chance is negligibly small (one in 280, to be exact).
If you hashed 280 random messages, you'd find one pair that hashed to
the same value. That's the "brute force" way of finding collisions,
and it depends solely on the length of the hash value. "Breaking" the
hash function means being able to find collisions faster than that. According to
a paper written
Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin of
the Shandong University, China, they were able to find collisions in SHA-1 in 269
calculations. But keep in mind that 269 is something like
590295810358705651712. So you are still looking at a SETI size amount of
calculations to crack it. Maybe the new Mac dual cores will finally be fast
enough.
SHA is not the only HASH out there either there are lots of other hashish
available. The best kinds of Hash originate from the Northern provinces between
Hindu Kush and, .... sorry that the wrong kind of hash. Examples of well-known
hash functions are MD2 and MD5 and SHA. I do not recommend using an MD2 or an
MD5 hash though. MDx hashes have many well known
weaknesses and have been crack many times over. Don't believe me, just download
a copy of the tool Cain & Able and see how easily you can bust one of your
MD5 hashes. There are successors to SHA-1: SHA-224, SHA-256, SHA-384, and
SHA-512. As of this writing PHP, ASP and PERL did not yet have a native
implementation of the higher SHA functions. There are third party libraries SHA
scripts and libraries available.
A final word on hashes is like anything else with computers always stay up to
date on what is going on with the type of hash function that you are using. New
cracks and exploits pop up everyday, and so do new and strong hash and
encryption methods.
So where does Hash Tables fit in all this? From wikipedia
: a hash
table, or a hash
map, is a data
structure that associates keys
with values.
The primary operation it supports efficiently is a lookup:
given a key (e.g. a person's name), find the corresponding value (e.g. that
person's telephone number). It works by transforming the key using a hash
function into a hash,
a number that the hash table uses to locate the desired value. And yes
you can write a hash table for your web app's
if you want to put the time into it. But your hash table will only be as strong
as your hash function. An yes you could even write your own hash function, but
that is beyond to scope of this article.
Some interesting reading about hashing:
http://en.wikipedia.org/wiki/Perfect_hashing
http://en.wikipedia.org/wiki/Hash_collision
http://en.wikipedia.org/wiki/Xiaoyun_Wang
http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
