Colin Percival's scrypt: a new chapter in the history of encryption

Today at the 2009 BSDCan conference, Colin Percival (of FreeBSD and Tarsnap) announced a new key derivation function called scrypt. I am not a math person by any means - and the slides from the presentation explain it pretty well - but what Percival has done here is phenomenal. I feel lucky to have been there in person for the presentation.

The basic concept is that sequential memory-hard algorithms make dedicated encryption ASICs significantly more costly because they are sequential (difficult to run in parallel) and memory-hard (require a significant amount of RAM relative to the size of the input.)

In other words, making the math hard and difficult to run on ten thousand cores increases the time required, and making the math need a lot of room to be worked on increases the money required to crack the password. This is because it's relatively cheap to put 10,000 encryption-specific CPU mini-cores on a single die, but it's expensive to feed them piles of fast RAM in a small space.

This is nothing short of historic.

Brute-force attacks against encrypted passwords will change overnight - for passwords created after scrypt becomes available, that is. What was once a trivial password to crack becomes decidedly less trivial - literally by an order of magnitude. By Percival's back-of-the-slide-rule math, an 8-character password with good entropy (pretty random-looking) encrypted in .1 seconds (good enough for authentication speeds) will take on the rough order of CAD$4.8M to crack. By contrast, the previous best method (bcrypt) would cost $130K.

Longer strings (source text longer than passwords) become decidedly stronger by much greater factors because the function can spend more time on them, as the user has less of an interactive expectation for file encryption. If allowed to chew on the data for 5 seconds or less, a relatively short English text string encrypted using scrypt would take CAD$210B (vs $47M for bcrypt(!))

This table from the presentation shows the rough cost estimates to crack a string in 1 year (click to enlarge):


The last column may look odd because I've taken this slide out of context. Because the 40-character string is English text, it has decidedly less entropy, and is therefore easier to crack.

This isn't just theory; Percival has published version 1.0 of working FreeBSD demonstration code.

I decided to check it out in its early state. Out of the box, the demo code makes some quick checks of your system to see how much RAM you have, and tries to sanely limit how much it uses - because it can use a lot of RAM, very very quickly. There are also limits on how large a passphrase it will currently accept, as well as other parameters automatically sized based your system's memory size.

On a quick check of the code, the options are:

• m - maximum memory fraction (default: .5, or 50% of RAM as reported by the hw.usermem sysctl for decryption; .128 for encryption)


• M - maximum memory in bytes (default: 0)


• t - maximum time in seconds (default: 5 for encryption; 300 for decryption)

In my testing on a 512M system, I couldn't immediately get it to eat more than 128M of RAM; not sure if this is fully by design, or if I'm passing the parameters incorrectly.

royce@heffalump$ time ./scrypt enc -m 1 -t 20 rand.in rand-scrypt.out
Please enter passphrase:
Please confirm passphrase:

real    0m25.090s
user    0m17.017s
sys     0m0.143s

The resulting file's header may not survive in future versions ... but for now, you can tell where it came from in the first six bytes:

royce@heffalump$ cut -b1-6 rand-scrypt.out | head -1
scrypt

At the presentation, FreeBSD Core Team member Brooks Davis asked a good question about the impact of large volumes of users trying to authenticate simultaneously on a system without huge amounts of RAM. Percival replied that the memory and other options could be tuned to fit the profile of a particular system. These parameters would be stored in the shadow password field, much as the salt and rounds are stored there today.

I look forward to seeing a full-fledged scrypt(3) show up in FreeBSD and OpenSSL ... and I'm sure that the Three Letter Agencies do not.

Binary Upgrade to FreeBSD 6.2

After the release of FreeBSD 6.2 was announced today, I decided to try Colin Percival's experimental binary OS upgrade method to upgrade a 6.1-RC2 system to 6.2-RELEASE.

