4
$\begingroup$

Will this algorithm make a cryptographically secure hash function? Can it be used to generate passwords? Is it secure enough for use as a MAC?

Divide the message into blocks.

The initial state is $h=314159265358979323846$.

For each message block $m$:

The new state is $h=(h+m)^2 \;\; mod \;\; pq$.

For a digest of size n bits repeat n times:

The new state is $h=h^2 \;\; mod \;\; pq$.

Return parity bit of $h$.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ That is one expensive hash function... $\endgroup$ – Thomas Feb 4 '17 at 4:48
  • $\begingroup$ Why is it so expensive? How slow is a modular multiply-add? $\endgroup$ – user43678 Feb 4 '17 at 5:04
  • $\begingroup$ @user43678 For a 2048-bit+ modulus, you are talking about tens of thousands of word-sized multiplications/additions/divisions per output bit. That is atrociously slow (talking hundreds of microseconds, maybe even milliseconds here with even short messages on modern desktop CPUs). You would be lucky to get 1MB/s out of it. $\endgroup$ – Thomas Feb 4 '17 at 5:08
  • 4
    $\begingroup$ Trivial collision for any $x$: $m_\pm=-h \pm x \pmod n$ $\endgroup$ – CodesInChaos Feb 4 '17 at 9:38
  • 1
    $\begingroup$ Also fast multiplication is very expensive in hardware. $\endgroup$ – CodesInChaos Feb 4 '17 at 9:39
3
$\begingroup$

The authors of the original algorithm (1) shows that the security of the $x^2 \bmod N$generator as a pseudorandom number generator (PRG) can be reduced to the quadratic residuosity problem.

The paper then shows that (all modulo the QRA):

Theorem 4: The generator is an unpredictable cryptographically secure pseudo-random sequence generator.

Theorem 5: The sequences produced by the generator pass every probabilistic polynomial time statistical test and that it has the property of unpredictability.

The basis for these properties is that a (probabalistic polynomial time with advantage $\epsilon$) predictor for the generator can be converted efficiently into a predictor of parity for $x_{-1}$ (for arbitrary $x_0$). They then show that such a predictor can be efficiently converted into a procedure for guessing quadratic residuosity (with an amplified $\frac{1}{2}-\epsilon$ advantage.).

The algorithm is a cryptographically secure PRG, provided that the quadratic resuosity problem remains a computationally hard problem under the assumptions made in the proof. According to this answer the assumptions made are easily misinterpreted and for the construction to be secure N needs to be very very large.

However and in any-case, secure PRGs do not inherently make secure cryptographic hash functions. A secure hash algorithm needs to be deterministic, collision resistant and first and second pre-image resistant.

As stated in the comments your algorithm would not make a secure hash function because it does not have the property of collision resistance:

$\forall x,h: h' = -h - x \bmod N $

This also implicitly breaks second pre-image resistance.

Since the hash function is not cryptographically secure it is not suitable for using to generate passwords or to authenticate messages.

Improve this answer
$\endgroup$

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.