3
$\begingroup$

I'm looking for behavior similiar to that of LCGs, (i.e. input and output sizes are same). Full cycle of $2^{32}$ different inputs generates full cycle of $2^{32}$ different outputs, distribution of which depends on large key. Obviously combined LCGs (with generated parameters based on the perturb seed key) seem trivially invertible through modular inverse, but you get the idea.

The hash has to accept small input and produce never-colliding equal sized output, and is keyed with large 'salt'/'nonce' key, to make precomputing generic table of all $2^{32}$ hashes for trivial inversion infeasible. The hash has to remain one way when 'seed' key and output is known (ie input should be difficult to compute out of those, short of bruteforcing 2^31 inputs for each particular seed+output and meeting in the middle for birthday).

This exotic requirement sets it apart from classical bijective trapdoor functions (RSA, MQ et al), as the output has to be much smaller than some input parameters (ie the "salt" seed).

Is this even feasible? It does not appear to be with traditional ARX/feistel, however I suspect there are still useable trapdoors in number theory - for example FSB and SWIFFTX. However I'm not sure if those can be adapted to the requirement above.

I'm OK with security parameter well below nbits/2, as long it is still reasonably difficult to invert algebraically.

Bottom line: Albeit related, perfect hash functions are not acceptable answer as there does not seem to be examples of cryptographically secure ones, much less any working as a trapdoor.

Block ciphers such as RC6 or AES rounds show some promise (by using the 'decrypt' part as our hash), but naive implementation seems to be reversible by running the rounds backwards (remember, the cipher key, our "seed" sbox which introduces non-linearity in those is publicly known, whereas the tiny "plaintext" is what is to be protected).

I presume block ciphers which break linearity through heavy input data dependency might work, however I have no idea what candidates I should be looking for.

Improve this question
$\endgroup$
5
  • $\begingroup$ $2^{32}$ brute force can be done in seconds (on a GPU) unless the 'hash' is very slow, so avoiding attacks faster than brute force does not seem to gain you anything much. You could just use format-preserving encryption and accept the fact that knowing the key allows decryption. $\endgroup$
    – otus
    Oct 10, 2015 at 4:14
  • $\begingroup$ I'm well aware. To avoid further discussions on the example security parameter, imagine 512 everywhere in the text instead of 32. $\endgroup$
    – kat
    Oct 10, 2015 at 4:29
  • $\begingroup$ If you change 32->512 the answer changes to: just use a collision resistant 512-bit hash. $\endgroup$
    – otus
    Oct 10, 2015 at 4:35
  • $\begingroup$ @otus Which hash function do you recommend - it has to be still full cycle (bijective). I do realize universe would end before enumerating all states with 512 bits, however my application is not to avert bruteforce through overkill like this - that's what the seed is for - it's an interactive protocol with constrained bandwidth and short lifetimes of this weird MAC I am trying to do. $\endgroup$
    – kat
    Oct 10, 2015 at 4:41
  • $\begingroup$ You should probably leave this question as is and ask another question about the specific problem you are trying to solve. It is not at all clear to me that you need a permutation. $\endgroup$
    – otus
    Oct 10, 2015 at 5:08

1 Answer 1

Reset to default
4
$\begingroup$

I'm sorry, but I don't believe that there are any known 'one way permutations' for small inputs (that stay one way if you know the 'key').

When we create a cryptographic permutation (or bijection; that's what we call a 'full cycle' function), we have two basic ways to do it:

  • We can take a series of easy to invert permutations ("round functions"), and glue them together to form a function that we hope is hard to invert.

This is the general design principle behind most block ciphers; we believe that if the key is secret, this can work very well. However, if you give someone the key, it becomes easy to invert (by just inverting each individual round function).

  • We can take advantage of some mathematical relation which is one-to-one (that is, it avoids collisions), but it doesn't do it for any naively obvious reasons.

We often find these sorts of things within public key cryptography; one such is $f(x) = g^x \bmod p$ (for appropriate $g, p$); this function can map the inputs $(1, p-1)$ into the range $(1, p-1)$ such that every output is possible.

One problem with this is that these types of functions are large; in the specific case I mentioned, we need $p$ to be perhaps 2048 bits to be really secure, and that's hard to describe as a small range.

Improve this answer
$\endgroup$
7
  • $\begingroup$ RSA is probably what I'm going to end up with (though not happy about it). On a related note, in the event g happens to be a weak composite (can't afford primality tests) and p is always hardcoded value, wouldn't there be a shortcut to derive x for an adversary? $\endgroup$
    – kat
    Oct 10, 2015 at 4:57
  • $\begingroup$ Actually, the function $f(x) = g^x$ that I mentioned is not RSA; instead, it's modular exponentiation. As for $p$ and $g$, you could select $p$ to be the group14 prime from datatracker.ietf.org/doc/rfc3526, and $g = p - key^2$; as long as $\sqrt{p} > key > 1$, that'll always be a strong value for which $f(x)$ is a bijection.. $\endgroup$
    – poncho
    Oct 10, 2015 at 11:14
  • $\begingroup$ My apologies for incorrect lingo (i refer to it as RSA as RSA simply exploits similiar congruence). My configuration at the moment is (in C-ish notation): G = primitive_roots_of_p[seed1]^seed2; p = 2^31-1; x = text to be hashed; Unfortunately I can't afford to square key, as that would result having "seed" even smaller than it already is. $\endgroup$
    – kat
    Oct 10, 2015 at 11:17
  • $\begingroup$ If $p$ is the 31 bit prime you appear to mention, well, that's quite weak (that is, easy to invert). I suspect that otus is right; you need to rethink the problem. Why do you think you need a public permutation anyways? What problem are you actually trying to solve? $\endgroup$
    – poncho
    Oct 10, 2015 at 11:32
  • $\begingroup$ It is the only one which appears to have bijective mapping with "hashing" property. Ie forward step is one powmul, the inverse is 2^30 powmuls. I'd rather avoid it if I could... As for the exact protocol, it's byzantine fault tolerance/quorum consensus, where client has to prove ownership of data it previously said it owns. The idea is to prevent clients from announcing us data they can can easily generate at runtime. This trapdoor forces client to not lie to us, as it would turn into fairly difficult PoW problem and would have to solve 2^30 steps for each 4 bytes it didnt store. $\endgroup$
    – kat
    Oct 10, 2015 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.