3
$\begingroup$

I'm looking to use password-style hashing to validate an environment, where some parts may be irrelevant. For example:

requirement = 0b1010
pattern = 0b1011
mask( a, b ) = a & b
hash( a ) = <any cryptographic hash>
condition = hash( mask( requirement, pattern ) )

# public
environment = 0b1110
hash( mask( environment, pattern ) ) == condition
-> true

So for the requirement 0b1010 and pattern 0b1011, both environments 0b1010 and 0b1110 would match (though typically there would be many more possibilities, since I expect only a small proportion of an environment to be relevant for a particular test)

The pseudo-code above would accomplish my goal, but it requires the pattern to be available in plain-text (since it must be applied to the given environment directly). The final check is performed publicly, and I would like to hide the pattern at this point, i.e.:

mask( a, b ) = ???
hash( a ) = ???
encryptedPattern = ???
condition = mask( hash( requirement ), encryptedPattern )

# public
environment = 0b1110
mask( hash( environment ), encryptedPattern ) == condition
-> true

The ultimate brute-force approach would be to generate salted hashes for every matching environment (doubling-up some possibilities to hide the information about how many bits the pattern masks out) and test them all in-turn, but clearly this isn't practical once more than a few bits are considered irrelevant.

I haven't been able to find anything on hashes constructed to have deliberate collisions, or accept ranges, and I don't believe it would be possible to retain positional information through a hash while maintaining irreversibility. At the same time, this feels like something which has probably already been studied, and I'm just missing the relevant terminology to find it.

Is there any existing work on this type of check, or methods which could be extended to support it? Alternatively, is it provably impossible?


For context, my eventual plan is to extend this by checking hash( mask( hash( environment ), encryptedPattern ) ) == hash( condition ), and use the unhashed condition (which would only be available by getting the "password" correct) as a key to decrypt other data.

$\endgroup$
  • $\begingroup$ So the idea is to allow matching some sort of pattern without revealing the (exact) pattern? What parts of the computation and data would be public? $\endgroup$ – otus Nov 28 '15 at 17:03
  • $\begingroup$ @otus the entire checking process would be public, so the algorithms behind mask and hash, as well as the condition and encryptedPattern variables in the second pseudo-code. The process which produces condition and encryptedPattern from the secret requirement and pattern would be private. $\endgroup$ – Dave Nov 28 '15 at 17:36
  • $\begingroup$ @Dave I'm not sure I entirely understand your issue, but it sounds similar to the problem addressed by "fuzzy extractors" and "secure sketches". The linked paper concerns itself with extracting keys from noisy biometric data (where repeated measurements do not yield exactly the same results). $\endgroup$ – Ella Rose Jul 4 '16 at 22:02
  • $\begingroup$ @EllaRose seems similar, but I'm trying to make what they denote as "P" secret rather than public $\endgroup$ – Dave Jul 5 '16 at 7:11
1
$\begingroup$

Suppose you had such a hash. Then anyone who knew some value for which the condition matched could find out the full pattern/mask:

  1. You know some environment for which mask(hash( environment ), encryptedPattern ) == encryptedCondition.
  2. You can flip one bit at a time, compute the masked hash, and see if you still get a match. If you do, that bit was masked out in the (unencrypted) mask pattern.

So possibly what you want is impossible. However, if you only need the pattern to remain hidden from those who do not know any matches, it may be possible using homomorphic encryption.

  1. Take a suitable homomorphic encryption system that allows computing ANDs and verifying the results*. Encrypt the mask m = E(pattern) and the condition c = E(requirement).
  2. The user encrypts a value E(environment), ANDs with the mask and compares to the condition: E(environment) & m == c.

* The system must be deterministic and have E(x) & E(y) = E(x&y).

(Note: the use of deterministic encryption means that a user can guess and test values against pattern and requirement. This is quite weak, but conceivably there could be applications.)

$\endgroup$
  • $\begingroup$ I only need it to be secret for users who do not know any matches. Homomorphic encryption sounds interesting (so I've just spent an hour reading about it!) It looks like the quoted speeds for fully homomorphic methods are far too slow for what I need, whereas the existing partially homomorphic methods support addition or multiplication; none list bitwise operators. I'll search some more, but are there any you know of? Also I take your point about it being relatively weak, but I expect the length of the requirement to balance that out (it will be ~4096 bits or more) $\endgroup$ – Dave Nov 28 '15 at 23:23
  • $\begingroup$ @Dave, yes, you would likely need FHE which is indeed slow. I don't know any partially homomorphic system that would have bitwise AND. $\endgroup$ – otus Nov 29 '15 at 8:01
  • $\begingroup$ OK, well I think you're right that homomorphic encryption is exactly what I'm looking for, so I'll mark this accepted. I'll just have to watch for improvements to the speed of the method. $\endgroup$ – Dave Nov 29 '15 at 20:43
  • $\begingroup$ @Dave: ​ ​ ​ Are you aware that that one can implement bitwise-and by multiplying the corresponding bits? ​ ​ ​ ​ $\endgroup$ – user991 Nov 30 '15 at 9:04
  • $\begingroup$ @otus: ​ In addition to being deterministic, it would also need to be that E(x) homomorphic-and E(y) gives E(x&y), rather than something else that decrypts to x&y. ​ ​ ​ ​ $\endgroup$ – user991 Nov 30 '15 at 9:08

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.