The research partners of Saphir initiated the conception of Shabal and were later joined by partners of the research project Saphir2 who actively contributed to the final design of Shabal. Saphir is an ANR funded project on hash functions. Saphir has started on March 2006 for a duration of three years and brought five partners together: Cryptolog International, DCSSI, France Telecom, Gemalto and LIENS. Partners of Saphir2 come from both industry and academia; in addition to partners of Saphir, 4 new partners: EADS SN, INRIA, Sagem Sécurité and UVSQ joined and contributed to the project.
History
Shabal was an entry in the NIST hash function competition, where it passed to the second round, but failed to enter the final round. Shabal was not selected as a finalist mainly due to security concerns. Although the security of the full hash algorithm was not compromised, the discovery of non-randomness properties with low time complexities raised concerns among NIST's cryptographers about the possibility of more powerful attacks in the future. The name of the algorithm was chosen as a tribute to Sébastien Chabal.
Description
Shabal uses a mode of operation that can be considered as a variant of a wide-pipe, Merkle–Damgård hash construction. The internal state of Shabal consists of three parts, denoted as A, B and C. The keyed permutation of Shabal updates A and B using nonlinear feedback shift registers that interact with each other. The main loop of the permutation uses modular multiplication by three and five, modular addition, XOR, complementation, and AND operations. The chaining mode of Shabal works as follows: ← PM,C ←, , where M is the message block, and W is the counter. After processing all message blocks, three finalization rounds are applied in which the message block and the counter values are fixed. Two tunable parameters are defined for Shabal, where p is the number of loops performed within the key permutation, and r is the size of A. The default value of is. Additionally, p and r should satisfy 16p ≡ 0 mod r. The same internal function is used for all output sizes of Shabal.
Output sizes of Shabal
Output sizes of Shabal, based on length of the digest are:
Various distinguishers have been proposed for the permutation of Shabal. Using cube testers, a statistical non-randomness property of Shabal's key permutation was described with time complexity 2300.
A rotational distinguisher to the keyed permutation of Shabal using 2171 calls was presented. The distinguisher is based on the observation that most of the operations in P preserve rotational relationships between inputs. However, the attack cannot be extended to the hash algorithm, due to the non-symmetric IV, the addition of the block counter and the existence of the finalization rounds.
Another distinguisher was presented, based on the observation that multiplication by three preserves the difference in the most significant bitwith probability one. Using this observation, the authors presented a method to find semi-equivalent keys for the keyed permutation. Under the related-key model, the authors also presented a method that distinguishes P from a random permutation using a single query. The method can be generalized to any security parameter. The authors also presented a method to find pseudo-collisions and pseudosecond-preimages for a variant of Shabal in which the number of iterations in the finalization is 24N, instead of 36. However, this attack does not work for the original Shabal, since it is not possible to cancel out the differences when the number of iterations is 36.
Some non-randomness properties were shown for the keyed permutation P that are easy to verify. The authors proposed a simple method to find fixed points in P. The inputs to the permutation were selected so that they are not affected by the loops in the permutation. The method is independent of the number of words in A and the number of rounds; therefore, the method works for any choice of the tunable security parameters. The authors also showed a way to construct many, large multi-collisions, where the only difference is in the key input.
A distinguisher was presented over some of the biased output bits using differential analysis with 223 data complexity.
A low weight pseudo-collision attack on the Shabal compression function with time complexity 284 was presented. A preimage attack with 2497 time and 2400memory complexity for Shabal 512 using security parameters.
None of the distinguishers directly threatens the claimed security of the hash algorithm. Moreover, the designers have modified the indifferentiability security proof of their chaining mode to require weaker assumptions than ideal ciphers.
