Hardware accelerated search for resource-efficient and secure permutation matrices

Permutation layer is a core component of substitution-permutation network block ciphers. Its design directly affects security and resource usage of the block cipher. It is a challenging problem to find permutation matrices with respect to predefined trade-off targets. In our work, we developed a hardware search engine on Xilinx Virtex-6 FPGA in order to accelerate the search of resource-efficient and secure (maximal branch number) 16 x 16 permutation matrices. Our engine completed the full spectrum search in 129 hours 48 minutes and found non-involutory and involutory permutation matrices with maximal branch number of 5 and minimum Hamming weight (HW) of 74 and 80, respectively. To the best of our knowledge, this is the first time that such a hardware accelerated custom search engine has been built and full spectrum permutation matrix search has been performed.