A reconfigurable architecture for searching optimal software code to implement block cipher permutation matrices

Programming in embedded systems has always been a challenge. Highly-constrained nature of embedded devices invalidates conventional coding practices. The whole practice turns into a skill game that heavily depends on the personal skills and experience of the programmer. Embedded security applications are no exceptions. Efficient software implementation of symmetric cryptography primitives such as substitution or permutation layers is a hard task and no systematic approach exists. In this study, we propose an efficient reconfigurable hardware architecture to find the most optimal code for the realization of block cipher permutation layers on embedded microcontrollers. The proposed architecture is highly parallel and realized on two Xilinx Virtex-6 XC6VLX240T FPGAs. It operates on a limited set of instructions pertinent to implementation of linear matrices. Predetermined number of instructions is executed in a pipelined manner and the resultant output register contents are checked either for match to a target matrix or for certain cryptographic properties. The realized architecture uses instructions from 8-bit AVR instruction set. However, it can easily be modified to work with instruction sets of different processors. Using our parallel architecture, we have been able to find several good permutation layer matrices with branch number 4 that can be realized with only 8 instructions. We were able to search up to 11 instructions and cover matrices with branch number 6 as well.