[ngddxzoq] crypt vs gpg s2k

hashing a password with 65 million rounds (key stretching) using SHA-512 and crypt(3) takes about 27 seconds.

$6$rounds=65000000$...
26.83user ...

encrypting a passphrase with s2k-count 65 million (the maximum) and hash algorithm SHA-512 takes 0.7 seconds with GPG:

$ command time gpg -ca --s2k-digest-algo SHA512 --s2k-mode 3 --s2k-count 65000000 foo
0.69user

time difference is a factor of 40.

investigating further:

for glibc crypt(3), key stretching is done in glibc-2.27/crypt/sha512-crypt.c .  it works approximately the way one expects, reinitializing and finalizing the hash algorithm each time.

  /* Repeatedly run the collected hash value through SHA512 to burn
     CPU cycles.  */
  for (cnt = 0; cnt < rounds; ++cnt)
    {
      /* New context.  */
      sha512_init_ctx (&ctx, nss_ctx);

      /* Add key or last result.  */
      if ((cnt & 1) != 0)
	sha512_process_bytes (p_bytes, key_len, &ctx, nss_ctx);
      else
	sha512_process_bytes (alt_result, 64, &ctx, nss_ctx);

      /* Add salt for numbers not divisible by 3.  */
      if (cnt % 3 != 0)
	sha512_process_bytes (s_bytes, salt_len, &ctx, nss_ctx);

      /* Add key for numbers not divisible by 7.  */
      if (cnt % 7 != 0)
	sha512_process_bytes (p_bytes, key_len, &ctx, nss_ctx);

      /* Add key or last result.  */
      if ((cnt & 1) != 0)
	sha512_process_bytes (alt_result, 64, &ctx, nss_ctx);
      else
	sha512_process_bytes (p_bytes, key_len, &ctx, nss_ctx);

      /* Create intermediate result.  */
      sha512_finish_ctx (&ctx, nss_ctx, alt_result);
    }

in GnuPG 1, key stretching is done in gnupg1-1.4.22/g10/passphrase.c in the function hash_passphrase.

in GnuPG 2, key stretching is done in libgcrypt20-1.8.1/cipher/kdf.c in the function openpgp_s2k.

both are approximately the same code:

    /* a little bit complicated because we need a ulong for count */
    while( count > len2 ) { /* maybe iterated+salted */
        md_write( md, s2k->salt, 8 );
        md_write( md, pw, pwlen );
        count -= len2;
    }

pgp gnupg gpg openpgp all work by creating one long string of length around 65 million bytes, repeating the salt and password as many times as necessary, and hashing it once.  this probably explains the speed difference.  how secure is this as a key stretching algorithm?  it seems unorthodox.  can clever tricks compute it faster than naively?