The underlying approach of this method -- the freebsd-update utility -- is included in the FreeBSD base system as of this release. Between OS releases, freebsd-update can be used to keep the OS patched for security vulnerabilities. This makes it much easier to maintain continuity of a system while keeping its operating system current and secure. I love to tinker as much as the next guy ... but when it comes to stability, I love freebsd-update.

The system that I upgraded (heffalump) was originally built as a 6.0 system. Using similar upgrade scripts, I subsequently upgraded to 6.1 and 6.2-RC2 without incident.

For my upgrade to 6.2-RELEASE, I followed the steps outlined here, changing 6.1-RC1 to 6.2-RELEASE where appropriate.

[root@heffalump ~]# date
Mon Jan 15 08:38:32 AKST 2007

[root@heffalump ~]# mkdir /usr/upgrade

[root@heffalump ~]# cd /usr/upgrade
[root@heffalump /usr/upgrade]# fetch http://www.daemonology.net/freebsd-update/upgrade-to-6.2.tgz
upgrade-to-6.2.tgz                            100% of   18 kB   20 kBps

[root@heffalump /usr/upgrade]# fetch http://www.daemonology.net/freebsd-update/upgrade-to-6.2.tgz.asc
upgrade-to-6.2.tgz.asc                        100% of  187  B  878 kBps

[root@heffalump /usr/upgrade]# gpg --verify upgrade-to-6.2.tgz.asc upgrade-to-6.2.tgz
gpg: directory `/root/.gnupg' created
gpg: new configuration file `/root/.gnupg/gpg.conf' created
gpg: WARNING: options in `/root/.gnupg/gpg.conf' are not yet active during this run
gpg: keyring `/root/.gnupg/pubring.gpg' created
gpg: Signature made Sun Jan 14 11:21:59 2007 AKST using DSA key ID CA6CDFB2
gpg: Can't check signature: No public key

[root@heffalump /usr/upgrade]# tar -xzf upgrade-to-6.2.tgz

[root@heffalump /usr/upgrade]# cd upgrade-to-6.2

[root@heffalump /usr/upgrade/upgrade-to-6.2]# sh freebsd-update.sh -f freebsd-update.conf -d /usr/upgrade -r 6.2-RELEASE upgrade
Looking up update.FreeBSD.org mirrors... 1 mirrors found.
Fetching public key from update1.FreeBSD.org... done.
Fetching metadata signature for 6.1-RELEASE from update1.FreeBSD.org... done.
Fetching metadata index... done.
Fetching 2 metadata files... done.
Inspecting system... done.

The following components of FreeBSD seem to be installed:
kernel/generic src/sys world/base world/dict world/doc world/info
world/manpages world/proflibs

The following components of FreeBSD do not seem to be installed:
kernel/smp src/base src/bin src/contrib src/crypto src/etc src/games
src/gnu src/include src/krb5 src/lib src/libexec src/release src/rescue
src/sbin src/secure src/share src/tools src/ubin src/usbin
world/catpages world/games

Does this look reasonable (y/n)? y

