Last Update: Dec 16, 2015
          -----[ Exploiting some weaknesses of PBKDF2 ]-----
----[ 0x00 ] Intro
----[ 0x01 ] PBKDF
----[ 0x02 ] SHA1
----[ 0x03 ] HMAC
----[ 0x04 ] RSA Labs' PBKDF2
----[ 0x05 ] Weaknesses
---------[+] Precomputing a message block
---------[+] Zero based
---------[+] Same value based
---------[+] Precomputing a word expansion
----[ 0x06 ] Conclusions
----[ 0x07 ] References



----[ 0x00 ] Intro

This article is based on a project we started in 2014 @ CLUB (Cryptography and 
Coding Laboratory) @ UNIMI. It has been presented in CANS 2015 [12] and 
published in [13].


+++ The paper can be found here +++


----[ 0x01 ] PBKDF

For several known reasons, in password-based cryptography a humanly manageable
password can't be directly used as a key for a given cryptographic system;
a Password-Based Key Derivation Function (PBKDF), is then used to generate a
proper cryptographic key of the desired length, starting from a user password.
PBKDFs are also used, instead of a simple hash function, for password hashing,
although they weren't originally designed for this purpose.

Generally speaking, a Key Derivation Function, KDF, is a function that take a
source of initial keying material, and derive from it one or more pseudorandom
keys. Key material can be any bit sequence from a source of more or less entropy
[1]. When the initial key material is from a source of low entropy,
specifically a user typed password, these KDFs are known as PBKDFs,
password-based KDFs.

PBKDFs should be relatively expensive to compute, in order to increase the 
computational effort of an exhaustive search attack. In cryptography this is
known as key stretching, a phrase that is now widely used the same as
key strengthening [2].
A typical approach consists in using a salt to prevent building universal
dictionaries, and an iteration count that specifies how many times the
underlying function should be iterated in order to slow down the computation of
the derived key.



----[ 0x2 ] SHA-1

We will not completely explain SHA-1 here, for those who are not familiar with
this hash function please refer to [9]. However to make a recap, in a
pre-processing phase SHA1 appends one bit set to 1 to the original message then
pad it with some bit set to 0, until the resulting message length is congruent
to 448 (mod 512), then appends L, the length of the original message,
represented in a 64-bit big-endian integer.
Therefore the message length is multiple of 512 bits.

The message is broken up into message blocks of 512 bits and then SHA1 processes
each message block as follow:

+ Divides it in sixteen 32bit words
+ Expands this 16 words to a total of 80 through bitwise operation like
  circular shift and exclusive-or
+ Compresses down this 80 words into 5 words applying some other functions
+ These 5 words are known as intermediate hash values

Now the next message block is processed, and each of its intermediate hash value
is added to each one calculated in the previous message block, and so on.
When the last message block is consumed, a concatenation of these 5 words is
returned, consisting in a 160 bit hash value.



----[ 0x3 ] HMAC

HMAC (Hash-based Message Authentication Code) is a specific algo for
calculating a message authentication code (MAC) involving a cryptographic hash
function and a secret key. As any MAC, it provides a way to verify both the
integrity and the authentication of a message.
HMAC can be used with any iterative cryptographic hash function, in combination
with a secret shared key. The cryptographic strength of HMAC depends on the
properties of the underlying hash function [5].
In 2006 M. Bellare proves that HMAC is a PRF under the sole assumption that the
underlying compression function is a PRF [11].
A Pseudo Random Function (PRF), is a function which emulates a random oracle:
no efficient algorithm can distinguish between a PRF and a random oracle output.
Typically, MACs are used between two parties that share a secret key in order to
validate information transmitted between these parties, but in PBKDF2 HMAC is
used as a PRF.

HMAC can be defined as follow:

	HMAC = H(K xor opad, H(K xor ipad, text))

where:
	
	H	is the hash function
	B	is the byte-length of H's internal block. 
	K	is the shared key
	ipad	is the byte 0x36 repeated B times
	opad	is the byte 0x5C repeated B times.
	text	is the message to be authenticated
	
Read the definition of HMAC as follow:

	h = H(K xor ipad || text)
	HMAC = H(K xor opad || h)

If K is shorter than B it's padded with 0s to fit the block size, before xoring
it with either ipad or opad.



----[ 0x04 ] RSA Labs' PBKDF2

RSA Laboratories, in PKCS5, defines widely referenced recommendations for the 
implementation of password-based cryptography [3].
They recommend one algorithm to derive keys: PBKDF2. It is commonly adopted in
many security related applications, for instance authentication on mobile
devices, key derivation for full disk encryption and password hashing.
[cite del paper di LUKS?]

