Camellia (algoritm)

Kamelia
Skapare Mitsubishi
Skapad 2000
publiceras 2000
Nyckelstorlek 128, 192 eller 256 bitar
Block storlek 128 bitar
Antal omgångar 18 eller 24
Sorts Feistel nätverk

Camellia är en symmetrisk blockchifferalgoritm ( blockstorlek 128 bitar, nyckel 128, 192, 256 bitar ), en av finalisterna i den europeiska NESSIE- tävlingen (tillsammans med AES och Shacal-2 ), utvecklad av japanska företag Nippon Telegraph and Telephone Corporation och Mitsubishi Electric Corporation (inlämnad 10 mars 2000 ). Certifierad av den japanska organisationen CRYPTREC som en algoritm som rekommenderas för industriell och statlig användning.

Camellia är en vidareutveckling av E2- krypteringsalgoritmen , en av de algoritmer som lämnats in till AES- tävlingen och som använder delar av MISTY1- algoritmen .

Algoritmens struktur är baserad på den klassiska Feistel-kedjan med preliminär och slutlig blekning . Slingfunktionen använder en icke-linjär transformation (S-boxar), ett linjärt spridningsblock var 16:e cykel (byte-för-byte XOR -operation ) och en byte-permutation.

Beroende på nyckellängden har den 18 cykler (128 bitars nyckel) eller 24 cykler (192 och 256 bitars nycklar).

Stöd för Camellia-algoritmen introducerades 2008 i Mozilla Firefox 3, men inaktiverades 2014 i Mozilla Firefox 33 [1] . Algoritmen är patenterad, men distribueras under ett antal gratislicenser, i synnerhet är den en del av OpenSSL- projektet .

Beskrivning

Generering av hjälpnyckel

Beteckning Menande
& Bitvis OCH (OCH)
| Bitvis ELLER (ELLER)
^ Bitvis exklusivt ELLER (XOR)
<< Logisk förskjutning vänster
>> Logisk högerväxling
<<< Rotera vänster
~y Inversion
Konstant Menande
MASK8 0xff
MASK32 0xffffffff
MASK64 0xffffffffffffffff
MASK128 0xffffffffffffffffffffffffffffffffffffffff
C1 0xA09E667F3BCC908B
C2 0xB67AE8584CAA73B2
C3 0xC6EF372FE94F82BE
C4 0x54FF53A5F1D36F1C
C5 0x10E527FADE682D1D
C6 0xB05688C2B3E6C1FD
1. Nyckeln (K) är uppdelad i 2 128-bitars delar KL och KR.
Nyckel KL KR
128 K 0
192 K >> 64 ((K & MASK64) << 64) | (~(K&MASK64))
256 K >> 128 K&MASK128
2. Beräkna 128-bitars tal KA och KB (se diagram). Variablerna D1 och D2 är 64-bitars. Dl = (KL ^ KR) >> 64; D2=(KL^KR)&MASK64; D2 = D2 ^ F(Dl, Cl); Dl = Dl ^ F(D2, C2); Dl=Dl^(KL>>64); D2=D2^(KL&MASK64); D2 = D2 ^ F(Dl, C3); Dl = D1 ^ F(D2, C4); KA = (Dl << 64) | D2; Dl = (KA ^ KR) >> 64; D2=(KA^KR)&MASK64; D2 = D2 ^ F(Dl, C5); Dl = D1 ^ F(D2, C6); KB = (D1 << 64) | D2; 3. Beräkna extra 64-bitars nycklar kw1, ..., kw4, k1, ..., k24, ke1, ..., ke6 beroende på nyckelstorleken:
128 bitar

kw1 = (KL <<< 0) >> 64;

kw2 = (KL <<< 0) & MASK64; k1 = (KA <<< 0) >> 64; k2 = (KA <<< 0) & MASK64; k3 = (KL <<< 15) >> 64; k4 = (KL <<< 15) & MASK64; k5 = (KA <<< 15) >> 64; k6 = (KA <<< 15) & MASK64; kel = (KA <<< 30) >> 64; ke2 = (KA <<< 30) & MASK64; k7 = (KL <<< 45) >> 64; k8 = (KL <<< 45) & MASK64; k9 = (KA <<< 45) >> 64; k10 = (KL <<< 60) & MASK64; kll = (KA <<< 60) >> 64; k12 = (KA <<< 60) & MASK64; ke3 = (KL <<< 77) >> 64; ke4 = (KL <<< 77) & MASK64; k13 = (KL <<< 94) >> 64; k14 = (KL <<< 94) & MASK64; k15 = (KA <<< 94) >> 64; k16 = (KA <<< 94) & MASK64; k17 = (KL <<< 111) >> 64; k18 = (KL <<< 111) & MASK64; kw3 = (KA <<< 111) >> 64; kw4 = (KA <<< 111) & MASK64;
192 och 256 bitar

