0
$\begingroup$

First, we observe that the expression X*Y mod P (where X and Y are secret and P is a large public prime) reveals no useful information.

Next we define an extending function E(U, M) which "somehow" transforms U in such a way to guarantee that the result consists of at least M bits. For example, by returning the bit pattern of U with the Mth bit set. (In practice we might add a few more constraints there in order to satisfy non-malleability).

Finally, we have a function F defined as follows:

Q = E(V, N)

F = (Q * E((Q * A) mod B, N)) mod C

Where A, B, C are large public primes, V is secret, and N is the number of bits of the largest prime.

So my question is, does F satisfy all of the following properties: non-reversibility, preimage resistance, and collision resistance?

Improve this question
$\endgroup$
26
  • $\begingroup$ Does the problem statement mention that $E$ is injective? Otherwise, what about $E(U,m)$ ignoring $U$ and returning the $m$-bit bitstring with $m$ bits at $1$? The corresponding $F$ would collide a lot. Also, $E$ must probably be independent of $A$, $B$ and $C$. $\endgroup$ – fgrieu♦ Nov 17 '20 at 14:36
  • $\begingroup$ Yes, which is precisely what I was referring to when I mentioned additional constraints. The actual idea I had in mind was to repeatedly concatenate the input with itself (separated by a restricted "symbol") at least once in order to ensure that E(U, m) is unique for all U. Furthermore, the computation of E does not involve any of A, B, or C. $\endgroup$ – Sir Galahad Nov 17 '20 at 15:08
  • $\begingroup$ It's difficult for anyone to answer your questions as the function F relies heavily on the largely unspecified function E. If E is SHA512 then F seems a lot better than if E is simply <<7. But if E is oracle-like then it suggests F need not exist. Note that if Q=E(v1,N)==Q=(E,v2,N) then it follows that QE(QA mod B,N) will be the same and this step is t/f unnecessary. In real life, use proper crypto. For fun, maybe look into NH-hashing into a large array of say 1024 64 bit hashes, then sieving them down into 8 or 4 using XOR/mod addition. I've already coded this if you are interested. $\endgroup$ – Modal Nest Nov 17 '20 at 15:14
  • $\begingroup$ Sure, I'd love to see it. And most likely I'll be posting a link to my final implementation as well once all of the details are ironed out. Anyway, the extension function as elaborated is not oracle-like, but is injective, which should be sufficient here. $\endgroup$ – Sir Galahad Nov 17 '20 at 15:25
  • 1
    $\begingroup$ @SirGalahad If you have an answer then please ask the person that led you in the right direction to write an answer or write one yourself. Or, if you think it is not useful to anybody else, then delete the question. $\endgroup$ – Maarten Bodewes♦ Nov 21 '20 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.