Independent Submission S. Kiyomoto Request for Comments: 7008 W. Shin Category: Informational KDDI R&D Laboratories, Inc. ISSN: 2070-1721 August 2013
A Description of the KCipher-2 Encryption Algorithm
Abstract
This document describes the KCipher-2 encryption algorithm. KCipher-2 is a stream cipher with a 128-bit key and a 128-bit initialization vector. Since the algorithm for KCipher-2 was published in 2007, security and efficiency have been rigorously evaluated through academic and industrial studies. As of the publication of this document, no security vulnerabilities have been found. KCipher-2 offers fast encryption and decryption by means of simple operations that enable efficient implementation. KCipher-2 has been used for industrial applications, especially for mobile health monitoring and diagnostic services in Japan.
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.
This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc7008.
Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
KCipher-2 is a stream cipher that uses a 128-bit secret key and a 128-bit initialization vector. Since the algorithm for KCipher-2 was published in 2007 [SASC07], it has been evaluated in academic and industrial studies. The security and performance of KCipher-2 have been rigorously evaluated by its developers and other institutions [SECRYPT07] [ICETE07] [CRYPTEC] [SIIS11]. As of the publication of this document, no attack on KCipher-2 has been successful. KCipher-2 can be efficiently implemented in software to provide fast encryption and decryption, owing to its uncomplicated design. Only four simple operations are used: exclusive-OR, addition, shift, and table lookup. When the algorithm is implemented in hardware, internal computations can be parallel to yield greater efficiency. Moreover, since its internal state representation only amounts to several hundred bits, KCipher-2 is suitable for resource-limited environments. KCipher-2 has been actively used in several industrial applications in Japan, has been published by an international standardization body (ISO/IEC 18033-4 [ISO18033]), and has been designated a Japanese e-Government recommended cipher [CRYPTECLIST].
In this section, we describe the internal components of KCipher-2 and define the operations for deriving key streams from an input key and an initialization vector. We illustrate the detailed operations, mostly in pseudocode format, but also provide code snippets written in the C language syntax when necessary.
All values in this document are stored in big-endian order (aka network byte order). We use the following notations in the description of KCipher-2.
^ Bitwise exclusive-OR
n#m mth power of n
+n Integer addition modulo 2#n
<<_r n n-bit left circular shift in an r-bit register
0x Hexadecimal representation
E[i] The (i + 1)th element of E when E is composed of consecutive multiple elements
GF Galois field. GF(n#m) means the finite field of exactly n#m elements
** Multiplication of elements on the finite field GF(2#32)
NOTE: Many texts denote "the mth power of n" by "n^m", but we write it using '#', instead of '^', to avoid reader confusion with the power operator and the XOR operator of the C language syntax.
The internal state of KCipher-2 can be denoted by S. The internal state consists of six sub-components: two feedback shift registers, FSR-A and FSR-B, and four internal registers, L1, R1, L2, and R2. We, therefore, often write S = (A, B, L1, R1, L2, R2), where A and B refer to FSR-A and FSR-B, respectively.
The two feedback shift registers (FSRs) are separately called Feedback Shift Register A (FSR-A) and Feedback Shift Register B (FSR-B). FSR-A is composed of five 32-bit units that are consecutively arranged. Each unit can be identified by A[0], A[1], A[2], A[3], and A[4]. Likewise, FSR-B is composed of eleven consecutive 32-bit units, B[0], ..., B[10]. All values stored in each 32-bit unit of FSR is in GF(2#32).
Besides FSR, KCipher-2 has four internal registers to store intermediate computation results during operation. The four registers are named L1, R1, L2, and R2.
Three major operations constitute the behavior of KCipher-2: init(), next(), and stream(). The init() operation initializes the internal values of the system. The next() operation derives new values of S' from the values of S, where S' and S refer to the internal state. The stream() operation derives a key stream from the current state S.
The next() operation takes the current state S = (A, B, L1, R1, L2, R2) as input. The size of the input amounts to twenty of the 32-bit units in total (five units for A, eleven for B, and one for L1, R1, L2, and R2). It produces the next state S' = (A', B', L1', R1', L2', R2'). This operation is mainly used to generate secure key streams by applying non-linear functions (NLFs) for every cycle of KCipher-2. Additionally, it is used to initialize the system. The behaviors are distinguished by the input parameter that indicates the operation modes.
Inside the next() operation, the internal registers are updated by the result of the substitution function described in Section 2.4.2. The feedback shift registers are also updated by feedback functions. The feedback functions include the multiplication of register units and the fixed elements a0, a1, a2, and a3 in a finite field. The fixed elements a0, ..., a3 are carefully chosen to provide the maximum length of the feedback shift registers. The theory behind the selection of fixed elements and the way to simplify the necessary multiplications are briefly described in Section 2.4.4.
The operation takes the following inputs:
o S = (A, B, L1, R1, L2, R2)
o mode = {INIT, NORMAL}, where INIT means the operation is used for initialization, and NORMAL means it is used for generating secure key streams.
The init() operation takes a 128-bit key (K) and a 128-bit initialization vector (IV) and prepares the values of the state variables for generating key streams.
o K = (K[0], K[1], K[2], K[3]), where each K[i] is a 32-bit unit and 0 <= i <= 3
o IV =(IV[0], IV[1], IV[2], IV[3]), where each IV[i] is a 32-bit unit and 0 <= i <= 3,
and the output is an initialized state S, which will be referenced as S(0). The output is derived from the following steps:
1. Expand K to the 384-bit internal key IK = (IK[0], ..., IK[11]), where IK[i] is a 32-bit unit and 0 <= i <= 11. The expansion procedure is as follows:
for m from 0 to 11 if m is 0, 1, 2, or 3: IK[m] = K[m]; else if m is 5, 6, 7, 9, 10, or 11: IK[m] = IK[m - 4] ^ IK[m - 1]; else if m is 4: IK[4] = IK[0] ^ sub_K2(IK[3] <<_32 8) ^ (0x01, 0x00, 0x00, 0x00); else if m is 8: IK[8] = IK[4] ^ sub_K2(IK[7] <<_32 8) ^ (0x02, 0x00, 0x00, 0x00);
Kiyomoto & Shin Informational [Page 7]
RFC 7008 A Description of KCipher-2 August 2013
NOTE: sub_K2 is the substitution function described in Section 2.4.2.
2. Initialize the feedback shift registers and the internal registers using the values of IK and IV as follows:
sub_K2() is a substitution function that is a permutation of GF(2#32), based on components from the Advanced Encryption Standard (AES) [FIPS-AES]. Its input is a 32-bit value divided into four 8-bit strings. Inside sub_K2(), an 8-to-8-bit substitution function, S_box(), is applied to each 8-bit string separately, and then a 32- to-32-bit linear permutation is applied to the whole 32-bit string. Our S_box() function is identical to the S-Box operation of AES, and our linear permutation is identical to the AES Mix Column operation.
Consider the input of sub_K2 as a 32-bit value W = (w[3], w[2], w[1], w[0]), where each subelement of w is an 8-bit unit. Prepare two 32-bit temporary storages, T = (t[3], t[2], t[1], t[0]) and Q = (q[3], q[2], q[1], q[0]), where t[i] and q[i] are 8-bit units and 0 <= i <= 3.
The 32-bit output Q is obtained from the following procedures:
1. Apply S_box() to each 8-bit input string. Note that S_box() is defined in Section 2.4.3.
for m from 0 to 3 t[m] = S_box(w[m]);
2. Calculate q by the matrix multiplication, Q = M * T in GF(2#8) of the irreducible polynomial f(x) = x#8 + x#4 + x#3 + x + 1, where
where GF_mult_by_2 and GF_mult_by_3 are multiplication functions in GF(2#8), defined as follows:
o The function GF_mult_by_2(t) multiplies 2 by the given 8-bit value t in GF(2#8) and returns an 8-bit value q as follows (lq is a temporary 32-bit variable):
lq = t << 1; if ((lq & 0x100) != 0) lq ^= 0x011B; q = lq ^ 0xFF;
o The function GF_mult_by_3(t) multiplies 3 by the given 8-bit value t in GF(2#8) and returns an 8-bit value q as follows (lq is a temporary 32-bit variable):
FSR-A and FSR-B are word-oriented linear feedback shift registers (LFSRs). In the next() operation of Section 2.3.1, the feedback functions to the two LFSRs are shown, which include multiplication of fixed elements a0, a1, a2, or a3 in GF(2#32). The fixed elements are carefully chosen to maximize the period of the key stream generated by the two registers. Here, we briefly explain how we obtain the fixed elements. Further details and theories can be found in [SECRYPT07].
We obtain a0 as follows. First, to guarantee that the period is maximized for an 8-bit unit, we consider p as the root of the primitive polynomial:
x#8 + x#7 + x#6, + x + 1 in GF(2).
Therefore, an 8-bit string y = (y7, ..., y0), where y7 is the most significant bit, can be written as:
y = y7(p#7) + y6(p#6) + ... + y1(p) + y0
Next, a0 is the root of irreducible polynomial of degree four:
respectively. The feedback polynomial to FSR-B that uses a1, a2, and a3 can produce the maximum-length period. The feedback polynomials to FSR-A and FSR-B are as written in Step 2 of the next() operation, and the mathematical notations of these polynomials can also be found in [SECRYPT07].
Calculation of the original feedback polynomials might be time- consuming because it includes multiplications in finite fields. However, these multiplications can be done faster if the multiples of a0, ..., a3 were already calculated for all possible inputs. The tables of amul0, ..., amul3 in Appendix A provide such pre- calculation results. As shown in Step 2 of next(), we can utilize these tables to finish the necessary calculations efficiently.
For example, consider the input as a 32-bit value w, which represents an element of GF(2#32). The 32-bit output string w' = a0 ** w can be obtained using the amul0 table in Appendix A.1 as follows:
w' = (w << 8) ^ amul0[w >> 24];
Likewise, multiplications of (a1 ** w), (a2 ** w), and (a3 ** w) can be obtained in the same way, simply by using the amul1, amul2, and amul3 tables that we provide in Appendixes A.2, A.3, and A.4.
Eventually, Step 2 of the next() operation, which updates A'[4] and B'[10], can be written in the C language syntax as follows. Note that nA[4] and nB[10] correspond to A'[4] and B'[10], respectively, and temp1 and temp2 are 32-bit variables.
In this section, we use the notation S(i) to specifically reference the values of the internal state at i (where i >= 0), which is an arbitrary, discrete temporal moment (aka cycle) after the initialization.
Given a 128-bit key K, a 128-bit initialization vector (IV), KCipher-2 is initialized as follows:
S(0) = init(K, IV);
where S(0) is a state representation. With an initialized state S(i), where i >= 0, a 64-bit key stream X(i) can be obtained using the stream() operation, as follows:
X(i) = stream(S(i));
To generate a new key stream X(i + 1), use the next() operation and the stream() operation as follows:
Given a 64-bit message block M and a key stream X, an encrypted message E is obtained by
E = M ^ X;
Conversely, the decrypted message D is obtained by
D = E ^ X;
The original message M and the decrypted message D are identical when the same key stream is used.
3. Security Considerations
We recommend reinitializing and rekeying after 2#58 cycles of KCipher-2, which means after generating 2#64 key stream bits. It is important to make sure that no IV is ever reused under the same key.
[FIPS-AES] National Institute of Standards and Technology, "Advanced Encryption Standard (AES)", FIPS PUB 197, November 2001, <http://csrc.nist.gov/publications/ fips/fips197/fips-197.pdf>.
Appendix B. A Simple Implementation Example of KCipher-2
We provide an example implementation of KCipher-2 written in C. The implementation is simple; we do not consider storage or time complexity, nor do we consider software engineering-related issues, such as encapsulation, modularity, and so on.
B.1. Code Components I - Definitions and Declarations
#include <stdio.h> #include <stdint.h>
#define INIT 0 #define NORMAL 1
void init (unsigned int *, unsigned int *); void next(int); void stream (unsigned int *, unsigned int *);
static const uint8_t S_box[256] = { ... // as defined in Section 2.4.3 };
static const uint32_t amul0[256] = { ... // as defined in Appendix A.1 };
static const uint32_t amul1[256] = { ... // as defined in Appendix A.2 };
static const uint32_t amul2[256] = { ... // as defined in Appendix A.3 };
static const uint32_t amul3[256] = { ... // as defined in Appendix A.4 };
/* Global variables */
// State S uint32_t A[5]; // five 32-bit units
Kiyomoto & Shin Informational [Page 22]
RFC 7008 A Description of KCipher-2 August 2013
uint32_t B[11]; // eleven 32-bit units uint32_t L1, R1, L2, R2; // one 32-bit unit for each
// The internal key (IK) and the initialization vector (IV) uint32_t IK[12]; // (12*32) bits uint32_t IV[4]; // (4*32) bits
/** * Do multiplication in GF(2#8) of the irreducible polynomial, * f(x) = x#8 + x#4 + x#3 + x + 1. The given parameter is multiplied * by 2. * @param t : (INPUT). 8 bits. The number will be multiplied by 2 * @return : (OUTPUT). 8 bits. The multiplication result */ uint8_t GF_mult_by_2 (uint8_t t) { uint8_t q; uint32_t lq;
lq = t << 1; if ((lq & 0x100) != 0) lq ^= 0x011B; q = lq ^ 0xFF;
return q; }
/** * Do multiplication in GF(2#8) of the irreducible polynomial, * f(x) = x#8 + x#4 + x#3 + x + 1. The given parameter is multiplied * by 3. * @param t : (INPUT). 8 bits. The number will be multiplied by 3 * @return : (OUTPUT). 8 bits. The multiplication result */ uint8_t GF_mult_by_3 (uint8_t t) { uint8_t q; uint32_t lq;
// m = 4 ... 11, but not 4 nor 8 IK[9] = IK[5] ^ IK[8]; IK[10] = IK[6] ^ IK[9]; IK[11] = IK[7] ^ IK[10]; }
/** * Set up the initial state value using IK and IV. See Step 2 of * init() in Section 2.3.2. * @param key[4] : (INPUT), (4*32) bits * @param iv[4] : (INPUT), (4*32) bits * @modify S : (OUTPUT), (A, B, L1, R1, L2, R2) */ void setup_state_values (uint32_t *key, uint32_t *iv) { // setting up IK and IV by calling key_expansion(key, iv) key_expansion(key, iv);
// setting up the internal state values A[0] = IK[4]; A[1] = IK[3]; A[2] = IK[2]; A[3] = IK[1]; A[4] = IK[0];
/** * Initialize the system with a 128-bit key (K) and a 128-bit * initialization vector (IV). It sets up the internal state value * and invokes next(INIT) iteratively 24 times. After this, * the system is ready to produce key streams. See Section 2.3.2. * @param key[12] : (INPUT), (4*32) bits * @param iv[4] : (INPUT), (4*32) bits * @modify IK : (12*32) bits, by calling setup_state_values() * @modify IV : (4*32) bits, by calling setup_state_values() * @modify S : (OUTPUT), (A, B, L1, R1, L2, R2) */ void init (uint32_t *k, uint32_t *iv) { int i;
Kiyomoto & Shin Informational [Page 25]
RFC 7008 A Description of KCipher-2 August 2013
setup_state_values(k, iv);
for(i=0; i < 24; i++) { next(INIT); } }
/** * Non-linear function. See Section 2.4.1. * @param A : (INPUT), 8 bits * @param B : (INPUT), 8 bits * @param C : (INPUT), 8 bits * @param D : (INPUT), 8 bits * @return : (OUTPUT), 8 bits */ uint32_t NLF (uint32_t A, uint32_t B, uint32_t C, uint32_t D ) { uint32_t Q;
Q = (A + B) ^ C ^ D;
return Q; }
/** * Derive a new state from the current state values. * See Section 2.3.1. * @param mode : (INPUT) INIT (= 0) or NORMAL (= 1) * @modify S : (OUTPUT) */ void next (int mode) { uint32_t nA[5]; uint32_t nB[11]; uint32_t nL1, nR1, nL2, nR2; uint32_t temp1, temp2;
C.2. Another Key Stream Generation with the State Values
In this section, the initialization procedure and the key stream generation are illustrated in detail. The given 128-bit key (K) and the 128-bit initialization vector (IV) are as follows:
To complete the initialization, the next() operation is applied to the state values 24 times (in Section 2.3.2, Step 3). Let us denote each repeated application of the next() operation by init(i), where 1 <= i <= 24. The internal state values resulting from each init(i) are shown in Appendixes C.2.1 - C.2.24.
Note that the result of init(24) is also referred to as S(0) (in Section 2.3.2). Since the state is S(0), the stream() operation (in Section 2.3.3) can be applied and generate key streams.
Key stream at S(0) : 9FB6B580A6A5E7AF
Henceforth, a new key stream can be produced by 1) obtaining a new state by applying the next() operation to the current state, and 2) generating a new key stream by applying the stream() operation to the new state.