Generate the AES & HMAC keys take too much time

Question

I am using this method in an Android app to generate the AES & HMAC keys.

private static final int PBE_ITERATION_COUNT = 10000;
private static final int AES_KEY_LENGTH_BITS = 128;
private static final int HMAC_KEY_LENGTH_BITS = 256;
private static final String PBE_ALGORITHM = "PBKDF2WithHmacSHA1";
private static final int AES_KEY_LENGTH_BYTES = AES_KEY_LENGTH_BITS >> 3;
private static final int HMAC_KEY_LENGTH_BYTES = HMAC_KEY_LENGTH_BITS >> 3;

public static AesHmacKeyPair generateKeyFromPassword(String password, byte[] salt) throws GeneralSecurityException {
    PrngFixes.fixPrng();
    //Get enough random bytes for both the AES key and the HMAC key:
    KeySpec keySpec = new PBEKeySpec(password.toCharArray(), salt,
            PBE_ITERATION_COUNT, AES_KEY_LENGTH_BITS + HMAC_KEY_LENGTH_BITS);
    SecretKeyFactory keyFactory = SecretKeyFactory
            .getInstance(PBE_ALGORITHM);
    byte[] keyBytes = keyFactory.generateSecret(keySpec).getEncoded();
    // Split the random bytes into two parts:
    byte[] confidentialityKeyBytes = copyOfRange(keyBytes, 0, AES_KEY_LENGTH_BYTES);
    byte[] integrityKeyBytes = copyOfRange(keyBytes, AES_KEY_LENGTH_BYTES, AES_KEY_LENGTH_BYTES + HMAC_KEY_LENGTH_BYTES);
    //Generate the AES key
    SecretKey confidentialityKey = new SecretKeySpec(confidentialityKeyBytes, CIPHER);

    //Generate the HMAC key
    SecretKey integrityKey = new SecretKeySpec(integrityKeyBytes, HMAC_ALGORITHM);
    return new AesHmacKeyPair(confidentialityKey, integrityKey);
}

The issue now that I am facing is, this method takes too much time. It approximately takes two seconds on my device. And as my profile, it's caused by this line of code:

byte[] keyBytes = keyFactory.generateSecret(keySpec).getEncoded();

I don't have much experience with cipher/ encryption/ decryption. Please help to give me some advice, how would I speed up this method? Or are there any equivalence approach that I should follow instead of this method.

Your support will be very appreciated

Thanks.

Answer 1

TL;DR: use a better password and bring back the iterations and use a KBKDF2 to derive the AES and HMAC keys.

---

PBKDF2 is an algorithm that explicitly contains a work factor, in this case an iteration count. It has been designed to securely derive a key from a password. The idea is that even strong passwords are generally not secure enough and that an attacker has to perform the required work to derive the key.

Unfortunately you'd have to perform the same work, possibly on a much slower device such as a smart phone. 10K is about the minimum of iterations that you'd perform nowadays. However, if you have an alphabet of 70 characters then you could just extend your password with 2-3 fully random characters to achieve the same thing. You'd still need to use PBKDF2 and a salt, but you can use a much lower iteration count.

---

PBKDF2 has a design to deliver any number of bits as output. It however has a design flaw where additional bits require that the entire work has to be performed all over again. As Math.ceil((128.0 + 256.0) / 160.0) = 3 you're basically performing the PBKDF2 function three times. The attacker can however validate the first (AES) key by just performing it once. So you have 3 times less the performance than the attacker, with no gain.

Rather than using PBKDF2 in this kind of way you should request 160 bits from it, and then append a label to it. E.g. a counter in 4 bytes: 00000001 (hex). Then you can use SHA-256 or 512 to generate a key from it. For the next key you'd use 00000002 as a label (etc.). Or you can get fancy and use one of the KBKDF's (Key Based Key Derivation Functions) in Bouncy Castle.

The KBKDF with the counter I specified above is called KDF2 (or KDF1, they just differ wrt the counter value, which doesn't matter wrt security). HKDF is much more complex and has a better security argument behind it.

---

Here is an example that uses HMAC and a textual label instead of the hash and counter specified above:

private static final int PBE_ITERATION_COUNT = 10000;
private static final int AES_KEY_LENGTH_BITS = 128;
private static final int HMAC_KEY_LENGTH_BITS = 256;
private static final String PBE_ALGORITHM = "PBKDF2WithHmacSHA1";
private static final int AES_KEY_LENGTH_BYTES = AES_KEY_LENGTH_BITS >> 3;
private static final int HMAC_KEY_LENGTH_BYTES = HMAC_KEY_LENGTH_BITS >> 3;
private static final String CIPHER = "AES";
private static final String HMAC_ALGORITHM = "HMACSHA256";
private static final int MASTER_KEY_LENGTH_BITS = 160; // max for PBKDF2 configured with SHA-1

public static AesHmacKeyPair generateKeyFromPassword(String password, byte[] salt) throws GeneralSecurityException {
    // PrngFixes.fixPrng(); <-- needs to be put back
    //Get enough random bytes for just the master key:
    KeySpec keySpec = new PBEKeySpec(password.toCharArray(), salt,
            PBE_ITERATION_COUNT, MASTER_KEY_LENGTH_BITS);
    SecretKeyFactory keyFactory = SecretKeyFactory
            .getInstance(PBE_ALGORITHM);
    byte[] masterKeyBytes = keyFactory.generateSecret(keySpec).getEncoded();

    //Generate the AES key
    byte[] confidentialityKeyBytes = kdf(masterKeyBytes, "ENC", AES_KEY_LENGTH_BYTES);
    SecretKey confidentialityKey = new SecretKeySpec(confidentialityKeyBytes, CIPHER);

    //Generate the HMAC key
    byte[] integrityKeyBytes = kdf(masterKeyBytes, "MAC", HMAC_KEY_LENGTH_BYTES);
    SecretKey integrityKey = new SecretKeySpec(integrityKeyBytes, HMAC_ALGORITHM);

    return new AesHmacKeyPair(confidentialityKey, integrityKey);
}

private static byte[] kdf(byte[] inputKeyMaterial, String label, int outputKeyBytes) {
    try {
        Mac mac = Mac.getInstance("HMACSHA256");
        mac.init(new SecretKeySpec(inputKeyMaterial, "HMACSHA256"));
        mac.update(label.getBytes(StandardCharsets.US_ASCII));
        byte[] confidentialityKeyBytes = mac.doFinal();
        return Arrays.copyOf(confidentialityKeyBytes, outputKeyBytes);
    } catch (NoSuchAlgorithmException | InvalidKeyException e) {
        throw new RuntimeException("HMAC operation doesn't work", e);
    }
}