Implementation of SHA512-crypt vs MD5-crypt

If you have a new installation, you’re probably using SHA512-based passwords instead of the older MD5-based passwords described in detail in the previous post, which I’ll assume you’ve read. sha512-crypt is very similar to md5-crypt, but with some interesting differences.

Since the implementation of sha512 is really less interesting than the comparison with md5-crypt, I’ll describe it by striking out the relevant parts of the md5-crypt description and writing in what sha512-crypt does instead.

Like md5-crypt, it can be divided into three phases. Initialization, loop, and finalization.

1. Generate a simple md5 sha512 hash based on the salt and password
2. Loop 1000 5000 times, calculating a new sha512 hash based on the previous hash concatenated with alternatingly the hash of the password and the salt. Additionally, sha512-crypt allows you to specify a custom number of rounds, from 1000 to 999999999
3. Use a special base64 encoding on the final hash to create the password hash string

The main differences are the higher number of rounds, which can be user selected for better (or worse) security, the use of the hashed password and salt in each round, rather than the unhashed ones, and a few tweaks of the initialization step.

Here’s the real sha512-crypt initialization.

1. Let “password” be the user’s ascii password, “salt” the ascii salt (truncated to 8 16chars) , and “magic” the string “$1$”
2. Start by computing the Alternate sum, sha512(password + salt + password)
3. Compute the Intermediate₀ sum by hashing the concatenation of the following strings:
   1. Password
   2. Magic
   3. Salt
   4. length(password) bytes of the Alternate sum, repeated as necessary
   5. For each bit in length(password), from low to high and stopping after the most significant set bit
      • If the bit is set, append a NUL byte the Alternate sum
      • If it’s unset, append the first byte of the password
4. New: Let S_factor be 16 + the first byte of Intermediate₀
5. New: Compute the S bytes, length(salt) bytes of sha512(salt, concatenated S_factor times).
6. New: Compute the P bytes, length(password) bytes of sha512(password), repeated as necessary

Step 3.5 — which was very strange in md5-crypt — now makes a little more sense. We also calculated the S bytes and P bytes, which from here on will be used just like salt and password was in md5-crypt.

From this point on, the calculations will only involve the password P bytes, salt S bytes, and the Intermediate₀ sum. Now we loop 5000 times (by default), to stretch the algorithm.

• For i = 0 to 4999 (inclusive), compute Intermediate_i+1 by concatenating and hashing the following:
  1. If i is even, Intermediate_i
  2. If i is odd, password P bytes
  3. If i is not divisible by 3, salt S bytes
  4. If i is not divisible by 7, password P bytes
  5. If i is even, password P bytes
  6. If i is odd, Intermediate_i
  At this point you don’t need Intermediate_i anymore.

You will now have ended up with Intermediate₅₀₀₀. Let’s call this the Final sum. Since sha512 is 512bit, this is 64 bytes long.

The bytes will be rearranged, and then encoded as 86 ascii characters using the same base64 encoding as md5-crypt.

1. Output the magic, “$6$”
2. New: If using a custom number of rounds, output “rounds=12345$”
3. Output the salt
4. Output a “$” to separate the salt from the encrypted section
5. Pick out the 64 bytes in this order: 63 62 20 41 40 61 19 18 39 60 59 17 38 37 58 16 15 36 57 56 14 35 34 55 13 12 33 54 53 11 32 31 52 10 9 30 51 50 8 29 28 49 7 6 27 48 47 5 26 25 46 4 3 24 45 44 2 23 22 43 1 0 21 42
   • For each group of 6 bits (there’s 86 groups), starting with the least significant
     • Output the corresponding base64 character with this index

And yes, I do have a shell script for this as well: sha512crypt. This one takes about a minute to generate a hash, due to the higher number of rounds. However, it doesn’t support custom rounds.

I hope these two posts have provided an interesting look at two exceedingly common, but often overlooked, algorithms!

 sha512crypt

#!/bin/bash

# sha512-crypt
# sha512-crypt for GNU and Bash

b64="./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

