5
$\begingroup$

Given many very short (or low-entropy) values – like 6-digit numbers – that are stored as hashes using a fixed secret pepper, e.g.:

value  | pepper               | hash = SHA265(value + pepper)
-------+----------------------+-----------------------------------------------------------------
100001 | e03c920babf6325ac56d | 75e3283fe3dbc8e1f86ac5ea7ac5325896a6036d5d2d73f355dca41b9dab4a42
100002 | e03c920babf6325ac56d | 20b50e24dc8a984905de5850e67167928f937f171a2e6cb9998c0a8131a11dda
100003 | e03c920babf6325ac56d | f555173d08ebd020b45a655cee159c2684ad98cd4901dc85ec047b565d3a4a05

... and assuming that an attacker knows that the values are 6-digit numbers and that the hashes were computed that way.

Could the attacker retrieve the values (or even the pepper) from the hashes? Do the short values make the hash more vulnerable / less secure?

$\endgroup$
  • $\begingroup$ Could an attacker cause a value provided by them to be hashed (e.g. by entering it through your system)? If they can, and they could access the database, they could do a brute-force attack (by getting the value of the hash for each possible input value). SHA256 is fast, and a rainbow table of all possible values would be small (under 32 MiB). Security could be improved by using a salt, or a slow algorithm (key derivation function or password hashing function). $\endgroup$ – John B. Lambe Apr 8 '18 at 21:05
  • $\begingroup$ @JohnB.Lambe no, it's not possible for an attacker to invoke a hash creation. $\endgroup$ – Stefan Apr 8 '18 at 22:51
7
$\begingroup$

The assumption seems to be that the adversary wants to confirm a guess of $\mathtt{value}$ given $\mathtt{hash}=\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, for unknown random secret $\mathtt{pepper}$. This is an ad-hoc PRF of $\mathtt{value}$ with symmetric key $\mathtt{pepper}$.

No, the small size/entropy in $\mathtt{value}$ is not an issue. Neither is having a million of millions of $\mathtt{value}$ (or/and of leaked $\mathtt{hash}$ ). Without a successful and complete guess of $\mathtt{pepper}$, as far as we know, the adversary can't learn anything about $\mathtt{value}$ from its $\mathtt{hash}$ (beyond two $\mathtt{value}$ being identical with practical certainty when their $\mathtt{hash}$ is, something that additional random public salt would fix, see Maarten Bodewes's answer). Main theoretical weakness is the relatively small size of $\mathtt{pepper}$ (here 80-bit), which should be 128-bit or more by modern standards. Of course, there's the issue of keeping $\mathtt{pepper}$ secret, and other implementation issues (but the classic timing side channel of memcmp does not matter).

The best known generic attack is essentially brute force. For each guess of $\mathtt{value}$, it enumerates $\mathtt{pepper}$, computes $\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, and compares to the given $\mathtt{hash}$ (or the full list of theses). If there are several guesses of $\mathtt{value}$ with different likelihood, it pays to try the guesses from most to least likely. If $\mathtt{value}$ was long (so that $\mathtt{value}\mathbin\|\mathtt{pepper}$ exceeds the 64-byte block size of the SHA-256 internals), it would pay to cache the intermediate values that do not vary with each $\mathtt{pepper}$.

Note: we'd have better academic security assurance if we used HMAC-SHA-256 rather than this ad-hoc PRF. See M. Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, in Journal or Cryptology, 2015, originally in proceedings of Crypto 2006.

$\endgroup$
  • $\begingroup$ The given pepper was just an example, the actual one could be much longer. So a large number of such hashes is not an issue, either? Maybe even a complete list off all 1 million possible hashes? $\endgroup$ – Stefan Apr 8 '18 at 11:19
  • 2
    $\begingroup$ @Stefan: For sufficiently long values and peppers, I believe attacks like the key-splitting attack of Preneel & Oorschot 1995 might become faster than brute force (but still infeasible in practice, since applying them to your scheme would involved finding an SHA-256 collision as one step of the attack). That said, as long as the combined length of your value + pepper is at most 512 bits (= one SHA-256 input block), you should be safe even from this theoretical attack. Or you could just use HMAC. $\endgroup$ – Ilmari Karonen Apr 8 '18 at 12:06
  • $\begingroup$ @IlmariKaronen: I wonder starting with what size of $\mathtt{pepper}$ "The best known generic attack is essentially brute force" starts to fail. I'd say that's much above 128-bit (but have no proof, and that's where HMAC shines). $\endgroup$ – fgrieu Apr 8 '18 at 12:13
  • 3
    $\begingroup$ More like PRF than MAC; the nomenclature of HMAC seems like a historical accident of its first use. MAC per se guarantees nothing about obscuring the input in the output. $\endgroup$ – Squeamish Ossifrage Apr 8 '18 at 15:55
3
$\begingroup$

Your example seems to use a unique number. If value is not unique then duplicates will show up in the hash field. In that case an attacker could possibly request you to hash a specific value and check if there is a duplicate somewhere.

This is why you generally should use a hash or - even better, password hash - that stores a unique or large random salt in addition of having access to a pepper.

$\endgroup$
  • 2
    $\begingroup$ So remember Salt'n'Peppa :P $\endgroup$ – Maarten Bodewes Apr 8 '18 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.