1
$\begingroup$

Playing around with some ideas for a hash-function using simple primitives, I came up with this construction:

Select two large safe primes, $B$ and $M$, where $B < M$. Define $C$ as the concatenation of key $K$ (a passphrase) with any number of salt/nonce parameters $S_i$, where each field is separated by the ASCII "field separator" character $\mathbb{0x1e}$.

Now construct hash $H$ by repeating the following steps:

  1. Set $E$ to be the repeated concatenation of $C$ such that $M < E$, where each copy of $C$ is separated by the ASCII "record separator" character $\mathbb{0x1c}$.

  2. Calculate $R$ as $B^E \bmod M$.

  3. Starting from the last digits of $R$:

    a. Extract 8 bits and "move backward" that many steps + 1.

    b. Extract 4 bits and append to $H$.

    c. If the length of $H$ is sufficient, we are done.

    d. Repeat until we have "reached the beginning" of $R$.

  4. Set $C$ to the current value of $R$.

  5. Go back to step 1.

As far as I can tell, the algorithm seems to satisfy all of the requirements of a CPRNG, such as first and second preimage-resistance, collision-resistance, etc.

The questions I have specifically are

  1. if it does indeed guarantee such a thing?
  2. are there any similar methods being used today?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

You are essentially doing a "regular sampling" of the bits of a power modulo a prime $M$ where the base is another prime $B$ (taking every 4 out of every 12 bits). So the relevant problem is discrete logarithm with regularly structured known bits.

A few comments:

  • There is the Blum-Blum-Shub generator which takes only the LSB or a few (of the order $\log n$ where $n=pq$ the RSA modulus) and the square function is used instead of an arbitrary power. And then the squaring is iterated before the next bit is taken. It is considered insecure to take many more bits. You are taking a very large number of bits, but your problem is different since you are not iterating but taking bits at one go.
  • Discrete log with a significant fraction of bits known is weak. Look up Coppersmith's attack which is an application of lattice basis reduction algorithms (like LLL) to find small solutions to polynomials modulo $N$. The application of this method ranges from several attacks on RSA, to solving the hidden number problem (for Diffie-Hellman key exchange or (EC)DSA).
  • Finally, I believe there isn't an advantage to use another safe prime $B$ as a base. Any nonzero base modulo $M$ is a valid generator with equivalent cryptographic properties: "the prime $M$ knows nothing about the prime $B$".
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks, I did actually consider the Coppersmith attack (the Blum Blum Shub generator even came to mind) when designing the algorithm, which is basically why I chose to select bits in a random-walk fashion rather from the least significant bits. AFAICT this effectively prevents such things because it acts like a "sponge construction" where too much information is lost in the process to be of any use. $\endgroup$ Commented Apr 19 at 22:53
  • $\begingroup$ For example (if we switch to 4-bit jumps for the sake of simplicity) if R is equal to C47[6]87FA5[B]76072A7[9]41785[9]37695[B]230A96A92BB[F]8D7A737[C]82[F]1EE7A67[9]1[8]653[1]B3E92C7FB1E425[F]70EE6E529[6]F5A60FB31A[E]6C610B7285B[5]9A686F7[7]5E3[B]6C6F59D24D6613F then the bits extracted on the first iteration would be the ones marked in brackets, ie: 6B9BFCF981F6E57B. $\endgroup$ Commented Apr 19 at 22:54
  • $\begingroup$ For extremely large R this should mean that we glean almost nothing by inspecting the output. (Please do correct me if I am wrong.) As to why I chose a safe-prime as a base, that was simply because they seem to produce more randomly-distributed outputs than otherwise, which I believe is a very important property for this particular construction. $\endgroup$ Commented Apr 19 at 22:54
  • $\begingroup$ Just wanted to add that the actual algorithm selects 4 out of every ~250 bits from an unstructured chunk of data. Moreover, the data itself is generated in a highly unpredictable fashion, from the concatenation operation, down to the modulo result R. Changing a single bit in the input also yields a completely different output, so it isn't malleable enough to be susceptible to either pre-image nor so-called "birthday" attacks. $\endgroup$ Commented Apr 20 at 2:09

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.