Near-Collisions for the Reduced Round Versions of Some Second Round SHA-3 Compression Functions Using Hill Climbing

2010-12-15
Turan, Meltem Soenmez
Uyan, Erdener
A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the second round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. Among the 130 possible reduced variants of Fugue-256, we practically observed collisions for 7 variants (e.g. (k, r, t) = (1, 2,5)) and near-collisions for 26 variants (e.g. 234/256 bit near-collision for (k, r, t) = (2,1,8)).

Suggestions

Statistical analysis of block ciphers and hash functions
Sulak, Fatih; Doğanaksoy, Ali; Department of Cryptography (2011)
One of the most basic properties expected from block ciphers and hash functions is passing statistical randomness testing, as they are supposed to behave like random mappings. Previously, testing of AES candidate block ciphers was done by using the statistical tests defined in the NIST Test Suite. As some of the tests in this suite require long sequences, data sets are formed by concatenating the outputs of the algorithms obtained from various input types. However, the nature of block cipher and hash functi...
Infinite length hash chains and their applications
Bicakci, K; Baykal, Nazife (2002-06-12)
Hash Chains are used extensively in various cryptography, applications such as one-time passwords, server-supported signatures and micropayments. In this paper, we present a method, called Infinite Length Hash Chains to improve the flexibility of this chaining idea by using public-key techniques. One of its distinguishing features is that communication and computation overhead of restarting of the system is avoided. For the owner of the chain it is possible to go in either way in the chain at any time witho...
Hyperspectral Image Classification via Basic Thresholding Classifier
Toksoz, Mehmet Altan; Ulusoy, İlkay (2016-07-01)
We propose a lightweight sparsity-based algorithm, namely, the basic thresholding classifier (BTC), for hyperspectral image (HSI) classification. BTC is a pixelwise classifier which uses only the spectral features of a given test pixel. It performs the classification using a predetermined dictionary consisting of labeled training pixels. It then produces the class label and residual vector of the test pixel. Since incorporating spatial and spectral information in HSI classification is quite an effective way...
Bit-Wise Unequal Error Protection for Variable-Length Block Codes With Feedback
Nakiboğlu, Barış; Zheng, Lizhong; Coleman, Todd P (2013-03-01)
The bit-wise unequal error protection problem, for the case when the number of groups of bits is fixed, is considered for variable-length block codes with feedback. An encoding scheme based on fixed-length block codes with erasures is used to establish inner bounds to the achievable performance for finite expected decoding time. A new technique for bounding the performance of variable-length block codes is used to establish outer bounds to the performance for a given expected decoding time. The inner and th...
Exit probabilities of markov modulated constrained random walks
Başoğlu Kabran, Fatma; Sezer, Ali Devin; Department of Financial Mathematics (2018)
Let X be the constrained random walk on Z2+ with increments (0, 0), (1, 0), (−1, 1), (0, −1) whose jump probabilities are determined by the state of a finite state Markov chain M. X represents the lengths of two queues of customers (or packets, tasks, etc.) waiting for service from two servers working in tandem; the arrival of customers occur with rate λ(Mk), service takes place at rates μ1(Mk), and μ2(Mk) where Mk denotes the current state of the Markov chain M. We assume that the average arrival rate is l...
Citation Formats
M. S. Turan and E. Uyan, “Near-Collisions for the Reduced Round Versions of Some Second Round SHA-3 Compression Functions Using Hill Climbing,” Hyderabad, India, 2010, vol. 6498, p. 131, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65262.