[Crypto: age] scrypt, From Password to Key

age uses scrypt to derive a key from a passphrase. A key derivation function is an algorithm that calculates a key from other input values. Each scrypt operation uses time and memory.

The header post showed a salt and a work factor. Together with the passphrase, those values let scrypt make the same wrapping key during encryption and decryption.

A longer key does not make a passphrase less predictable

The encryption algorithm uses a key of a fixed size. A passphrase can have a different length. scrypt converts the passphrase into a key of that size.

This conversion does not add random choices to the passphrase. If an attacker tries the correct passphrase, scrypt makes the correct key. A common password remains predictable even when the derived key has 32 bytes.

The useful cost is the work for each attempt. The owner usually derives the key once to decrypt a file. An attacker must repeat the calculation for each candidate passphrase.

The parameters in an age file

For the example header, the stored work factor is 18. age interprets this as N = 2^18, or 262,144.

The pseudocode shows the inputs. It is a formula, not a command:

wrapping key = scrypt(
    passphrase = user input,
    salt = "age-encryption.org/v1/scrypt" followed by the 16 salt bytes,
    N = 262144,
    r = 8,
    p = 1,
    output length = 32 bytes
)

The fixed label separates this use of scrypt from uses with different labels. The random salt also makes the calculation specific to this file. Neither value is a secret.

The age 1.3.1 implementation uses these parameters and defaults to work factor 18. The format permits other work factors. Thus, the header value matters when age decrypts a file.

Why one attempt uses about 256 MiB

scrypt uses a large memory area during its calculation. The primary memory area has approximately 128 × N × r bytes.

For this example:

128 × 262144 × 8 = 268435456 bytes = 256 MiB

MiB means mebibytes. One MiB is 1,048,576 bytes. GiB means gibibytes. One GiB is 1,024 MiB. The program also uses some memory outside this primary area.

Ten attempts at the same time use about 2.5 GiB for their primary memory areas. This requirement makes large parallel attacks more expensive. Memory capacity limits how many attempts fit at once. Memory bandwidth limits how quickly the hardware can transfer data.

These limits do not prevent an attack. Hardware and implementation choices affect the rate. Some implementations exchange more calculation work for less memory. The scrypt specification gives the algorithm and its parameters.

Measure scrypt on your computer

The initial measurement used an Apple M5 and Python hashlib.scrypt. It recorded about 0.3701 seconds for each calculation, or 2.70 calculations each second. Those figures apply to that measurement. Other computers can give different results.

The Python example measures only scrypt. It does not decrypt an age file or test the authentication tag. Its salt includes the age label used in the file format.

Use Python 3 with hashlib.scrypt support. Make sure that more than 256 MiB of memory is available. The Python documentation gives the function parameters.

1. Save this code in a new file called measure_scrypt.py:

   python

   import hashlib
   import os
   import time
   
   cost = 1 << 18
   block_size = 8
   parallelism = 1
   main_memory = 128 * cost * block_size
   salt = b"age-encryption.org/v1/scrypt" + os.urandom(16)
   
   def derive_key(passphrase):
       return hashlib.scrypt(
           passphrase,
           salt=salt,
           n=cost,
           r=block_size,
           p=parallelism,
           dklen=32,
           # Permit memory for internal work outside the main area.
           maxmem=main_memory + (64 << 20),
       )
   
   # Exclude the initial call from the measured calls.
   derive_key(b"warmup")
   attempts = 8
   start = time.perf_counter()
   for index in range(attempts):
       derive_key(f"guess{index}".encode("ascii"))
   elapsed = time.perf_counter() - start
   
   print("seconds per calculation:", round(elapsed / attempts, 4))
   print("calculations per second:", round(attempts / elapsed, 2))
   

2. Run the file:

   bash

   python3 measure_scrypt.py
   

The first output number is the average time for one calculation. The second number is the number of calculations each second. Your results can differ with processor speed, memory, Python version, and other running programs.

What a higher work factor changes

An increase from 18 to 19 doubles N. The primary memory area increases from 256 MiB to 512 MiB. At work factor 20, it increases to 1 GiB.

The time usually increases too, but you must measure it for an accurate result. A larger work factor also increases the cost of legitimate decryption.

A slow calculation cannot compensate for a predictable passphrase. If the correct passphrase is the first candidate, only one attempt is necessary. Random selection from a large set increases the expected number of attempts in an exhaustive search.

The attack time post calculates this difference. First, the next post follows the wrapping key to the encrypted file key and payload.