INFORMATICA, 2009, Vol. 20, No. 1, 233423 2009 Institute of Mathematics and Informatics, VilniusKey-Dependent S-Box Generation in AES Block Cipher SystemKazys KAZLAUSKAS, Jaunius KAZLAUSKAS Institute of Mathematics and Informatics Akademijos 4, 08663 Vilnius, Lithuania e-mail: kazlauskktl.mii.ltReceived: June 2008; accepted: September 2008Abstract. Advanced Encryption Standard (AES) block cipher system is widely used in crypto- graphic applications. A nonlinear substitution operation is the main factor of the AES cipher sys- tem strength. The purpose of the proposed approach is to generate the random S-boxes changing for every change of the secret key. The fact that the S-boxes are randomly key-dependent and unknown is the main strength of the new approach, since both linear and differential cryptanalysis requireknown S-boxes. In the paper, we briefly analyze the AES algorithm, substitution S-boxes, linear and differential cryptanalysis, and describe a randomly key-dependent S-box and inverse S-box generation algorithm. After that, we introduce the independency measure of the S-box elements, and experimentally investigate the quality of the generated S-boxes.Keywords: advanced encryption standard, key-dependent S-boxes, generation algorithm.1. IntroductionCryptography has an important role in the security of data transmission and is the best method of data protection against passive and active fraud. The growing number commu- nicationusers has led to increasingdemand for security measures to protect data transmit- ted over open channels (Chen et al., 2008; Li et al., 2007; Sakalauskas, 2005). A cipher system is a set of reversible transformations from the set M of a plaintext into the set C of a ciphertext. Each transformation depends on a secret key and the ciphering algorithm. In the block cipher system, the plaintext is divided into the blocks and the ciphering is carried out for the whole block (El-Ramly et al., 2001). Two general principles of block ciphers are diffusion and confusion. Diffusion isspreading of the influence of a one plaintext bit to many ciphertext bits with intention to hide the statistical structure of the plaintext. Confusion is transformation that change dependence of the statistics of ciphertext on the statistics of plaintext. In most cipher sys- tems the diffusion and confusion is achieved by means of round repetition. Repeating a single round contributes to ciphers simplicity (Masuda et al., 2006). Modern block ci- phers consist of four transformations: substitution, permutation, mixing, and key-adding (Schneier, 1996; Menezes et al., 1997). Cryptographic objects are private key algorithms, public key algorithms and pseudo- random generators. Block ciphers transform usually the 128 or 256 bits string to a string24K. Kazlauskas, J. Kazlauskasof the same length under control of the secret key. Private key cryptography, such as DES (DES, 1977), 3DES, and Advanced Encryption Standard (AES) (AES, 2001), uses the same key for the sender and receiver to encrypt the plaintext and decrypt the ciphertext. Private key cryptography is more suitable for the encryption of a large amount of data. Public key cryptography, such as the Rivest-Shamir-Adleman (RSA) or Elliptic Curve al-gorithms, uses different keys for encryption and decryption. The AES algorithm defined by the National Institute of Standards and Technology of the United States has been ac- cepted to replace DES as the new private key encryption algorithm. AES overpass DES in improved security because of larger key sizes. AES is suitable for 8 bit microprocessor platforms and 32 bit processors (Su et al., 2003).Block cipher systems depend on the S-boxes, which are fixed and have no relation with the secret key. So only changeable parameter is the secret key. Since the only nonlin- ear component of AES is S-boxes, they are an important source of cryptographic strength. The use of key-dependent S-boxes in block cipher design has not been widely investi- gated in the literature. Research into S-box design has focused on determination of S-box properties which yield cryptographically strong ciphers, with the aim of selecting a small number of good S-boxes for use in a block cipher DES and CAST (Menezes et al., 1997).Some results have demonstrated that a randomly chosen S-box of sufficient size will have several of these desirable properties with high probability (Keliher, 2003). This paper outlines the work of the authors investigation into the design of a new pseudo-randomly generated key-dependent S-boxes. Other systems using key-dependentS-boxes have been proposed in the past, the most well-known is Blowfish (Schneier, 1996) and Khufu (Merkle, 1991). Each of these two systems uses the cryptosystem itself to generate the S-boxes. Preliminary results show, that our proposed algorithm has goodcryptographic strength, with the added benefit that is resistant to linear and differential cryptanalysis, which require that the S-boxes b