Energy-efficient bcrypt cracking

Bcrypt is a password hashing scheme based on the Blowfish block cipher. It was designed to be resistant to brute force attacks and to remain secure despite of hardware improvements.

Expensive key schedule with user-defined cost setting makes this hash slow while rapid random 32-bit lookups using Blowfish’s variable S-boxes require 4 KB of local memory per instance. This memory access pattern makes bcrypt moderately unfriendly to parallel implementation on modern CPUs, where on one hand gather addressing is required in order to exploit the CPUs’ SIMD capabilities, and on the other even when gather addressing is in fact available the L1 data cache size becomes the limiting factor.

Despite of this (and due to it), it is possible to achieve much better performance per Watt with hardware implementations of bcrypt, which holds true not only for ASICs, but also for certain many-core processor architectures and FPGAs.

Presenter: Katja Malvoni, student of Master in Computer Engineering (University of Zagreb).

Conference: PasswordsCon Bergen 2013.