-1
$\begingroup$

I am considering how long a SHA-1 computation will need on modern CPU/GPU's. Just in case we are interested in brute forcing and consider the birthday paradoxon, then we need consider the SHA-1 output range of 160 (?) Bits.

The number of brute force attempts, until our attack is by 50% successful, requires $\left\lceil 1.18\cdot \sqrt{2^{160}} \right\rceil \sim 1.43 \cdot 10^{24}$ attemptions. How long would, say Intel's i3/5/7, require until this computations and comparisons are done?

The measure should be given in time per mega byte.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ So where are you stuck in calculations? $\endgroup$ – axapaxa Sep 18 '17 at 13:41
  • 1
    $\begingroup$ You know that this has been done, by an attack about ten thousand times cheaper than brute force? shattered.it (Now, of course, you can extend that collision by any suffix you want at essentially zero cost to get arbitrarily many other collisions.) $\endgroup$ – Squeamish Ossifrage Sep 18 '17 at 13:45
  • 1
    $\begingroup$ ...Also, how do you measure the answer to your question per megabyte? $\endgroup$ – Squeamish Ossifrage Sep 18 '17 at 13:46
  • 1
    $\begingroup$ @fgrieu Actually, cpb performance should be somewhat consistent across generations, because AFAIK only low-power server- / NAS-targeted CPUs (like Pentiums and Celerons) got SHA-EX. I'd guess Intel considered SHA not to be a concern on the Core i series and used the chip area in a better way. $\endgroup$ – SEJPM♦ Sep 18 '17 at 13:53
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because not enough research was done; even the assertion that the "birthday paradoxon" (sic) applies seems uncertain and hard to reconcile with a result "in time per mega byte", or at least unjustified. Reposted with fix of the error pointed out in SEJPM's comment. $\endgroup$ – fgrieu Sep 18 '17 at 14:00
3
$\begingroup$

SHA-1 runs at 2.24 cpb on an AMD Ryzen 1700 (at 2994MHz) for somewhat short messages (ie 576 bytes) which is a very relevant number given that you don't want to hash large messages, but many messages.

So for the full message you need a little less than 1300 cycles. So now suppose we have an optimized architecture / shorter messages and get this down to 1000 cycles per attempt.

You can now compute the speed yourself. In this case a Ryzen achieves $$8\cdot 2994\cdot 10^6/10^3\approx 24\cdot 10^6$$ attempts per second, that is, 24 million.

|improve this answer
$\endgroup$
  • $\begingroup$ If I validate that for a 4096 bit input message, I reach rounded $4\cdot 10^9$ years per birthday-attack. Is that right or did I did any mistake? The Ryzen-speed is $$R := 8\cdot 2994\cdot 10^6 c/s$$ (cycles per second) which leads to the measure $$A := R/(2\cdot 10^3)\ \left[ (c/s)(c/a)\right]= 4\cdot 2994\cdot 10^3 [a/s]\sim 12\cdot 10^6 [a/s]$$ (attemps per second) and this leads to the required time for brute forcing: $$T := 1.43\cdot 10^{24} / A\ \left[a/(a/s)\right] = 1.2 \cdot 10^{17} s \sim 4 \cdot 10^9\ years$$ $\endgroup$ – Shalec Sep 18 '17 at 14:41
  • $\begingroup$ If I'll do a parallelization of n Ryzen cards, it is $R\gets R^n$ through that computation? $\endgroup$ – Shalec Sep 18 '17 at 14:51
  • $\begingroup$ Oh.. I meant $R\gets n\cdot R$. $\endgroup$ – Shalec Sep 18 '17 at 15:00
  • $\begingroup$ @Shalec yes, using $n$ Ryzen CPUs in parallel should roughly linearly reduce the required time. $\endgroup$ – SEJPM♦ Sep 18 '17 at 18:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.