Comment by ReidZB | Hacker News Reader

Comment by ReidZB | Hacker News Reader

Parent Full thread

You're right --- had they used something other than ECB mode. For example, if they used CBC mode with a proper IV, assuming the key is not stolen or compromised, the passwords would be quite secure.

The issue becomes verifying the passwords, then: supposing you have a CBC mode oracle, like a HSM, how can you verify two passwords are the same? (This is probably the reason they chose ECB mode in the first place.) In fact, if you allow the user to test if two ciphertexts represent the same plaintext --- and nothing else --- you still break the very definition of secure encryption, namely that a secure encryption scheme should have, as one popular definition, indistinguishable ciphertexts (usually under a chosen-plaintext attack).

So you have to develop some new way to measure security for the scheme, or perhaps somehow measure the damage that an equality oracle can inflict upon an IND-CPA secure scheme. The notion of indistinguishable ciphertexts roughly reflects the inability of an attacker to reliably learn any function of the plaintext from the ciphertext. Throwing that idea out the window seems unwise, since it's such an elegant idea. So, anyway, you're off in uncharted waters, not a good place to be if you're securing users' passwords.

All of that is relatively complex, though, so just let me know if I need to elaborate on some idea more. (I am never sure how in-depth to go in these posts.)

For anyone wondering about the acronyms above, ECB is Electronic Codebook, CBC is Cipher-block Chaining, and IV is an Initialization Vector used in CBC. IND-CPA is Indistinguishability under chosen-plaintext, a method of attack.

These are explained at [1] and [2]

[1] http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

[2] http://en.wikipedia.org/wiki/Ciphertext_indistinguishability

> The issue becomes verifying the passwords, then: supposing you have a CBC mode oracle, like a HSM, how can you verify two passwords are the same? (This is probably the reason they chose ECB mode in the first place.)

Why is that? What's wrong with verifying a password in CBC mode with different IV?

AFAIK you need the same IV for both encryption and decryption.

Some calculate an IV using existing components (such as has of email or name or such), some always use 0x0 as IV. But safest method is to have a random IV (preferably also stored in a HSM along with the key) per encrypted account.

I am assuming that the DB server cannot decrypt. If the DB server has decryption permissions, and it is compromised, then there's little need in encrypting the passwords anyway as an attacker will simply decrypt them by hand. (They may not get all of them before being detected, but they'd still get some or most --- and they might look for high-value targets!)

Unlike ECB mode, you can't just encrypt the same password again and check to see if the ciphertexts are the same --- the IVs will be different (hopefully!). So, can you somehow check two ciphertexts with different IVs to see if they represent the same plaintext? Nope, probably not: if you could, then the scheme would no longer have indistinguishable encryptions under a chosen-plaintext attack [1]. Briefly, this ability to test if two ciphertexts represent the same plaintext would allow the adversary in the IND-CPA game to simply encrypt both of the plaintexts and test them against the challenge ciphertext. (See the [1] reference for more info on this.)

In fact, this is exactly the property you don't want. You don't want to be able to determine if two users have the same password. If the DB server were able to test ciphertext equality, then it could pairwise-test each pair of users (or again only hunt for high-value targets).

If you were really adamant on encrypting passwords, I'd also suggest that we'd need to pad the password out to the max password length to prevent the revelation of password length. But of course, I very strongly suggest against password encryption. Still: that's another thing to consider in this hypothetical scenario.

[1] http://en.wikipedia.org/wiki/Ciphertext_indistinguishability

Why go through all that when you could use the username or email together with the password to encrypt it with 3DES ECB mode? Those would be unique and users who have same passwords would still have different ciphertexts.

Sorry for my late response.

3DES has a block size of 64 bits, or 8 bytes. Unlike a hash function where the whole input affects the whole output (the strong avalanche criterion and whatnot), in ECB mode encryption, data is only changed on 8-byte block boundaries.

So, for example, suppose the user's username was 8 characters, their email was 16 characters, and their password was some more characters. Then if you use

  3DES-ECB(uname || email || passwd)

where || denotes concatenation, then uname and email will take up 3 blocks and the password will be the rest... this is essentially the same scenario as the Adobe leak, except that the attacker now has to worry about how the password falls across the block boundaries. In this contrived scenario, the password starts a new block of its own, so the addition of the uname/email adds no security here.

Since the uname/email lengths are public, you still might be able to cross-reference sections of identical passwords with other users, depending on how the blocks line up. In any case, this scheme still doesn't offer the unconditional security level you'd like.

I'd recommend the Matasano crypto challenge [1]. It covers some material similar to this pretty early on, so you get your feet wet here.

[1] http://www.matasano.com/articles/crypto-challenges/

Wow thanks that was interesting, hadnt thought of that.

> I am assuming that the DB server cannot decrypt. If the DB server has decryption permissions, and it is compromised, then there's little need in encrypting the passwords anyway as an attacker will simply decrypt them by hand.

I am not an expert in security/cryptography, but to decrypt you need a secret key, don't you? In this case Adobe believes the cracker doesn't have the secret key which means if Adobe engineers did use CBC and random IV for each password, the cracker can't learn much even provided with hints in the database.

So if you store the IV and the ciphertext in DB, and when you want to authenticate, you encrypt the plaintext with that IV with your secret key. I don't see why that can't be done. Encryption is really only as strong as your secret key security and the IV in this case looks like a salt in hashing scheme. The difference encryption is bi-directional and hashing is one-way.

So I don't understand why they have to use EBC mode. I am not getting your point.

Reply on news.ycombinator.com