RFC 2898 (PKCS #5 v2.0) and PBKDF2: Determinism, Entropy, and Cryptanalytic Bounds of Password Cryptography

Research paper. Subject of study: RFC 2898, PKCS #5: Password-Based Cryptography Specification, Version 2.0 , B. Kaliski, RSA Laboratories, September 2000.

RFC 2898 formalizes a family of password cryptography mechanisms: the PBKDF1 and PBKDF2 key derivation functions, the PBES1/PBES2 password encryption schemes, the PBMAC1 authentication scheme, and the ASN.1 representation of their parameters. The central contribution of PBKDF2 is not to “strengthen” a weak password to a random key, but to increase the computational cost of a single password candidate check during offline brute-force attacks.

The key cryptanalytic fact is that PBKDF2 is a deterministic mapping from the input (P,S,c,dkLen,PRF) to the keying material. Therefore, repeated hashing or applying a PRF does not create new secret entropy: given fixed public parameters, the uncertainty of the result is bounded by the uncertainty of the password. Salt eliminates massive precomputability and ties the search to a specific entry, and the parameter c linearly increases the cost of verification; neither of these mechanisms alone transforms a small dictionary password into a cryptographically strong secret.

Keywords: PBKDF2, RFC 2898, PKCS #5, KDF, entropy, salt, offline search, dictionary attack, HMAC, PBES2, PKCS #8, cryptanalysis.

1. Subject and context

RFC 2898, published as an IETF informational document, reproduces PKCS #5 v2.0; it describes the processing of passwords for key derivation, encryption, and integrity checking. The document is specifically focused on protecting sensitive data and private keys in the context of PKCS #8.

A password isn’t a ready-made symmetric key: it’s textual, has an ambiguous encoding, and typically has significantly less entropy than a random AES key. This is where the KDF problem arises: to obtain a byte string of the required length while simultaneously making mass verification of password hypotheses more expensive.

A historical example. In early UNIX systems, salt was used in password hashes to destroy the universality of precomputed tables: the same password would yield different check values for different users. RFC 2898 applies the same principle to key derivation: the salt is not secret, but it forces the attacker to work with each salt separately.

2. Notation and threat model

Designation	Meaning	Cryptanalytic role
`P`	Password as an octet string	The only supposed secret; its distribution determines practical durability.
`S`	Salt	A public unique parameter that breaks precomputations and inter-record matches.
`c`	Number of iterations	Multiplier for the cost of one password check; does not add entropy.
`PRF`	Pseudo-random function	RFC 2898 defaults to HMAC-SHA-1; modern implementations typically fix the more modern PRF profile/format.
`dkLen`	Length of the derived key	Determines the output size, but not the independent secrecy beyond the password.
`DK`	Derived key	Input to a cipher or MAC; a deterministic function of the parameters.

The most dangerous and typical model is an offline attack . Having received a container with salt, KDF parameters, and a cryptographic object being verified (e.g., an encrypted PKCS #8 key), the attacker enumerates candidates p, calculates PBKDF2(p,...) , and verifies the result against a known structure, MAC, or successful decryption.

3. Salt and iterations

3.1. Purpose of salt

RFC 2898 recommends a random salt of at least eight octets (64 bits) and specifies that when multiple keying material assignments are used, the salt should distinguish between operations and key lengths. Modern engineering practice recommends selecting a salt from a cryptographically strong random number generator and ensuring its uniqueness per record; longer values do not eliminate password weakness, but they virtually eliminate the possibility of accidental salt collisions.

\[ DK = KDF(P,S) \]

The salt shouldn’t be hidden: it’s typically stored next to the KDF result. Its effect isn’t to increase the number of passwords, but to increase the space of parameterized computations an attacker would have to precompute for the same dictionary.

A cryptanalytic example: If a million records use the same unsalted password hash, a single candidate table attacks all records simultaneously. With independent salts, the same dictionary must be run for each record. However, a user with a password qwerty is still vulnerable: an attacker can simply compute PBKDF2 for the password qwerty with their specific salt.

3.2 Iteration parameter

RFC 2898 considered a minimum of 1000 iterations reasonable for the year 2000. This is a historical recommendation, not a modern safety profile: hardware performance and parallel accelerators have changed dramatically, so parameters should be calibrated on target hardware and regularly reviewed.

\[ \operatorname{Cost}_{\mathrm{guess}} \approx c \cdot \operatorname{Cost}_{\mathrm{PRF}} \]

Iterations provide a work factor : the legitimate user and the attacker pay the same amount of work for a single hypothesis. Protection is useful only because the server or container owner performs this action rarely, while the attacker does it billions of times.

Archive example. Apple’s iOS backup format used PBKDF2 to protect backups; forensic and password auditing tools rely on this autonomous verification of candidates against a known container structure. The presence of PBKDF2 slows down this verification, but doesn’t negate it if the password was chosen from a predictable space.

4. PBKDF1: compatibility, not target selection

PBKDF1 defines a chain of iterations of a hash function over P || S. RFC 2898 limits it to MD2, MD5, or SHA-1, and the result length to the digest length: 16 octets for MD2/MD5 and 20 octets for SHA-1; this function is retained for compatibility with legacy systems and is not recommended for new projects.

\[ T_1=Hash(P\parallel S),\qquad T_j=Hash(T_{j-1}),\qquad DK=T_c[0..dkLen-1] \]

The limited output length and historical primitives make PBKDF1 an unsuitable basis for a new design. It’s important to distinguish MD5 or SHA-1 collisions from a brute-force password scenario: in KDF, the main practical risk is often not collisions, but low entropy P and the high speed of candidate verification.

A practical example from an audit. When analyzing old PKCS #12/PBE containers, parameters compatible with the DES, RC2, MD5, and SHA-1 era are encountered. Even without cryptanalytic “hash cracking,” small key sizes and weak user passwords create a more realistic attack trajectory—offline dictionary attack.

5. PBKDF2: design

PBKDF2 allows output of arbitrary, practically useful lengths through PRF result blocks. RFC 2898 specifies a maximum length of dkLen <= (2^32 - 1) * hLen, where hLen is the length of the PRF result, and defines the block index as a four-octet representation INT(i) in most significant byte first order.

\[ l=\left\lceil \frac{dkLen}{hLen}\right\rceil,\qquad r=dkLen-(l-1)hLen \] \[ U_1=PRF(P,S\parallel INT(i)),\qquad U_j=PRF(P,U_{j-1})\quad (2\le j\le c) \] \[ F(P,S,c,i)=U_1\oplus U_2\oplus\cdots\oplus U_c \] \[ DK=T_1\parallel T_2\parallel\cdots\parallel T_{l-1}\parallel T_l[0..r-1],\qquad T_i=F(P,S,c,i) \]

The recurrent chain U_j reduces intra-block parallelism, and the XOR of all iterates serves as a conservative design measure against chain degeneracy. Furthermore, blocks with different indices i can be calculated independently, and PBKDF2 is not a memory-hard KDF: specialized hardware can efficiently parallelize multiple password hypotheses.

from hashlib import pbkdf2_hmac
from secrets import token_bytes

password = b"correct horse battery staple"  # пример, не хранить так в коде
salt = token_bytes(16)                       # соль хранится вместе с параметрами
iterations = 600_000                          # пример: калибровать на целевой системе
key = pbkdf2_hmac("sha256", password, salt, iterations, dklen=32)

# Для хранения нужны как минимум: алгоритм PRF, salt, iterations, dkLen и результат/контейнер.
record = {
    "kdf": "PBKDF2-HMAC-SHA256",
    "salt_hex": salt.hex(),
    "iterations": iterations,
    "dklen": 32,
}

Application example. PBKDF2-HMAC-SHA256 with a 16-byte salt can be used to generate a 32-byte encryption key, but the number of iterations cannot be safely copied from an article or other project: it is selected by measuring the acceptable latency on the server/client and the parameter update policy.

6. Entropy: What PBKDF2 Doesn’t Do

Consider fixed public parameters S, c, dkLen and PRF. Then the derived key is a deterministic function of only the password random variable: DK = f(P). By data processing inequality, a deterministic transformation is unable to increase the source entropy.

\[ DK=f(P;S,c,dkLen,PRF) \] \[ H(DK\mid S,c,dkLen,PRF)\le H(P\mid S,c,dkLen,PRF) \] \[ H_\infty(DK\mid S,c,dkLen,PRF)\le H_\infty(P) \]

Here H is the Shannon entropy, and H_\infty is the min-entropy, which is critical for assessing the probability of the most probable guess. The output DK may appear statistically uniform to an observer without knowledge of the password, but its computational feasibility for an attacker is determined by the probability distribution of passwords, not the output length.

\[ H_\infty(P)=-\log_2\left(\max_p \Pr[P=p]\right) \]

If a user chooses one of 10,000 predictable passwords, the upper bound on the uniform entropy of that choice is approximately 13.3 bits, regardless of whether PBKDF2 outputs 128, 256, or 512 bits. A 256-bit result doesn’t mean 256 bits of security: it’s simply the same length as a byte string.

A significant difference. The salt can be random and have high entropy, but it is usually known to the attacker. Therefore, its randomness is useful against precomputation and record correlation, but it is not the secret entropy of the key in the autonomous attack model.

7. Cryptanalytic fact

Claim. For fixed PBKDF2 parameters, the number of meaningful candidates in an exhaustive search is determined by the password space, not the space of derived keys. If an attacker has a verifiable cryptographic artifact, they construct the same deterministic result for each candidate.

\[ \text{For each }p\in\mathcal{D}:\quad DK_p=PBKDF2(p,S,c,dkLen),\quad \operatorname{Verify}(DK_p,\mathcal{A})\in\{0,1\} \]

Here \mathcal{D} , is a dictionary or probabilistically ordered candidate space, and \mathcal{A} is a known artifact: a MAC, a file header, a valid ASN.1 encoding, a known piece of plaintext, or an encrypted private key. PBKDF2 doesn’t prevent verification; it just makes it more expensive.

\[ W \approx N\cdot c\cdot C_{PRF} \]

The value N is the number of candidates tested before success or exhaustion, and C_PRF is the cost of one PRF call. Increasing the c cost scales the effort roughly linearly for both the defender and the attacker; fundamental weaknesses N can only be improved by increasing the unpredictability of the password or changing the authentication model.

Illustration. Let’s assume a six-digit PIN, meaning there are no more than 1,000,000 possible combinations. PBKDF2 with a larger value c will increase the time for a brute-force attack but will not change the number of possible secrets. A random passphrase generated from a sufficiently large independent space changes the size and shape of the distribution \mathcal{D}; KDF cannot create this property.

8. PBES1 and PBES2

Scheme	RFC 2898 design	Evaluation for modern systems
PBES1	PBKDF1 + DES or RC2 in CBC; the key and IV are extracted from the 16 octets of DK.	Legacy compatibility. DES, RC2, MD2/MD5/SHA-1, and small key sizes are not reasonable choices for a new design.
PBES2	PBKDF2 + the chosen encryption scheme; the KDF and encryption parameters are passed via AlgorithmIdentifier.	A flexible framework suitable for compatible containers with a modern choice of KDF, cipher, and authenticated encryption.

PBES1 uses CBC and historical block ciphers; the RFC explicitly recommends PBES2 for new applications. CBC encryption alone, without separate, strong authentication, lacks integrity, and flawed differences in decryption and padding processing have historically led to oracle attacks in other protocols and implementations.

\[ DK=KDF(P,S,c,dkLen),\qquad C=Enc_{DK}(M;\text{parameters}) \]

Archived context. In 2013, the Lucky Thirteen attack demonstrated the practical significance of subtle differences in the processing time of CBC padding in TLS. This is not an attack on PBKDF2 as a KDF, but it is an important reminder: the strength of a password container is determined by the KDF, cipher, authentication, format, and the absence of side channels.

9. PBMAC1 and key sharing

PBMAC1 constructs a MAC from a derived key: first, the KDF is obtained DK, then the chosen MAC scheme computes or verifies the tag T. The RFC appendix gives HMAC-SHA-1 as an example; identifiers and parameters must be unambiguously serialized in ASN.1.

\[ DK=KDF(P,S,c,dkLen),\qquad T=MAC_{DK}(M) \]

The RFC warns of the danger of interoperability if the same derived material or its prefix is used in different roles. A practical principle is domain separation: independent salts with destination labels or separate KDF calls for the encryption key and authentication key.

# Концептуальный пример domain separation:
K_enc = PBKDF2(password, b"app:v1:enc:" + random_salt, c, 32)
K_mac = PBKDF2(password, b"app:v1:mac:" + random_salt, c, 32)

# В новом протоколе предпочтительнее AEAD и чётко определённый формат,
# а не самодельная схема «CBC + отдельный MAC».

A cryptanalytic example from the RFC. The document considers a scenario in which an attacker reuses a salt and achieves a discovery for a shorter key; if this key is a prefix of a longer derived key, this could compromise the security of the original operation. For this reason, the salt may include a designation of the key’s purpose and length.

10. ASN.1, OID, and Reproducibility

Appendix A of RFC 2898 defines the ASN.1 structures , id-PBKDF2 = {pkcs-5 12}, id-PBES2 = {pkcs-5 13} and related AlgorithmIdentifier. For PBKDF2, the salt, iteration count, optional key length, and PRF are serialized; the original PRF value in the document is HMAC-SHA-1.

PBKDF2-params ::= SEQUENCE {
  salt CHOICE {
    specified   OCTET STRING,
    otherSource AlgorithmIdentifier
  },
  iterationCount INTEGER (1..MAX),
  keyLength      INTEGER (1..MAX) OPTIONAL,
  prf            AlgorithmIdentifier DEFAULT hmacWithSHA1
}

Format is part of cryptographic security. An error in interpreting the password encoding, default PRF, key length, IV, or iteration count can lead to either inability to decrypt or a decrease in security due to an implicit downgrade. Therefore, the container must explicitly store the version and all parameters, and the software implementation must validate the boundaries and supported algorithms.

A real-life example. PEM/PKCS #8 files often serve as portable containers for private keys between OpenSSL, web servers, HSM tools, and CI systems. During an audit, it’s important to read the ASN.1 parameters as they appear, rather than assuming that “PEM with a password” automatically means a modern KDF, a sufficient number of iterations, and authenticated encryption.

11. RFC 2898’s Limits Today

PBKDF2 remains widely supported and useful where compatibility is more important than maximum resistance to accelerated brute-force attacks. However, its computational burden is primarily CPU-based, and memory is rarely a scarce resource; therefore, GPUs, FPGAs, and ASICs can check multiple independent passwords in parallel more efficiently than a typical server CPU.

For new password storage systems, memory-hard functions are preferred, primarily Argon2id, with memory, time, and parallelism parameters selected experimentally. To protect data, the KDF task should be separated from the encryption task: use a random, high-entropy data key and AEAD mode, and use the password KDF to wrap this key or to obtain the key in a strictly defined, versioned format.

Don’ts: Don’t reuse the same password without a unique salt; don’t set a fixed “forever” number of iterations; don’t consider 256-bit output as proof of 256-bit password strength; don’t use PBES1 for new data; don’t mix password encodings without a UTF-8 specification/normalization; don’t construct a homemade encryption/MAC composition without a clear cryptographic scheme.

12. Practical profile

Task	Recommended engineering measure	Audit check
Storing passwords	Argon2id when possible; PBKDF2 only when reasonably compatible.	Unique salt, version, parameters, acceptable delay, migration policy.
PBKDF2 compatible	Explicitly record the modern PRF, the salt from the CSPRNG, and the calibrated work factor.	No HMAC-SHA-1 “by default” due to carelessness; parameters are saved with the record.
Encryption of private data	A PBES2-like container with a modern AEAD or secure wrapper around a random data key.	Check integrity, nonce/IV, absence of oracle differences, format versioning.
Several key roles	Independent KDF call or domain separation.	The ENC/MAC/KEK keys are not prefixes of a single unlabeled output.

Numerical parameters cannot be declared universal: they must be measured on the minimum supported device and set according to the acceptable latency. The system must be able to recognize old parameters upon user login and repackage or recalculate the record with the new parameters after successful authentication.

Final Provision

PBKDF2 is a well-defined mechanism for slowing down brute-force attacks and obtaining keys of a given length, and RFC 2898 established an important model for separating KDF, encryption, MAC, and format parameters. However, its output cannot be interpreted as a missing-secrecy generator: given known parameters, it remains a deterministic function of the password.

Therefore, the cryptanalytic strength of a password scheme is determined jointly by the password distribution, the cost of testing a single hypothesis, the uniqueness of the salt, the quality of serialization, and the properties of the surrounding encryption/authentication scheme. Iterations increase the cost of attack; salt eliminates scalable precomputation; only an unpredictable secret increases the initial entropy bound.

Sources

RFC 2898 and PBKDF2: determinism, entropy and cryptanalytic limits: https://quchat.ru/rfc-2898-and-pbkdf2-determinism-entropy-and-cryptanalytic-limits/

B. Kaliski. PKCS #5: Password-Based Cryptography Specification, Version 2.0 . RFC 2898, IETF, September 2000. https://datatracker.ietf.org/doc/html/rfc2898
Y. Sheffer, R. Holz, P. Saint-Andre. Recommendations for Secure Use of Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS) . RFC 9325, 2022.
A. Biryukov, D. Dinu, D. Khovratovich. Argon2: the memory-hard function for password hashing and other applications . RFC 9106, 2021.
NIST. SP 800-132: Recommendation for Password-Based Key Derivation , 2010.
Lucky Thirteen: NJ AlFardan, KG Paterson. Lucky Thirteen: Breaking the TLS and DTLS Record Protocols , IEEE S&P, 2013.