Authentication Systems: Password verification systems use key stretching to slow down authentication attempts, making online brute-force attacks impractical while maintaining reasonable performance for legitimate users.

Seed Generation: When generating cryptographic seeds or salts from user-provided entropy, key stretching ensures the resulting material has sufficient cryptographic strength for secure key generation.

Key Participants

The key stretching process involves several participants:

Input Secret: The weak, human-generated password or passphrase that serves as the initial entropy source. This typically has low entropy (40-60 bits for typical passwords) compared to cryptographic requirements (128+ bits).

Salt: A random value unique to each user or key derivation instance. The salt prevents identical passwords from producing identical stretched keys and defeats rainbow table attacks.

Key Derivation Function (KDF): The cryptographic algorithm that performs the stretching operation. Modern KDFs include PBKDF2, bcrypt, scrypt, and Argon2.

Iteration Count/Work Factor: A parameter controlling how many times the stretching operation is applied. Higher values provide greater security but require more computation time.

Output Key: The cryptographically strong key produced by the stretching process, suitable for use in encryption, authentication, or further key derivation.

Process Flow

The key stretching process follows a well-defined sequence of operations designed to maximize computational cost for attackers while remaining practical for legitimate users.

Step 1: Input Preparation

The process begins with input preparation, where the user-provided secret (password or passphrase) is prepared for processing:

1. Encoding: The password string is encoded into bytes using a consistent encoding (typically UTF-8)
2. Normalization: The password may undergo Unicode normalization to ensure consistent representation across different systems
3. Validation: Basic validation ensures the password meets minimum requirements (length, character set)

Step 2: Salt Generation or Retrieval

The salt component is either generated (for new keys) or retrieved (for existing keys):

New Key Generation:

• Generate a cryptographically random salt using a CSPRNG
• Salt length typically matches or exceeds the output key length (128-256 bits)
• Store the salt alongside the stretched key or in the keystore metadata

Existing Key Derivation:

• Retrieve the previously generated salt from storage
• The same salt must be used to reproduce the same stretched key from the same password

Step 3: Key Derivation Function Application

The core stretching operation applies the selected KDF with configured parameters:

PBKDF2 (Password-Based Key Derivation Function 2):

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

Where:

• PRF = Pseudorandom function (typically HMAC-SHA256 or HMAC-SHA512)
• Password = Input password bytes
• Salt = Random salt bytes
• c = Iteration count (work factor)
• dkLen = Desired output key length

The function iteratively applies the PRF:

U1 = PRF(Password, Salt || INT(i))
U2 = PRF(Password, U1)
U3 = PRF(Password, U2)
...
Uc = PRF(Password, Uc-1)
T = U1 XOR U2 XOR U3 XOR ... XOR Uc

Modern Alternatives:

Argon2 (recommended for new implementations):

• Memory-hard algorithm resistant to GPU/ASIC attacks
• Configurable memory cost, time cost, and parallelism
• Winner of the Password Hashing Competition (2015)

scrypt:

• Memory-hard algorithm requiring large memory allocations
• Resistant to hardware acceleration attacks
• Higher memory requirements than PBKDF2

bcrypt:

• Adaptive algorithm with configurable cost factor
• Built-in salt generation
• Widely used in authentication systems

Step 4: Output Key Extraction

The output extraction phase produces the final stretched key:

1. Length Adjustment: If the KDF output length differs from requirements, extract or expand to the needed length
2. Format Conversion: Convert the raw bytes to the required format (raw bytes, hex, base64, etc.)
3. Key Material Separation: If multiple keys are needed, use the stretched key as input to a key derivation function to generate separate keys

Step 5: Secure Storage and Usage

The final phase involves secure handling of the stretched key:

Storage Considerations:

• Never store the stretched key in plaintext
• Store only the salt and KDF parameters needed to reproduce the key
• Use the stretched key immediately for its intended purpose (encryption, authentication)
• Clear the stretched key from memory after use

