Towards the Development of Stronger S-Box
No Thumbnail Available
Date
2013-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
The heart of symmetric block cipher is the F function. This function relies on the use of the Sbox.
Therefore S-box should be constructed to be strong against cryptanalytic attack. One
characteristics of strong S-box is nonlinearity that is the difficulty to approximate S-box by a set
of linear equation. This thesis presents the design of stronger S-box using an optimized dynamic
hill climbing method.
Boolean functions have application in a variety of systems; including block ciphers, stream
ciphers and hash functions. In particular in block cipher it is applicable in S-box development.
The strengths of both Boolean function and S-box are able to provide a cipher with strong
properties to resist known and potential cryptanalytic attacks. Thus, in order to get a desirable
measure we work on the cryptographic properties of Boolean function and S-box.
The main cryptographic properties required by strong Boolean functions and S-boxes are
nonlinearity, autocorrelation, algebraic order, Strict Avalanche Criteria, Avalanche and Bit
independency with different cryptographic applications requiring different acceptable measures
of these and other properties. As combinations of cryptographic properties exhibited by functions
can be conflicting, finding cryptographically strong functions often means that a trade-off needs
to be made when optimizing property values.
This thesis focused on obtaining stronger S-box by customizing one of the heuristic Boolean
function optimization method named as Dynamic Hill Climbing. Dynamic hill climbing method
is efficient in optimizing one or more cryptographic properties of a single Boolean function, but
strength of individual Boolean functions may not lead to strong S-box. Thus, we optimized the
Dynamic Hill Climbing method to get both stronger Boolean functions for cryptographic
application and S-box. The Optimized Dynamic Hill Climbing method and the overall value of
Optimized Dynamic Hill Climbing method in optimizing S-box is clearly presented in this thesis.
Therefore, 15 S-boxes are generated using the customized Dynamic Hill Climbing algorithm to
optimize the nonlinearity of S-box. The newly generated S-boxes are tested and compared with
Advanced Encryption Standard, Camellia, Hierocrypt and Skipjack. As result, we have found Sboxes
with nonlinearity 102.
Keywords: Boolean function, S-box, nonlinearity, algebraic order, autocorrelation
Description
Keywords
Boolean Function; S-Box, Nonlinearity; Algebraic Order; Autocorrelation