5
$\begingroup$

Clearly it would provide perfect insight if all 256 bits were used. What about if 255 were used? Would the general behavior and properties of "sha-255" be expected to be close to sha-256? What about "sha-5?" I imagine at some point the insight we can gain must break down, but am not sure exactly where that is.

sha-256 has such a large range of potential outputs that it is impossible for me to do certain experiments with it to analyze the behavior. But I presume that I couldn't, for example, truncate outputs to the first 10 bits or whatever, and then assume that observed behavior will extrapolate to the real sha-256, or else we would likely be able to know far more about it than we can.

I like to learn by experiment and observation. Are there any constructs with behaviors similar to cryptographic hash functions like this, but that I can actually exhaust the range of, and gain any insight into the secure constructs from?

My guess is no because of the lack of some insights into the secure constructs, but I'm not certain. Is insight already lost at "sha-255?"

$\endgroup$
7
$\begingroup$

If this provided any insight, we would consider SHA-256 to be broken. In general, we expect the $n$-bit truncation of SHA-256 to resemble an $n$-bit uniform random function. For example, finding a 10-bit partial preimage costs an expected ${\approx}2^{10}$ trials; finding a 10-bit partial collision costs an expected ${\approx}2^5$ trials.

That said, there are often simplified versions of cryptographic primitives for study:

  • One obvious simplification of SHA-256 is to reduce the number of rounds from 64—for SHA-256 as for most cryptographic primitives with rounds, the first (and, for unbroken cryptosystems, only) attacks published in the literature are on reduced-round variants.

  • Aside from varying the number of rounds, Keccak supports any power-of-two word size from 1-bit to 64-bits; SHA-3 is based on 64-bit Keccak with a 1600-bit state, but you could study 1-bit Keccak with a 25-bit state (with any number of rounds).

  • The SHA-3 candidate BLAKE came with several toy versions BLOKE, FLAKE, BLAZE, and BRAKE.

$\endgroup$
  • 1
    $\begingroup$ Just for clarity (and please correct me if I'm wrong), we currently believe the full SHA-256 algorithm to not be broken in this way (and thus n-bits of SHA-256 to not be broken either), but we have made successful attacks against the reduced rounds variants of the algorithms. $\endgroup$ – Cort Ammon - Reinstate Monica Nov 15 at 17:29
0
$\begingroup$

Any experiment made with SHA-256 or any truncation of that, devised without knowledge of SHA-256 (or just without knowledge of its constants h0..h7), and with input length constrained to block the length extension property (e.g. fixed), should conclude that the output behaves like uniform random, except that identical input leads to identical output.

Any other coclusion is a mistake in the design of the experiment, or statistically insignificant, or (improbably) a major result against the security of SHA-256.

$\endgroup$
  • 1
    $\begingroup$ SHA-256 with hidden constants is easy to distinguish from random by length extension attack. Two chosen input queries and negligible computation suffice. $\endgroup$ – Polytropos Nov 17 at 6:51
  • $\begingroup$ @Polytropos: very right! Fixed. $\endgroup$ – fgrieu Nov 17 at 9:43

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.