kw1 = (KL <<< 0) >> 64;

kw2 = (KL <<< 0) & MASK64; k1 = (KB <<< 0) >> 64; k2 = (KB <<< 0) & MASK64; k3 = (KR <<< 15) >> 64; k4 = (KR <<< 15) & MASK64; k5 = (KA <<< 15) >> 64; k6 = (KA <<< 15) & MASK64; kel = (KR <<< 30) >> 64; ke2 = (KR <<< 30) & MASK64; k7 = (KB <<< 30) >> 64; k8 = (KB <<< 30) & MASK64; k9 = (KL <<< 45) >> 64; k10 = (KL <<< 45) & MASK64; kll = (KA <<< 45) >> 64; k12 = (KA <<< 45) & MASK64; ke3 = (KL <<< 60) >> 64; ke4 = (KL <<< 60) & MASK64; k13 = (KR <<< 60) >> 64; k14 = (KR <<< 60) & MASK64; k15 = (KB <<< 60) >> 64; k16 = (KB <<< 60) & MASK64; k17 = (KL <<< 77) >> 64; k18 = (KL <<< 77) & MASK64; ke5 = (KA <<< 77) >> 64; ke6 = (KA <<< 77) & MASK64; k19 = (KR <<< 94) >> 64; k20 = (KR <<< 94) & MASK64; k21 = (KA <<< 94) >> 64; k22 = (KA <<< 94) & MASK64; k23 = (KL <<< 111) >> 64; k24 = (KL <<< 111) & MASK64; kw3 = (KB <<< 111) >> 64; kw4 = (KB <<< 111) & MASK64;

Kryptering

Kryptering sker enligt Feistel-schemat med 18 steg för en 128-bitars nyckel och 24 steg för 192- och 256-bitars nycklar. Vart sjätte steg tillämpas funktionerna FL och FLINV.

128 bitar

Dl = M > 64; // Krypterat meddelande är uppdelat i två 64-bitars delar

D2=M&MASK64; Dl = Dl^kwl; // Förblekning D2 = D2^kw2; D2 = D2 ^ F(Dl, kl); Dl = Dl ^ F(D2, k2); D2 = D2 ^ F(Dl, k3); Dl = D1 ^ F(D2, k4); D2 = D2 ^ F(Dl, k5); Dl = Dl ^ F(D2, k6); Dl = FL(Dl, kel); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2 ^ F(Dl, k7); Dl = Dl ^ F(D2, k8); D2 = D2 ^ F(Dl, k9); Dl = D1 ^ F(D2, k10); D2 = D2 ^ F(Dl, kll); Dl = Dl ^ F(D2, k12); Dl = FL(Dl, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2 ^ F(Dl, k13); Dl = Dl ^ F(D2, k14); D2 = D2 ^ F(Dl, k15); Dl = Dl ^ F(D2, k16); D2 = D2 ^ F(Dl, k17); Dl = D1 ^ F(D2, k18); D2 = D2^kw3; // Slutlig blekning Dl=Dl^kw4; C = (D2 << 64) | Dl;
192 och 256 bitar

Dl = M > 64; // Krypterat meddelande är uppdelat i två 64-bitars delar

