Why does Signal repeatedly hash the secure passphrase?

Question

Background: I'm working on creating a small program to extract my messages from Signal's newly-added (beta) encrypted backup feature.

In the Signal codebase for their Android app, I noticed that instead of just hashing both the salt and passphrase once, they repeatedly hash it 250,000 times.

MessageDigest digest = MessageDigest.getInstance("SHA-512");
byte[]        input  = passphrase.replace(" ", "").getBytes();
byte[]        hash   = input;

if (salt != null) digest.update(salt);

for (int i=0;i<250000;i++) {
    if (i % 1000 == 0) { EventBus.getDefault().post(new BackupEvent(BackupEvent.Type.PROGRESS, 0)); }
    digest.update(hash);
    hash = digest.digest(input);
}

return ByteUtil.trim(hash, 32);

(Source code can be found here)

I don't understand what benefits this offers over something that conceptually does:

sha512sum(sha512sum(concat(salt, passphrase)))

Am I correct in assuming that this does not add any extra security? Why exactly has this been done?

---

Additional Information:

The password for the backup is generated here and is 30 bytes long and then set contextually on line 37 of that file. This code was added in the commit 22 days ago, when encrypted backup was added and is currently only visible in the beta version of the app.

Answer 1

Cryptographic hashes are designed to be fast and collision resistant. It turns out that when hashing passwords, it is more secure to have a slow hash function. One way to make a fast hash function slow is to iterate it. Like is done here.

Think about it this way. If an attacker is able to compute a million hash calculations in a second, if you only ran your password through the hash function once, they would be able to attempt a million guesses each second. On the other hand, if you iterate the hash function 250,000 times, now the attacker can only make 4 guesses a second. That is a pretty substantial reduction and increases the amount of work the attacker has to do. If users were really good at choosing passwords, this might not matter, but the fact of the matter is that users are not good at choosing good passwords. Making the hash function slow helps in that regard.

In the case of Signal, it looks like encrypted backups is a beta-feature. Looking at one screenshot, it appears that the backup key is not user chosen. It is likely (haven't dug through the code) a 30 digit random number. That means it has about 100 bits of entropy at best. My guess is that the designers still wanted a slow hash function for the reasons listed above, even though the passphrase was not user chosen. Making it slow is a good trade-off for having less entropy. They could have made the random number longer to get more entropy (256 bits maybe), but that would have made the backup key that the user has to store much longer.

Answer 2

Am I correct in assuming that this does not add any extra security?

No. This does add security and is a standard practice when dealing with passwords. What they do there is called a password hashing scheme (PHS), sometimes also referred to as password-based key derivation function (PBKDF). Other common instances of this are Argon2, bcrypt, scrypt or PBKDF2 with the former three being more technically advanced than the scheme at hand.

---

So why do we do this?

Well, it turns out that users suck at choosing passwords. They usually pick their passwords from a small set of possible passwords. So as we can't actually force the users to pick really strong passwords because they will game all the rules we can come up with.

Because users pick their passwords from a small set, an attacker can just try all these passwords until one works, so we use the only option we have left, we make this check operation much more expensive so that an attacker who wants to try all the $2^{20}$ most likely passwords, has to invest about one second of time per try. This is negligible for a single derivation for the user, but when you need to try that many passwords, it adds up and can somewhat salvage the fact that passwords suck.

---

From the (now deleted) comments (by Jer):

If the only point is to slow down logon attempts so someone trying to guess a password can't check tons of them very quickly, why not just sleep for half a second or something like that?

If an attacker gets hands-on the file / the hash, they surely will not obey to this standard behavior and sleep for half a second, they will just have a short laugh and remove this behavior when trying to recover the password.

So he starts going through his list of "known" passwords (the "2^20 most likely") and applying the hash function, and seeing if the result matches the hash he obtained? But how does he know the hash function (including the number of iterations)?

Yes, that's how it works and the hash function including iterations, can either by obtained from context (e.g. by reading the technical documentation), by reverse-engineering the software (if available), by just guessing for common schemes or by the format of the hash (e.g. if it is the modular crypt format which contains iterations parameters, the salt and the hash identifier).