Boole is a cryptographic primitive that can be used as a hash function, message authentication code (MAC) and a synchronous stream cipher. Boole was designed in response to NISTs Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA3) Family, herein referred to as SHA-3.
The NIST submission as it was sent in is here.
I'd like to thank Tor Bjorstad from the University of Bergen for spotting a couple of errors in the specification for Boole. While they are minor in keystrokes, they are of course fundamentally important. The errata appear below.
Errata:
On page 7 section 3.2, describing cycling the register, in step 1, "for i=1..14" should be "for i = 0..14".
In figure 1 on page 6, the arrow leading from "rsum" to the register is one cell too far right. (If revising the paper, I would probably write text to explain the diagram too.)
In section 3.6, describing the nonlinear functions (in two places), "fourth-degree function of 5 bits of the input" should say "fourth-degree function of 9 bits of the input". Similarly, in the 64-bit case, "9 bits of the input" should say "26 bits of the input".
Revised paper and presentation are available.
Unfortunately Boole (as a hash function) is broken. Ivica Nikolic and his friends found an elegant preimage attack. Also Tomislav Nad, Florian Mendel and Martin Schlaeffer have found collisions for Boole-32 and the technique should scale to Boole-64 as well. The paper is not out yet.
A simple tweak to Boole (XORing the x-accumulator to R[8] during input) prevents the first attack, and complicates the second.
Clearly, though, the design was not robust enough for a hash function. I knew hash functions were hard, and these results rub my nose in it. So, despite having designed the tweak as an intellectual exercise, I consider Boole to be a dropout from the SHA-3 competition.
If you have comments, please send them to ggr@seer-grog.net
Greg Rose (ggr@seer-grog.net)