MUGI Ver. 1.3 2002 5 8 1
1 3 2 3 2.1 Panama... 4 2.2... 5 3 5 3.1... 5 3.2... 5 3.3... 6 3.3.1... 6 3.3.2... 6 3.3.3... 7 3.3.4... 7 4 8 4.1... 8 4.2... 8 4.3... 9 4.3.1... 9 4.3.2... 9 4.4... 9 4.4.1 ρ... 9 4.4.2 λ... 10 4.5... 10 4.6... 11 4.7... 12 4.7.1 S-box................................ 12 4.7.2... 12 4.7.3 F... 13 4.7.4... 13 5 14 5.1......................... 14 5.2... 14 A S-box 16 B 0x02 17 C 18 2
1 128 ( )128 2 3 4 5 2 ( ) Panama[DC98] Panama 1998 Daemen Clapp Panama Panama Panama Panama [Eval] MUGI AES[FIPS-197] 3
Panama 2.1 2.2 2.1 Panama S F f (S, F,f) (S, F) (internal-state machine) 1 t S (t) Panama 2 Panama ( 1) ρ λ Panama ρ SPN ρ Panama λ ( ) Panama Internal State Buffer State Output Filter Out[t] λ ρ Update Function 1: Panama Panama (Panama-like keystream generator: PKSG) PKSG 1 2 a b ρ λ f ((a, b), (ρ, λ),f) 4
Panama (1) ρ a SPN b a (t+1) = ρ(a (t),b (t) ). (2) λ b a b (t+1) = λ(b (t),a (t) ). (3) f a f a (1/2 ) 2.2 AES[FIPS-197] ( S-box) PKSG 3 3.1 >>> n n ( 64 ) <<< n n ( ) 0x 16 3.2 64 64 5
1 ( ) big endian 8 x 0,...,x 7 1 a a = [MSB] x 0 x 1... x 7 [LSB]. [MSB] [LSB] x i i 1 2 b 0,...,b n B =(b i ) i b i,j b i j a 32 a H 32 a L 3.3 3.3.1 GF(2 8 ) GF(2 8 ) ϕ(x) ϕ(x) =x 8 + x 4 + x 3 + x +1=0x11b, GF (2 8 ) = GF(2)[x]/(ϕ(x)) GF(2) ({0, 1} 7 ) 1 8 b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x + b 0, 0x57 0101 0111 x 6 + x 4 + x 2 + x +1 3.3.2 2 mod 2 0x57 + 0xa3 =(x 6 + x 4 + x 2 + x +1)+(x 7 + x 5 + x +1) 6
= x 7 + x 6 + x 5 + x 4 + x 2 0xf4. 3.3.3 GF(2 8 ) 2 GF(2 8 ) f(x) = a i x i x x f(x) bi x i+1 mod ϕ(x) 0x02 0x87 = x (x 7 + x 2 + x +1) = x 8 + x 3 + x 2 + x =(x 4 + x 3 + x +1)+x 3 + x 2 + x = x 4 + x 2 +1 = 0x15. x i f(x) GF(2 8 ) 2 f(x) = a i x i,g(x) = b i x i f g f g(x) = 14 i=0 j=0 i (a j b i j )x i mod ϕ(x), 3.3.4 f,g GF(2 8 ) f a + g b = 1 mod ϕ(x), a, b GF(2 8 ) g f g = f 1 0 GF(2 8 ) a 1 = a 254, a 7
4 2 4.3 4.4 4.4 4.7 4.5 4.6 4.1 MUGI 128 ( )K 128 ( )I n(n ) n : K I n : Out[i] (1 i n) Step 1. K ρ Step 2. I ρ Step 3. Step 4. n (64 ) 4.2 128 ( )K 128 ( )I K(I) K 0,K 1 (I 0,I 1 ) 8
4.3 4.3.1 a 3 a 0,a 1,a 2 4.3.2 b 16 b 0,...,b 15 4.4 PKSG ρ λ PKSG Update (a (t+1),b (t+1) ) = Update(a (t),b (t) ) = (ρ(a (t),b (t) ),λ(b (t),a (t) )). MUGI ρ λ 4.4.1 ρ ρ a 2 F Feistel ( 2) b ρ a (t+1) 0 = a (t) 1, a (t+1) 1 = a (t) 2 F(a (t) 1,b(t) 4 ) C 1, a (t+1) 2 = a (t) 0 F(a (t) 1,b(t) 10 <<< 17) C 2. C 1,C 2 F AES (S-box) F 4.7.3 9
b 4 (t) 64 b 10 (t) 64 a 0 (t) a 1 (t) a 2 (t) 64 64 64 17 <<< F F C 1 C 2 64 64 a 0 (t+1) a 1 (t+1) a 2 (t+1) 2: ρ 4.4.2 λ λ b a λ b (t+1) j = b (t) j 1 (j 0, 4, 10), b (t+1) 0 = b (t) 15 a(t) 0, b (t+1) 4 = b (t) 3 b(t) 7, b (t+1) 10 = b (t) 9 (b(t) 13 <<< 32). 4.5 K a 0 = K 0, a 1 = K 1, a 2 = (K 0 <<< 7) (K 1 >>> 7) C 0. C 0 ρ b b 15 i =(ρ i+1 (a, 0)) 0. ρ i ρ i ρ(a, 0) b 0 K ρ 10
a a(k) =ρ 16 (a 0, 0) I a a(k, I) 0 = a(k) 0 I 0, a(k, I) 1 = a(k) 1 I 1, a(k, I) 2 = a(k) 2 (I 0 <<< 7) (I 1 >>> 7) C 0, a 16 ρ ρ 16 (a(k, I), 0) 16 a (1) = Update 16 (ρ 16 (a(k, I), 0),b(K)). b(k) K 4.6 64 t Out[t] Out[t] =a (t) 2, 64 1 1: t 49 K 48,..., 33 (ρ ) 32 I 31,..., 16 (ρ ) 15,...,0 (Update) 1,... Out[t] 11
4.7 4.4 4.5 4.4.1 F F SPN S-box GF(2 8 ) 4 4 4.7.1 S-box 4.7.2 4.7.3 F 4.7.4 4.7.1 S-box 8 S-box AES S-box GF(2 8 ) x x 1 (0 1 =0 ) b = S(x) b = x 1, b 0 b 1 b 2 b 3 b = 4 b 5 b 6 b 7 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 7 1 1 0 0 0 1 1 0. S-box A 4.7.2 F 4 4 S-box AES MDS M 4 X = x 0 x 1 x 2 x 3 12
M : x 0 0x02 0x03 0x01 0x01 M(x) =M x 1 x 2 = 0x01 0x02 0x03 0x01 0x01 0x01 0x02 0x03 x 3 0x03 0x01 0x01 0x02 3.3 0x01, 0x02, 0x03 0x01 0x03 = 0x01 0x02 0x02 0x02 B x 0 x 1 x 2 x 3. 4.7.3 F F () S-box (MDS M +) ( 3) F 64 (X,B) Y F : Y = F (X,B) O = X B, O 0 O 1 O 2 O 3 O 4 O 5 O 6 O 7 = O, P i = S(O i ) (0 i<8), P H = P 0 P 1 P 2 P 3, P L = P 4 P 5 P 6 P 7, Q H = M(P H ), Q L = M(P L ), Q 0 Q 1 Q 2 Q 3 = Q H, Q 4 Q 5 Q 6 Q 7 = Q L, Y = Q 4 Q 5 Q 2 Q 3 Q 0 Q 1 Q 6 Q 7. S-box M [FIPS-197] F 4.7.4 C 0 ρ C 1,C 2 13
8 8 8 8 8 8 8 8 Buffer S S S S S S S S M M F-function 3: F : C 0 = 0x6A09E667F3BCC908, C 1 = 0xBB67AE8584CAA73B, C 2 = 0x3C6EF372FE94F82B. 2, 3, 5 2 64 64 16 5 5.1 K I K I 5.2 P 64 K I (4) 14
key K initial vector I key K initial vector I 128 128 128 128 MUGI 64 MUGI 64 plaintext P ciphertext C ciphertext C plaintext P 64 64 encryption 64 64 decryption 4: [DC98] J. Daemen, C. Clapp, Fast Hashing and Stream Encryption with PANAMA, Fast Software Encryption, 5th International Workshop, FSE 98, Proceedings, LNCS Vol. 1372, Springer-Verlag, 1998. [FIPS-197] National Institute of Standards and Technology, Federal Information Processing Standards Publication 197, Advanced Encryption Standard (AES). [WFT01],,, F,, SCIS 2001-6A-4, 2001. [WFST01a],,,,,, ISEC2001-8, 2001. [WFST01b],,,, Panama,, ISEC2001-57, 2001. [Eval],,,,, 2001, available at http://www.sdl.hitachi.co.jp/crypto/mugi/index-j.html. 15
A S-box S-box S(x) = Sbox[x] Sbox[256] = { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 }; 16
B 0x02 0x02 0x02 x = mul2[x] mul2[256] = { 0x00, 0x02, 0x04, 0x06, 0x08, 0x0a, 0x0c, 0x0e, 0x10, 0x12, 0x14, 0x16, 0x18, 0x1a, 0x1c, 0x1e, 0x20, 0x22, 0x24, 0x26, 0x28, 0x2a, 0x2c, 0x2e, 0x30, 0x32, 0x34, 0x36, 0x38, 0x3a, 0x3c, 0x3e, 0x40, 0x42, 0x44, 0x46, 0x48, 0x4a, 0x4c, 0x4e, 0x50, 0x52, 0x54, 0x56, 0x58, 0x5a, 0x5c, 0x5e, 0x60, 0x62, 0x64, 0x66, 0x68, 0x6a, 0x6c, 0x6e, 0x70, 0x72, 0x74, 0x76, 0x78, 0x7a, 0x7c, 0x7e, 0x80, 0x82, 0x84, 0x86, 0x88, 0x8a, 0x8c, 0x8e, 0x90, 0x92, 0x94, 0x96, 0x98, 0x9a, 0x9c, 0x9e, 0xa0, 0xa2, 0xa4, 0xa6, 0xa8, 0xaa, 0xac, 0xae, 0xb0, 0xb2, 0xb4, 0xb6, 0xb8, 0xba, 0xbc, 0xbe, 0xc0, 0xc2, 0xc4, 0xc6, 0xc8, 0xca, 0xcc, 0xce, 0xd0, 0xd2, 0xd4, 0xd6, 0xd8, 0xda, 0xdc, 0xde, 0xe0, 0xe2, 0xe4, 0xe6, 0xe8, 0xea, 0xec, 0xee, 0xf0, 0xf2, 0xf4, 0xf6, 0xf8, 0xfa, 0xfc, 0xfe, 0x1b, 0x19, 0x1f, 0x1d, 0x13, 0x11, 0x17, 0x15, 0x0b, 0x09, 0x0f, 0x0d, 0x03, 0x01, 0x07, 0x05, 0x3b, 0x39, 0x3f, 0x3d, 0x33, 0x31, 0x37, 0x35, 0x2b, 0x29, 0x2f, 0x2d, 0x23, 0x21, 0x27, 0x25, 0x5b, 0x59, 0x5f, 0x5d, 0x53, 0x51, 0x57, 0x55, 0x4b, 0x49, 0x4f, 0x4d, 0x43, 0x41, 0x47, 0x45, 0x7b, 0x79, 0x7f, 0x7d, 0x73, 0x71, 0x77, 0x75, 0x6b, 0x69, 0x6f, 0x6d, 0x63, 0x61, 0x67, 0x65, 0x9b, 0x99, 0x9f, 0x9d, 0x93, 0x91, 0x97, 0x95, 0x8b, 0x89, 0x8f, 0x8d, 0x83, 0x81, 0x87, 0x85, 0xbb, 0xb9, 0xbf, 0xbd, 0xb3, 0xb1, 0xb7, 0xb5, 0xab, 0xa9, 0xaf, 0xad, 0xa3, 0xa1, 0xa7, 0xa5, 0xdb, 0xd9, 0xdf, 0xdd, 0xd3, 0xd1, 0xd7, 0xd5, 0xcb, 0xc9, 0xcf, 0xcd, 0xc3, 0xc1, 0xc7, 0xc5, 0xfb, 0xf9, 0xff, 0xfd, 0xf3, 0xf1, 0xf7, 0xf5, 0xeb, 0xe9, 0xef, 0xed, 0xe3, 0xe1, 0xe7, 0xe5 }; 17
C key[16] = {0} iv[16] = {0} output = 0xc76e14e70836e6b6, 0xcb0e9c5a0bf03e1e, 0x0acf9af49ebe6d67, 0xd5726e374b1397ac, 0xdac3838528c1e592, 0x8a132730ef2bb752, 0xbd6229599f6d9ac2, 0x7c04760502f1e182,... key[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f} iv[16] = {0xf0, 0xe0, 0xd0, 0xc0, 0xb0, 0xa0, 0x90, 0x80, 0x70, 0x60, 0x50, 0x40, 0x30, 0x20, 0x10, 0x00} output = 0xbc62430614b79b71, 0x71a66681c35542de, 0x7aba5b4fb80e82d7, 0x0b96982890b6e143, 0x4930b5d033157f46, 0xb96ed8499a282645, 0xdbeb1ef16d329b15, 0x34a9192c4ddcf34e,... 18