HKDF: how to get new keys and what hash functions have to do with it

For modern encryption algorithms, one of the factors affecting cryptographic strength is the key length. According to the NIST standard , the cryptographic strength of algorithms must be at least 112 bits. For symmetric algorithms, this means that the minimum key length must be 224 bits, for asymmetric ones based on number theory (for example, solving the factorization problem for the RSA algorithm ), the minimum reliable length is 2048 bits [1]. Cryptography on elliptic curves does not save from using large keys.

But what if the existing keys are not long enough to be safely used in our chosen algorithms? Or do we need more keys than we have? This is where KDF (Key Derivation Function) comes to the rescue - this is a function that generates one or more cryptographically strong secret keys based on a given secret value (in the literature referred to as the master key, and sometimes the master key) using a pseudo-random function. And what is especially important, it allows you to set the length of the key generated as a result of your work, and its strength will be the same as that of a random key of the same length [2], [3].

KDF . , - HKDF, , Python'.

1. KDF

:

, KDF , "--" (- - extract-and-expand):

1. "" . - "" , . ;

   
   
   
   
   

2. , , "" . .

   
   
   
   
   

.

Randomness Extraction:

- - :

:

• SKM (Source Keying Material) - ( ) , PRK, - . , "" KDF;

  
  
  
  
  

• XTR (randomness eXTRactor) - . , SKM PRK. , ( );

  
  
  
  
  

• PRK (PseudoRandom Key) - . ;

  
  
  
  
  

• XTSalt (eXTractor Salt) - , .. ( ) , , . .

  
  
  
  
  

, . - KDF . , HKDF, , -.

Key Expansion:

(PRK) L, . :

:

• PRF* (PseudoRandom Function with variable length) - , . , counter feedback mode;

  
  
  
  
  

• CTXInfo (context information) - ( , , , ). , , , ;

  
  
  
  
  

• PRK - ;

  
  
  
  
  

• DKM (Derived Keying Material) - L.

  
  
  
  
  

, . ? ?

, . , KDF "" , . , "" , .

, - (-) , , . , premaster secret TLS , (IETF). , , , , PRF* ( PRF* ).

2. HKDF

HKDF (HMAC Key Derivation Function) KDF. KDF ( PRF*), , HMAC.

HKDF

HMAC , - , - , . HashLen ( ), . || ("") . HMAC(key, a || b) , - key a b.

, HKDF :

XTS, SKM CTXInfo , KDF, K(i), i = 1,...,t :

1. PRK = HMAC-Hash(XTS, SKM) - , (SKM) (PRK). PRK , HMAC (HMAC-Hash) HashLen . , - , "" - . , SKM , PRK .

   
   
   
   
   

2. K(1) = HMAC-Hash(PRK, CTXinfo || 0),
   
   K(i+1) = HMAC-Hash(PRK, K(i) || CTXinfo || i), 1 ≤ i < t,

   
   
   
   
   

t = L/HashLen - "", L. i . , HashLen, L K. L: L ≤ 255 * HashLen.

KDF, - ; , HashLen. , , -, XTSalt PRK.

. . , "" , . , , , .. , HKDF , . SKM.

3. HKDF

HKDF : Java, JavaScript, PHP, Python. , , , , :

import hashlib
import hmac
from math import ceil

hash_len = 32

def hmac_sha256(key, data):
    return hmac.new(key, data, hashlib.sha256).digest()

def hkdf(length: int, ikm, salt: bytes = b"", CTXinfo: bytes = b"") -> bytes:
    #  -  , ,    ,
    #     hash_len:
    if len(salt) == 0:
        salt = bytes([0] * hash_len)
    
    #  :      
    #   -:
    prk = hmac_sha256(salt, ikm)
    
    k_i = b"0"  #     -  0
    dkm = b""   # Derived Keying Material
    t = ceil(length / hash_len)
    
    #  :   -  K(i),  
    #     . ,     
    #   K(i)    K(i-1):
    for i in range(t):
        k_i = hmac_sha256(prk, k_i + CTXinfo + bytes([1 + i]))
        dkm += k_i
    
    #     hash_len,    length :
    return dkm[:length]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

:

>>> output = hkdf(100, b"input_key", b"add_some_salt")
>>>
>>> print(''.join('{:02x}'.format(byte) for byte in output))
2bcd8350cc31b6945b23b2a47add4d5ec4b1bd9fad0387590bf4e9f4d34ea456e63267c765e7cd5451df1f6f18f41eaba20de594fd8c6a008120276438d18fc4122ec152fff03204c966261b60408a569b6b0e3527ae4a34570c62b2d060fd15f3176a36
>>>
>>> print(len(out))
100
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, hkdf



output "input_key" "add_some_salt". , , , . .  100 , , !

:

• IETF: https://tools.ietf.org/html/rfc5869

  
  
  
  
  

• : https://eprint.iacr.org/2010/264

  
  
  
  
  

• - KDF: https://www.coursera.org/lecture/crypto/key-derivation-A1ETP

  
  
  
  
  

• [1] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf, 9.

  
  
  
  
  

• [2] https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-108.pdf, 16-19;

  
  
  
  
  

• [3] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf, 108-109;

  
  
  
  
  

• [4] General guidelines for using KDF: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf , pp. 17, 22