Usage Patterns:

• Use the stretched key to encrypt/decrypt keystore contents
• Derive additional keys from the stretched key using HKDF or similar
• Use the stretched key for authentication token generation

Technical Requirements

Implementing secure key stretching requires careful attention to cryptographic requirements, performance considerations, and error handling.

Cryptographic Requirements

Algorithm Selection:

The choice of key derivation function significantly impacts security:

PBKDF2 Requirements:

• Use HMAC-SHA256 or HMAC-SHA512 as the PRF
• Minimum iteration count: 100,000 (NIST SP 800-132 recommendation as of 2010)
• Modern recommendations: 600,000+ iterations for HMAC-SHA256
• Adjust iteration count based on acceptable authentication delay (100-500ms)

Argon2 Requirements (preferred for new implementations):

• Use Argon2id variant (hybrid of Argon2i and Argon2d)
• Minimum memory: 64 MB (OWASP recommendation)
• Minimum iterations: 3
• Parallelism: 4 threads
• Output length: Match encryption key requirements (256 bits for AES-256)

Salt Requirements:

• Uniqueness: Each password must use a unique salt
• Randomness: Generate salts using cryptographically secure random number generators (CSPRNG)
• Length: Minimum 128 bits (16 bytes), preferably 256 bits (32 bytes)
• Storage: Store salt in plaintext alongside encrypted data or in keystore metadata

Output Key Requirements:

• Length: Match the requirements of the target encryption algorithm
  • AES-128: 128 bits (16 bytes)
  • AES-256: 256 bits (32 bytes)
  • ChaCha20: 256 bits (32 bytes)
• Entropy: The stretched key should have full entropy across its length
• Uniqueness: Different passwords or salts must produce different keys

Timing Considerations

Performance Tuning:

Key stretching introduces intentional computational delay that must be balanced against usability:

Target Delay:

• Authentication systems: 100-500ms acceptable delay
• Keystore unlocking: 500ms-2s acceptable for infrequent operations
• Batch operations: May require lower iteration counts with compensating controls

Iteration Count Calibration:

# Pseudocode for calibrating iteration count
def calibrate_iterations(target_delay_ms, algorithm):
    iterations = 10000
    while True:
        start = time()
        test_stretch(algorithm, iterations)
        elapsed = time() - start
        
        if elapsed >= target_delay_ms:
            return iterations
        
        # Increase iterations proportionally
        iterations = int(iterations * (target_delay_ms / elapsed))

Hardware Considerations:

• Calibrate iteration counts on the target hardware platform
• Mobile devices may require lower iteration counts than servers
• Consider using memory-hard algorithms (Argon2, scrypt) to resist GPU acceleration

Adaptive Parameters:

• Store the iteration count with the salt
• Allow increasing iteration counts over time as hardware improves
• Implement migration strategies to re-stretch keys with stronger parameters

Error Handling

Input Validation Errors:

class KeyStretchingError(Exception):
    """Base exception for key stretching errors"""
    pass

class InvalidPasswordError(KeyStretchingError):
    """Password does not meet requirements"""
    pass

class InvalidSaltError(KeyStretchingError):
    """Salt is invalid or missing"""
    pass

def validate_inputs(password, salt, iterations):
    if not password or len(password) < MIN_PASSWORD_LENGTH:
        raise InvalidPasswordError("Password too short")
    
    if not salt or len(salt) < MIN_SALT_LENGTH:
        raise InvalidSaltError("Salt too short or missing")
    
    if iterations < MIN_ITERATIONS:
        raise KeyStretchingError(f"Iteration count too low: {iterations}")

Cryptographic Errors:

• Handle algorithm unavailability gracefully
• Validate KDF output length matches expectations
• Detect and report memory allocation failures for memory-hard algorithms

Timing Attack Mitigation:

• Use constant-time comparison for password verification
• Avoid early termination on validation failures
• Ensure consistent timing regardless of password correctness

