Network Working Group J. Park
Request for Comments: 4009 S. Lee
Category: Informational J. Kim
J. Lee
KISA
February 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 cipher and the key scheduling
algorithm (Section 2), the S-boxes (Appendix A), and a set of test
vectors (Appendix B).
1. Introduction1.1. SEED Overview
SEED is a 128-bit symmetric key block cipher that has been developed
by KISA (Korea Information Security Agency) and a group of experts
since 1998. SEED is a national standard encryption algorithm in
South 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.
Park, et al. Informational [Page 1]
RFC 4009 The SEED Encryption Algorithm February 2005
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 strong against known attacks
- Two 8x8 S-boxes
- Mixed operations of XOR and modular addition
SEED has been widely used in South Korea for confidential services
such as electronic commerce; e.g., financial services provided in
wired and wireless communication.
1.2. 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 left circular rotation by n bits
>> n right circular rotation by n bits
0x hexadecimal representation
2. The Structure of SEED
The input/output block size of SEED is 128-bit, and the key length is
also 128-bit. 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.
A pseudo code for the structure of SEED is as follows:
for (i = 1; i <= 16; i++)
{
L = R;
R = L ^ F(Ki, R);
}
Park, et al. Informational [Page 2]
RFC 4009 The SEED Encryption Algorithm February 20052.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:
- 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
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)]] + G[ 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 (= Z0 || Z1 || Z2 || Z3) of the function G with four 8-bit inputs
X (= X0 || X1 || X2 || X3) are as follows:
Z0 = {S1(X0) & m0} ^ {S2(X1) & m1} ^ {S1(X2) & m2} ^ {S2(X3) & m3}
Z1 = {S1(X0) & m1} ^ {S2(X1) & m2} ^ {S1(X2) & m3} ^ {S2(X3) & m0}
Z2 = {S1(X0) & m2} ^ {S2(X1) & m3} ^ {S1(X2) & m0} ^ {S2(X3) & m1}
Z3 = {S1(X0) & m3} ^ {S2(X1) & m0} ^ {S1(X2) & m1} ^ {S2(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(X)= {S1(X) & m3} || {S1(X) & m2} || {S1(X) & m1} || {S1(X) & m0}
SS1(X)= {S2(X) & m0} || {S2(X) & m3} || {S2(X) & m2} || {S2(X) & m1}
SS2(X)= {S1(X) & m1} || {S1(X) & m0} || {S1(X) & m3} || {S1(X) & m2}
SS3(X)= {S2(X) & m2} || {S2(X) & m1} || {S2(X) & m0} || {S2(X) & m3}
Park, et al. Informational [Page 3]
RFC 4009 The SEED Encryption Algorithm February 2005
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.
2.3. Key Schedule
The key schedule generates each round 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
The following table shows constants used in KCi:
i | Value i | Value
============================================
KC1 | 0x9e3779b9 KC2 | 0x3c6ef373
KC3 | 0x78dde6e6 KC4 | 0xf1bbcdcc
KC5 | 0xe3779b99 KC6 | 0xc6ef3733
KC7 | 0x8dde6e67 KC8 | 0x1bbcdccf
KC9 | 0x3779b99e KC10 | 0x6ef3733c
KC11 | 0xdde6e678 KC12 | 0xbbcdccf1
KC13 | 0x779b99e3 KC14 | 0xef3733c6
KC15 | 0xde6e678d KC16 | 0xbcdccf1b
Park, et al. Informational [Page 4]
RFC 4009 The SEED Encryption Algorithm February 2005
A pseudo code for the key schedule is as follows:
for (i = 1; i <= 16; i++)
{
Ki0 = G(Key0 + Key2 - KCi);
Ki1 = G(Key1 - Key3 + KCi);
if (i % 2 == 1)
Key0 || Key1 = (Key0 || Key1) >> 8;
else
Key2 || Key3 = (Key2 || Key3) << 8;
}
2.4. Decryption Procedure
Decryption procedure is the reverse step of the encryption procedure.
It can be implemented by using the encryption algorithm with reverse
order of the round subkeys.
2.5. SEED Object Identifiers
For those who may be using SEED in algorithm negotiation within a
protocol, or in any other context that may require the use of OIDs,
the following three OIDs have been defined.
algorithm OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) korea(410) kisa(200004) algorithm(1) }
id-seedCBC OBJECT IDENTIFIER ::= { algorithm seedCBC(4) }
seedCBCParameter ::= OCTET STRING -- 128-bit Initialization Vector
The id-seedCBC OID is used when the CBC mode of operation based on
the SEED block cipher is provided.
id-seedMAC OBJECT IDENTIFIER ::= { algorithm seedMAC(7) }
seedMACParameter ::= INTEGER -- MAC length, in bits
The id-seedMAC OID is used when the message authentication code (MAC)
algorithm based on the SEED block cipher is provided.
pbeWithSHA1AndSEED-CBC OBJECT IDENTIFIER ::=
{ algorithm seedCBCwithSHA1(15) }
PBEParameters ::= SEQUENCE {
salt OCTET STRING,
iteration INTEGER } -- Total number of hash iterations
Park, et al. Informational [Page 5]
RFC 4009 The SEED Encryption Algorithm February 2005
This OID is used when a password-based encryption in CBC mode based
on SHA-1 and the SEED block cipher is provided. The details of the
PBE computation are well described in Section 6.1 of [RFC2898].
3. Security Considerations
No security problem has been found on SEED. See [ISOSEED] and
[CRYPTREC].
4. References4.1. Normative References
[TTASSEED] Telecommunications Technology Association (TTA), "128-bit
Symmetric Block Cipher (SEED)", TTAS.KO-12.0004,
September, 1998 (In Korean)
http://www.tta.or.kr/English/new/main/index.htm
[RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography
Specification Version 2.0", RFC 2898, September 2000.
4.2. Informative References
[ISOSEED] ISO/IEC, ISO/IEC JTC1/SC 27 N 256r1, "National Body
contributions on NP 18033 Encryption algorithms in
response to document SC 27 N 2563", October, 2000
[CRYPTREC] Information-technology Promotion Agency (IPA), Japan,
CRYPTREC. "SEED Evaluation Report", February, 2002
http://www.kisa.or.kr/seed/seed_eng.htmlPark, et al. Informational [Page 6]
RFC 4009 The SEED Encryption Algorithm February 2005
Authors' Addresses
Jongwook Park
Korea Information Security Agency
78, Garak-Dong, Songpa-Gu, Seoul, 138-803
REPUBLIC OF KOREA
Phone: +82-2-405-5432
FAX : +82-2-405-5499
EMail: khopri@kisa.or.kr
Sungjae Lee
Korea Information Security Agency
Phone: +82-2-405-5243
FAX : +82-2-405-5499
EMail: sjlee@kisa.or.kr
Jeeyeon Kim
Korea Information Security Agency
Phone: +82-2-405-5238
FAX : +82-2-405-5499
EMail: jykim@kisa.or.kr
Jaeil Lee
Korea Information Security Agency
Phone: +82-2-405-5300
FAX : +82-2-405-5499
EMail: jilee@kisa.or.kr
Park, et al. Informational [Page 16]
RFC 4009 The SEED Encryption Algorithm February 2005
Full Copyright Statement
Copyright (C) The Internet Society (2005).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the IETF's procedures with respect to rights in IETF Documents can
be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Park, et al. Informational [Page 17]
