11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Your suggested sha512^2(salt | passphrase) is needlessly weaker than HMAC(salt, passphrase). See HMAC for why. $\endgroup$ – cypherfox Mar 21 '18 at 1:23
  • $\begingroup$ @cypherfox It was given as an example of an alternative. There are lots of alternative things they could have done here, my question was why they settled on this approach. $\endgroup$ – Finn O'leary Mar 21 '18 at 23:41
  • $\begingroup$ Yes, but HMAC is the first step of transforming a hash function when using PBKDF2. Aka effectively iterated-HMAC. $\endgroup$ – cypherfox Mar 22 '18 at 1:10
21
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 100 bits of entropy is quite sufficient, if you actually have those 100 bits of entropy. That's enough for a billion processors trying a billion keys per second each to need to run for thousands of years before they have an appreciable chance of breaking it. $\endgroup$ – Henning Makholm Mar 21 '18 at 1:07
  • $\begingroup$ @henning, most organizations that recommend key lengths for data security do not consider 100 bits as secure enough for long term (say 20+ years) security. $\endgroup$ – mikeazo Mar 21 '18 at 1:21
  • 1
    $\begingroup$ @nic here are some posts that answer your question: crypto.stackexchange.com/questions/21052/… and crypto.stackexchange.com/questions/48720/… $\endgroup$ – mikeazo Mar 21 '18 at 10:45
  • 1
    $\begingroup$ I am curious. The Signal developers are not cryptographic novices; why are they iterating SHA-512 rather than just using (eg) Argon2? $\endgroup$ – Martin Bonner supports Monica Mar 21 '18 at 11:34
  • 1
    $\begingroup$ @NicHartley If the hash is "random" (a more precise articulation of the property likely wouldn't fit in a comment), then this doesn't increase the number of collisions. A poorly designed has, e.g. one for which the output is "concentrated" on some outputs more than others, will likely get even worse as it's iterated. $\endgroup$ – Acccumulation Mar 21 '18 at 21:04
11
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.