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?

  • 4
    $\begingroup$ Your construction offers no advantage over computing HMAC(key, id) on a trusted device, relying on its rate limiting features and on key being unextractable. $\endgroup$ – CodesInChaos May 21 '15 at 9:57
  • $\begingroup$ @CodesInChaos Right. The only advantage of using RSA here is that it is probably 1) already available and 2) already slow (for private key operations, which is what I presume we are talking about). Eh, wouldn't be an advantage to check the validity of H with a public key as well? $\endgroup$ – Maarten Bodewes May 21 '15 at 11:44
  • 1
    $\begingroup$ I presume that with SHA512SUM you are simply referring to SHA-512 (sha512sum is not an algorithm, it's a GNU command line utility) and that with RSA you are referring to RSA / PKCS#1 v1.5 signature generation? Have you taken a look at PBKDFs? $\endgroup$ – Maarten Bodewes May 21 '15 at 11:49
  • $\begingroup$ Here's how facebook does it : twitter.com/filosottile/status/552830697942319105 Note - they use a salt, which you really should consider as well. $\endgroup$ – user2552 May 22 '15 at 14:38

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.

  • $\begingroup$ Not the answer I expected, but... Well, reality is reality. I would like to see an answer on whether the function I've came up actually have the property that H is not computable from ID. So if I solve the brute-force case (perhaps with more serious rate limiting), then it is okay. $\endgroup$ – Árpád Magosányi May 21 '15 at 18:52
  • $\begingroup$ The best you can do in this case is something like an HMAC with a secret key. If an attacker doesn't have the key (or an oracle), they won't be able to enumerate the hashes. $\endgroup$ – Stephen Touset May 21 '15 at 21:36
  • $\begingroup$ The attacker is able to use the service, so keeping the key secret does not help against the enumeration, it is important for stretching and rate limiting.. The outside attacker is rate limited by the program (e.g. 20 tries from one IP in a day). The inside attacker is rate limited by the token (one RSA sign is 0.3s), and its use by the algorithm (e.g. I can include more rounds of signature in the algorithm). $\endgroup$ – Árpád Magosányi May 22 '15 at 7:04

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.