Fetching metadata signature for 6.2-RELEASE from update1.FreeBSD.org... done.
Fetching metadata index... done.
Fetching 1 metadata patches. done.
Applying metadata patches... done.
Fetching 1 metadata files... done.
Inspecting system... done.
Preparing to download files... done.
Fetching 3734 patches.....10....20....30....40....50....60....70....80....90....100....110....120....130....140....150....160....170....180....190....200....210....220....230....240....250....260....270....280....290....300....310....320....330....340....350....360....370....380....390....400....410....420....430....440....450....460....470....480....490....500....510....520....530....540....550....560....570....580....590....600....610....620....630....640....650....660....670....680....690....700....710....720....730....740....750....760....770....780....790....800....810....820....830....840....850....860....870....880....890....900....910....920....930....940....950....960....970....980....990....1000....1010....1020....1030....1040....1050....1060....1070....1080....1090....1100....1110....1120....1130....1140....1150....1160....1170....1180....1190....1200....1210....1220....1230....1240....1250....1260....1270....1280....1290....1300....1310....1320....1330....1340....1350....1360....1370....1380....1390....1400....1410....1420....1430....1440....1450....1460....1470....1480....1490....1500....1510....1520....1530....1540....1550....1560....1570....1580....1590....1600....1610....1620....1630....1640....1650....1660....1670....1680....1690....1700....1710....1720....1730....1740....1750....1760....1770....1780....1790....1800....1810....1820....1830....1840....1850....1860....1870....1880....1890....1900....1910....1920....1930....1940....1950....1960....1970....1980....1990....2000....2010....2020....2030....2040....2050....2060....2070....2080....2090....2100....2110....2120....2130....2140....2150....2160....2170....2180....2190....2200....2210....2220....2230....2240....2250....2260....2270....2280....2290....2300....2310....2320....2330....2340....2350....2360....2370....2380....2390....2400....2410....2420....2430....2440....2450....2460....2470....2480....2490....2500....2510....2520....2530....2540....2550....2560....2570....2580....2590....2600....2610....2620....2630....2640....2650....2660....2670....2680....2690....2700....2710....2720....2730....2740....2750....2760....2770....2780....2790....2800....2810....2820....2830....2840....2850....2860....2870....2880....2890....2900....2910....2920....2930....2940....2950....2960....2970....2980....2990....3000....3010....3020....3030....3040....3050....3060....3070....3080....3090....3100....3110....3120....3130....3140....3150....3160....3170....3180....3190....3200....3210....3220....3230....3240....3250....3260....3270....3280....3290....3300....3310....3320....3330....3340....3350....3360....3370....3380....3390....3400....3410....3420....3430....3440....3450....3460....3470....3480....3490....3500....3510....3520....3530....3540....3550....3560....3570....3580....3590....3600....3610....3620....3630....3640....3650....3660....3670....3680....3690....3700....3710....3720....3730.. done.
Applying patches... done.
Fetching 5495 files... done.

The script said "Fetching 5495 files," but since it wasn't providing a progress indicator, I rigged one up in another window:

royce@heffalump$ while true; do ls -1 /usr/upgrade| wc -l; ls -lARt /usr/upgrade | head -2; sleep 1; done
   3783
total 50548
-rw-r--r--  1 root   stephb   262982 Jan 15 09:14 ac156aa7853fca9e0c739ce6e0e8691ac9a2a651653e74e69f845a9a91832ca7.gz

When it is finished, the script reports files that it cannot update, files that will be removed, files that will be added, and files that will be replaced. Make specific note of the files that cannot be updated; you will want to manually compare them with the distributed files when you're finished.

The following files are affected by updates, but no changes have
been downloaded because the files have been modified locally:
/etc/devd.conf
/etc/mail/sendmail.cf
/etc/mail/submit.cf

The following files will be removed as part of updating to 6.2-RELEASE-p0:
/etc/periodic/weekly/120.clean-kvmdb
/usr/include/c++/3.4/ext/demangle.h
/usr/lib/libpcap.so.4
/usr/lib/libpthread.so.2
/usr/share/doc/en_US.ISO8859-1/articles/building-products/b378.html
/usr/share/doc/en_US.ISO8859-1/articles/wp-toolbox/x32.html
/usr/share/doc/en_US.ISO8859-1/books/handbook/kernelconfig-nodes.html
/usr/share/doc/en_US.ISO8859-1/books/handbook/mac-examplehttpd.html
/usr/share/doc/en_US.ISO8859-1/books/handbook/mac-labelingpolicies.html
/usr/share/doc/en_US.ISO8859-1/books/handbook/network-bind9.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/LEGALNOTICE.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/c1038.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/c1189.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/c1234.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/c19.html
/usr/share/doc/en_US.ISO8859-1/books/porters-handbook/c190.html

[snip]