PBKDF2 takes a user passphrase p, a random salt s, an iteration counter c,
and dkLen, the derived key length, and return the derived key DK.

	DK = PBKDF2(p,s,c,dkLen)

Unlike the earlier standard, PBKDF2 can derives keys of arbitrary length,
it generates as many block Ti as needed to cover dkLen, the desired key length.

Each Ti is generated iterating the underlying PRF as many times as specified by
an iteration counter c.
The length of the Ti is bounded by hLen, the length of the PRF output.


The DK is the concatenation of i blocks where i = ceiling(dkLen/hLen).

	DK = T1 || T2 || ... || Ti

where:

	T1 = F(p,s,c,1)
	T2 = F(p,s,c,2)
	.
	.
	.
	Ti = F(p,s,c,i)

Each Ti is computed as:

	Ti = U1 xor U2 xor ... xor Uc

where:

	U1 = PRF(p,S||i)
	U2 = PRF(p,U1)
	.
	.
	.
	Uc = PRF(p,Uc-1)


The numbers of iterations will be a burning question, choosing a reasonable 
value depends on environment and varies from an application to another, it 
should be selected as large as possible, as long the time required to generate 
the key is acceptable for the user.
For very critical keys on very powerful system an iteration count of 10.000.000 
may be appropriate, while a minimum of 1000 iterations is recommended for 
general purpose [4].

Unlike the password, the salt and the iteration count do not need to be kept
secret.

We focus on PBKDF2 with HMAC [5], we show that is possible to avoid most of the
CPU intensive operations which are the core of the PBKDF2 derivation process,
by substituting them with a set of equivalent less onerous instructions, this
way the algorithm strength is significantly reduced.
This entail a consequent decrease of the time one needs to spend performing any
such exhaustive key search attack on password derived keys.
Note that the time needed to try all password derived keys is significantly less
then the time needed to try all possible keys.

The same method can be used with HMAC with many hash functions such as SHA-2
and MD5 but for simplicity we focus on HMAC-SHA1, that is the default for
PBKDF2.

This way it is possible to derive a key in HALF TIME with respect to the
vanilla method.

Moreover we present some other minor optimizations that reduce even more the
derivation time. As a consequence an exhaustive key search attack against a key
derived with PBKDF2 is significantly less expensive, and this is an additional
reason to look for new password based key derivation schemes [6].



----[ 0x5 ] Weaknesses

As we previously said PBKDF2 aims to slow down brute force attacks through CPU
intensive operations in the key derivation process.

In this section we present different improvements in the computation of the
PBKDF2 algorithm. Some of these concern the precomputation of some values,
that can be reused instead of recalculating them during the derivation process.
These precomputations are independent from the cryptographic hash function used
in HMAC, because they are applied directly to the HMAC definition;
other optimizations aim to reduce the number of instructions avoiding useless
operation exactly in the HMAC's hash function, these are clearly dependent from
the specific hash function adopted. 
We will show how it is possible to reduce the strength of PBKDF2 by more than
50% against exhaustive key search attacks.

The improvements we present are not related to any specific implementation of
PBKDF2.

For the following improvements as an example we will use as Salt length the
one define in the LUKS format [7][8].