stringToNumber() { 
    expression=0
    for((i=0; i<${#1}; i++))
    do
        expression=$(printf '(%s)*256+%d' "$expression" "'${1:$i:1}")
    done
    bc <<< "$expression"
}

# Turn some string into a \xd4\x1d hex string
stringToHex() { 
    for((i=0; i<${#1}; i++))
    do
        printf '\\x%x' "'${1:i:1}"
    done
}

# Turn stdin into a \xd4\x1d style sha512 hash
sha512hex() { 
    sum=$(sha512sum) 
    read sum rest <<< "$sum" # remove trailing dash
    hex=$(sed 's/../\\x&/g' <<< "$sum")
    echo "$hex"
}

# Turn an integer into a crypt base64 string with n characters
intToBase64() { 
    number=$1
    n=$2
    for((j=0; j>=1)) 
        do
            if (( i & 1 ))
            then
                printf "$alternate"
            else 
                printf "$password" 
            fi
        done

    } | sha512hex
    )
    firstByte=$(hexToInt $(getBytes "$intermediate" 0))

    p_bytes=$(for((i=0; i<$passwordLength; i++)); do printf "$password"; done | sha512hex | head -c $((passwordLength*4)) )
    s_bytes=$(for((i=0; i<16+${firstByte}; i++)); do printf "$salt"; done  | sha512hex | head -c $((saltLength*4)) )


    for((i=0; i<5000; i++))
    do
        intermediate=$({
            (( i & 1 )) && printf "$p_bytes" || printf "$intermediate"
            (( i % 3 )) && printf "$s_bytes"
            (( i % 7 )) && printf "$p_bytes"
            (( i & 1 )) && printf "$intermediate" || printf "$p_bytes"
        } | sha512hex)
    done

    # Rearrange the bytes and crypt-base64 encode them
    hex=$(base64EncodeBytes 86 "$intermediate" \
        63  62 20 41  40 61 19  18 39 60  59 17 38  37 58 16  15 36 57  56 14 35 \
            34 55 13  12 33 54  53 11 32  31 52 10   9 30 51  50  8 29  28 49  7 \
             6 27 48  47  5 26  25 46  4   3 24 45  44  2 23  22 43  1   0 21 42)

    printf "%s$salt\$%s\n" "$magic" "$hex" 

}


if [[ $# < 1 ]] 
then
    echo "Usage: $0 password [salt]" >&2 
    exit 1
fi

password=$(stringToHex "$1")
salt=$(stringToHex "$2")
[[ -z $salt ]] && salt=$(tr -cd 'a-zA-Z0-9' < /dev/urandom | head -c 16) 

doHash "$password" "$salt" '$6$'

Password hashing with MD5-crypt in relation to MD5

If you haven’t reinstalled recently, chances are you’re using MD5-based passwords. However, the password hashes you find in /etc/shadow look nothing like what md5sum returns.

Here’s an example:

/etc/shadow:
$1$J7iYSKio$aEY4anysz.gtXxg7XlL6v1

md5sum:
7c6483ddcd99eb112c060ecbe0543e86

What’s the difference in generating these hashes? Why are they different at all?

Just running md5sum on a password and storing that is just marginally more secure than storing the plaintext password.

Thanks to GPGPUs, a modern gaming rig can easily try 5 billion such passwords per second, or go over the entire 8-character alphanumeric space in a day. With rainbow tables, a beautiful time–space tradeoff, you can do pretty much the same in 15 minutes.

MD5-crypt employs salting to make precomputational attacks exponentially more difficult. Additionally, it uses stretching to make brute force attacks harder (but just linearly so).

As an aside, these techniques were used in the original crypt from 1979, so there’s really no excuse to do naive password hashing anymore. However, at that time the salt was 12 bits and the number of rounds 25 — quite adorable in comparison with today’s absolute minimum of 64 bits and 1000 rounds.

The original crypt was DES based, but used a modified algorithm to prevent people from using existing DES cracking hardware. MD5-crypt doesn’t do any such tricks, and can be implemented in terms of any MD5 library, or even the md5sum util.

As regular reads might suspect, I’ve written a shell script to demonstrate this: md5crypt. There are a lot of workarounds for Bash’s inability to handle NUL bytes in strings. It takes 10 seconds to generate a hash, and is generally awful..ly funny!

Let’s first disect a crypt hash. man 3 crypt has some details.

If salt is a character string starting with the characters
"$id$" followed by a string terminated by "$":

       $id$salt$encrypted

then instead of using the DES machine, id  identifies  the
encryption  method  used  and this then determines how the
rest of the password string is interpreted.  The following
values of id are supported:

       ID  | Method
       -------------------------------------------------
       1   | MD5
       2a  | Blowfish (on some Linux distributions)
       5   | SHA-256 (since glibc 2.7)
       6   | SHA-512 (since glibc 2.7)

Simple and easy. Split by $, and then your fields are Algorithm, Salt and Hash.

md5-crypt is a function that takes a plaintext password and a salt, and generate such a hash.

To set a password, you’d generate a random salt, input the user’s password, and write the hash to /etc/shadow. To check a password, you’d read the hash from /etc/shadow, extract the salt, run the algorithm on this salt and the candidate password, and then see if the resulting hash matches what you have.

md5-crypt can be divided into three phases. Initialization, loop, and finalization. Here’s a very high level description of what we’ll go through in detail:

1. Generate a simple md5 hash based on the salt and password
2. Loop 1000 times, calculating a new md5 hash based on the previous hash concatenated with alternatingly the password and the salt.
3. Use a special base64 encoding on the final hash to create the password hash string

Put like this, it relatively elegant. However, there are a lot of details that turn this from elegant to eyerolling.

Here’s the real initialization.

1. Let “password” be the user’s ascii password, “salt” the ascii salt (truncated to 8 chars), and “magic” the string “$1$”
2. Start by computing the Alternate sum, md5(password + salt + password)
3. Compute the Intermediate₀ sum by hashing the concatenation of the following strings:
   1. Password
   2. Magic
   3. Salt
   4. length(password) bytes of the Alternate sum, repeated as necessary
   5. For each bit in length(password), from low to high and stopping after the most significant set bit
      • If the bit is set, append a NUL byte
      • If it’s unset, append the first byte of the password

I know what you’re thinking, and yes, it’s very arbitrary. The latter part was most likely a bug in the original implementation, carried along as UNIX issues often are. Remember to stay tuned next week, when we’ll compare this to SHA512-crypt as used on new installations!

From this point on, the calculations will only involve the password, salt, and Intermediate₀sum. Now we loop 1000 times, to stretch the algorithm.

• For i = 0 to 999 (inclusive), compute Intermediate_i+1 by concatenating and hashing the following:
  1. If i is even, Intermediate_i
  2. If i is odd, password
  3. If i is not divisible by 3, salt
  4. If i is not divisible by 7, password
  5. If i is even, password
  6. If i is odd, Intermediate_i
  At this point you don’t need Intermediate_i anymore.

You will now have ended up with Intermediate₁₀₀₀. Let’s call this the Final sum. Since MD5 is 128bit, this is 16 bytes long.

The bytes will be rearranged, and then encoded as 22 ascii characters with a special base64-type encoding. This is not the same as regular base64:

Normal base64 set:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Crypt base64 set:
./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

Additionally, there is no padding. The leftover byte will be encoded into 2 base64 ascii characters.

1. Output the magic
2. Output the salt
3. Output a “$” to separate the salt from the encrypted section
4. Pick out the 16 bytes in this order: 11 4 10 5 3 9 15 2 8 14 1 7 13 0 6 12.
   • For each group of 6 bits (there are 22 groups), starting with the least significant
     • Output the corresponding base64 character with this index

Congratulations, you now have a compatible md5-crypt hash!

As you can see, it’s quite far removed from a naive md5(password) attempt.

Fortunately, one will only ever need this algorithm for compatibility. New applications can use the standard PBKDF2 algorithm, implemented by most cryptography libraries, which does the same thing only in a standardized and parameterized way.

As if this wasn’t bad enough, the next post next week will be more of the same, but with SHA512-crypt!

md5cript.sh

#!/bin/bash
# md5-crypt for GNU and Bash

b64="./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

stringToNumber() { 
    expression=0
    for((i=0; i<${#1}; i++))
    do
        expression=$(printf '(%s)*256+%d' "$expression" "'${1:$i:1}")
    done
    bc <<< "$expression"
}

# Turn some string into a \xd4\x1d hex string
stringToHex() { 
    for((i=0; i<${#1}; i++))
    do
        printf '\\x%x' "'${1:i:1}"
    done
}

# Turn stdin into a \xd4\x1d style md5 hash
md5hex() { 
    sum=$(md5sum) 
    read sum rest <<< "$sum" # remove trailing dash
    hex=$(sed 's/../\\x&/g' <<< "$sum")
    echo "$hex"
}

# Turn an integer into a crypt base64 string with n characters
intToBase64() { 
    number=$1
    n=$2
    for((j=0; j>=1)) 
        do
            if (( i & 1 ))
            then
                printf '\x00' 
            else 
                printf "$password" | head -c 1
            fi
        done

    } | md5hex
    )

    for((i=0; i<1000; i++))
    do
        intermediate=$({
            (( i & 1 )) && printf "$password" || printf "$intermediate"
            (( i % 3 )) && printf "$salt"
            (( i % 7 )) && printf "$password"
            (( i & 1 )) && printf "$intermediate" || printf "$password"
        } | md5hex)
    done

    # Rearrange the bytes and crypt-base64 encode them
    encoded=$(base64EncodeBytes 22 "$intermediate" 11  4 10 5  3 9 15  2 8 14  1 7 13  0 6 12)

    printf "%s$salt\$%s\n" "$magic" "$encoded" 

}


if [[ $# < 1 ]] 
then
    echo "Usage: $0 password [salt]" >&2 
    exit 1
fi

password=$(stringToHex "$1")
salt=$(stringToHex "$2")
[[ -z $salt ]] && salt=$(tr -cd 'a-zA-Z0-9' < /dev/urandom | head -c 8) 

doHash "$password" "$salt" '$1$'

What’s in a SSH RSA key pair?

You probably have your own closely guarded ssh key pair. Chances are good that it’s based on RSA, the default choice in ssh-keygen.

RSA is a very simple and quite brilliant algorithm, and this article will show what a SSH RSA key pair contains, and how you can use those values to play around with and encrypt values using nothing but a calculator.

RSA is based on primes, and the difficulty of factoring large numbers. This post is not meant as an intro to RSA, but here’s a quick reminder. I’ll use mostly the same symbols as Wikipedia: you generate two large primes, p and q. Let φ = (p-1)(q-1). Pick a number e coprime to φ, and let d ≡ e^-1 mod φ.

The public key is then (e, n), while your private key is (d, n). To encrypt a number/message m, let the ciphertext c ≡ m^e mod n. Then m ≡ c^d mod n.

This is very simple modular arithmetic, but when you generate a key pair with ssh-keygen, you instead get a set of opaque and scary looking files, id_rsa and id_rsa.pub. Here’s a bit from the private key id_rsa (no passphrase):


-----BEGIN RSA PRIVATE KEY-----
MIIBygIBAAJhANj3rl3FhzmOloVCXXesVPs1Wa++fIBX7BCZ5t4lmMh36KGzkQmn
jDJcm+O9nYhoPx6Bf+a9yz0HfzbfA5OpqQAyC/vRTVDgHhGXY6HFP/lyWQ8DRzCh
tsuP6eq9RYHnxwIBIwJhAKdf+4oqqiUWOZn//vXrV3/19LrGJYeU

...
-----END RSA PRIVATE KEY-----

How can we get our nice RSA parameters from this mess?

The easy way is with openssl: (I apologize in advance for all the data spam in the rest of the article).


root@suresh ~/.ssh $ openssl rsa -text -noout < id_rsa
Private-Key: (768 bit)
modulus:
     00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
     54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
     ...
publicExponent: 35 (0x23)
privateExponent:
     00:a7:5f:fb:8a:2a:aa:25:16:39:99:ff:fe:f5:eb:
     57:7f:f5:f4:ba:c6:25:87:94:48:64:93:fb:3d:a7:
     ...
prime1:
    ...
prime2:
    ...
exponent1:
    ...
exponent2:
    ...
coefficient:
    ...

Here, modulus is n, publicExponent is e, privateExponent is d, prime1 is p, prime2 is q, exponent1 is d_P from the Wikipedia article, exponent2 is d_Q and coefficient is q_Inv.

Only the first three are strictly required to perform encryption and decryption. The latter three are for optimization and the primes are for verification.

It’s interesting to note that even though the private key from RSA’s point of view is (d,n), the OpenSSH private key file includes e, p, q and the rest as well. This is how it can generate public keys given the private ones. Otherwise, finding e given (d,n) is just as hard as finding d given (e,n), except e is conventionally chosen to be small and easy to guess for efficiency purposes.

If we have one of these hex strings on one line, without colons, and in uppercase, then bc can work on them and optionally convert to decimal.


# If you don't want to do this yourself, see end for a script
root@suresh ~/.ssh $ { echo 'ibase=16'; cat | tr -d ':\n ' | tr a-f A-F; echo; } | bc

00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
98:c8:77:e8:a1:b3:91:09:a7:8c:32:5c:9b:e3:bd:
….
Ctrl-d to end input
13158045936463264355006370413708684112837853704660293756254884673628\
63292…

We also need a power-modulo function, since b^e % m is unfeasibly slow if you go by way of b^e. Luckily, bc is programmable.


root@suresh ~/.ssh $ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

# Our powermod function:
define pmod(b,e,m) { if(e == 0 ) return 1; if(e == 1) return b%m; rest=pmod(b^2%m,e/2,m); if((e%2) == 1) return (b*rest)%m else return rest; }

#Define some variables (this time unabbreviated)
n=13158045936463264355006370413708684112837853704660293756254884673628\
63292777770859554071108633728590995985653161363101078779505801640963\
48597350763180843221886116453606059623113097963206649790257715468881\
4303031148479239044926138311

e=35

d=10150492579557375359576342890575270601332058572166512326253768176799\
23111571423234513140569517447770196903218153051479115016036905320557\
80231250287900874055062921398102953416891810163858645414303785372309\
5688315939617076008144563059

# Encrypt the number 12345
c=pmod(12345, e, n)

# Show the encrypted number
c
15928992191730477535088375321366468550579140816267293144554503305092\
03492035891240033089011563910196180080894311697511846432462334632873\
53515625


#Decrypt the number
pmod(c, d, n)
12345

Yay, we’ve successfully encrypted and decrypted a value using real life RSA parameters!

What’s in the public key file, then?

ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAGEA2PeuXcWHOY6WhUJdd6xU+zVZr758gFfsEJnm3iWYyHfoobORCaeMMlyb472diGg/HoF/5r3LPQd/Nt8Dk6mpADIL+9FNUOAeEZdjocU/+XJZDwNHMKG2y4/p6r1FgefH suresh@suresh.spam

This is a very simple file format, but I don’t know of any tools that will decode it. Simply base64-decode the middle string, and then read 4 bytes of length, followed by that many bytes of data. Repeat three times. You will then have key type, e and n, respectively.

Mine is 00 00 00 07, followed by 7 bytes “ssh-rsa”. Then 00 00 00 01, followed by one byte of 0×23 (35, our e). Finally, 00 00 00 61 followed by 0×61 = 97 bytes of our modulus n.

If you want to decode the private key by hand, base64-decode the middle bit. This gives you an ASN.1 encoded sequence of integers.

This is an annotated hex dump of parts of a base64-decoded private key

30 82 01 ca   - Sequence, 0x01CA bytes
    02 01: Integer, 1 byte
        00
    02 61:    - Integer, 0x61 bytes (n).
        00 d8 f7 ae 5d c5 87 39 8e 96 ... Same as from openssl!
    02 01:  - Integer, 1 byte, 0x23=35 (e)
        23
    02 61  - Integer, 0x61 bytes (d)
        00 a7 5f fb 8a 2a aa 25 16 39 ...
    ...

Here’s a bash script

#!/bin/bash

set -e

die() { 
    echo "$@" >&2
    exit 1
}

if [[ -z $1 ]] 
then
    die "Usage: $0 private_rsa_key"
fi

sshkey=$(< $1) 
if [[ $sshkey != "-----BEGIN RSA PRIVATE KEY-----"* ]]
then
    die "This does not appear to be an RSA private key"
fi

if [[ $sshkey == *ENCRYPTED* ]] 
then
    echo "Key is encrypted, using openssl to decrypt"
    sshkey=$(openssl rsa <<< "$sshkey")
fi

base64key=$(sed '1d; $d;' <<< "$sshkey") #the base64 data
decdump=$(base64 -d <<< "$base64key" | od -t u1 | sed -e 's/^[^ ]*//')
decbytes=$(echo $decdump | tr ' ' '\n') #decimal bytes, one on each line

readInt() { 
    read byte 
#    echo "read type $byte" >&2
    (( (byte & 0x1F) != 2 )) && \
        die "$byte doesn't encode an integer :O"

    length=$(readLength)
#    echo "read length $length" >&2
    exp="0"
    for((i=0; i&2
        exp="($exp)*256+$b"
    done
    bc <<< "$exp" | tr -d '\n\\ '
}

readLength() { 
    local bytes length n i 
    read bytes

    n=$((bytes&0x7F))
    if (( bytes & 0x80 ))
    then
        length=0
        for((i=0; i /dev/null # the sequence length
    unknown=$(readInt)
    n=$(readInt) #modulo
    e=$(readInt) #public exponent
    d=$(readInt) #private exponent
    p=$(readInt) #first prime
    q=$(readInt) #second prime
    exp1=$(readInt) # d mod p-1
    exp2=$(readInt) # d mod q-1
    c=$(readInt) || c=0 # p^1 mod q

    length=$(bc -l <<< "scale=20; v=l($n)/l(2); scale=1; v/1")
    echo "# Key is $length bits long"
    echo "# Input for bc:"
    echo "n=$n" 
    echo "p=$p" 
    echo "q=$q" 
    echo "e=$e"
    echo "d=$d"
    echo "c=$c"
    echo "exp1=$exp1"
    echo "exp2=$exp2"
    echo "scale=0"
    echo "define pmod(b,e,m) { if(e == 0 ) return 1; if(e == 1) return b%m; rest=pmod(b^2%m,e/2,m); if((e%2) == 1) return (b*rest)%m else return rest;  }"
    echo "define encrypt(message) { return pmod(message, e, n); }"
    echo "define decrypt(message) { return pmod(message, d, n); }"
    echo "define verify() { return n == p*q && (d*e)%((p-1)*(q-1)) == 1 && exp1 == d % (p-1) && exp2 == d % (q-1) && (c*q)%p == 1; }"
    echo "# End bc"
) <<< "$decbytes"  

that will decode a private key and output variable definitions and functions for bc, so that you can play around with it without having to do the copy-paste work yourself. It decodes ASN.1, and only requires OpenSSL if the key has a passphrase.

When run, and its output pasted into bc, you will have the variables n, e, d, p, q and a few more, functions encrypt(m) and decrypt(c), plus a verify() that will return 1 if the key is valid. These functions are very simple and transparent.

Enjoy!

RapidShare downloading script

• A RapidShare downloading script for Linux/Unix (requires Bash and Curl). Downloads all rapidshare files from a given web page.

Linux problems with solutions

These are some various linux/unix problems I've encountered over the years, but which I was not able to find a solution for online. Hopefully this will save you the trouble I had.


Problem:
Network interface (or anything else on the pci bus) says "SIOCSIFFLAGS: Resource temporarily unavailable"
Cause: 
No IRQ assigned to the device, check /proc/pci (irq says 0)
Solution: 
Enter the bios setup (F1 or Del on boot), disable the option 'Plug n Play OS'.
Reason: 
This will make your bios set up IRQs for you.
Problem:
USB mouse using /dev/psaux, the ps/2 mouse device.
Cause: 
Bios usb legacy support in action, probably because Linux didn't probe for USB devices (which causes the bios to release control of them).
Solution: 
Compile the kernel with USB support, Input Core and USB HID.
Reason: 
Duh.
Problem:
USB mouse still doesn't work on /dev/input/mice, but /dev/psaux, even when USB support is compiled in.
Cause: 
Legacy USB support again. You might not have compiled in support for your USB chipset (the UHCI parts in USB support).
Solution: 
Compile UHCI. If not working, try the alternate drivers.
Reason: 
Duh.
Problem:
Accidentally cat'ing a binary file causes the all the characters you type next to show up as odd symbols.
Cause:
The binary file contained a 016 (so, Shift Out) character.
Solution:
Run 'reset'. You can alsO specifically print a 017 (Shift In) character using echo -e '\017'.
Reason:
Shift Out is canceled by a Shift In.
Problem:
You scanned an ext3 file system with fsck.ext2/e2fsck, and now you can't boot.
Cause:
fsck.ext2 deleted the journaling inode, essentially making it an ext2 fs.
Solution:
Either use tune2fs -j device to add the journal node again, or use [c]fdisk to set the partition type to ext2 instead of ext3.
Reason:
tune2fs -j will fix the fs back to ext3 journaling mode, cfdisk will have the system use it as unjournaled ext2.
Problem:
Some program (especially older ones like RealPlayer, and other multimedia tools/players) hangs when loading, or give a message like "Can't open audio device /dev/dsp: Resource temporarily unavailable." or "No Sound"
Cause:
Trying to open /dev/dsp (the sound device), but it's busy already taken so the program waits or fails.
Solution:
Kill whatever might be hogging it, like artsd. You can find the specific PID using fuser /dev/dsp.
Reason:
The app will now have exclusive sound access, and will load without waiting for the device to be free.
Problem:
Lilo doesn't boot your new kernel, giving you odd boot signature messages.
Cause:
It can't find the 0xAA55 byte at the end of the boot sector, probably because you didn't run 'lilo' after updating lilo.conf or replacing the kernel file.
Solution:
Run lilo. Get a rescue floppy if needed.
Reason:
Lilo will now store the correct abs disk location for the kernels.
Problem:
The localhost loopback address 127.0.0.1 doesn't work, and so some servers stop functioning and you can only connect to yourself through your lan address.
Cause:
The lo interface might not be configured right.
Solution:
Run "ifconfig lo up 127.0.0.1"
Reason:
The loopback interface should now be up and configured with the standard loopback address.
Problem:
CUPS printer claim to be ready, but is turned off when you start a job, and deletes the job when you start the printer.
Cause:
You've upset the manual gods.
Solution:
Curse, read the manual, delete all the cups files, read the manual, download and compile cups, read the manual, try again.
Reason:
The manual gods will be happy with your sacrifice and will allow you to print (worked for me atleast :)
Problem:
When using the disk kupdated hogs the cpu, making the system slow to a crawl. The mouse stops responding for several seconds at a time. Serial comm gives errors like "/dev/ttyS0: 1 input overrun(s)".
Cause:
Slow IDE throughput due to unsupported chipset. Run 'hdparm -t /dev/hda' to make sure (it will be really low, around 2-6mb/s)
Solution:
Compile a kernel that supports your IDE chipset (just enable them all).
Reason:
koala_man: Btw, the 'reason' part for the 'kupdated hogs CPU because of disk usage' thing is because the system runs in PIO mode, meaning the main CPU have to manage all reading and writing, rather than letting the chipset use busmastering.
Problem:
Konqueror doesn't show gif images.
Cause:
No gif support in QT
Solution:
Edit $QTDIR/src/kernel/qgif.h, define QT_BUILTIN_GIF_READER as 1 (tiny file, plenty of comments). configure with -qt-gif. No need to recompile konqueror.
Reason:
The QT library now supports gif, and konqueror can use it.
Problem:
GTK apps like gimp and xchat suddenly got disgusting fonts.
Cause:
Something changed the settings, possibly an install of another gtk version.
Solution:
Make a ~/.gtkrc file:

style "user-font"
 {
         font="-misc-fixed-medium-r-normal-*-14-*-*-*-c-*-iso8859-1"
 }
 widget_class "*" style "user-font"

Replace the font if that doesn't suit you.
Reason:
A new default font is now set, instead of the ugly previous one.Problem:
Konqueror is slow when browsing FTP sites.
Cause:
The icon preview feature occupies the connection, forcing a relogin when changing directories.
Solution:
Uncheck 'ftp' in the KDE Control Center under Previews in File Manager.
Reason:
Konqueror will now use the connection it made for browsing, rather than showing icon previews.
Problem:
When starting Half-Life in Wine, a message comes up saying "Could not open MCI file for playback: 279: Cannot use 'all' as the device name with the specified command"
Cause:
Dunno.
Solution:
Run as "wine hl.exe -- -console"
Reason:
No clue.
Problem:
Half-Life in Wine has no sound.
Cause:
DirectSound errors?
Solution:
Try setting voice_enable "0" in config.cfg
Reason:
No clue, but it worked for me.
Problem:
When running Half-Life in Wine, pressing Tab causes the screen to go black (but displays "Half-Life" in the left corners).
Cause:
Locked up Alt key perhaps
Solution:
Click somewhere, then click the top left corner. Press Escape then Resume Game. Then hit Alt.
Reason:
I guess the game didn't get the alt-release keycode.
Problem:
Sendmail ignores aliases in /etc/mail/aliases, even after sighups.
Cause:
Sendmail reads from a database, not that file.
Solution:
Use the -bi option (or even better, run newaliases).
Reason:
It'll update the database (/etc/mail/aliases.db).
Problem:
KMail's menu bar is missing.
Cause:
I dunno, messing with styles and themes possibly.
Solution:
Set MenuBar=Disabled in ~/.kde/share/config/kmailrc to, yes, Enabled.
Reason:
I didn't see any way of turning it through the gui, so I did it manually.
Problem:
Mounting of NFS shares is slow, taking exactly five minutes.
Cause:
Not quite sure.
Solution:
Install Portmap on both client and server.
Reason:
I don't know.
Problem:
Apache's mod_proxy won't allow CONNECTs on vhosts.
Cause:
I think the manual lies. Mod_proxy doesn't seem to like vhosts.
Solution:
Make it server wide.
Reason:
Cow.
Problem:
Can't figure out how to whitelist sites using Apache proxies (but can blacklist with ProxyBlock)
Cause:
Not pondering long enough.
Solution:

    Order Deny,Allow
    Deny from all
    

    
    Order Allow,Deny
    Allow from all
    

Reason:
That's just the way it is.Problem:
nvtv only gives black/white output (on an old TV using an s-video to scart converter).
Cause:
Cheap converter
Solution:
Set the Connector to Convert.
Reason:
Quoth the faq, "You have a SVideo (S-VHS) to Composite connector that uses only the luminance (Y) line of the SVideo connection."
Problem:
Quick access to the konqueror options for changing browser identification and enabling/disabling Java/plugins/javascript not present in the Tools menu.
Cause:
These are additional plugins not present in all default installs.
Solution:
Install konq-plugins in debian, or the kde addons module from the source tree.
Reason:
Duh.
Problem:
Can't make KDE display an html web page as desktop background wallpaper. (Redundant wording for google's pleasure)
Solution:
kwebdesktop
Problem:
Neverwinter Nights crashes [on debian], giving only "Error" as a message.
Cause:
Running in 16bit mode.
Solution:
Run X in 24bit mode.
Reason:
I don't know, gdb indicates a libGLU issue.
Problem:
Irssi or anything else just hangs, and Ctrl+Q doesn't fix it. And you're using screen.
Cause:
Screen has an [ES]TX feature too. Perhaps you managed to trigger it.
Solution:
Ctrl-A Q
Reason:
Makes screen write stuff again.
Problem:
The Cisco vpnclient says "Could not attach to driver. Is kernel module loaded?", and yes, the module's loaded.
Cause:
Nowhere to route packets.
Solution:
Check that your nic is listed in ifconfig (if it's not and it's usb, try [re]loading usb-ohci or ohci-hcd). And up it with dhcpcd or something.
Reason:
Now it can connect.
Problem:
atitvout says "VBE call failed", esp on Radeon Mobility 7500 (M7 LW).
Cause:
Something about the card not detecting tv-out by itself.
Solution:
Turn the box off. Plug in TV-out. Boot. Start X, and put it in 640x480 (or 800x600). atitvout auto pal; atitvout -f t
Reason:
The card will sense the TV and allow you to turn on tv output.
Problem:
DVD playing using mplayer and TV-out sucks. With mplayer -vo xv, only the top half of the image is shown. With x11 it only occupies a small area, and with -zoom it runs crap slow and the interlacing is just awful.
Cause:
Dunno
Solution:
Set X to 640x480, mplayer -noframedrop -vo x11 -fs file
Reason:
Dunno, but it looks really great.
Problem:
UXterm doesn't show bold fonts (or xterm with wideChars (-wc))
Solution:
Set a wideFont ala "xterm*VT100*wideFont: -efont-biwidth-medium-r-*-*-14-*-*-*-*-*-*-*"
Problem:
Compiling irssi says "/bin/sh: 0: not found" (OpenBSD).
Solution:
Does your locale exist? Try unsetting all the LC_* variables, configure and make again.
Problem:
IMAP (imaps) hangs in kmail.
Cause:
kdelibs built without SSL, the imaps kioslave is built but just hangs.
Solution:
Recompile with ssl.
Problem:
Gentoo says "* error scanning /etc" whenever emerge does something.
Cause:
'find /etc' said modules.conf was there, but wasn't there. An xfs corruption, obviously.
Solution:
I booted from a rescue cd and did xfs_repair. Everything worked smoothly after that.
Problem:
(ok, so this isn't linux) On Solaris on a sun-ray thin client, xlocks locks the screen when you pull out the smart card and I want to change or disable this.
Solution:
Kill your existing utaction process, and/or start a new one with the desired action in -d. (/opt/SUNWut/lib/utaction -d command). Also note the -e if you want the action to only run once.
Problem:
(Solaris again) While compiling OpenGL applications using GLU on solaris, linking failes with Undefined symbol: __1cG__CrunKpure_error6F_v_ __1cG__CrunMex_rethrow_q6F_v_ c::c(N6, (int0_t)) c::c(N6, (int0_t)), ld: fatal: Symbol referencing errors. No output written to fluffy
Cause:
GLU requires libCrun which in turn requires libstdc++.
Solution:
Link with both these libs, -lCrun -lstdc++
Problem:
Cinelerra just hangs with a blank window titled "x".
Solution:
Try it in another wm. Or for Ion, use a FloatWS.
Problem:
Getting accelerated X-video output on a UniChrome Pro CN700 on Ubuntu 7.04 (Feisty Fawn) on an EPIA EN12000EG for TV-out playback.
Solution:
As of 2007-05-11, OpenChrome supports the CN700 in svn (but not in the stable release). Get and compile the driver (requires automake1.9, not the fancy new stuff), replace via_drv.so in /usr/lib/xorg/modules/drivers with the OpenChrome one. Optionally load the 'drm' and 'via' kernel modules. Then configure X to use the 'via' driver. Here's my xorg.conf, for a widescreen PAL TV. Hope you have an easier time than I did.
Problem:
irrecord fails on lirc 0.8.2, with kernel 2.6.22.1. It when a button is pressed, it exits immediately but claims "irrecord: no data for 10 secs, aborting, irrecord: gap not found, can't continue"
Solution:
lirc 0.8.2 doesn't support this kernel (it's probably fixed in the latest version by the time you read this). Downgrade to 2.6.20 and it works like a charm.
Problem:
Keyboard shortcuts for internet/multimedia keys (Volume Up/Down) don't work in games/rdesktop/stepmania.
Cause:
Games tend to grab the keyboard for exclusive access, so no other apps including the shortcut daemon can get to them.
Solution:
Use actkbd
Reason:
actkbd uses the evdev interface (/dev/input/event*), so it gets events regardless of the X server.
Problem:
Aplay/mplayer only plays 48000 Hz stereo files, saying "[AO_ALSA] Unable to set hw-parameters: Invalid argument" and "aplay: set_params:961: Unable to install hw params:" irrespectively. No mono and no non-48kHz files work.
Cause:
Alsa doesn't know how to resample, but doesn't mention that even when you specifically ask it to in .asoundrc.
Solution:
Rebuild alsa-libs to include all the pcm plugins. In Gentoo, this means sticking ALSA_PCM_PLUGINS="*" in make.conf and emerge alsa-lib.
Reason:
Alsa should now be able to resample audio and magically play all the other formats, even without ~/.asoundrc or /etc/asound.conf
Problem:
Latex on Ubuntu says

kpathsea: Running mktexmf ptmr8t
! I can't find file `ptmr8t'.
<*> ...:=ljfour; mag:=1; nonstopmode; input ptmr8t

(for pslatex) or

kpathsea: Running mktexmf pplr8t
! I can't find file `pplr8t'.
<*> ...:=ljfour; mag:=1; nonstopmode; input pplr8t

(for pdflatex)
Cause:
Missing fonts
Solution:
Install texlive-fonts-recommendedProblem:
When trying to automake something, it says

src/Makefile.am:85: Libtool library used but `LIBTOOL' is undefined
src/Makefile.am:85:   The usual way to define `LIBTOOL' is to add `AC_PROG_LIBTOOL'
src/Makefile.am:85:   to `configure.ac' and run `aclocal' and `autoconf' again.
src/Makefile.am:85:   If `AC_PROG_LIBTOOL' is in `configure.ac', make sure
src/Makefile.am:85:   its definition is in aclocal's search path.

and AC_PROG_LIBTOOL is indeed in configure.ac.
Cause:
libtool was not installed
Solution:
apt-get install libtoolProblem:
GtkRadiant 1.5 (64bit) maps render and play fine in Quake 3 / OpenArena, but the lighting is all wrong/bright/shadowless and vis says

--- BasePortalVis (80) ---
0...1...2...3...4...5...6...7...8...9...************ ERROR ************
pthread_join failed
2.5.17
threads: 4
Q3Map         - v1.0r (c) 1999 Id Software Inc.
Q3Map (ydnar) - v2.5.17
GtkRadiant    - v1.5.0 Aug  7 2008 02:15:55
Last one turns the lights off
...
--- TraceGrid ---
0...1...2...3...4...5...6...7...8...9...************ ERROR ************
pthread_join failed

Cause:
Something is broken in the Q3Map2 SMP support.
Solution:
Add "-threads 1" to both the vis and the light steps to force single-threading, which does work.Problem:
OpenWRT/Tomato on a WRT54GL fails to get DHCP on eth0.1, while a computer works fine on the same cable.
Cause:
The ISP might be limiting by MAC to one box per customer.
Solution:
Wait some hours without using the computer, then try the router again. Or for instant gratification, set the mac address of eth0.1, eth0.0 and eth0 to the computer's.
Problem:
Postfix SMTP auth fails with "5.7.8 Error: authentication failed: authentication failure" and a mail.log full of

postfix/smtpd[5227]: warning: SASL authentication problem: unable to open Berkeley db /etc/sasldb2: No such file or directory
postfix/smtpd[5227]: warning: SASL authentication failure: Password verification failed
postfix/smtpd[5227]: warning: 217-14-10-74-dhcp-osl.bbse.no[217.14.10.74]: SASL PLAIN authentication failed: authentication failure

even though /etc/sasldb2 exists. This is on Debian 5.0, lenny.
Cause:
SASL thinks it has to look for /etc/sasldb2 in its chroot dir, while we really want it to use saslauthd.
Solution:
Stick the following in /etc/postfix/sasl/smtpd.conf:

pwcheck_method: saslauthd
mech_list: PLAIN LOGIN
log_level: 5

Now Postfix/SASL should use the daemon rather than the file.Problem:
glxinfo (and opengl apps) crashes X, using OpenChrome on VIA hardware. glxinfo says

name of display: :0.0
libGL error: open DRM failed (Operation not permitted)
libGL error: reverting to (slow) indirect rendering
display: :0  screen: 0
direct rendering: No (If you want to find out why, try setting LIBGL_DEBUG=verbose)

And the X server says "getDrawableInfo failed to look up window".
Cause:
Bad owner/permissions on /dev/dri/card*
Solution:

chown root:video /dev/dri/card*
chmod 660 /dev/dri/card*

Problem:
'hunt' says "hunt: Can't find myself" when starting
Cause:
Your local hostname fails to resolve
Solution:
Add your `hostname` to /etc/hosts