3
$\begingroup$

Note: This is not the same as Multiple iterations of AES for key derivation?.

Almost everyone has AES-NI nowadays - when building a cryptographic application, is is possible to leverage this to create a kdf that is about as slow for the attacker to attempt a single key on a single CPU as it is for the user to derive one key?

Also, is it possible to feed the last block of AES-CBC as the key of the next round of encryption over the rest of the ciphertext to make it memory-hard, and avoid encrypt-one-block-at-a-time-many-times attacks, as the entire ciphertext needs to be in memory?

Essentially, key derivation would work something like this, just a lot more times:

$\endgroup$
  • $\begingroup$ so you are going to start with encrypting n blocks of 128 bits in CBC mode, and then using last block ciphertext as key to encrypt n-1 of ciphertext. what is your rough estimate that n should be? Because this will dictate how much it resist against bruteforce like other KDF. $\endgroup$ – khan Oct 11 '17 at 17:53
  • $\begingroup$ About 16K-32K iterations interactively $\endgroup$ – id01 Oct 11 '17 at 18:01
  • $\begingroup$ Just implemented it... 32K is painfully slow. I'd say 16K iterations. $\endgroup$ – id01 Oct 11 '17 at 18:16
  • $\begingroup$ for 32K iterations, what is the length of initial stream of 0's? and how much time is it taking? $\endgroup$ – khan Oct 11 '17 at 18:19
  • $\begingroup$ Length would be half a megabyte. It doesn't end, at least on my very slow but AES-NI enabled laptop... 16K iterations takes about 7 seconds, 8K iterations takes about 2 seconds. According to my calculations, 16K iterations should lead to about 2GB total of encryption. $\endgroup$ – id01 Oct 11 '17 at 18:29
4
$\begingroup$

Here's an answer that takes your question down a different path. RFC 2898, "PKCS #5: Password-Based Cryptography Specification: Version 2.0" is the document that defines the PBKDF2 function, in section 5.2. Although PBDKF2 is normally instantiated with HMAC, the spec says that any pseudorandom function (PRF) may be used, with the implicit proviso that the PRF must accept variable-length keys (since the password is used as the key).

RFC 4615, "The Advanced Encryption Standard-Cipher-based Message Authentication Code-Pseudo-Random Function-128 (AES-CMAC-PRF-128) Algorithm for the Internet Key Exchange Protocol (IKE)" defines such a variable-length key PRF on top of AES-CMAC (RFC 4493):

The AES-CMAC-PRF-128 algorithm is identical to AES-CMAC defined in [RFC4493] except that the 128-bit key length restriction is removed.

CMAC itself is a CBC-like mode that was designed to fix the shortcomings of the CBC MAC (which is only secure for fixed-length message spaces).

So by plugging in those reasonably standard components together you get an AES-based password-based KDF that is a bit different from your diagram but you might find close enough for your purposes.

$\endgroup$
  • $\begingroup$ It seems like unless you do successive iterations of the MAC it is relatively fast. However, if you do successive iterations of the MAC, it is not very memory-heavy. Are you sure the AES CMAC is bruteforce-resistant? $\endgroup$ – id01 Oct 11 '17 at 21:32
  • 2
    $\begingroup$ The iterations come from the PBKDF2 construction itself, which takes an iteration count as an argument. It's certainly not memory-heavy. It's simply not obviously worse than PBKDF2-HMAC-SHA-1 or similar, that's about all I'd claim. $\endgroup$ – Luis Casillas Oct 11 '17 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.