----[ Precomputing a message block

Deeply analyzing PBKDF2, HMAC, and their interaction, we noticed that it is
possible to halve the time one need to spend on deriving a key from a password,
by simply calculating once and only once the intermediate hash values of the
first message block for the two SHA1 calls in the first HMAC invocation.

These precomputed intermediate hash values will be the same for all the SHA-1
calls in all HMAC invocations of the derivation process.

The main problem is that PBKDF2 calls HMAC always with the same password P,
which pads this password always with the same two values to create a string
as long as the message block length that its underlying hash function works
with. This allows us to precompute the first message block of the two SHA1
calls, and then reuse them in all the subsequent HMAC invocations.

Since we can avoid to process one of the two message block in every SHA-1
call, this optimization reduce by 50% the operations involved in the
derivation process.

As previously said because this improvement exploits a weakness in the way
PBKDF2 uses HMAC, it can be reused with several hash functions such as SHA-2
family [9], MD5, and many others.

Note that only in the case of the most first HMAC call the advantage gained
applying this idea depends on the salt length (defined by the application).
In fact if the salt length exceeds the hash function message block length,
it will be unavoidable to compute more than two message blocks.
In all the other calls the SHA1 of the previous message block is used as salt,
and we will never have to compute more than two message blocks.
Hence this particular most first case will not affect the global gain.





----[ Zero based optimization

Given that every SHA1 call, except the first one in U1, are performed on a
string formatted according to the scheme in the figure below, we can observe
that every time there are 287 zeros in the last 512 bits of the string,
these 512 bits are the second message block processed in every SHA1 call.
There are more than 287 zeros to be precise, because the string end with the
binary representation of L, the length in bit of the message to be hashed,
that in our case, according to HMAC scheme [5], is always 672, this
value is represented on 64 bit, leaving room for more 22 consecutive zeros.

SHA1, in the main word expansion phase, expands its 512-bits message block
iterating t from 16 to 79 using the following function:

	W[t] = ROTL((W[t-3] xor W[t-8] xor W[t-14] xor W[t-16]), 1)

The result is that for a few steps, the word expansion function is working
with some W[t] filled with zeros. We can simply not execute a few XOR operations
because XORing a value with zero result in the same value. This optimize a
little the procedure as suggested by Atom [10].
In the standard word expansion are carried out 192 XOR, knowing this
optimization can be implemented an ad-hoc word expansion that use 165 XOR,
saving 27.
It should be remembered that this word expansion is executed in each SHA1 call,
there are two SHA1 call for each HMAC, and many HMAC call as the number of the
iteration chosen by the application.
This means that there will be probably many SHA1 calls. :)





----[ Same value based optimization

It is possible to avoid some other useless operations in the word expansion of
the first message block too. As we can see from the figure below, the first
message block of each SHA1 call has the same padding values in every invocations,
so, like in the previous zero-based optimization, we can avoid some useless
operations. We should know that XORing a value to itself result in zero.
Supposing that an attacker can organize its password list in same length classes,
for each class the SHA1 word expansion will work with the same number of W[t]'s
filled with the HMAC padding value, 0x36 or 0x5C, hence, depending on the
password length we can avoid more or less XORs, like in the previous 0 based.
The organization in same length classes is essential for the sake of write a
reasonable hypothetical ad-hoc word expansion, that, based on password length,
avoids a few XOR sum.

Note that if used in combination with our precomputed-message-block
optimization, the gain obtained due to this trick is far too low because we
process the first message block only once for each derivation, independently
from the iteration count.

In the standard word expansion are carried out 192 XOR, knowing this
optimization can be implemented an ad-hoc word expansion that use 162 XOR,
saving 30.





----[ Precomputing a word expansion

This is a little improvement strongly related to HMAC-SHA1.
In PBKDF2 the derived key is obtained extracting the first dkLen bytes from the
concatenation of the computed T[i]:

	DK = T1 || T2 || ... || Ti

where:	

	i = ceiling(dkLen/hLen)

Hence to derive a key we have first to compute a certain number of T[i] and then
extract the key from their concatenation. In the computation of each T[i],
more specifically in the first HMAC call of each T[i], are calculated two SHA1
hashes, as specified by the HMAC algorithm; deeply analyzing the first SHA1
invocation we noticed that, as highlighted in the following figure, the second
message block does not depend on the password at all.
Hence, given a salt, the word expansion of this message block produce the same
values independently from the password. This means that an attacker can avoid
to compute this word expansion in each try of its password list, reusing the
same precomputed values.






----[ 0x06 ] Conclusions

Implementation note in RFC2104 [5] describes our "Precomputing message block"
as a performance improvement for message authentication, but in PBKDF2
HMAC should help to slow down the derivation process instead.

We found that in 2015 this weakness affects two of the main crypto libraries: 
Libgcrypt v1.6.3 and ARM mbed TLS v1.3.11.

It's important that every crypto library implements this improvement, to 
better understand how this could affect real world applications we will post 
another interesting article about the LUKS format and Cryptsetup asap.


To be continued ...



----[ 0x07 ] References

[1]  Hugo Krawczyk, Cryptographic Extraction and Key Derivation: The HKDF Scheme 
[2]  Strengthening passwords, Abadi, Martin and Lomas, T.Mark A and Needham,
     Roger
[3]  RSA Laboratories, PKCS #5 V2.1: Password Based Cryptography Standard 
[4]  NIST, SP800-132: Recommendation for password-based key derivation 
[5]  RFC 2104: HMAC: Keyed-hashing for message authentication 
[6]  Password Hashing Competition 
[7]  C. Fruhwirth, New methods in Hard Disk Encryption 
[8]  C. Fruhwirth, LUKS On-Disk Format Specification Version 1.2.1
[9]  NIST, FIPS PUB 180-4: Secure Hash Standard
[10] Jens Steube, Optimizing computation of Hash-Algorithms as an attacker
[11] Bellare, New roofs for NMAC and HMAC: Security without Collision-Resistance
[12] The 14th International Conference on Cryptology and Network Security
[13] Cryptology and Network Security - 14th International Conference, CANS 2015,
     Marrakesh, Morocco, December 10-12, 2015, Proceedings