On Security of Key Derivation Functions in Password-based Cryptography

Most common user authentication methods use some form of password or a combination of passwords. However, encryption schemes are generally not directly compatible with user passwords and thus, Password-Based Key Derivation Functions (PBKDFs) are used to convert user passwords into cryptographic keys. In this paper, we analyze the theoretical security of PBKDF2 and present two vulnerabilities, γ-collision and δ-collision. Using AES-128 as our exemplar, we show that due to γ-collision, text encrypted with one user password can be decrypted with γ 1 different passwords. We also provide a proof that finding− a collision in the derived key for AES-128 requires δ lesser calls to PBKDF2 than the known Birthday attack. Due to this, it is possible to break password-based AES-128 in O(264) calls, which is equivalent to brute-forcing DES.