Authentication

Passwords

Password strength and entropy

A longer password using a larger character set will be more secure. The number of possibilities is given by $p = w^l$, where $w$ is the size of the character set and $l$ is the length.

The number of possibilities can be very large, so a logarithmic scale is used to quantify strength. The entropy of a password is given by $x = \log_2 w^l$ or equivalently $l\log_2 w$. Entropy gives the theoretical uncertainty of a password, but in reality people are likely to use common words or numbers.

Hashing and salting

Passwords must never be stored as plain text. They should instead be hashed. Hash functions are one-way functions which return the same fixed length output for a given input. When the user enters a password, the hash can be compared to the stored hash. If they are the same the password is correct.

Salting a password before hashing it gives additional protection against lookup attacks as it will change the hash of the password. A salt is just some random data which is appended or prepended to the password before it is hashed. The salt is then stored alongside the hash so when the user enters a password, the salt can be added before comparing the hash.

Biometric authentication

Biometric authentication makes use of unique biological features, such as fingerprints or irises. This is ideal as only the intended user has the correct biological features, but it is susceptible to false positives.

Password cracking

Brute force attack

Try every possible input combination. Very inefficient.

Dictionary attacks

Use a list of common words or phrases which people are likely to use as passwords. Simple and usually effective.

Lookup tables

Pre-calculate the hash of many potential passwords, then look up an unknown hash to get the original password. Time efficient as hash tables have fast access and hashes only have to be calculated once. Space inefficient as a large number of password/hash pairs have to be stored.

Reverse lookup tables

Like a lookup table, but makes use of a hash chain. The hash chain is computed using a reduction function which maps hash values back into password values. The hash function and reduction function are applied a set number of times and only the first and last passwords are stored together.

To perform a lookup, apply the reduction and hash functions until a password matching an end password in the table is found. Then, take the start password and create the hash chain up until that point. The value before the hash being looked up is the desired password.

Reverse lookup tables are more efficient than simple lookup tables, but are susceptible to hash chain collisions, where two chains contain the same sub-chain at some point. This is redundant data and wastes space.

Rainbow tables

The rainbow table is designed to reduce chain collision by using different reduction functions for each reduction.