Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://link.springer.com/article/10.1007/s12095-009-0011-5 below:

A combinatorial analysis of recent attacks on step reduced SHA-2 family

We perform a combinatorial analysis of the SHA-2 compression function. This analysis explains in a unified way the recent attacks against reduced round SHA-2. We start with a general class of local collisions and show that the previously used local collision by Nikolić and Biryukov (NB) and Sanadhya and Sarkar (SS) are special cases. The study also clarifies several advantages of the SS local collision over the NB local collision. Deterministic constructions of up to 22-round SHA-2 collisions are described using the SS local collision and up to 21-round SHA-2 collisions are described using the NB local collision. For 23 and 24-round SHA-2, we describe a general strategy and then apply the SS local collision to this strategy. The resulting attacks are faster than those proposed by Indesteege et al using the NB local collision. We provide colliding message pairs for 22, 23 and 24-round SHA-2. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family.¹

This is a preview of subscription content, log in via an institution to check access.

Springer+ Basic

€34.99 /Month

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

1. Biham, E., Chen, R.: Near-collisions of SHA-0. In: Matthew Franklin, K. (ed.) Advances in Cryptology—CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, 15–19 August 2004, Proceedings. Lecture Notes in Computer Science, vol. 3152, pp. 290–305. Springer, New York (2004)

2. Chabaud, F., Joux, A.: Differential collisions in SHA-0. In: Krawczyk, H. (ed.) Advances in Cryptology—CRYPTO 1998, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, 23–27 August 1998, Proceedings. Lecture Notes in Computer Science, vol. 1462, pp. 56–71. Springer, New York (1998)

3. Damgård, I.: A design principle for hash functions. In: Brassard, G. (ed.): Advances in Cryptology—CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, 20–24 August 1989, Proceedings. Lecture Notes in Computer Science, vol. 435, pp. 416–427. Springer, New York (1990)

4. Dobbertin, H.: Cryptanalysis of MD4. In: Gollmann, D. (ed.) Fast Software Encryption. Lecture Notes in Computer Science, vol. 1039, pp 53–69. Springer, New York (1996)

   Google Scholar 

5. Dobbertin, H.: Cryptanalysis of MD4. J. Cryptol. 11(4), 253–271 (1998)

   Article  MATH  Google Scholar 

6. Gilbert, H., Handschuh, H.: Security analysis of SHA-256 and sisters. In: Matsui, M., Robert Zuccherato, J. (eds.) Selected Areas in Cryptography, 10th Annual International Workshop, SAC 2003, Ottawa, Canada, 14–15 August 2003, Revised Papers. Lecture Notes in Computer Science, vol. 3006, pp. 175–193. Springer, New York (2003)

7. Indesteege, S., Mendel, F., Preneel, B., Rechberger, C.: Collisions and other non-random properties for step-reduced SHA-256. In: Selected Areas in Cryptography, 15th Annual International Workshop, SAC 2008, Revised Papers, Sackville, 14–15 August 2008

8. Indesteege, S., Mendel, F., Preneel, B., Rechberger, C.: Collisions and other non-random properties for step-reduced SHA-256. Cryptology eprint Archive, April 2008. http://eprint.iacr.org/cgi-bin/versions.pl?entry=2008/131 (there are 7 versions dated 25 Mar, 27 Mar, 01 Apr, 08 Apr (2 versions), 14 Jul, 15 Jul) (2008)

9. Klima, V.: Tunnels in Hash Functions: MD5 Collisions Within a Minute. Cryptology ePrint Archive, Report 2006/105 (2006). http://eprint.iacr.org/

10. Mendel, F., Pramstaller, N., Rechberger, C., Rijmen, V.: Analysis of step-reduced SHA-256. In: Matthew Robshaw, J.B. (ed.) Fast Software Encryption, 13th International Workshop, FSE 2006, Graz, Austria, 15–17 March 2006, Revised Selected Papers. Lecture Notes in Computer Science, vol. 4047, pp. 126–143. Springer, New York (2006)

11. Mendel, F., Pramstaller, N., Rechberger, C., Rijmen, V.: Analysis of step-reduced SHA-256. Cryptology eprint Archive, March (2008) http://eprint.iacr.org/2008/130

12. Merkle, R.C.: One way hash functions and DES. In: Brassard, G. (ed.): Advances in Cryptology—CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, 20–24 August 1989, Proceedings. Lecture Notes in Computer Science, vol. 435, pp. 428–446. Springer, New York (1990)

13. Nikolić, I., Biryukov, A.: Collisions for step-reduced SHA-256. In: Nyberg, K. (ed.) Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, 26–28 March 2008. Lecture Notes in Computer Science, vol. 5086, pp. 1–16. Springer, New York (2008)