D2=M&MASK64; Dl = Dl^kwl; // Förblekning D2 = D2^kw2; D2 = D2 ^ F(Dl, kl); Dl = Dl ^ F(D2, k2); D2 = D2 ^ F(Dl, k3); Dl = D1 ^ F(D2, k4); D2 = D2 ^ F(Dl, k5); Dl = Dl ^ F(D2, k6); Dl = FL(Dl, kel); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2 ^ F(Dl, k7); Dl = Dl ^ F(D2, k8); D2 = D2 ^ F(Dl, k9); Dl = D1 ^ F(D2, k10); D2 = D2 ^ F(Dl, kll); Dl = Dl ^ F(D2, k12); Dl = FL(Dl, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2 ^ F(Dl, k13); Dl = Dl ^ F(D2, k14); D2 = D2 ^ F(Dl, k15); Dl = Dl ^ F(D2, k16); D2 = D2 ^ F(Dl, k17); Dl = D1 ^ F(D2, k18); Dl = FL(Dl, ke5); // FL D2 = FLINV(D2, ke6); // FLINV D2 = D2 ^ F(Dl, k19); Dl = D1 ^ F(D2, k20); D2 = D2 ^ F(Dl, k21); Dl = D1 ^ F(D2, k22); D2 = D2 ^ F(Dl, k23); Dl = Dl ^ F(D2, k24); D2 = D2^kw3; // Slutlig blekning Dl=Dl^kw4; C = (D2 << 64) | Dl;

Hjälpfunktioner F, FL, FLINV

F-, FL- och FLINV-funktionerna tar emot 2 64-bitars parametrar som indata - F_IN-data och KE-nyckel.
F-funktionen använder 16 8-bitars variabler t1, ..., t8, y1, ..., y8 och 1 64-bitars variabel. Utdata från funktionen är ett 64-bitars nummer.
FL- och FLINV-funktionerna använder 4 32-bitars variabler x1,x2,k1,k2. Utdata från funktionen är ett 64-bitars nummer. FLINV-funktion - inverterad till FL

F-funktion

x = F_IN^KE;

tl = x >> 56; t2 = (x >> 48) & MASK8; t3 = (x >> 40) &MASK8; t4 = (x >> 32) &MASK8; t5 = (x >> 24) & MASK8; t6 = (x >> 16) &MASK8; t7 = (x >> 8) &MASK8; t8=x&MASK8; t1 = SBOX1[tl]; t2 = SBOX2[t2]; t3 = SBOX3[t3]; t4 = SBOX4[t4]; t5 = SBOX2[t5]; t6 = SBOX3[t6]; t7 = SBOX4[t7]; t8 = SBOX1[t8]; y1 = t1 ^ t3 ^ t4 ^ t6 ^ t7 ^ t8; y2 = t1^t2^t4^t5^t7^t8; y3 = t1^t2^t3^t5^t6^t8; y4 = t2^t3^t4^t5^t6^t7; y5 = t1^t2^t6^t7^t8; y6 = t2^t3^t5^t7^t8; y7 = t3^t4^t5^t6^t8; y8 = t1^t4^t5^t6^t7; F_OUT = (y1 << 56) | (y2 << 48) | (y3 << 40) | (y4 << 32)| (y5 << 24) | (y6 << 16) | (y7 << 8) | y8;
FL funktion

var x1, x2 som 32-bitars heltal utan tecken;

var k1, k2 som 32-bitars heltal utan tecken; x1 = FL_IN >> 32; x2 = FL_IN&MASK32; k1 = KE >> 32; k2=KE&MASK32; x2 = x2^((x1 & k1) <<< 1); xl = xl^(x2|k2); FL_OUT = (x1 << 32) | x2;
FLINV funktion

var y1, y2 som 32-bitars heltal utan tecken;

var k1, k2 som 32-bitars heltal utan tecken; y1 = FLINV_IN >> 32; y2 = FLINV_IN&MASK32; k1 = KE >> 32; k2=KE&MASK32; yl = yl^(y2|k2); y2 = y2^ ((yl & kl) <<< 1); FLINV_OUT = (y1 << 32) | y2;

S-block

Värdet på SBOX1-funktionen bestäms från följande tabell:

