4
$\begingroup$

To estimate the time for brute-force attack we need to compute keyspace size divided by hash rate, where the hash rate (hash/second) varies depending on the computer's capabilities.

The website https://bench.cr.yp.to/results-hash.html shows the hash rate for different computers. Can you explain the following two confusing phenomena?

  1. The hash rate decreases as the message size increases.
  2. Core i3 has a higher hash rate than Core i7 for SHAKE128.
$\endgroup$
4
$\begingroup$

The hash rate decreases as the message size increases.

What's quoted by the benchmark decreases with the message size. But it is not a "hash rate", at least in hashes per unit of time on a certain computer as thought by the OP. The unit is cycles per byte, thus higher values mean proportionally more cycles spent, more time spent, and less hashes performed (with all of many other more important things being equal).

Assume computer(s) used to their full computing power for hashing, with a total of $u$ CPU(s), each with $n$ core(s) running a frequency $f$ (in Hertz), for total time $t$ (in seconds), to hash $m$ messages each $b$-byte, with each hash produced requiring $c$ cycles of one execution thread of one core of one CPU. It holds that $$u\cdot n\cdot f\cdot t=m\cdot c$$ Derivation: Left side is the number of cycles across all $u\cdot n$ cores, with $f\cdot t$ cycles for each core given frequency and time spent. Right side is the number of cycles $m\cdot c$ necessary to hash the messages, given how many messages there are, and how many cycles are required for each hash. They are equal due to the assumed "used to their full computing power", which can be closely met when $m\gg u\cdot n$ by splitting the messages evenly among the cores.
What the linked benchmark quotes is $c/b$ in cycles per byte, where cycles are those actually used by one thread running sequential code computing the hash. This quantity $c/b$ depends a lot on the algorithm, the CPU architecture, and the quality of the code (including fitness to the CPU, compiler..); on the value of $b$, especially when low (see below), which is why $c/b$ is given for several values of $b$; and seldom on the rest.
Note: Thread(s) running on a core have to share that core's $f\cdot t$ cycles. My understanding of the benchmarks quoted is that the number of threads per core is considered part of the CPU architecture; if that could be adjusted, e.g. to 1 or 2 at boot time, there would be separate benchmarks or/and the $c/b$ quoted would be the highest achieved.
Note: The benchmarks quoted, and the present answer, stick to fixed hash output size, e.g. 32-byte. SHAKE128 has variable-size output, and this could be an extra parameter.

Most practical hashes (including SHA-3/SHAKE) group bytes (after padding) into block of fixed size $B$-byte ($B=136$ for SHA3-256/SHAKE128), and have an iterated structure processing blocks sequentially. It follows that $c$ grows with $b$ approximately as $$c=c_0+c_1\lceil(b+b_0)/B\rceil$$ (ignoring cache and other effects), where $0\le b_0<B$ is a padding size in bytes ($b_0=1$ for all SHA-3), $c_0$ is a fixed overhead in cycles, $c_1$ is the number of extra cycles to hash an extra block (with $c_1<c_0$ for SHA-3), $\lceil x\rceil$ is rational $x$ rounded up to the next integer. The quantity $c/b$ reported by the benchmark is:

  • for small messages (up to $B-b_0$-byte), approximately $(c_0+c_1)/b$, decreasing quickly with $b$;
  • for large messages ($b\gg B)$, approximately $c_1/B$, largely independently of $b$.

Overall $c/b$ mostly lowers as $b$ increases (converging to some constant), but with initially noticeable sawtooth jumps.

c/b as a function of b


In an earlier question and comment to another, the OP mentions wanting to hash 40-bit messages and wondering to what degree that's vulnerable to brute force search of the message. Let's evaluate how much time the hashing (which dominates the effort) would require to cover the whole message space.

Messages are $\lceil40/8\rceil=5$-byte, thus the appropriate column of the quoted benchmark is for $b=8$-byte messages (giving the same $\lceil(b+b_0)/B\rceil=1$). With an Intel Core i7-7800X featuring $n=6$ cores running at $f=3.5\text{GHz}$, it was timed SHAKE128 at a median of $c/b=112.25$ cycles per byte. Hence with $u=1$ such CPU, the time to hash all $m=2^{40}$ messages is: $$t=\frac{m\cdot(c/b)\cdot b}{u\cdot n\cdot f}\approx\frac{2^{40}\cdot112\cdot8}{1\cdot6\cdot3.5\cdot10^9}\approx47000\text{s}\approx13\text{h}$$ Note: In this computation we used $b=8$ of the benchmark rather than $b=5$ for the number of bytes hashed, because we are trying to compute $c$ as $(c/b)\cdot b$ in a situation where $c$ is approximately independent of $b$. If we hashed a long message, we'd use the much lower $c/b$ benchmarked for that condition, and the $b$ for the message hashed, since we'd be in a situation where $c$ is approximately proportional to $b$. In between, we can compute the $(c/b)\cdot b$ quoted for the two benchmarks with the closest sizes, deduce the two corresponding $c$, and interpolate for our $b$ per a $c=c_0+c_1\lceil(b+b_0)/B\rceil$ model.
Note: The "Base" value of $f$ is what matters rather than the higher "Turbo", since the later can't be sustained for multiple cores, at least within manufacturer specs.