Usage Patterns

Key stretching appears in several common patterns within cryptographic systems, particularly in KERI implementations.

Pattern 1: Keystore Encryption

The most common usage pattern in KERI is keystore protection, where key stretching derives the encryption key for the keystore database:

Initialization Flow:

1. User provides passcode during keystore creation
2. Generate random salt (256 bits)
3. Apply key stretching: encryption_key = stretch(passcode, salt, iterations)
4. Use encryption_key to encrypt keystore contents
5. Store salt and iteration count in keystore metadata
6. Clear passcode and encryption_key from memory

Unlock Flow:

1. User provides passcode to unlock keystore
2. Retrieve salt and iteration count from keystore metadata
3. Apply key stretching: encryption_key = stretch(passcode, salt, iterations)
4. Attempt to decrypt keystore contents
5. If decryption succeeds, keystore is unlocked
6. If decryption fails, passcode is incorrect
7. Clear passcode and encryption_key from memory

Pattern 2: Seed Derivation

Key stretching can strengthen user-provided entropy for seed generation:

Seed Generation:

def generate_seed_from_passphrase(passphrase, salt=None):
    # Generate salt if not provided
    if salt is None:
        salt = os.urandom(32)  # 256 bits
    
    # Stretch the passphrase
    stretched = argon2.hash(
        passphrase.encode('utf-8'),
        salt=salt,
        time_cost=3,
        memory_cost=65536,  # 64 MB
        parallelism=4,
        hash_len=32,  # 256 bits
        type=argon2.Type.ID
    )
    
    # Use stretched key as seed
    seed = stretched
    
    return seed, salt

Pattern 3: Multi-Factor Key Derivation

Combining key stretching with multiple factors for enhanced security:

Two-Factor Key Derivation:

def derive_key_two_factor(password, device_secret, salt):
    # Stretch password
    password_key = pbkdf2_hmac(
        'sha256',
        password.encode('utf-8'),
        salt,
        iterations=600000,
        dklen=32
    )
    
    # Combine with device secret
    combined = password_key + device_secret
    
    # Final derivation
    final_key = pbkdf2_hmac(
        'sha256',
        combined,
        salt,
        iterations=1,  # Already stretched
        dklen=32
    )
    
    return final_key

Pattern 4: Hierarchical Key Derivation

Using stretched keys as master keys for hierarchical deterministic key derivation:

Master Key Derivation:

def derive_master_key(passphrase, salt):
    # Stretch passphrase to master key
    master_key = argon2.hash(
        passphrase.encode('utf-8'),
        salt=salt,
        time_cost=3,
        memory_cost=65536,
        parallelism=4,
        hash_len=64,  # 512 bits for HKDF
        type=argon2.Type.ID
    )
    
    return master_key

def derive_child_key(master_key, context, index):
    # Use HKDF to derive child keys
    info = f"{context}:{index}".encode('utf-8')
    child_key = hkdf.derive(
        master_key,
        length=32,
        info=info,
        salt=b''
    )
    
    return child_key

Best Practices

Security Best Practices:

1. Use Modern Algorithms: Prefer Argon2id over PBKDF2 for new implementations
2. Sufficient Iteration Counts: Use at least 600,000 iterations for PBKDF2-HMAC-SHA256
3. Unique Salts: Generate a new random salt for each password
4. Secure Storage: Store salts and parameters securely but separately from encrypted data
5. Memory Clearing: Zero out sensitive material (passwords, keys) after use
6. Constant-Time Comparison: Use constant-time comparison for password verification

Performance Best Practices:

1. Calibrate Parameters: Tune iteration counts for target hardware
2. Cache Stretched Keys: For session-based systems, cache the stretched key during the session
3. Progressive Enhancement: Increase iteration counts over time as hardware improves
4. Async Operations: Perform key stretching asynchronously to avoid blocking UI

Integration Considerations:

