one-way deterministic hash for low entropy input?

Question

My problem is the following: we have a low entropy data called ID. (personal id number of 10 decimal digits plus a sum, and it contains a date) We want to create a data (H) which is the same for the same id, but id can neither be computed nor brute-forced by trying all combinations. It should be proven that even we are not able to reconstruct ID from H using neither computation nor brute force

My solution: use k:= an RSA1024 key residing in a slow hardware token, unextractable the reason is to improve entropy

H:=SHA512SUM(RSA(k,SHA512SUM(ID))) We limit third parties to 1 operation per minute.

Please comment on whether this solution is sound enough, or are there better solution for the problem. What measures can we use to express the soundness of the solution?

Answer 1

I don't think this problem is solvable as specified.

With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext.

If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} \approx 2^{33}$ iterations, and it might be feasible to use key stretching and/or rate-limited hardware to slow down the hashing enough to make such a search unfeasible.

Unfortunately, you say that some of the digits encode a date. If these ID numbers are anything like the local government IDs around here, I'm assuming something like 6 digits encoding a birthdate (in DDMMYY format, or similar) plus a four-digit sequence number. This reduces the necessary search space significantly:

• Just the date format reduces the search space a lot: since there are only 356 valid dates in a year (or 366 for leap years), the actual number of valid IDs is only about $10^{8.4} \approx 2^{28}$.

• If an attacker is targeting a specific person, they'll likely know the target's age to at least within a decade or so. This cuts the search space further down by a factor of (at least) 10.

• In the worst case, the attacker already knows the target's age and birth date, and only needs to determine the last four digits of the ID. Thus, they only need to search $10^4 \approx 2^{13}$ ID numbers!

• To make things even worse, the last four digits might not be random either. If they're instead assigned sequentially, lower numbers will be much more common, and so a sequential exhaustive search is likely to find the correct ID much sooner than one would expect if they were randomized.

Basically, in the worst-case scenario described above (which, really, isn't that far-fetched at all), no amount of key stretching will help: if your organization wants to be able to legitimately process more than one ID per minute, then a determined attacker with access to the same resources (which is a reasonable assumption, if internal attacks are a concern) and knowledge of the date part of the ID will be able to de-hash the ID in less than one week (= 10,080 minutes). If you need to be able to process one ID per second, the attacker only needs up to three hours. That holds regardless of the hashing or encryption method you're using, or the tools you use to implement it.