# Replacing the PRF in PBKDF2 with Keccak

I am unable to find a reliable, tested library for a decent password based key derivation function e.g. Scrypt in the programming language I am using, but I have a reliable library for PBKDF2 (which by default uses SHA2-256) and it also allows me to replace the hash function to use Keccak-256 (C=512) instead.

Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2? For example, maybe Keccak is not designed for this usage?

Would it be considered a better PRF than SHA2?

I understand it's not a memory hard function, so not as effective as Scrypt in slowing down a serious attacker, however I can compensate for that by restricting password length to at least 30 characters and 100,000 or so iterations.

-
If there's no reason in particular to avoid using SHA-2, just use SHA-2. SHA-3 is currently intended as a ready alternative in the event that the SHA-2 family of ciphers is broken, but that is not yet the case. – Stephen Touset Mar 21 '15 at 2:56
Well there is a reason to avoid it, it is designed by the NSA. – 504811E Mar 21 '15 at 3:53
ASICs for Bitcoin can't do PBKDF2; they are highly specialized to the exact Bitcoin operations (i.e. SHA256(SHA256(stuff)), and checking the number of zeroes). NSA design is not a particular weakness of SHA-2; it's an open algorithm that has been subject to extensive cryptanalysis, far more than SHA-3 has seen, which would tend to undermine the notion that there's a backdoor. More relevantly, what construction does it use for Keccak? Does it use the standard HMAC construction with Keccak? Is that different from HMAC with SHA-3? – cpast Mar 21 '15 at 4:52
Keccak is substantially faster in hardware than SHA-256, you would make the function MORE vulnerable to brute force attack – Richie Frame Mar 21 '15 at 5:24
And, to reiterate your earlier point, Keccak is slower on general purpose CPUs right now than it is in hardware. A critical component of a slow KDF is to minimize any disadvantage the defender has when compared to an attacker, and Keccak currently is weaker than SHA-2 in that regard. Furthermore, while no professional cryptographer I know of has serious reservations about SHA-2 due to NSA involvement, the point is moot. PBKDF2 is built on HMAC, whose strongest security proof requires only that the underlying function is a PRF. – Stephen Touset Mar 21 '15 at 15:20

Is there anything wrong with swapping SHA2 for Keccak for use in PBKDF2?

There are 2 main issues. Performance and implementation.

Performance

The performance issue is from an attacker-defender scenario, where the attacker is able to provide FPGA or ASIC resources. In this scenario, Keccak is several times faster than SHA-2. I will use a Blake comparison for SHA-256, as they perform similarly. Both Blake and SHA-2 are ARX type hash functions.

STM 90nm ASIC
Keccak-256 = 33333 Mbit/s @ 51 Kgates, Blake-256 = 4763 Mbit/s @ 37K gates, a 7X performance advantage with a 37% area disadvantage, 5.1X overall advantage

UMC 90nm ASIC
Keccak-256 = 43011 Mbit/s @ 50 Kgates, Blake-256 = 6966 Mbit/s @ 47.5K gates, a 6.17X performance advantage with a 5% area disadvantage, 5.86X overall advantage

Xilinx Virtex 5 FPGA
Keccak-256 = 12817 Mbit/s @ 1272 slices, Blake-256 = 2245 Mbit/s @ 1523 slices, a 5.7X performance advantage with a 20% area advantage, 6.83X overall advantage

It can be seen an attacker with hardware resources has a performance advantage of 6 times on average vs Blake. In software, Keccak can average half the speed of SHA-512 at the same security level, and can be faster vs SHA-256. This is dependent on the message size, as the block sizes are not the same.

Newer processors will also contain additional instructions to improve the performance of SHA-256 hashing, the level of improvement is yet to be determined.

Implementation

The main implementation issue is centered around the design and purpose of HMAC.

HMAC is designed specifically for MD type hash functions like SHA and MD5. Its purpose is to change the initial values to something other than those in the specification. MD type hashes work like a block cipher, with the message the key, and the initial values the plaintext. The ciphertext is then the hash digest. With longer messages, the cipher works in OFB mode, with a key change. The final ciphertext block is then the hash. HMAC works by cycling $[key \oplus ipad]$ for 1 iteration to get a new secret IV, then it processes the message. The output is then processed as the new message using $[key \oplus opad]$ to generate a different secret IV.

Keccak is not an MD type hash function, so the entire purpose of HMAC is lost. Keccak works using the sponge construction with a large internal state. The general rule is to simply prefix the message with the secret key in order to create a keyed hash construction. It is suggested that this would actually be stronger than HMAC because of the large internal state that is kept secret, vs HMAC where an attacker can see the entire state unless there is truncation.

Using Keccak in an HMAC construction is of course possible, but will be much slower than key prefixing, and may not have a security advantage.

The other implementation issue is with code size. On 32-bit systems, SHA-256 will have a massive advantage over Keccak, since blitsliced Keccak is larger and more complex. On 64-bit systems, SHA-512 is a better fit, and Keccak in native 64-bit code is quite compact. The fact that the round constants can be derived at runtime is an advantage, but is usually only used when small code is required, such as an RFID card.

NSA

I hesitated putting this section here, but since the comments on the question are a hot topic, I figured it would be pertinent.

Just because the NSA designed something, does not mean it is bad, or secretly backdoored. The NSA is not some super boogeyman, the employees are human beings, and their computers need to obey the laws of thermodynamics. They can not easily sneak something by the cryptographic community. Almost everyone suspected Dual_EC_DRBG was tainted, and advised against its use, even before it became a standard. The only reason it got used was either bribery or incompetence.

I know nobody who suspects the same about SHA-2. Additionally, SHA is one of the most widely studied hash families, with decades of analysis by cryptographers all over the world, including the Russians, Chinese, Iranians, etc. It has stood the test of time better than MD5 and RIPEMD. The only exploitable issues are those common to all MD type hash functions, and if used in HMAC they are mostly irrelevant. SHA-2 is used by the US government to protect state secrets from its enemies, confidently.

If you want to use PBKDF and still don't trust the cryptographic community's view on SHA-2 and all the public analysis for whatever reason, use Blake-512 instead. It has far inferior attacker advantage numbers, excellent software performance, and well analyzed security. I am a fan of truncating the output, I would only keep 256 to 320-bits.

I am postulating that SHA3 may preserve the entropy in the salt and password better than SHA2

Not enough to compensate for the performance advantage of an attacker, if that is even the case..

-