14. Sanadhya, S.K., Sarkar, P.: 22-step collisions for SHA-2. arXiv e-print archive, arXiv:0803.1220v1, March 2008. http://de.arxiv.org/abs/0803.1220 (dated 08 Mar) (2008)

15. Sanadhya, S.K., Sarkar, P.: New local collisions for the SHA-2 hash family. In: Nam, K.-H., Rhee, G. (ed.) Information Security and Cryptology—ICISC 2007, 10th International Conference, Seoul, Korea, 29–30 November 2007, Proceedings. Lecture Notes in Computer Science, vol. 4817, pp. 193–205. Springer, New York (2007)

16. Sanadhya, S.K., Sarkar, P.: Attacking reduced round SHA-256. In: Bellovin, S., Gennaro, R. (eds.) Applied Cryptography and Network Security—ACNS 2008, 6th International Conference, New York, NY, 03–06 June 2008, Proceedings. Lecture Notes in Computer Science, vol. 5037. Springer, New York (2008)

17. Sanadhya, S.K., Sarkar, P.: Attacking step reduced SHA-2 family in a unified framework. Cryptology ePrint Archive, Report 2008/271, 2008. http://eprint.iacr.org/ (dated Jun 12, and Jun 19) (2008)

18. Sanadhya, S.K., Sarkar, P.: Deterministic constructions of 21-step collisions for the SHA-2 hash family. In: Editors, editor, Information Security, 11th International Conference, ISC 2008, Taipei, Taiwan, September 2008, Proceedings. Lecture Notes in Computer Science. Springer, New York (2008)

19. Sanadhya, S.K., Sarkar, P.: New collision attacks against up to 24-step SHA-2 . In: Progress in Cryptology—INDOCRYPT 2008, 9th International Conference on Cryptology in India, Kharagpur, 14–17 December 2008

20. Sanadhya, S.K., Sarkar, P.: Non-linear reduced round attacks against SHA-2 Hash family. In: Mu, Y., Susilo, W. (eds.) Information Security and Privacy - ACISP 2008, The 13th Australasian Conference, Wollongong, Australia, 7–9 July 2008, Proceedings. Lecture Notes in Computer Science, vol. 5107. Springer, New York (2008)

21. Secure Hash Standard: Federal Information Processing Standard Publication 180-2. Department, U.S., of Commerce, National Institute of Standards and Technology(NIST) (2002). http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenot ice.pdf

22. Stevens, M., Lenstra, A.K., de Weger, B.: Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In: Naor, M. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4515, pp. 1–22. Springer, New York (2007)

    Google Scholar 

23. Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the Hash Functions MD4 and RIPEMD. In: Cramer, R. (ed.): Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494, pp. 1–18. Springer, New York (2005)

24. Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, 14–18 August 2005, Proceedings. Lecture Notes in Computer Science, vol. 3621, pp. 17–36. Springer, New York (2005)

25. Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.): Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494, pp. 19–35. Springer, New York (2005)

Download references

We would like to thank the reviewers for suggesting changes to improve the readability of the paper.

1. Applied Statistics Unit, Indian Statistical Institute, 203, B.T. Road, Kolkata, 700108, India

   Somitra Kumar Sanadhya & Palash Sarkar

Correspondence to Palash Sarkar.

¹This work builds upon and subsumes previous work [14, 18–20] done by us. Whereas the previous works focussed on obtaining collisions for a fixed number of rounds, the current work provides the combinatorial framework for understanding how such collisions arise.

Examples of colliding message pairs for 22, 23 and 24-round SHA-256 and SHA-512 using the standard IV are shown in Tables 16, 17, 18, 19, 20, 21, and 22.

The NB local collision has (w,x,y,z) = (1, − 1,0,0); δW _i  = 1, δW _i + 8 = − 1 and δW _j  = 0, for j = i + 4,i + 5,i + 6,i + 7. Here 8 ≤ i ≤ 10. The message word differences δW _i + 1, δW _i + 2 and δW _i + 3 are given by the following equations:

$$\left.\begin{array}{rcl} \delta W_{i+1} & = & -1 - \delta f_{IF}^{i}(1,0,0) - \delta \Sigma_1(e_i), \\ \delta W_{i+2} & = & - \delta f_{IF}^{i+1}(-1,1,0) - \delta \Sigma_1(e_{i+1}), \\ \delta W_{i+3} & = & - \delta f_{IF}^{i+2}(0,-1,1). \end{array}\right\} $$

(22)

Suppose that the NB local collision is placed between Step i and Step i + 8, i = 8,9,10; and it is desired to obtain a collision for i + 14 steps. Since the local collision ends at Step i + 8, from the differential path of the local collision in Table 4, we require the difference in the message word δW _i + 8 to be − 1.

