PBKDF2 is a well-known password-based key derivation function. In order to slow attackers down, PBKDF2 introduces CPU-intensive operations based on an iterated pseudorandom function (in our case HMAC-SHA-1). If we are able to speed up a SHA-1 or an HMAC implementation, we are able to speed up PBKDF2-HMAC-SHA-1. This means that a performance improvement might be exploited by regular users and attackers. Interestingly, FIPS 198-1 suggests that it is possible to precompute first message block of a keyed hash function only once, store such a value and use it each time is needed. Therefore the computation of first message block does not contribute to slowing attackers down, thus making the computation of second message block crucial. In this paper we focus on the latter, investigating the possibility to avoid part of the HMAC-SHA-1 operations. We show that some CPU-intensive operations may be replaced with a set of equivalent, but less onerous, instructions. We identify useless XOR operations exploiting and extending Intel optimizations, and applying the Boyar-Peralta heuristic. In addition, we provide an alternative method to compute the SHA-1 message scheduling function and explain why attackers might exploit these findings to speed up a brute force attack against PBKDF2.

Exploiting an HMAC-SHA-1 optimization to speed up PBKDF2 / A. Visconti, F. Gorla. - In: IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING. - ISSN 1545-5971. - (2018). [Epub ahead of print]

Exploiting an HMAC-SHA-1 optimization to speed up PBKDF2

A. Visconti
Primo
;
2018

Abstract

PBKDF2 is a well-known password-based key derivation function. In order to slow attackers down, PBKDF2 introduces CPU-intensive operations based on an iterated pseudorandom function (in our case HMAC-SHA-1). If we are able to speed up a SHA-1 or an HMAC implementation, we are able to speed up PBKDF2-HMAC-SHA-1. This means that a performance improvement might be exploited by regular users and attackers. Interestingly, FIPS 198-1 suggests that it is possible to precompute first message block of a keyed hash function only once, store such a value and use it each time is needed. Therefore the computation of first message block does not contribute to slowing attackers down, thus making the computation of second message block crucial. In this paper we focus on the latter, investigating the possibility to avoid part of the HMAC-SHA-1 operations. We show that some CPU-intensive operations may be replaced with a set of equivalent, but less onerous, instructions. We identify useless XOR operations exploiting and extending Intel optimizations, and applying the Boyar-Peralta heuristic. In addition, we provide an alternative method to compute the SHA-1 message scheduling function and explain why attackers might exploit these findings to speed up a brute force attack against PBKDF2.
Boyar-Peralta heuristic; Cryptography; Force; HMAC-SHA-1; Intel optimizations; Message authentication; Optimization; Password; Password-Based Key Derivation Function 2; PKCS #5
Settore INF/01 - Informatica
2018
Article (author)
File in questo prodotto:
File Dimensione Formato  
11_IACR_SHA1_Rev1.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 1.45 MB
Formato Adobe PDF
1.45 MB Adobe PDF Visualizza/Apri
08514806.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.42 MB
Formato Adobe PDF
1.42 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/609749
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 11
social impact