Dan Kaminsky's Blog

Forward:
It is unfortunately common practice that applications which allow
users to remember their passwords as a convenience rarely encrypt them
but instead opt to simply obfuscate them.

Actually, it’s an unfortunately (verging on ridiculously) common practice to
think that there’s any difference between encoding a password using a fixed
algorithm and “encrypting” a password using a fixed key.

There isn’t one.

This is easily provable in terms of mere simplicity. How hard is it to
reverse engineer the instructions a binary executes to implement some
homebrew obfuscation? Reasonably doable, but it’s definitely at least a bit
of work–much more work than just tracing the application opening up some
file “c:\sekret.key” that happens to be the 168 bit Triple-DES key that’ll
decrypt its password database.

So does that mean that 3DES is less secure than some homebrew? No. It
means 3DES is being misused. Badly.

Any system that attempts to verify a password by comparing the password
plaintext supplied against the correct password plaintext has already lost.
No matter how many obfuscations and contortions it goes through, it can
never escape the fact that the system itself must have permanently available
access to the password plaintext. Encrypting the password with 3DES means
nothing; the decryption key for the password is as functionally open as code
for the executable running the home brew system. (Indeed, as we saw above,
since the secrecy is distilled rather than hidden in binary code, it’s
actually *easier* to rip off passwords when they’re 3DES encrypted!)

Of course, the obvious question is how a system verify the correctness of a
password without actually posessing that password. It’s a question that’s
rather repeatedly answered. Password handling is simultaneously one of the
few Solved Problems of Cryptography *and* one of the most misunderstood.
Simply store a MD5 or SHA-1 one-way hash of the password. One way hashes
lead to a fixed size, deterministic, and computationally unfeasable to
invert value from some amount of input data. Passwords make great input
data. When a plaintext password comes in, compare the MD5/SHA-1 hash of the
submitted password with the stored hash. If it matches, the password was
correct. If it doesn’t match, the password wasn’t correct.

There are (much) more advanced password exchange systems for network
password exchange, SRP for example, but if your system needs to locally
verify a password from the user, *please*, before cryptographers around the
world walk out in disgust, at least just store a hash instead of the actual
plaintext. Hashes prevent plaintext-equivalent information from being
stored at all. That means there’s nothing for an attacker to decrypt en
masse–he or she can only try password after password to see if it hashes
correctly.

The core theoretical problem with encrypting *or* encoding passwords
actually derives from the fact that different users–indeed, all users–are
all dependant on one nonsecret: Either a fixed algorithm or a fixed key is
shared throughout the vendor’s clientele. There’s no secrecy in my password
database if you’ve got the same password or algorithm protecting yours.
Sooner or later, one of us is going to post to Bugtraq the simple method to
decrypt the other’s database. With hashes, there exists no key that *can*
decrypt the database.

One reasonably simple solution(translation: somebody contact me if this is
in error) for those who have implemented a respected encryption system(RC4,
Blowfish, even *DES* qualifies) to obfuscate access to their password
database is to encrypt passwords with themselves–i.e. encrypt “fg&^2jfa”
with the key “fg&^2jfa”. Using one way hashes essentially challenges a user
to provide the only value that will invert the hash equation, i.e. the
original data. Encrypting content with itself similarly challenges a user
to prove they have the only value that will invert the encryption equation,
again, the original data. While plaintext is indeed stored on a host, only
somebody who already *has* the plaintext can access it. That happens to
overlap exactly with the intent of a password system.

The most common reason why hash systems aren’t used, of course, is that
often the plaintext is needed by the system for purposes outside of
verification. Sometimes the system needs to automatically represent itself
as a user–with the user’s passwords–in order to fulfill the demands of a
protocol. This is primarily a problem with network authentication when no
plaintext has been exchanged, only hashes. But local authenticators will
*always* have access to the plaintext password, because they control the
user interface that the user uses to actually enter it in the first place!
If the password is representing the user, then storing the plaintext in RAM
while the user can be presumed to still be controlling the machine(two
minutes since last keypress?) means the required password would be made
available. The only reason a local authenticator would need to store an
easily decryptable password is if, at arbitrary times when the user wasn’t
around to supply the password, the system needed to prove to itself or
someone else that it indeed had the plaintext password.

Indeed, it’d need to be able to access a password before a user ever entered
it in the first place. At that point, who exactly is the system
representing, anyway? It’s actually not an empty question. Automated mail
checkers and instant messengers are often are expected to have access to a
plaintext password without having to retrieve it from the user on each
reboot. At that point, the physical security of the system and the hard
drive is turned into the authentication token for the user controlling that
system. Given the mass of IM services I’ve known some people to run and the
number of reboots this mass entails, forcing users to repetitively log in
becomes a difference between life and death. Ideally, passwords of this
type would be locally managed by a single “identity password” that the user
typed in once on login and that never needed to be transmitted or recorded
anywhere. Security may begin with the physical, but it sure better not end
there.

Most systems, however, simply don’t have those kinds of requirements, and
that leads to the bottom line: Use hashes. It’s a solved problem. Stop
helping people hack your code, stop helping people hack our servers, stop
helping me quote Susan Powter. Please. Thank you.