The basic idea is to ensure that the message word differences are all zero after the local collision ends. This will ensure that the two messages will not introduce any difference in the registers. Therefore, δW _i + 9 = δW _i + 10 = ...= δW _i + 14 = 0. From Table 9 it follows that we require δσ ₁(δW _i + 8) + δW _i + 3 = 0 to ensure that δW _i + 10 = 0.

We now show for SHA-512, it is difficult to find values of δW _i + 3 and δσ ₁(W _i + 8) which are of the same order of magnitude. The values of δW _i + 3 are biased towards small magnitudes. In contrast, the values of σ ₁(W _i + 8) − σ ₁(W _i + 8 − 1) for SHA-512 are biased towards large magnitudes. This makes it difficult to achieve equality of the two terms as required to ensure δW _i + 10 = 0.

In the discussion that follows, we use X _i to denote the i ^th bit of a 64-bit quantity X. We also use the convention that the index of the least significant bit is 0.

\(Pr[ P_j \ne (P+1)_j] = 1/2^j\) , where the probability is taken over random P.

The necessary and sufficient condition for the j ^th bit of P and P + 1 to differ is that all the bits from 0 to (j − 1) in P are 1. This happens with probability 1/2^j, hence proved. □

If two numbers X and Y are such that \(X_i \ne Y_i\) and X _i − 1 = Y _i − 1 , then |X − Y| ≥ 2^i − 1 + 1.

Without loss of generality, suppose X _i  = 1 and Y _i  = 0. Let Z = X − Y. If Z _i  = 1, then clearly Z ≥ 2ⁱ and we are done.

So, suppose Z _i  = 0 and consider the process of binary subtraction of Y from X to obtain Z. Since X _i  = 1 and Y _i  = 0, the result Z _i  = 0 can happen only if the subtraction of Y _i − 1 Y _i − 2...Y ₀ from X _i − 1 X _i − 2...X ₀ produces a carry. But since X _i − 1 = Y _i − 1, this implies the following two things.

1. 1.

   Z _i − 1 = 1.

2. 2.

   The subtraction of Y _i − 2 Y _i − 3...Y ₀ from X _i − 2 X _i − 3... X ₀ produces a carry.

1. 1.

   Z _i − 1 = 1.

2. 2.

   The subtraction of Y _i − 2 Y _i − 3...Y ₀ from X _i − 2 X _i − 3... X ₀ produces a carry.

The second point implies that at least one bit of Z _i − 2 Z _i − 3... Z ₀ must be 1. This together with the first point Z _i − 1 = 1 implies that Z ≥ 2^i − 1 + 1. Hence proved. □

Next we prove that the probability that the absolute value of δW _i + 3, in the NB local collision is larger than 2^j is bounded above by 1/2^j − 1.

If the NB local collision is started at Step i, then \(Pr[|\delta W_{i+3}|\geq 2^j]<1/2^{j-1}\).

Since the local collision is started from step i, the message difference δW _i + 3 is given by (22). This equation gives:

$$\begin{array}{lll} \delta W_{i+3} &=& - \delta f_{IF}^{i+2}(0,-1,1), \\ &=& -f_{IF}(e_{i+2}, f_{i+2}-1, g_{i+2}+1) + f_{IF}(e_{i+2}, f_{i+2}, g_{i+2}), \\ &=& -f_{IF}(e_{i+2}, e_{i+1}-1, e_{i}+1) + f_{IF}(e_{i+2}, e_{i+1}, e_{i}). \end{array}$$

The two f _IF terms in the computation above have the same first argument e _i + 2. The second and the third arguments have a modular difference of ±1. If the j ^th bit of e _i + 2 is 1 then the two f _IF functions will select the corresponding bit from the middle argument, else from the third argument.

Let A = f _IF (e _i + 2, e _i + 1 − 1, e _i  + 1) and B = f _IF (e _i + 2, e _i + 1, e _i ). Further, let P _n be the event that \(A_n \ne B_n\). The event \(\delta W_{i+3} \ge 2^j\) can happen if and only if at least one of the bits j, j + 1, ...63 of δW _i + 3 is 1, i.e., if and only if at least one of the events P _j , P _j + 1, ...P ₆₃ holds.

Now we are ready to bound the probability of the required event. In the fourth step below, we use the fact that f _IF (a,b,c) = b if a = 1 and = c if a = 0.

