Blogaria

What's a hash value anyway?

The principle works as follows. One can convert text to a value by chopping the text into chunks and feeding them into some algorithm which is non-reversible. That means that if you have the text, you can compute the value - but not the other way 'round.

Imagine the following hash function: If you want to compute the hash value of a name, then take each letter of that name, where a=1, b=2 and so on, and add these values. The result is the hash of that name. This very simple hash function illustrates the concept: "karel" would become 11+1+18+5+12=47, while "eddie" would become 27. But knowing only the number 47, it would be impossible to reconstruct my first name. So the algorithm is truly one-way.

What good is storing a hash instead of the original data?

So based on this algorithm, one could distinguish two names without actually knowing them, but only knowing the hash. E.g., let's say that both Eddie and I register at some website. I am mainly interested in music and build up my profile accordingly, while Eddie is interested in tech news stories. Now let's say that the website owner is so privacy-aware that he decides not to store the usernames in a database, but only the hashes. I can still log on using "karel" and Eddie can log on using "eddie", but the first thing the website will do, is convert my name to "number 47" and Eddie's to "number 27". Then the website looks up a personal profile based on the hash number, and shows corresponding data on the site. So profile number 47 will display playlists of music, and profile number 27 will display the latest tech news. The trick here is that the actual user name only exists on the login page, where I enter "karel" and Eddie enters "eddie". Beyond that login page, the user name no longer exists, only the hash!

No problems so far. But what is it good for? Well, one important aspect is, that my username is not stored in the site's list of profiles. So a malevolent sysop there cannot get at my username and log in using my account! Since only number "47" is known there, the malevolent sysop has no way of knowing that he must type "karel" to steal my identity.

But wait! This hash algorithm isn't too safe, is it? Number 47 can also be constructed using four j's (four times 10) and one g (7). So user name "jjjjg" would also access my profile. And what if my evil twin Lerak decided to register? He would also hit the same hash!

Accidentally hitting the same hash is called a 'collision'. Obviously a good hash function should not be only one-way, but should also avoid collisions. There are very good hash functions out there, such as the SHA family. However, none of these are guaranteed to avoid collisions.

Is there a practical application for this?

Two things are happening here: One, when I'm purchasing something for ten euro's, the site asks my bank: "Is the balance of Kubat, with account number 123456789, sufficient for a transaction of 10 euro's?" Two, the last name Kubat and the account number 123456789 are stored in some database of the site.

There is a number of dangers lurking here. First, someone may be eavesdropping on the chitchat between the site and my bank. They can find out that the combination Kubat/123456789 is valid for making purchases, and start making purchases in my name! Second, any malevolent employee of the site can find this in the site's database and also misuse my identity for their profit.

Obviously I don't want that to happen. So we can take a number of measures - e.g., secure transactions between the site and my bank, and restrict database access for all but a few site employees. Unfortunately, however well designed the security measures may be, there will always be ways around them. And there is still the basic question - do the data need to be there in the first place?

So, why don't we use hashes instead of plain text data?

• The hash512 value of my last name "Kubat" is UlieNqKVJFYPlgu7ZAMUl0J5SG5ZV7nKtF9AK+fuuV/K3uljp0Glj2CyUFvC3N1GCV7SgxBmxkTOmCM+EeIGeA.
• When I log onto the site, I state my last name just once - on the login page. Beyond that, my last name just isn't available anymore, only the above hash.
• The hash of my account number "123456789" is 2eZ2LdHI6vbWGzxhkvxAjU1tXxF20MKRabwk5xw/J0rSf81YEbMT1oH35V7ALXPUmclUVba1u1A6z1dPuo/+hQ. I'd have to enter my account number just once, when making the first purchase. AFter that, the site's database would store that "Person UlieNqKVJFYPlgu7ZAMUl0J5SG5ZV7nKtF9AK+fuuV/K3uljp0Glj2CyUFvC3N1GCV7SgxBmxkTOmCM+EeIGeA has account 2eZ2LdHI6vbWGzxhkvxAjU1tXxF20MKRabwk5xw/J0rSf81YEbMT1oH35V7ALXPUmclUVba1u1A6z1dPuo/+hQ".
• When I purchase an item, the site would ask my bank: "Does person UlieNqKVJFYPlgu7ZAMUl0J5SG5ZV7nKtF9AK+fuuV/K3uljp0Glj2CyUFvC3N1GCV7SgxBmxkTOmCM+EeIGeA with account 2eZ2LdHI6vbWGzxhkvxAjU1tXxF20MKRabwk5xw/J0rSf81YEbMT1oH35V7ALXPUmclUVba1u1A6z1dPuo/+hQ have a balance high enough to cover ten euro's?"
• My bank cannot reverse the supplied hashes to my name and account number; no-one can. But that's not necessary! My bank has a full list of customers and account numbers, They can pre-generate lists of hashes, and compare the two hashes that the site sends with their list to find my data.

