SRP verifier strength

[Tom Holroyd]

Measurement of SRP verifier strength against an offline dictionary attack.

Intro

In a dictionary attack, an SRP verifier is computed for all words in a
dictionary of possible passwords, given constant username, salt, and SRP
parameters (prime modulus and generator), and compared against a stolen
verifier.

Methods

The dictionary used contained 10,000 words chosen at random from a larger
corpus.  The average word length was 7.76 characters.

A large sample of verifiers were prepared using passphrase lengths of 8,
16, 24, and 32 characters, and the user name 'alice'.  10 verifiers were
prepared for each prime in the default list (the 'primes' file plus the
libsrp primes) from the OpenSSH+SRP distribution.  The passphrases were
not in the dictionary.

The user time (returned by the times() function) was measured for the time
taken to check all 10,000 words against each known verifier.  Times were
measured on a 667 MHz Linux/Alpha 21264.  Results are given as the "crack
rate" in words per second (wps).  Higher rates mean the dictionary attack
succeeds sooner.

Results

In general, longer primes had lower crack rates.  The following table
summarizes the average wps across all primes of a given size.

+------+----------+------+
| bits | avg_wps  | n    |
+------+----------+------+
|  512 | 2123.036 |   40 |
|  640 | 1588.509 |   40 |
|  768 | 1381.072 |   80 |
| 1024 | 1015.222 |   80 |
| 1026 |  947.602 | 1680 |
| 1280 |  742.186 |   40 |
| 1536 |  576.117 |   40 |
| 2048 |  368.924 |   40 |
| 2049 |  357.929 | 1040 |
+------+----------+------+

For these rates, doubling the size of the prime increases the time to do
the dictionary search by an average factor of approximately 2.5.

These rates are to be compared with the DES (*nix crypt()) rate on the
same machine of ~300,000 wps, the MD5 rate of 704 wps, and the Blowfish
rate of 90 wps (values from a "John the Ripper" benchmark).  Thus a prime
length of about 1350 bits matches the MD5 rate.  (Note that md5_crypt()
was designed to be very slow, and runs over 1000 separate hashes to build
the passwd entry, while most of the SRP time is in a single modular
exponentiation.)

For a given bit length, the choice of prime (when a choice was available)
made only a small difference.  The table shows the percent difference
between the minimum and maximum average crack rates across primes of a
given length.

+------+----------+----------+---------+----+
| bits | min_wps  | max_wps  | percent | n  |
+------+----------+----------+---------+----+
|  768 | 1379.679 | 1382.464 |   0.201 |  2 |
| 1024 | 1001.226 | 1033.758 |   3.147*|  2 |
| 1026 |  938.486 |  959.641 |   2.204*| 42 |
| 2049 |  356.257 |  360.235 |   1.104 | 26 |
+------+----------+----------+---------+----+
* these values are actually too high because
 network time synchronization operations on this
 machine caused several jumps in the system clock
 during the test

Passphrase length was not a factor; the differences in crack rate were
negligible, and when the average rate was appropriately normalized, the
passphrase lengths were ordered randomly.  This was to be expected,
because all passphrases are hashed to the same length.

In summary, while the SRP protocol itself remains strong even with a low
entropy passphrase, the verifier entries are no stronger than with other
common methods (except DES).  Thus it may be assumed that stolen verifier
files (such as /etc/tpasswd and $HOME/.ssh/verifier) are typically
vulnerable, where "typically" refers to the fact that many users choose
very bad passwords.  Even for 2049 bit primes, 10 million passphrases can
be checked in less than 8 hours on this machine.  High entropy
passphrases, of course, result in verifiers that resist dictionary or
brute force attack: 8 characters chosen at random from [a-z0-9] takes over
90 years on average with a 1026 bit modulus, and 250 years with a 2049 bit
modulus.

Dr. Tom Holroyd
"I am, as I said, inspired by the biological phenomena in which
chemical forces are used in repetitious fashion to produce all
kinds of weird effects (one of which is the author)."
	-- Richard Feynman, _There's Plenty of Room at the Bottom_