The following files will be added as part of updating to 6.2-RELEASE-p0:
/bin/pgrep
/bin/pkill
/boot/kernel/amdsmb.ko
/boot/kernel/geom_md.ko
/boot/kernel/if_ixgb.ko
/boot/kernel/if_stge.ko
/boot/kernel/ipmi.ko
/boot/kernel/linsysfs.ko
/boot/kernel/mfi_linux.ko
/boot/kernel/nfsmb.ko
/boot/kernel/ng_tag.ko
/boot/kernel/ppc.ko
/boot/kernel/rr232x.ko
/etc/freebsd-update.conf
/etc/rc.d/auditd
/etc/rc.d/auto_linklocal
/etc/rc.d/bridge
/etc/rc.d/bthidd
/etc/rc.d/mdconfig
/etc/rc.d/mdconfig2
/etc/rc.d/mountlate
/etc/security/audit_class

[snip]

The following files will be updated as part of updating to 6.2-RELEASE-p0:
/COPYRIGHT
/bin/[
/bin/cat
/bin/chflags
/bin/chio
/bin/chmod
/bin/cp
/bin/csh
/bin/date
/bin/dd
/bin/df
/bin/domainname
/bin/echo
/bin/ed
/bin/expr
/bin/getfacl
/bin/hostname
/bin/kenv
/bin/kill
/bin/link
/bin/ln
/bin/ls
/bin/mkdir
/bin/mv
/bin/pax
/bin/ps
/bin/pwd
/bin/rcp
/bin/realpath
/bin/red
/bin/rm
/bin/rmail

I then performed the first part of the install, which installs the new kernel and supporting files:

[root@heffalump /usr/upgrade/upgrade-to-6.2]# date
Mon Jan 15 09:32:24 AKST 2007
[root@heffalump /usr/upgrade/upgrade-to-6.2]#
[root@heffalump /usr/upgrade/upgrade-to-6.2]# sh freebsd-update.sh -f freebsd-update.conf -d /usr/upgrade install
Installing updates...
Kernel updates have been installed.  Please
reboot and run "freebsd-update.sh install" again to
finish installing updates.

I rebooted as instructed:

[root@heffalump /usr/upgrade/upgrade-to-6.2]# shutdown -r now
Shutdown NOW!
shutdown: [pid 96143]
[root@heffalump /usr/upgrade/upgrade-to-6.2]#
*** FINAL System shutdown message from royce@heffalump.prv.tycho.org ***
System going down IMMEDIATELY



System shutdown time has arrived

After reboot, note that we are running a 6.2-RELEASE kernel, but userland has
not yet been updated:

[root@heffalump ~]# uname -a
FreeBSD heffalump.prv.tycho.org 6.2-RELEASE FreeBSD 6.2-RELEASE #0: Fri Jan 12 10:40:27 UTC 2007     root@dessler.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  i386

[root@heffalump ~]# ls -la /bin/ps
-r-xr-xr-x  1 root  wheel  28728 Jul  2  2006 /bin/ps

We now install the rest of the files that have been changed between 6.1-RC2 and 6.2:

[root@heffalump ~]# cd /usr/upgrade/upgrade-to-6.2

[root@heffalump /usr/upgrade/upgrade-to-6.2]# sh freebsd-update.sh -f freebsd-update.conf -d /usr/upgrade install
Installing updates... done.

[root@heffalump /usr/upgrade/upgrade-to-6.2]# date
Mon Jan 15 09:45:17 AKST 2007

Another reboot, and now our kernel and userland match:

royce@heffalump$ uname -a

FreeBSD heffalump.prv.tycho.org 6.2-RELEASE FreeBSD 6.2-RELEASE #0: Fri Jan 12 10:40:27 UTC 2007     root@dessler.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  i386

royce@heffalump$ ls -la /bin/ls
-r-xr-xr-x  1 root  wheel  23444 Jan 15 09:37 /bin/ls

Once my download of ISO for disc1 is complete, I'll look at the three straggling files (/etc/devd.conf,/etc/mail/sendmail.cf, and /etc/mail/submit.cf) and merge any changes as appropriate.