SHA256 HMAC brute force with chosen plaintext attacks

Question

This is a follow up to Is It Possible To Reconstruct a Cryptographic Hash's Key

I am using a SHA-256 HMAC function on a single-word input: sha256hmac(privatekey,word) = output. The private key length is 128 bits, it does not change. The "word" is literally one short word.

Assuming an attacker knows "word" and "output" for multiple words (e.g., dog = "dsfwrw3r3r323211", cat = "3erwerwetwewer"):

• Is it significantly easier for an attacker to identify the private key by brute force with the above word/output pairs, as compared to a situation where they do not have those pairs?
• Is this brute force vulnerability (with word/output pair knowledge) an actual security concern?

Answer 1

I'll assume that "sha256hmac" designates HMAC using SHA-256 as the underlying hash function.

HMAC is used for its intended usage: the first parameter privatekey is a key, I assume random and secret, of fair length (128-bit); the second parameter word is a (possibly public) message; output is a (possibly public) cryptogram. Observing any number of (word, output) pairs, even for word of an adversary's choice, will not enable to recover privatekey or otherwise compute new result.

Its hard to tell if having (word, output) pairs makes the task significantly easier: it goes from impossible with no pair at all, to infeasible using any foreseeable technology with some pairs (unless we consider quantum computers practically applicable to cryptography as foreseeable, which requires some dose of optimism).

With one privatekey of 128-bit, I think we are good against brute force for two decades, with fair confidence. If there was billions privatekey and the adversary could obtain output for the same word for each of these privatekey, we would NOT be quite that safe with the 128-bit key size (the adversary has a remotely feasible task of finding one privatekey), and we would need more bits: 192 are fine, 256 aplenty.

The most practical danger is privatekey leaking, by organizational means, or side-channel attack.

---

The modern security argument for HMAC is Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance (full version), originally in proceedings of Crypto 2006.