0 ett 2 3 fyra 5 6 7 åtta 9 a b c d e f
0 112 130 44 236 179 39 192 229 228 133 87 53 234 12 174 65
ett 35 239 107 147 69 25 165 33 237 fjorton 79 78 29 101 146 189
2 134 184 175 143 124 235 31 206 62 48 220 95 94 197 elva 26
3 166 225 57 202 213 71 93 61 217 ett 90 214 81 86 108 77
fyra 139 13 154 102 251 204 176 45 116 arton 43 32 240 177 132 153
5 223 76 203 194 52 126 118 5 109 183 169 49 209 23 fyra 215
6 tjugo 88 58 97 222 27 17 28 femtio femton 156 22 83 24 242 34
7 254 68 207 178 195 181 122 145 36 åtta 232 168 96 252 105 80
åtta 170 208 160 125 161 137 98 151 84 91 trettio 149 224 255 100 210
9 16 196 0 72 163 247 117 219 138 3 230 218 9 63 221 148
a 135 92 131 2 205 74 144 51 115 103 246 243 157 127 191 226
b 82 155 216 38 200 55 198 59 129 150 111 75 19 190 99 46
c 233 121 167 140 159 110 188 142 41 245 249 182 47 253 180 89
d 120 152 6 106 231 70 113 186 212 37 171 66 136 162 141 250
e 114 7 185 85 248 238 172 tio 54 73 42 104 60 56 241 164
f 64 40 211 123 187 201 67 193 21 227 173 244 119 199 128 158

Till exempel: SBOX1(0x7a)=232.
SBOX2, SBOX3 och SBOX4 definieras från SBOX1 enligt följande:

SBOX2[x] = SBOX1[x] <<< 1; SBOX3[x] = SBOX1[x] <<< 7; SBOX4[x] = SBOX1[x <<< 1];

Dekryptering

Dekrypteringsalgoritmen är identisk med kryptering, med den enda skillnaden att hjälpnycklarna byts ut enligt följande schema, beroende på längden på den ursprungliga nyckeln:

Nyckelstorlek
128 bitar 192 eller 256 bitar
kw1 <-> kw3 kw1 <-> kw3
kw2 <-> kw4 kw2 <-> kw4
k1 <-> k18 k1 <-> k24
k2 <-> k17 k2 <-> k23
k3 <-> k16 k3 <-> k22
k4 <-> k15 k4 <-> k21
k5 <-> k14 k5 <-> k20
k6 <-> k13 k6 <-> k19
k7 <-> k12 k7 <-> k18
k8 <-> k11 k8 <-> k17
k9 <-> k10 k9 <-> k16
k10 <-> k15
k11 <-> k14
k12 <-> k13
ke1 <-> ke4 ke1 <-> ke6
ke2 <-> ke3 ke2 <-> ke5
ke3 <-> ke4



Krypteringsexempel

Nyckel: 0123456789abcdeffedcba9876543210

Krypterat meddelande: 0123456789abcdefeffedcba9876543210

Krypterat meddelande: 67673138549669730857065648eabe43

Nycklar

k[1]=ae71c3d55ba6bf1d

k[2]=169240a795f89256 k[3]=a2b3c4d5e6f7ff6e k[4]=5d4c3b2a19080091 k[5]=e1eaadd35f8e8b49 k[6]=2053cafc492b5738 k[7]=79bdffdb97530eca k[8]=8642002468acf135 k[9]=d7e3a2d24814f2bf k[10]=00123456789abcde k[11]=d169240a795f8ukv k[12]=6ae71c3d55ba6bf1 k[13]=1d950c840048d159 k[14]=e26af37bffb72ea6 k[15]=e57e2495ab9c70f5 k[16]=56e9afc745a49029 kw[1]=0123456789abcdef kw[2]=fedcba9876543210 kw[3]=492b5738e1eaadd3 kw[4]=5f8e8b492053cafc ke[1]=56e9afc745a49029 ke[2]=e57e2495ab9c70f5 ke[3]=97530eca86420024 ke[4]=68acf13579bdffdb

Säkerhet

Enligt författarna till algoritmen:

Vi har visat att framgången med differentiell [2] och linjär [3] kryptoanalys är nästan omöjlig mot en hel 18-runders Camellia-cykel. Dessutom designades Camellia för att motstå mer sofistikerade kryptografiska attacker såsom differentialattacker av hög ordning [4] [5] , interpolationsattacker [6] [7] , "linked-key"-attacker [8] [9] , förkortade differentialattacker [10] [11] och andra

Originaltext  (engelska)[ visaDölj] Vi bekräftade att det är extremt osannolikt att differentiella och linjära attacker kommer att lyckas mot hela 18-rundor Camellia. Dessutom designades Camellia för att erbjuda säkerhet mot andra avancerade kryptoanalytiska attacker inklusive differentialattacker av högre ordning, interpolationsattacker, attacker med relaterade nyckel, trunkerade differentialattacker och så vidare