That search is easily feasible for an individual with a single computer. Further, a rainbow table would allow to make that computation only once, then invert any hash of a 40-bit message in seconds with e.g. a mobile phone.

The task is so easy that using CPU(s) is adequate (they are easiest to program). For larger attacks, after an initial coding effort, GPUs would be more effective on speed, or/and cost and energy (their superior performance comes from $n$ being many hundreds for each GPU). FPGAs and ultimately ASICs are even superior (they have potential to decrease both $c$ and additional investment per added hashing capacity, by exactly tailoring the circuitry to the task). That's how the aggregate of bitcoin miners gets a hash rate over $2^{82}$ SHA-256 hashes per day (May 2018, per that source reporting SHA256d hashes comprising two SHA-256).


Core i3 has a higher hash rate than Core i7 for SHAKE128

After noting that hash rate is in cycles/byte, that observation amounts to: in a comparison, a core of a CPU with a higher digit following "Core i" in its Intel marketing designation happens to have the desirable property of requiring less clock cycles than the other one.

This is far from a general rule, as (for the Intel x86 line) $c/b$ depends much more on how recent the CPU is. The stated difference is largely attributable to architectural improvements increasing IPC between Q1'11 when the Core i3 referenced was introduced, and Q2'17 when the Core i7 referenced was.

The values of $b$, $u$, $n$ and $f$ have more essential influence on hashing performance of a computer, which is $m/t=u\cdot n\cdot f/c$ hashes per second, with $c$ proportional to $b$ for large $b$.

$\endgroup$
  • $\begingroup$ Thank you so much for ur answer with a nice justification. Please one more thing, may you help me to understand how did you get this equation: (u * n * f * t = m * c ) based on what and is there any reference for this equation??? thanks again and wish to get your answer soon... $\endgroup$ – Al-Ani May 9 '18 at 13:02
  • $\begingroup$ @Al-Ani: I added a derivation of the formula. It is so basic in parallel computing and benchmarking that it generally goes unstated and is often missed! That's why I made this answer... $\endgroup$ – fgrieu May 9 '18 at 13:29
1
$\begingroup$

Summary from the linked webpage:

\begin{array}{l l l} \textbf{CPU} & \textbf{freq.} & \textbf{cpb} \text{(long)} & \textbf{cpb} \text{(4096 bytes)}\\ \text{i7-7800X} & 6 \times 3500\,\text{MHz} & 4.52 & 4.73 \\ \text{i3-2310M} & 2 \times 2100\,\text{MHz} & 9.23 & 9.40 \end{array}

Note that the "hashrate" is given in cycles per byte. This is because the "speed" of a hash is mostly linear in the amount of bytes; i.e., twice the amount of data takes twice the time. This is not true for short messages, where the setup time (initialization) of the hash function takes a more significant time.

You can see that when going from the long messages to smaller messages; the amount of cycles needed per byte goes up, since the initialization time gets divided by a smaller amount of bytes.

The cpb actually measure the time it takes per byte for the hash function. For the i3, this value is higher. This is not because it's "an i3" compared "an i7". It is because we're talking about a newer i7 versus an older i3 (seventh generation versus second generation). Indeed, the cpb value tries to measure the CPU architecture, not the tier, price, or clock. This makes comparisons between different CPUs and architectures possible.


Now, to go from cycles per byte to hashrate, you would need to invert the number, then multiply by the CPU frequency. For the i7 with long messages, you get $774\,$MB/s, for the i3 $228\,$MB/s.

$\endgroup$
  • 3
    $\begingroup$ Actually if you want to have a measure of the "hash rate" as in "hashes per second", you probably want to use the value for really short hashes, as this would indicate the OP is trying to brute-force a pre-image. $\endgroup$ – SEJPM May 8 '18 at 13:28
  • $\begingroup$ The cpbdoes not directly measure time it takes per byte for the hash function; rather, cycles (which is proportional). Further, the OP asks about hash rate per computer. Therefore the number of core(s) per CPU must be factored in: the benchmarks linked are not per CPU, but per core. Of course the number of CPUs per computer also matters. $\endgroup$ – fgrieu May 9 '18 at 2:25

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.