Re: Which checksums/hashes do not have any 'internal cycles'?

Claudio Grondi wrote:
Let's consider the 32-bit CRC as a mapping of all four byte long strings
onto another four byte long strings representing the CRC values of the
first mentioned ones.

The 32-bit CRC has at least one 'internal cycle' because the CRC-32 of
chr(0xFF)+chr(0xFF)+chr(0xFF)+chr(0xFF)
is the integer
0xFFFFFFFF
which expressed as a four byte string is
chr(0xFF)+chr(0xFF)+chr(0xFF)+chr(0xFF)

Which of the known checksums/hashes does not have any 'internal cycles',
i.e.
- starting at any checksum value and taking it as input for
- calculating a checksum in order to take this value as input for
- calculating a checksum value ... (i.e. continuing with above ^)
'visits' all of the possible checksum values?

As I am after gaining some deeper understanding of what checksums/hashes
are, can someone please explain it to me or point me to appropriate
resources helping me to get enlightened on this subject?

Claudio Grondi

Are you asking about fixed points, f(x) = x, or are you asking about
functions that eventually cycle after some number of iterations?

It is easy to find simple funtions without fixed points, like f(x) = x
+ 1 (mod 2^32), but for good cryptographic hash functions like SHA-256,
the answer is not known.

All hash functions must eventually cycle. If the input and output is n
bits, then after 2^n + 1 iterations, at least two outputs must be
identical.

-- Matt Mahoney

.

Relevant Pages

  • Re: Which checksums/hashes do not have any internal cycles?
    ... onto another four byte long strings representing the CRC values of the ... The 32-bit CRC has at least one 'internal cycle' because the CRC-32 of ... calculating a checksum in order to take this value as input for ... functions that eventually cycle after some number of iterations? ...
    (comp.compression)
  • Which checksums/hashes do not have any internal cycles?
    ... Let's consider the 32-bit CRC as a mapping of all four byte long strings onto another four byte long strings representing the CRC values of the first mentioned ones. ... The 32-bit CRC has at least one 'internal cycle' because the CRC-32 of ... calculating a checksum in order to take this value as input for ...
    (comp.compression)