Applikation

Stöd för Camellia lades till i den slutliga versionen av Mozilla Firefox 3 2008 [12] . Senare samma år meddelade FreeBSD-utvecklingsteamet att stöd för denna kryptering också inkluderades i FreeBSD 6.4-RELEASE. I september 2009 lade GNU Privacy Guard till stöd för Camellia i version 1.4.10. Dessutom innehåller många populära säkerhetsbibliotek som Crypto++, GnuTLS, PolarSSL och OpenSSL [13] även stöd för Camellia.

Jämförelse med jämnåriga

Algoritm Antal logiska element Nyckelberäkningstid, ns Kryptering/dekrypteringstid, ns Bandbredd, Mb/s
Kryptering/dekryptering Nycklar Total kvantitet
DES 42,204 12.201 54,405 - 55.11 1161,31
Trippel-DES 124,888 23,207 128,147 - 157,09 407,40
MARS 690,654 2,245,096 2,935,754 1740,99 567,49 225,55
RC6 741,641 901,382 1,643,037 2112,26 627,57 203,96
Rijndael 518.508 93,708 612.834 57,39 65,64 1950.03
Orm 298,533 205,096 503,770 114,07 137,40 931,58
Tvåfisk 200,165 231,682 431,857 16.38 324,80 394,08
Kamelia 216,911 55,907 272,819 24.36 109,35 1170,55

[fjorton]

Utvecklare

Se även

Anteckningar

  1. Bug 1036765 - Inaktivera chiffersviter som inte finns i förslaget "Browser Cipher Suite" som fortfarande är aktiverade . Hämtad 18 september 2015. Arkiverad från originalet 3 februari 2018.
  2. M. Matsui , Linear Cryptanalysis Method for DES Chipher - Lecture Notes in Computer Science, s. 386–397, Springer-Verlag, 1994
  3. E. Biham och A. Shamir , Linear Cryptanalysis Method for DES Cipher - Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1994
  4. LRKnudsen , "Truncated and Higher Order Differentials," Fast Software Encryption - Second International Workshop, Lecture Notes in ComputerScience 1008, s.196–211, Springer-Verlag, 1995.
  5. T. Jakobsen och LR Knudsen , The Interpolation Attack on Block Chiphers, Fast Software Encryption, FSE'97, Lecture Notes in Computer Science 1267, s.28–40, Springer-Verlag, 1997.
  6. T. Jakobsen och LR Knudsen , The Interpolation Attack on Block Chiphers, Fast Software Encryption, FSE'97, Lecture Notes in Computer Science 1267, s.28–40, Springer-Verlag, 1997.
  7. K. Aoki , "Praktisk utvärdering av säkerhet mot generaliserad interpolationsattack", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japan), Vol. E83-A, No.1, pp.33–38, 2000.
  8. E. Biham , New Types of Cryptanalytic Attacks Using Related Keys, Journal of Cryptology, Vol.7, No.4, pp.229–246, Springer-Verlag, 1994.
  9. J.Kelsey, B.Schneier och D.Wagner , "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES," Advances in Cryptology - CRYPTO'96, Lecture Notes in Computer Science 1109, s. 237–251, Springer-Verlag, 1996.
  10. LRKnudsen , Trunkated and Higher Order Differentials, Fast Software Encryption - Second International Workshop, Lecture Notes in Computer Science 1008, s.196–211, Springer-Verlag, 1995.
  11. M. Matsui och T. Tokita , Cryptanalysis of a Reduced Version of the Block Chipher E2, Fast Software Encryption - 6th International Workshop, FSE'99, Lecture Notes in Computer Science 1636, s.71–80, Springer-Verlag, 1999 .
  12. Camellia-chiffer lagt till i Firefox (nedlänk) . Mozilla Asien . Mozilla (30 juli 2009). Arkiverad från originalet den 29 februari 2012. 
  13. NTT (2006-11-08). Open Source Community OpenSSL-projektet antar nästa generations internationella standardchiffer "Camellia" utvecklat i Japan . Pressmeddelande . Arkiverad från originalet den 8 mars 2008. Hämtad 2008-02-29 .
  14. Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima och Toshio Tokita Camellia: En 128-bitars blockchiffer som är lämplig för flera plattformar - design och analys

Länkar