Masking is a class of well-known countermeasure against side-channel attacks by employing the idea of secret sharing. In this paper, we propose a generic table recomputation-based masking scheme at any chosen order t, named divided S-box masking (DSM), and its security has been proved under the security framework from Crypto 2003. The table recomputation-based masking is suitable for software implementation and the masked table can be stored in memory, where it can be accessed fast. For any input, DSM scheme generates n output shares by two queries. DSM scheme requires two vectors L and R, and a matrix M of random numbers. Each element of L is the XOR result of the output of S-box and n - 1 random numbers. These n - 1 random numbers are stored in two lines of M and R which is a vector of indexes for the second query. Furthermore, we performed the attacks on the software implementation of DSM to evaluate its practical security, and compared the timing and space complexity with the existing table recomputation-based masking in the same platform to verify the advantage of the DSM.

SUMMARY The recent cryptanalysis on block ciphers has two major trends. Side channel analysis (SCA) has become a new threat to the hardware implementations of encryption algorithms. On the other hand, reverse engineering has been adopted to explore the unknown part of the encryption algorithms, which has become a new target of the cryptanalysis. Some drawbacks have been found in the existing methods of reverse engineering, which target on the special structures or utilize the flaws in the unknown parts. The major disadvantage is that the number of rounds to be analyzed is limited, and the complexity is high. The existing SCAs for reverse engineering depend on the leakage models in a large extent and mainly focus on the single component of the algorithms, whereas the other parts of the target algorithm are known. In this paper, we present a more general and feasible reverse analysis by combining the mathematical methods and the SCA methods. We use the strict avalanche criterion for the non‐linear operations of block ciphers and apply the power analysis to reverse the structure parameters. We propose a new reverse analysis method to reduce the dependency on the leakage models, which can be combined with the structural cryptanalysis to reverse the internal parameters of the linear and non‐linear operations. We finally achieve the reverse analysis on the unknown round function of block ciphers. Copyright © 2013 John Wiley & Sons, Ltd.