Rectangle Attacks on Reduced Versions of the FBC Block Cipher

The FBC block cipher is an award-winning algorithm of the recent Cryptographic Algorithm Design Competition in China, which has three versions: FBC128-128 with a 128-bit block size and a 128-bit key size, FBC128-256 with a 128-bit block size and a 256-bit key size, and FBC256 with a 256-bit block size and a 256-bit key size. The best previously published cryptanalysis results on FBC are an impossible differential attack on 13-round FBC128-128 and a boomerang attack on 13-round FBC128-256. In this paper, we exploit a 12-round rectangle distinguisher with probability \(2^{-234}\) of FBC128 and a 16-round rectangle distinguisher with probability \(2^{-448}\) of FBC256, and observe that preliminary satisfying ciphertext quartets can be efficiently filtered out by sorting plaintext pairs according to some nibble positions at the ciphertext side during key-recovery phase, and finally we mount rectangle attacks on 14-round FBC128-128, 15-round FBC128-256 and 19-round FBC256 to recover their respective user key. Our attacks break more rounds than any previously published attacks on FBC.