1
$\begingroup$

Sha1/0 (160 bits output), md5(128 bits output) has block size of 512 bits. Gost has 256 bits.

What is the reason behind having it specifically 512/256/1024 bits?

What are the various factors which are considered while choosing a specific block size for an algorithm ?

Sorry for the naive question !! :-)

$\endgroup$
1
$\begingroup$

There are really two considerations: fulfilling the security requirements, and doing so efficiently.

Security Considerations

Typically you would select the minimum secure block size depending on the type of algorithm in question, and the target operating environment. A block size that is too small can lead to attacks of time/space complexity that can be performed in practice. For an example, see the sweet32 attack.

Your question mentions hashes, but also mentions algorithm design in general, and the core of a hash function is often times a type of psueodrandom permutation (PRPs are arguably the workhorses of symmetric cryptography).

The block size will need to take into account the type of hashing construction, i.e. a Merkle–Damgård construction versus a sponge construction. For example, the full Keccak uses a larger state than many other designs, which may be related to the fact that much of the state is truncated before being output.

Using a block size smaller than 128 bits is almost guaranteed to enable attacks against your design (which may or may not be applicable, depending your use case). Larger block sizes tend to offer greater security.

Hardware considerations and performance play an integral role.

Using too small of a block size will not make effective use of the available registers on the machine. Using too large of a block size will also not make effective use of the available registers on the machine.

In an otherwise solidly designed psuedorandom permutation, memory accesses in the main loop can/will become the dominant cost, especially in the case of SIMD registers. If you have a bunch of MOV operations into an SIMD register in the main loop of your PRP, you will quickly eat into the advantage provided by SIMD.

SIMD operations are important. In order to compete on the throughput front, it is effectively a requirement to utilize SIMD operations. These instructions allow the application of an instruction to a larger number of registers in parallel. This will effectively multiply your block size while processing it in more or less the same amount of time.

Typically, you would initially target one of: constrained hardware, 8-bit platforms, 32-bit platforms, 64-bit platforms, then use the available SIMD instructions (if any) to increase the throughput of the design. Not all platforms offer SIMD operations - clearly, if you are designing for constrained hardware, this advice about SIMD does not really apply anymore.

Using a block size larger than 1024 bits is likely to be too big on almost any normal platform. To use a 1024-bit permutation effectively, you would need 64-bit registers, with 1 SIMD register spanning the length of 4 normal registers (256-bits), and 4 SIMD registers dedicated to your data (constants and other information that will also put pressure on the registers), then you can operate efficiently on 1024-bits at a time.

Modern desktop CPU's offer 64-bit registers. However, there are still many places where 32-bit platforms are used, as well as 8-bit platforms; Performance on these platforms will suffer if your design does not cater to them.

Similarly, if you design an algorithm that operates on 8 bits at a time, performance may suffer on a platform with wider registers.

Designing an algorithm that is friendly on all platforms is a topic of current research

In general, it will probably tend to yield a more balanced algorithm to design for an 8-bit or 32-bit platform, then run multiple instances in parallel via SIMD. This way you can ensure that performance is acceptable on all platforms, rather than excellent at one end of the spectrum, and horrible at the other.

Gimli opts for a 384-bit block size, so that is probably the sweet spot for balanced performance on all platforms. You may be able to squeeze slightly more performance out of a 512-bit block size, depending the nature of your design.

Why is the performance section larger than the security one?

If efficiency is not a concern, then the game becomes too easy. Just make everything huge. Don't expect your design to see use in the real world if you can't hash more then 20MB/s on a desktop CPU...

$\endgroup$
1
$\begingroup$

Let $N$ be the block size in bits, used in the Merkle–Damgård construction of the given hash function.

The smaller $N$ is, the more iterations have to be executed to yield the hash value, hence the algorithm becomes more (computationally) expensive.

The larger $N$ is, the more inefficient it becomes for messages of length $M$, where $M<N$, since the input message would have to be padded out until it fills at least one block of size $N$. It would not be desirable having to add 1013 bits of data if you only need to hash 10-bit inputs. (in fact, you would have to pad out a bit less since there is a field-length field at the end of the block)

Finding a trade-off lies with the developers - I guess 512-bit blocks have been established as a consensus as MD5, and most SHA-2 members work on this length.

$\endgroup$
  • 2
    $\begingroup$ The part "hence the algorithm becomes more (computationally) expensive" is at least non-trivial, and unconvincing. OK, the smaller $N$ is, the more iterations there are. However, a smaller $N$ leads to a faster round, and that at least partially compensates. And if larger $N$ led to no significant increase in the duration of a round, and was safe, we'd use larger $N$ for overall increased hash speed. A reason why we do not use larger $N$ (on top of the reason given) is that it makes the round function significantly slower, or/and less secure. $\endgroup$ – fgrieu Jan 13 '18 at 14:20
  • $\begingroup$ I think the lower bound on N is usually related to the security level of the hash. If you want to emit a 256-bit digest at the end of it all, you need at least 256 bits of internal state, or else your hash isn't really providing the collision resistance it's supposed to. The next important thing is that each block of input needs to be fully mixed with the state before the next block begins, otherwise again your collision resistance isn't what it's supposed to be. $\endgroup$ – Jack O'Connor May 24 at 23:36
  • $\begingroup$ [Continuing:] So if you're going to fully mix some input with 256 bits of state, it doesn't make sense to mix 1 bit of input at a time. You'd have to do a lot of mixing steps just for that 1 input bit, to make sure it has a chance to affect each of the 256 state bits. It's going to be much more efficient to mix some larger block size of input at a time, so that each mixing operation (say adding two 32-bit words) has a chance to bring as many input bits and state bits into contact as possible. Usually that works out to something like "input block size = state size", give or take a factor of 2. $\endgroup$ – Jack O'Connor May 24 at 23:37
0
$\begingroup$

We have two primary design goals when building an encryption of cryptographic hash function: Security, and speed. Block,key,and state sizes are selected to meet these goals. In general more bits mean more security, and at the very least we need enough to make generic brute force attacks infeasible in the forseable future. (Including birthday attacks). In the past 128 bits seemed more than enough, now the margin a128 bit encryption doesn't seem to have much security margib. And for a hash function it is obvious 128 bits are totally inadequate, as 2^64 operations are achieveable in several attack scenarios. On the other hand we want general purpose cryptographic primitives to be very efficient. And for standardized versions they need to be efficient across many possible implementation platforms. This means we prefer sizes which are a multiple of commin word sizes. So multiple if 32 or 64 bits is prefereed. Powers of 2 are also useful, especially when implementing in hardware. Note with assymetric operations like DH or RSA, we know of attacks far more efficient than brute force and key sizes grow to counter best known attacks and an extra margin from that.

$\endgroup$
  • $\begingroup$ The question was about the length of blocks, not the final hash length which is independent. For example, MD5 could also work with 1024bit block partitioning and still yield a 128bit output (it would take a modified compression function). How do larger block sizes increase security? $\endgroup$ – indiscreteLogarithm Jan 13 '18 at 9:23
  • $\begingroup$ Sorry, misread the question. I would argue the important part is not the block size but rather the internal state size. Increasing the size of the internal state gives protection against several types of attacks, such as multi-collisions built from internal state collisions. $\endgroup$ – Meir Maor Jan 13 '18 at 9:58

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.