The GDPR blog post • Hacker News Board

Re: The GDPR blog post

#141

Post by lvh » Wed, May 30, 2018, 12:40 PM UTC

hvidgaard wrote: post #137

lvh wrote: post #95

Earlier quoted context omitted.

That's not provably the case at all. We can absolutely do better, for reasons the root of this thread raises. If that were true, why isn't SHA256 the state of the art in password storage? Reason: the input space is small enough to enumerate. I posted a comment with an alternative construction plus rationale: https://news.ycombinator.com/item?id=17153329

I never said anything about SHA256. I talked about one-way functions. The thread model is an adversary that gets unlimited access to the values stored for this purpose, and knows the function used to compute it. He wants to check if a given email is in the set. One-way functions is provably the best way to be able to ask yes/no to the question if this email is in the set with no false answers. I have not said anythin…

You did say hash function.

Would you mind jotting down that proof?

Re: The GDPR blog post

#142

Post by lvh » Wed, May 30, 2018, 12:41 PM UTC

hvidgaard wrote: post #139

lvh wrote: post #53

Earlier quoted context omitted.

Yes. They don't quite define how the hash works in the post, but assuming it's something like SHA256(email), that's easy to enumerate. There are ways to do this better. Let's say that it's 1 party and you're trying to figure out if you've seen en email address before. (That's the case in the article, there are also schemes where you and another entity can figure out if you both saw any email addresses -- but that's n…

> You can fix that problem by also adding a PRF (pseudorandom function) that you rate-limit vigorously. Think of a PRF as a keyed hash -- the usual example is HMAC-SHA256. If you're capable of keeping PRF key material safe but might leak a database dump (not unreasonable), the PRF forces the attack to be online: an attacker can only validate guesses as long as they have access to the PRF, and the PRF comes with audit…

What? A PRF having a secret key is not “security by obscurity.” I am documenting how the entire process works and where the security properties come from.

Re: The GDPR blog post

#143

Post by hvidgaard » Fri, Jun 01, 2018, 9:00 AM UTC

lvh wrote: post #141

hvidgaard wrote: post #137

Earlier quoted context omitted.

I never said anything about SHA256. I talked about one-way functions. The thread model is an adversary that gets unlimited access to the values stored for this purpose, and knows the function used to compute it. He wants to check if a given email is in the set. One-way functions is provably the best way to be able to ask yes/no to the question if this email is in the set with no false answers. I have not said anythin…

You did say hash function. Would you mind jotting down that proof?

A proper cryptographic hash function is a one way function, if they exist.

But I'd frame your question the other way around then. You do not want to store the emails in a form that leaks any data. For that we need a compressing function. My (unwritten) assumption was that if the adversary compromise the system to get the data, they'll get any secrets too. This means that a HMAC is no better than a cryptographic hash function.

I know that is quite possible to create a system where this would be significantly harder than just a DB dump. But that is both significantly more difficult, and expensive. I'll admit that the formulation "provable the best we can do" should've had a big fat asterisk with the disclaimer about the threat model.

So, if an attacker have the data set and secrets, and wants to compute if a particular input is a member of this set. Can you do better than a cryptographic hash function?

Re: The GDPR blog post

#144

Post by lvh » Fri, Jun 01, 2018, 3:28 PM UTC

hvidgaard wrote: post #143

lvh wrote: post #141

Earlier quoted context omitted.

You did say hash function. Would you mind jotting down that proof?

A proper cryptographic hash function is a one way function, if they exist. But I'd frame your question the other way around then. You do not want to store the emails in a form that leaks any data. For that we need a compressing function. My (unwritten) assumption was that if the adversary compromise the system to get the data, they'll get any secrets too. This means that a HMAC is no better than a cryptographic hash…

Can you write down in pseudocode exactly what you're suggesting? As in db.write(sha256(email)) or whatever.