$$\begin{array}{lll} Pr\left[\delta W_{i+3} \ge 2^j\right] &=& Pr \left[ \bigcup_{i \ge j} P_i \right] \\ &\le& \sum\limits_{i \ge j} Pr[P_i] \\ &=& \sum\limits_{i \ge j} ( Pr[(e_{i+2})_i = 0] \cdot Pr[P_i| ((e_{i+2})_i=0)] + Pr[(e_{i+2})_i = 1]\\ &&\cdot Pr[P_i| ((e_{i+2})_i=1)] )\\ &=& \sum\limits_{i \ge j}\left ( \frac{1}{2} \cdot Pr[(e_i+1)_i \ne e_i] \right . \left . + \frac{1}{2} \cdot Pr[(e_{i+1}-1)_i \ne e_{i+1}] \right ) \\ &=& \frac{1}{2} \cdot \sum\limits_{i \ge j} \left ( \frac{1}{2^{i}} + \frac{1}{2^{i}} \right ) ~~\mbox{(Using Proposition~2)}\\ &<& \frac{1}{2^{j-1}}. \end{array}$$

This proves the result. □

We now look at the distribution of values of σ ₁(W) − σ ₁(W − 1) for random choices of W.

For the function σ ₁ used in SHA-512,

$$ |\sigma_1(W) - \sigma_1(W-1)| \ge (2^{42}+2^{39}+2^{38}+2^{36}-2^3), $$

where W is any 64-bit word.

The function σ ₁ is defined for SHA-512 as:

$$ \sigma_1(W) = ROTR^{19}(W) \oplus ROTR^{61}(W) \oplus SHR^{6}(W). $$

(23)

Let the 64-bit word W be specified as (w ₆₃,w ₆₂, ..., w ₁,w ₀) where w ₀ is the least significant bit of W. Then σ ₁(W) can be expressed as bit-wise XOR of three quantities having bit pattern shown below.

Bit Index

63

62

...

58

57

...

45

44

...

0

ROTR ¹⁹

w ₁₈

w ₁₇

...

w ₁₃

w ₁₂

...

w ₀

w ₆₃

...

w ₁₉

ROTR ⁶¹

w ₆₀

w ₅₉

...

w ₅₅

w ₅₄

...

w ₄₂

w ₄₁

...

w ₆₁

SHR ⁶

0

0

...

0

w ₆₃

...

w ₅₁

w ₅₀

...

w ₆

Let W ^′ = W − 1. Then similar structure for \(\sigma_1(W^{\prime})\) can also be visualized. We are interested in the magnitude of \(\sigma_1(W) - \sigma_1(W^{\prime})\).

Let j be the least index such j ^th bit of W is 1. That is, w _j  = 1 and w _i  = 0 for all i ≤ j − 1. Then we have, \(w_i \ne w^{\prime}_i\) for i ≤ j and \(w_i = w^{\prime}_i\) for i > j. Now we consider two cases for j.

0 ≤ j ≤ 40. In this case, we have that \(w_i = w^{\prime}_i\) for i = 63, 51, 50, 42, 41 and \(w_0 \ne w^{\prime}_0\). From the structure of σ ₁(W) and \(\sigma_1(W^{\prime})\), we note that their 45^th bits will be unequal but their 44^th bits will be equal. Using Proposition 3 we get, \(|\sigma_1(W) - \sigma_1(W^{\prime})| \ge 2^{44}+1\).

j ≥ 41. We need to consider the individual cases j = 41, 42, ...63 here. Consider the case j = 41 first. In this case, we know the exact bit pattern in W and W ^′ up to 41 bits. Only the high order bits from 42 to 63 are unknown in these two quantities. We also know that these high order bits are the same in W and W ^′. Since these are only 22 bits, we can exhaustively search this space and compute the value \(|\sigma_1(W) -\sigma_1(W^{\prime})|\) for the case j = 41. As j is increased, the same idea can be used with even smaller search space. The size of the complete search space is 1 + 2 + 2² + ... + 2²² = 2²³ − 1. A C program running on an ordinary PC takes a fraction of a second to traverse this space.

Using exhaustive search, we found the minimum vale of |σ ₁(W) − σ ₁(W − 1)| to be 000004cffffffff8 which occurred for j = 42. This value is equal to (2⁴² + 2³⁹ + 2³⁸ + 2³⁶ − 2³).

We have left one particular case of W undiscussed. This is the special case when all the bits in W are zero. In this case, we can compute the difference directly since σ ₁(0) = 0 and \(\sigma_1(-1) = 1+2+\ldots +2^{57}\). Thus, we have the difference = 2⁵⁸ − 1.

Combining all the cases, the result is proved.

Sanadhya, S.K., Sarkar, P. A combinatorial analysis of recent attacks on step reduced SHA-2 family. Cryptogr. Commun. 1, 135–173 (2009). https://doi.org/10.1007/s12095-009-0011-5

Download citation

• Received: 20 November 2008

• Accepted: 24 February 2009

• Published: 19 March 2009

• Issue Date: September 2009

• DOI: https://doi.org/10.1007/s12095-009-0011-5

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.3