Example of a really weak hash function

The algorithm

The Award BIOS (at least version 4.5) has a very weak built-in hash function for password checking. The password consists of up to 8 characters, each must have an ASCII value between 32 and 127. With the password, the BIOS computes a 16-bit "checksum" using the following algorithm:

checksum := 0;
for each charcter of the password (from left to right):
    rotate checksum 2 bits to the left
    add ASCII-value of the character to checksum (without carry)

The following table is a illustration with the password 'secret!?'.

As you can see the checksum for the password 'secret!?' is 12136. This value is stored in the battery powered CMOS RAM. Every time the computer boots and password checking is enabled, the BIOS asks for the password, computes the checksum and validates it with the stored value in the CMOS RAM. If the computed value is equal to the stored, access is granted and the computer continues to boot. If not, the BIOS asks again, and again, and again (maybe with reboot after 3 failures).

The weakness

From the 8-char password, the BIOS computes a 16-bit checksum. This is also known as a 'hash function'. Hash functions (like MD5) compute a short value (often 128 or 160 bits) from an arbitrary long text. The BIOS computes a 16 bit long value from an eight characters long password. There a two weaknesses: The value is only 16 bit long, and the algorithm is rather easy ('rotate-add').

16 bit value: With 8 characters with ASCII values from 32 to 127, there are 96^8 unique passwords. 96^8=7,213,895,789,838,336. The 16 bits of the hash value can lead to 2^16=65536 different values. So, there are only 65536 really different passwords. That means that on average 110,075,314,176 (110 billion) passwords have the same hash value (96^8/2^16)!

Easy algorithm: The algorithm consists of two simple binary operations, rotation and addition. As you can see in the following, this is easy to break.

The collision

... [text missing] ...
I'm sorry, but this page isn't complete yet. Please be patient.
Thanks.

Source Code (in Python)

#!/usr/bin/env python

import sys
import string

def compute_hash_value(password):
    hash_value = 0
    for char in password:
        hash_value = (hash_value << 2) | (hash_value >> 14)
        hash_value = hash_value + ord(char)
        hash_value = hash_value & 0xffff
    return hash_value

def compute_collision(hash_value):
    digits = [0, 0, 0, 0, 0, 0, 0, 0]

    help_chk = hash_value
    for i in [7, 6, 5, 4, 3, 2, 1, 0]:
        digits[i] = digits[i] | (help_chk & 3)
        help_chk = help_chk >> 2

    if hash_value<48:
        digits[0] = digits[0] | 4
    elif hash_value>=48 and hash_value<52:
        digits[7] = digits[7] + 1
    elif hash_value>=52 and hash_value<256:
        digits[7] = digits[7] | 4
    elif hash_value>=256 and hash_value<1024:
        digits[6] = digits[6] | 4

    result = ""
    for digit in digits:
        result = result + (chr(digit+48))
    return result

if __name__=="__main__":
    print "Please enter your Password:",
    password = string.strip(sys.stdin.readline())
    hash = compute_hash_value(password)
    print "The hash value is:", hash
    print "One collision is:", compute_collision(hash)

Download source code