[Cryptography] Homomorphic and Structured Encryption

[Jerry Leichter]

> Use cases where you expect most things not to be in the database don't seem to be common.  Years ago, David Wittenberg and I got a patent (long expired) on using a Bloom filter with cryptographic hash functions to test whether proposed password was already in use by anyone in a system.  Because of the cryptographic hashes, it would be impractical to determine what passwords were actually in use.  This is a case where you expect most of the answers to be "not found."  However, checking the "found" items would require keeping the actual passwords around, which you don't want to do. But ... that could be used if you were checking for matches to *leaked* passwords, I suppose.
> 
> Doesn't the use of random salts stored with the password hashes make that approach rather useless or am I misunderstanding something?
I haven't described what the system was meant to do.

Imagine an organization that wants to avoid reuse of passwords even among different people in the organization.  So the obvious approach would be that whenever anyone changes their password, it gets sent to a central database which stores every password ever used, and if it's there, the password is rejected.  Now this is a bad model for a couple of reasons:  The database is an incredibly high-value target.  Someone in a position to see the updates sent to the database can see what passwords are being set.  And someone who gets a rejection knows that the password he was trying is actually in use.

So you replace the central database with a Bloom filter.  You send only the hashes of proposed passwords, and you use cryptographically secure hashes.  Now, having a copy of the database gives you little information.  Yes, you could test a dictionary of words by hashing them yourself and seeing if the filter accepts them - but the owner of the filter can simply keep up with the dictionaries being used by attackers and insert the values in the filter himself.  This prevents people from choosing those passwords - which would be vulnerable to an attack using the known dictionaries - and would make a dictionary attack on the filter pointless as everything in the dictionary would come back as a positive.  Someone intercepting an update would see a cryptographic hash which they couldn't invert to get the proposed password - and trying a dictionary attack against it would be just as pointless as attacking the filter, as if you find that one of the dictionary words matches the hashed value, it's going to be rejected anyway.  And because the Bloom filter has false positives, just because your proposed password is rejected doesn't tell you someone is actually using it - so we make a virtue of a weakness.

I won't claim this is a highly likely use case - perhaps even less today than we played around with it back in the late 70's or so.  We just thought it was a neat idea, and since DEC would pay for the patent ... why not?

                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20220228/434a3dfd/attachment.htm>