Network Working Group H.J. Lee Request for Comments: 4269 S.J. Lee Obsoletes: 4009 J.H. Yoon Category: Informational D.H. Cheon J.I. Lee KISA December 2005 The SEED Encryption Algorithm Status of This Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes the SEED encryption algorithm, which has been adopted by most of the security systems in the Republic of Korea. Included are a description of the encryption and the key scheduling algorithm (Section 2), the S-boxes (Appendix A), and a set of test vectors (Appendix B). This document obsoletes RFC 4009. Lee, et al. Informational [Page 1] RFC 4269 The SEED Encryption Algorithm December 2005 1. Introduction 1.1. Changes from RFC 4009 This specification obsoletes RFC 4009, because RFC 4009 had ambiguous function and SS-boxes definitions cryptographically. Thus, some definitions have been changed, and for better understanding, the SEED pseudo codes have been modified. This update is to provide clarity and facilitate the development of interoperable implementations. The SEED algorithm itself has not been changed. This specification updates RFC 4009 in the following areas: - Pseudo code changes. The pseudo code in Section 2 of RFC 4009 is insufficient for the explanation of the structure of SEED. Thus, detailed pseudo code is introduced. - Some corrections of errata, which are the definitions of R1', Z, X, and SS-boxes. 1.2. SEED Overview SEED is a 128-bit symmetric key block cipher that has been developed by KISA (Korea Information Security Agency) since 1998. SEED is a national standard encryption algorithm in the Republic of Korea [TTASSEED] and is designed to use the S-boxes and permutations that balance with the current computing technology. It has the Feistel structure with 16-round and is strong against DC (Differential Cryptanalysis), LC (Linear Cryptanalysis), and related key attacks, balanced with security/efficiency trade-off. The features of SEED are outlined as follows: - The Feistel structure with 16-round - 128-bit input/output data block size - 128-bit key length - A round function that is strong against known attacks - Two 8x8 S-boxes - Mixed operations of XOR and modular addition SEED has been widely used in the Republic of Korea for confidential services such as electronic commerce; e.g., financial services provided in wired and wireless communication. Lee, et al. Informational [Page 2] RFC 4269 The SEED Encryption Algorithm December 2005 1.3. Notation The following notation is used in the description of the SEED encryption algorithm: & bitwise AND ^ bitwise exclusive OR + addition in modular 2**32 - subtraction in modular 2**32 || concatenation > n right circular rotation by n bits 0x hexadecimal representation 2. The Structure of SEED The input/output block size of SEED is 128 bits, and the key length is also 128 bits. SEED has the 16-round Feistel structure. A 128-bit input is divided into two 64-bit blocks (L, R), and the right 64-bit block is an input to the round function F, with a 64-bit subkey Ki generated from the key schedule. L is the most significant 64 bits of 128-bit input, and R is the least significant 64 bits. A pseudo code for the structure of SEED is as follows: Input : (L, R) for i = 1 to 15 T = R; R = L ^ F(Ki, R); L = T; L = L ^ F(K16, R), R=R Output : (L, R) Where T is a temporary. 2.1. The Round Function F SEED uses two 8x8 S-boxes, permutations, rotations, and basic modular operations such as exclusive OR (XOR) and additions to provide strong security, high speed, and simplicity in its implementation. A 64-bit input block of the round function F is divided into two 32-bit blocks (R0, R1) and wrapped with 4 phases: Lee, et al. Informational [Page 3] RFC 4269 The SEED Encryption Algorithm December 2005 - A mixing phase of two 32-bit subkey blocks (Ki0, Ki1) - 3 layers of function G (see Section 2.2), with additions for mixing two 32-bit blocks Where R0 is the most significant 32 bits of R, and R1 is the least significant 32 bits. The outputs (R0', R1') of function F are as follows: R0' = G[ G[ G[(R0 ^ Ki0) ^ (R1 ^ Ki1)] + (R0 ^ Ki0)] + G[(R0 ^ Ki0) ^ (R1 ^ Ki1)]] + G[ G[(R0 ^ Ki0) ^ (R1 ^ Ki1)] + (R0 ^ Ki0)] R1' = G[ G[ G[(R0 ^ Ki0) ^ (R1 ^ Ki1)] + (R0 ^ Ki0)] + G[(R0 ^ Ki0) ^ (R1 ^ Ki1)]] 2.2. The Function G The function G has two layers: a layer of two 8x8 S-boxes and a layer of block permutation of sixteen 8-bit sub-blocks. The outputs Z (= Z3 || Z2 || Z1 || Z0) of the function G with four 8-bit inputs X (= X3 || X2 || X1 || X0) are as follows: Z0 = {S0(X0) & m0} ^ {S1(X1) & m1} ^ {S0(X2) & m2} ^ {S1(X3) & m3} Z1 = {S0(X0) & m1} ^ {S1(X1) & m2} ^ {S0(X2) & m3} ^ {S1(X3) & m0} Z2 = {S0(X0) & m2} ^ {S1(X1) & m3} ^ {S0(X2) & m0} ^ {S1(X3) & m1} Z3 = {S0(X0) & m3} ^ {S1(X1) & m0} ^ {S0(X2) & m1} ^ {S1(X3) & m2} where m0 = 0xFC, m1 = 0xF3, m2 = 0xCF, and m3 = 0x3F. To increase the efficiency of G function, four extended S-boxes "SS-box" (see Appendix A.2) are defined as follows: SS0(X0)= {S0(X0)& m3} || {S0(X0)& m2} || {S0(X0)& m1} || {S0(X0)& m0} SS1(X1)= {S1(X1)& m0} || {S1(X1)& m3} || {S1(X1)& m2} || {S1(X1)& m1} SS2(X2)= {S0(X2)& m1} || {S0(X2)& m0} || {S0(X2)& m3} || {S0(X2)& m2} SS3(X3)= {S1(X3)& m2} || {S1(X3)& m1} || {S1(X3)& m0} || {S1(X3)& m3} New G function, Z, can be defined as follows: Z = SS0(X0) ^ SS1(X1) ^ SS2(X2) ^ SS3(X3) This new G function is faster than the original G function but takes more memory to store four SS-boxes. Lee, et al. Informational [Page 4] RFC 4269 The SEED Encryption Algorithm December 2005 2.3. Key Schedule The key schedule generates each round's subkeys. It uses the function G, addition in modular 2**32, subtraction in modular 2**32, and (left/right) circular rotation. A 128-bit input key is divided into four 32-bit blocks (Key0, Key1, Key2, Key3). The two 32-bit subkeys of the ith round, Ki0 and Ki1, are generated as follows: - Type 1 : Odd round Ki0 = G(Key0 + Key2 - KCi) Ki1 = G(Key1 - Key3 + KCi) Key0 || Key1 = (Key0 || Key1) >> 8 - Type 2 : Even round Ki0 = G(Key0 + Key2 - KCi) Ki1 = G(Key1 - Key3 + KCi) Key2 || Key3 = (Key2 || Key3) > 8 else Key2 || Key3 = (Key2 || Key3)