1. Version Parameters: Store algorithm version and parameters with each stretched key
2. Migration Support: Implement mechanisms to re-stretch keys with updated parameters
3. Fallback Handling: Support multiple algorithm versions during transitions
4. Monitoring: Log key stretching performance metrics to detect anomalies

KERI-Specific Considerations

Within the KERI ecosystem, key stretching plays a critical role in protecting the root-of-trust established by autonomic identifiers.

Keystore Protection

KERI implementations like KERIpy and cesride use key stretching to protect encrypted keystores containing:

• Private signing keys: Used to sign key events
• Private rotation keys: Pre-rotated keys for future rotations
• Seeds: Cryptographic seeds for hierarchical key derivation
• Salts: Random values used in key generation

The keystore encryption key is derived from a user-provided passcode using key stretching, ensuring that even if the encrypted keystore file is compromised, the attacker must perform expensive key stretching operations for each password guess.

Seed Generation

When generating seeds from user-provided passphrases (rather than purely random generation), key stretching ensures the resulting seed has sufficient cryptographic strength for secure key derivation. This is particularly important for:

• Backup and recovery: Users may prefer memorable passphrases over random seeds
• Multi-device synchronization: Shared passphrases enable key synchronization across devices
• Hierarchical key management: Strong seeds enable secure hierarchical key derivation

Security Trade-offs

Key stretching in KERI contexts involves balancing several factors:

Security vs. Usability:

• Higher iteration counts provide better security but slower keystore unlocking
• Mobile devices may require lower iteration counts than servers
• Frequent keystore access may necessitate session-based caching

Entropy vs. Memorability:

• Purely random seeds provide maximum entropy but are difficult to memorize
• Passphrase-derived seeds are memorable but require key stretching for security
• BIP-39 seed phrases provide a middle ground with structured randomness

Performance vs. Security:

• Key stretching adds computational overhead to keystore operations
• Custodial agents may require optimized key stretching for scale
• Hardware security modules can accelerate key stretching

By properly implementing key stretching, KERI systems can accommodate human-friendly authentication mechanisms while maintaining the cryptographic strength required for secure autonomic identifier management.

Async Operations: Perform key stretching asynchronously in web applications to avoid blocking the UI thread.

Versioning and Migration

Store Parameters: Always store the algorithm identifier, version, and parameters (iterations, memory, parallelism) alongside the salt. This enables:

• Algorithm upgrades without breaking existing keys
• Gradual migration to stronger parameters
• Support for multiple algorithm versions during transitions

Migration Strategy: Implement opportunistic re-stretching: when a user successfully authenticates with old parameters, re-stretch their password with updated parameters and update the stored values.

Error Handling

Validation: Validate all inputs before stretching:

• Password length meets minimum requirements
• Salt is present and of correct length
• Iteration count meets minimum threshold

Timing Attacks: Ensure consistent timing regardless of password correctness. Don't return early on validation failures.

Resource Limits: Handle memory allocation failures gracefully, especially for memory-hard algorithms like Argon2 and scrypt.

KERI-Specific Considerations

Keystore Protection: In KERI implementations, key stretching protects the keystore containing private keys, pre-rotated keys, and seeds. The stretched key serves as the encryption key for the keystore database.

Seed Derivation: When deriving seeds from user passphrases, apply key stretching before using the seed for hierarchical key derivation.

Multi-Device Synchronization: For synchronized keystores across devices, ensure consistent key stretching parameters and salt values. Store parameters in keystore metadata that syncs with the encrypted data.

Hardware Security Modules: When using HSMs, leverage hardware-accelerated key stretching if available, but ensure the HSM supports the chosen algorithm and parameters.

Testing

Unit Tests: Test key stretching with known test vectors to ensure correct implementation.

Performance Tests: Measure key stretching performance on target hardware to validate parameter choices.

Security Tests: Verify that different passwords produce different stretched keys, and that the same password with different salts produces different keys.

Compatibility Tests: Ensure stretched keys can be reproduced across different platforms and library versions.