No Tricks: The spin on passwords for AES

Sunday, December 14, 2008

The spin on passwords for AES

In Are AES-256 keys too Large? I discussed that 256-bit keys will fall short of their implied security when derived from passwords or embedded in protocols with other cryptography. To achieve the equivalent of 256-bit security users would need to select 40 character passwords at random, and protocols would need to employ RSA keys with at least 13,000 bits. At times 256-bit keys are just too big for their own good.

Nonetheless AES-256 is being widely deployed since it conveniently lies at the intersection of good marketing and pragmatic security. In upgrading from AES-128 to AES-256 vendors can legitimately claim that their products use maximum strength cryptography, and key lengths can be doubled (thus squaring the effort for brute force attacks) for a modest 40% performance hit.

Perhaps this reasoning prevailed at Adobe when they recently upgraded their document encryption scheme from AES-128 in v8 to AES-256 in v9. However Adobe later had to announce that v9 in fact offers less security against brute force attacks as compared to v8. What went wrong? They forgot about the spin.

The Spin Factor

A well-known standard for converting passwords (or in fact arbitrary bit strings) into cryptographic keys is the password-based cryptography standard PKCS #5 from RSA. PKCS #5 has been stable at version 2 for almost 10 years now, and has also been published as RFC 2898. PKCS #5 defines a generic PBKDF (Password-Based Key Derivation Function) to produce a cryptographic key from a password or passphrase

Key = PBKDF( salt, password, iteration count)

PBKDF takes the bit string and salt value, and repeatedly applies a pseudo-random function, such as a hash function, to produce the cryptographic key.

The number of applications of the hash function is called the iteration count. Both the salt and the iteration count have been introduced to thwart exhaustive attacks. The salt increases the space required to store a table of pre-computed password/key pairs, while the iteration counts increases the cost of computing a single password guess. PKCS #5 recommends that the iteration count be at least 1,000. Additional operations inserted to slow down performance for security reasons are also called spin.

Too Little Spin

Let's get back to Adobe with these ideas in mind. In Adobe v8, 50 calls to the MD4 hash function were required as well as 20 calls to RC4 to perform a single password guess. This limited the password guess rate to about 50,000 trials/second on a modern Intel processor. However in v9 the PBKDF computation was replaced by a single call to SHA-256, which according to ElcomSoft, allows a highly optimised attacker to undertake over 73 million trials/second. Attackers can brute force their way through the password space 1500 times faster in v9 than in v8.

Adobe has said that the intention of the changes from v8 to v9 were to make encrypted documents open faster, which they certainly achieved as compared to v8. But in this case security can only decrease when encryption key lengths are increased but are still bootstrapped off the same password base. To their credit, Adobe increased the length of passwords from 32 Roman characters in v8 to a massive 127 Unicode characters in v9, so it would be possible to select a password as secure as an AES-256 key. Even so, for higher-assurance applications, Adobe continues to recommend using PKI-based encryption or Adobe LiveCycle Rights Management encryption.

Micro Spin

David LeBlanc, a well-known security professional and author, recently described Microsoft's new agile encryption to be supported in Office 2007 SP2. The Microsoft standard is based on PKCS #5 and allows for a spin of up to 10 million iterations and a salt of length 64,000. LeBlanc states that brute-forcing passwords is a real threat, so it is a necessary evil to artificially inflate the work factor of performing password trials. In other words he's a fan of spin when required.

There was more than a hint of Schadenfruende when LeBlanc stated that their new method using a spin of 50,000 was over 15,000 times "slower" than Adobe v9. To be fair, LeBlanc also provides a link to another post from July where he reviewed Microsoft's spotty Office encryption history. It's quite unpleasant reading actually, and Leblanc went as far as saying that

As of Office 2007, we do warn you that the encryption we do on the binary documents is weak. Most of the time, it's so weak that it will only act as a mild deterrent. In some cases, we missed encrypting things entirely (which is actually called out in a KB article some time ago).

My advice is that if you must encrypt a binary document, use a 3^rd party tool to do it.

The line break and italics were added by me. The default encryption in Office 2007 is 40-bit RC4 and is only being corrected with the new standard available in Office 2007 SP2. Keep that in mind when using MS encryption before SP2.

Toxic Spin

If password policies are not made more complex when moving from AES-128 to AES-256 then this upgrade only brings marketing advantages but not security advantages. Deriving or bootstrapping AES keys from passwords is really an exercise in self-deception, especially when considering 256-bit keys. The discrepancy between the low entropy of passwords and the astronomical keyspace of AES-256 simply cannot be reconciled.

Adding spin to password-based computations is a workaround to the unpleasant fact that human habits and memory are vastly outmoded in today's IT environment. Everything is getting faster, better and cheaper - except us. Passwords remain the most toxic asset on the security balance sheet, but don't expect a bailout any time soon.