Search framework for neutral bits and boomerangs in SHA‐1 collision attacks

Abstract

Abstract Neutral bits and boomerangs are key techniques for accelerating collision search in SHA‐1 attacks. The current acceleration techniques for SHA‐1 near‐collision attacks are reviewed and a generic search framework for neutral bits and boomerangs is presented. The framework can efficiently construct auxiliary paths for a given differential path and message bit relations and find and store ideal boomerangs. The framework was applied to free‐start attacks for 76‐step SHA‐1, and the complexity was reduced from 250.25 ${2}^{50.25}$ to 247.9 ${2}^{47.9}$. Relaxing the boomerang's restrictions on message words, the authors propose an accelerating technique termed semi‐boomerangs, combined with the search framework of boomerangs, which increases the speed of collision search by 3.48 times in a free‐start attack for 80‐step SHA‐1 and the complexity for 80‐step attack was reduced from 257.5 ${2}^{57.5}$ to 255.7 ${2}^{55.7}$.

Keywords

• collision attack
• cryptography
• message searching
• SHA‐1