And consider the following real-life situation. Many people purchase items over the Internet and pay with their credit card. Each transaction needs to be verified with a credit card company, where a website might ask: "Is credit card holder A. Smith, with card number 1111222233334444 and verification code 123 and expiry date 02/10, good for 20 dollars?" Any malevolent person only needs to get hold of these data; once they have them, they are free to roam Internet sites and purchase items using Smith's stolen identity.

In contrast, imagine that the identifying data were a hash of the combined values. In this case we could build up one long identifier, consisting of "Smith,1111222233334444,123,02/10", compute the hash (which is incidentally "svzW3IjYHVr+sFj85FVXyZmMHrtcPMSJdZoTb9BXOjSfoEOdfZYeGYjSlMCbBcaPheYS1yiIMqu7ox+ICxjoIw") and use that -again- in the following way:

• The hash would be computed just once, when the user registers at the site. After that, the original data would be discarded, and only the hash would be stored in the site's database.
• Verification of the transaction for 20 dollars would only transmit the hash, not the separate data.

So where and how can this approach be used?

So for example, if websites were allowed to ask a credit card company: "Give me a list of all your customers whose balance is high enough to make a $20 purchase", then this approach couldn't be used - there is no "identifier" in the question to hash. Furtunately, this isn't a request that's allowed by the credit card companies (one may hope).

Is this appraoch in use?

Will the approach ever be used? One may hope so, I don't see any obstacles, only benefits. Well there is of course one obstacle - websites and credit card companies would need to change their systems to conform to the new way. This won't ever happen unless someone tells them to. As I stated previously: storing private data should be prohibited, unless it is absolutely necessary and there's no other way. That would be a good incentive!

Perl snippets for the playful

Here is the "idiotically simple" hash algorithm.

#!/usr/bin/perl

use strict;

# ihash - idiotic hash
# --------------------

# Check the command line.
die ("Usage: ihash name(s)\n") if ($#ARGV < 0);

# Show hash all arguments.
for my $n (@ARGV) {
    print ("$n: ", hash($n), "\n");
}

# The hash function
sub hash ($) {
    my $n = shift;
    my $h = 0;
    for my $c (split ('', $n)) {
	$c = lc($c);
	$h += ord($c) - ord('a') + 1;
    }
    return ($h);
}

Here's a short script to display sha512 hashes. You'll need the Perl module Digest::SHA to make this run.

#!/usr/bin/perl

# sha512 - displays the sha512 hash of all arguments

use strict;
use Digest::SHA qw(sha512_base64);

# Check the command line
die ("Usage: sha512 strings\n",
     "Displays the sha512 digest of all strings.\n") if ($#ARGV < 0);

for my $str (@ARGV) {
    print ("$str: ", sha512_base64 ($str), "\n");
}

I verified that Dutch account numbers between 000000000 and 999999999 do not collide when hashed using sha512. Here's now.

#!/usr/bin/perl

# sha-accnr-checker
# If we sha512-encode Dutch account numbers (which have 9 digits),
# will we encounter collisions?

use strict;
use Digest::SHA qw(sha512_base64);

# Make the output unbuffered
$|++;			   

# Hash of seen digests
my %used;

for my $nr (0..999999999) {
    # Pad account number to 9 positions, compute the digest
    my $acc = sprintf ("%9.9d", $nr);
    my $dig = sha512_base64 ($acc);
    
    # Stop if there's a collision
    die ("\n$acc conflicts with $used{$dig}\n",
	 "both yield sha512: $dig\n") if ($used{$dig});
    
    # Store digest since we've now used it
    $used{dig} = $acc;

    # Show a ticker so we see what's going on
    print ("\r$acc") if (! ($nr % 10000));
}

# All done
print ("\nno collisions detected\n");