Commit | Line | Data |
---|---|---|
22eafbca RO |
1 | /* |
2 | ||
3 | Reference implementation of the Kalyna block cipher (DSTU 7624:2014), all block and key length variants | |
4 | ||
5 | Authors: Ruslan Kiianchuk, Ruslan Mordvinov, Roman Oliynykov | |
6 | ||
7 | */ | |
8 | ||
9 | #include "transformations.h" | |
10 | #include "tables.h" | |
11 | ||
12 | ||
13 | kalyna_t* KalynaInit(size_t block_size, size_t key_size) { | |
14 | int i; | |
15 | kalyna_t* ctx = (kalyna_t*)malloc(sizeof(kalyna_t)); | |
16 | ||
17 | if (block_size == kBLOCK_128) { | |
18 | ctx->nb = kBLOCK_128 / kBITS_IN_WORD; | |
19 | if (key_size == kKEY_128) { | |
20 | ctx->nk = kKEY_128 / kBITS_IN_WORD; | |
21 | ctx->nr = kNR_128; | |
22 | } else if (key_size == kKEY_256){ | |
23 | ctx->nk = kKEY_256 / kBITS_IN_WORD; | |
24 | ctx->nr = kNR_256; | |
25 | } else { | |
26 | fprintf(stderr, "Error: unsupported key size.\n"); | |
27 | return NULL; | |
28 | } | |
29 | } else if (block_size == 256) { | |
30 | ctx->nb = kBLOCK_256 / kBITS_IN_WORD; | |
31 | if (key_size == kKEY_256) { | |
32 | ctx->nk = kKEY_256 / kBITS_IN_WORD; | |
33 | ctx->nr = kNR_256; | |
34 | } else if (key_size == kKEY_512){ | |
35 | ctx->nk = kKEY_512 / kBITS_IN_WORD; | |
36 | ctx->nr = kNR_512; | |
37 | } else { | |
38 | fprintf(stderr, "Error: unsupported key size.\n"); | |
39 | return NULL; | |
40 | } | |
41 | } else if (block_size == kBLOCK_512) { | |
42 | ctx->nb = kBLOCK_512 / kBITS_IN_WORD; | |
43 | if (key_size == kKEY_512) { | |
44 | ctx->nk = kKEY_512 / kBITS_IN_WORD; | |
45 | ctx->nr = kNR_512; | |
46 | } else { | |
47 | fprintf(stderr, "Error: unsupported key size.\n"); | |
48 | return NULL; | |
49 | } | |
50 | } else { | |
51 | fprintf(stderr, "Error: unsupported block size.\n"); | |
52 | return NULL; | |
53 | } | |
54 | ||
55 | ctx->state = (uint64_t*)calloc(ctx->nb, sizeof(uint64_t)); | |
56 | if (ctx->state == NULL) | |
57 | perror("Could not allocate memory for cipher state."); | |
58 | ||
59 | ctx->round_keys = (uint64_t**)calloc(ctx->nr + 1, sizeof(uint64_t**)); | |
60 | if (ctx->round_keys == NULL) | |
61 | perror("Could not allocate memory for cipher round keys."); | |
62 | ||
63 | for (i = 0; i < ctx->nr + 1; ++i) { | |
64 | ctx->round_keys[i] = (uint64_t*)calloc(ctx->nb, sizeof(uint64_t)); | |
65 | if (ctx->round_keys[i] == NULL) | |
66 | perror("Could not allocate memory for cipher round keys."); | |
67 | } | |
68 | return ctx; | |
69 | } | |
70 | ||
71 | ||
72 | int KalynaDelete(kalyna_t* ctx) { | |
73 | int i; | |
74 | free(ctx->state); | |
75 | for (i = 0; i < ctx->nr + 1; ++i) { | |
76 | free(ctx->round_keys[i]); | |
77 | } | |
78 | free(ctx->round_keys); | |
79 | free(ctx); | |
80 | ctx = NULL; | |
81 | return 0; | |
82 | } | |
83 | ||
84 | ||
85 | void SubBytes(kalyna_t* ctx) { | |
86 | int i; | |
87 | uint64_t* s = ctx->state; /* For shorter expressions. */ | |
88 | for (i = 0; i < ctx->nb; ++i) { | |
89 | ctx->state[i] = sboxes_enc[0][s[i] & 0x00000000000000FFULL] | | |
90 | ((uint64_t)sboxes_enc[1][(s[i] & 0x000000000000FF00ULL) >> 8] << 8) | | |
91 | ((uint64_t)sboxes_enc[2][(s[i] & 0x0000000000FF0000ULL) >> 16] << 16) | | |
92 | ((uint64_t)sboxes_enc[3][(s[i] & 0x00000000FF000000ULL) >> 24] << 24) | | |
93 | ((uint64_t)sboxes_enc[0][(s[i] & 0x000000FF00000000ULL) >> 32] << 32) | | |
94 | ((uint64_t)sboxes_enc[1][(s[i] & 0x0000FF0000000000ULL) >> 40] << 40) | | |
95 | ((uint64_t)sboxes_enc[2][(s[i] & 0x00FF000000000000ULL) >> 48] << 48) | | |
96 | ((uint64_t)sboxes_enc[3][(s[i] & 0xFF00000000000000ULL) >> 56] << 56); | |
97 | } | |
98 | } | |
99 | ||
100 | void InvSubBytes(kalyna_t* ctx) { | |
101 | int i; | |
102 | uint64_t* s = ctx->state; /* For shorter expressions. */ | |
103 | for (i = 0; i < ctx->nb; ++i) { | |
104 | ctx->state[i] = sboxes_dec[0][s[i] & 0x00000000000000FFULL] | | |
105 | ((uint64_t)sboxes_dec[1][(s[i] & 0x000000000000FF00ULL) >> 8] << 8) | | |
106 | ((uint64_t)sboxes_dec[2][(s[i] & 0x0000000000FF0000ULL) >> 16] << 16) | | |
107 | ((uint64_t)sboxes_dec[3][(s[i] & 0x00000000FF000000ULL) >> 24] << 24) | | |
108 | ((uint64_t)sboxes_dec[0][(s[i] & 0x000000FF00000000ULL) >> 32] << 32) | | |
109 | ((uint64_t)sboxes_dec[1][(s[i] & 0x0000FF0000000000ULL) >> 40] << 40) | | |
110 | ((uint64_t)sboxes_dec[2][(s[i] & 0x00FF000000000000ULL) >> 48] << 48) | | |
111 | ((uint64_t)sboxes_dec[3][(s[i] & 0xFF00000000000000ULL) >> 56] << 56); | |
112 | } | |
113 | } | |
114 | ||
115 | ||
116 | void ShiftRows(kalyna_t* ctx) { | |
117 | int row, col; | |
118 | int shift = -1; | |
119 | ||
120 | uint8_t* state = WordsToBytes(ctx->nb, ctx->state); | |
121 | uint8_t* nstate = (uint8_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
122 | ||
123 | for (row = 0; row < sizeof(uint64_t); ++row) { | |
124 | if (row % (sizeof(uint64_t) / ctx->nb) == 0) | |
125 | shift += 1; | |
126 | for (col = 0; col < ctx->nb; ++col) { | |
127 | INDEX(nstate, row, (col + shift) % ctx->nb) = INDEX(state, row, col); | |
128 | } | |
129 | } | |
130 | ||
131 | ctx->state = BytesToWords(ctx->nb * sizeof(uint64_t), nstate); | |
132 | free(state); | |
133 | } | |
134 | ||
135 | void InvShiftRows(kalyna_t* ctx) { | |
136 | int row, col; | |
137 | int shift = -1; | |
138 | ||
139 | uint8_t* state = WordsToBytes(ctx->nb, ctx->state); | |
140 | uint8_t* nstate = (uint8_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
141 | ||
142 | for (row = 0; row < sizeof(uint64_t); ++row) { | |
143 | if (row % (sizeof(uint64_t) / ctx->nb) == 0) | |
144 | shift += 1; | |
145 | for (col = 0; col < ctx->nb; ++col) { | |
146 | INDEX(nstate, row, col) = INDEX(state, row, (col + shift) % ctx->nb); | |
147 | } | |
148 | } | |
149 | ||
150 | ctx->state = BytesToWords(ctx->nb * sizeof(uint64_t), nstate); | |
151 | free(state); | |
152 | } | |
153 | ||
154 | ||
155 | uint8_t MultiplyGF(uint8_t x, uint8_t y) { | |
156 | int i; | |
157 | uint8_t r = 0; | |
158 | uint8_t hbit = 0; | |
159 | for (i = 0; i < kBITS_IN_BYTE; ++i) { | |
160 | if ((y & 0x1) == 1) | |
161 | r ^= x; | |
162 | hbit = x & 0x80; | |
163 | x <<= 1; | |
164 | if (hbit == 0x80) | |
165 | x ^= kREDUCTION_POLYNOMIAL; | |
166 | y >>= 1; | |
167 | } | |
168 | return r; | |
169 | } | |
170 | ||
171 | void MatrixMultiply(kalyna_t* ctx, uint8_t matrix[8][8]) { | |
172 | int col, row, b; | |
173 | uint8_t product; | |
174 | uint64_t result; | |
175 | uint8_t* state = WordsToBytes(ctx->nb, ctx->state); | |
176 | ||
177 | for (col = 0; col < ctx->nb; ++col) { | |
178 | result = 0; | |
179 | for (row = sizeof(uint64_t) - 1; row >= 0; --row) { | |
180 | product = 0; | |
181 | for (b = sizeof(uint64_t) - 1; b >= 0; --b) { | |
182 | product ^= MultiplyGF(INDEX(state, b, col), matrix[row][b]); | |
183 | } | |
184 | result |= (uint64_t)product << (row * sizeof(uint64_t)); | |
185 | } | |
186 | ctx->state[col] = result; | |
187 | } | |
188 | } | |
189 | ||
190 | void MixColumns(kalyna_t* ctx) { | |
191 | MatrixMultiply(ctx, mds_matrix); | |
192 | } | |
193 | ||
194 | void InvMixColumns(kalyna_t* ctx) { | |
195 | MatrixMultiply(ctx, mds_inv_matrix); | |
196 | } | |
197 | ||
198 | ||
199 | void EncipherRound(kalyna_t* ctx) { | |
200 | SubBytes(ctx); | |
201 | ShiftRows(ctx); | |
202 | MixColumns(ctx); | |
203 | } | |
204 | ||
205 | void DecipherRound(kalyna_t* ctx) { | |
206 | InvMixColumns(ctx); | |
207 | InvShiftRows(ctx); | |
208 | InvSubBytes(ctx); | |
209 | } | |
210 | ||
211 | void AddRoundKey(int round, kalyna_t* ctx) { | |
212 | int i; | |
213 | for (i = 0; i < ctx->nb; ++i) { | |
214 | ctx->state[i] = ctx->state[i] + ctx->round_keys[round][i]; | |
215 | } | |
216 | } | |
217 | ||
218 | void SubRoundKey(int round, kalyna_t* ctx) { | |
219 | int i; | |
220 | for (i = 0; i < ctx->nb; ++i) { | |
221 | ctx->state[i] = ctx->state[i] - ctx->round_keys[round][i]; | |
222 | } | |
223 | } | |
224 | ||
225 | ||
226 | void AddRoundKeyExpand(uint64_t* value, kalyna_t* ctx) { | |
227 | int i; | |
228 | for (i = 0; i < ctx->nb; ++i) { | |
229 | ctx->state[i] = ctx->state[i] + value[i]; | |
230 | } | |
231 | } | |
232 | ||
233 | ||
234 | void XorRoundKey(int round, kalyna_t* ctx) { | |
235 | int i; | |
236 | for (i = 0; i < ctx->nb; ++i) { | |
237 | ctx->state[i] = ctx->state[i] ^ ctx->round_keys[round][i]; | |
238 | } | |
239 | } | |
240 | ||
241 | ||
242 | void XorRoundKeyExpand(uint64_t* value, kalyna_t* ctx) { | |
243 | int i; | |
244 | for (i = 0; i < ctx->nb; ++i) { | |
245 | ctx->state[i] = ctx->state[i] ^ value[i]; | |
246 | } | |
247 | } | |
248 | ||
249 | ||
250 | void Rotate(size_t state_size, uint64_t* state_value) { | |
251 | int i; | |
252 | uint64_t temp = state_value[0]; | |
253 | for (i = 1; i < state_size; ++i) { | |
254 | state_value[i - 1] = state_value[i]; | |
255 | } | |
256 | state_value[state_size - 1] = temp; | |
257 | } | |
258 | ||
259 | ||
260 | void ShiftLeft(size_t state_size, uint64_t* state_value) { | |
261 | int i; | |
262 | for (i = 0; i < state_size; ++i) { | |
263 | state_value[i] <<= 1; | |
264 | } | |
265 | } | |
266 | ||
267 | void RotateLeft(size_t state_size, uint64_t* state_value) { | |
268 | size_t rotate_bytes = 2 * state_size + 3; | |
269 | size_t bytes_num = state_size * (kBITS_IN_WORD / kBITS_IN_BYTE); | |
270 | ||
271 | uint8_t* bytes = WordsToBytes(state_size, state_value); | |
272 | uint8_t* buffer = (uint8_t*) malloc(rotate_bytes); | |
273 | ||
274 | /* Rotate bytes in memory. */ | |
275 | memcpy(buffer, bytes, rotate_bytes); | |
276 | memmove(bytes, bytes + rotate_bytes, bytes_num - rotate_bytes); | |
277 | memcpy(bytes + bytes_num - rotate_bytes, buffer, rotate_bytes); | |
278 | ||
279 | state_value = BytesToWords(bytes_num, bytes); | |
280 | ||
281 | free(buffer); | |
282 | } | |
283 | ||
284 | ||
285 | void KeyExpandKt(uint64_t* key, kalyna_t* ctx, uint64_t* kt) { | |
286 | uint64_t* k0 = (uint64_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
287 | uint64_t* k1 = (uint64_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
288 | ||
289 | memset(ctx->state, 0, ctx->nb * sizeof(uint64_t)); | |
290 | ctx->state[0] += ctx->nb + ctx->nk + 1; | |
291 | ||
292 | if (ctx->nb == ctx->nk) { | |
293 | memcpy(k0, key, ctx->nb * sizeof(uint64_t)); | |
294 | memcpy(k1, key, ctx->nb * sizeof(uint64_t)); | |
295 | } else { | |
296 | memcpy(k0, key, ctx->nb * sizeof(uint64_t)); | |
297 | memcpy(k1, key + ctx->nb, ctx->nb * sizeof(uint64_t)); | |
298 | } | |
299 | ||
300 | AddRoundKeyExpand(k0, ctx); | |
301 | EncipherRound(ctx); | |
302 | XorRoundKeyExpand(k1, ctx); | |
303 | EncipherRound(ctx); | |
304 | AddRoundKeyExpand(k0, ctx); | |
305 | EncipherRound(ctx); | |
306 | memcpy(kt, ctx->state, ctx->nb * sizeof(uint64_t)); | |
307 | ||
308 | free(k0); | |
309 | free(k1); | |
310 | } | |
311 | ||
312 | ||
313 | void KeyExpandEven(uint64_t* key, uint64_t* kt, kalyna_t* ctx) { | |
314 | int i; | |
315 | uint64_t* initial_data = (uint64_t*) malloc(ctx->nk * sizeof(uint64_t)); | |
316 | uint64_t* kt_round = (uint64_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
317 | uint64_t* tmv = (uint64_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
318 | size_t round = 0; | |
319 | ||
320 | memcpy(initial_data, key, ctx->nk * sizeof(uint64_t)); | |
321 | for (i = 0; i < ctx->nb; ++i) { | |
322 | tmv[i] = 0x0001000100010001; | |
323 | } | |
324 | ||
325 | while(TRUE) { | |
326 | memcpy(ctx->state, kt, ctx->nb * sizeof(uint64_t)); | |
327 | AddRoundKeyExpand(tmv, ctx); | |
328 | memcpy(kt_round, ctx->state, ctx->nb * sizeof(uint64_t)); | |
329 | ||
330 | memcpy(ctx->state, initial_data, ctx->nb * sizeof(uint64_t)); | |
331 | ||
332 | AddRoundKeyExpand(kt_round, ctx); | |
333 | EncipherRound(ctx); | |
334 | XorRoundKeyExpand(kt_round, ctx); | |
335 | EncipherRound(ctx); | |
336 | AddRoundKeyExpand(kt_round, ctx); | |
337 | ||
338 | memcpy(ctx->round_keys[round], ctx->state, ctx->nb * sizeof(uint64_t)); | |
339 | ||
340 | if (ctx->nr == round) | |
341 | break; | |
342 | ||
343 | if (ctx->nk != ctx->nb) { | |
344 | round += 2; | |
345 | ||
346 | ShiftLeft(ctx->nb, tmv); | |
347 | ||
348 | memcpy(ctx->state, kt, ctx->nb * sizeof(uint64_t)); | |
349 | AddRoundKeyExpand(tmv, ctx); | |
350 | memcpy(kt_round, ctx->state, ctx->nb * sizeof(uint64_t)); | |
351 | ||
352 | memcpy(ctx->state, initial_data + ctx->nb, ctx->nb * sizeof(uint64_t)); | |
353 | ||
354 | AddRoundKeyExpand(kt_round, ctx); | |
355 | EncipherRound(ctx); | |
356 | XorRoundKeyExpand(kt_round, ctx); | |
357 | EncipherRound(ctx); | |
358 | AddRoundKeyExpand(kt_round, ctx); | |
359 | ||
360 | memcpy(ctx->round_keys[round], ctx->state, ctx->nb * sizeof(uint64_t)); | |
361 | ||
362 | if (ctx->nr == round) | |
363 | break; | |
364 | } | |
365 | round += 2; | |
366 | ShiftLeft(ctx->nb, tmv); | |
367 | Rotate(ctx->nk, initial_data); | |
368 | } | |
369 | ||
370 | free(initial_data); | |
371 | free(kt_round); | |
372 | free(tmv); | |
373 | } | |
374 | ||
375 | void KeyExpandOdd(kalyna_t* ctx) { | |
376 | int i; | |
377 | for (i = 1; i < ctx->nr; i += 2) { | |
378 | memcpy(ctx->round_keys[i], ctx->round_keys[i - 1], ctx->nb * sizeof(uint64_t)); | |
379 | RotateLeft(ctx->nb, ctx->round_keys[i]); | |
380 | } | |
381 | } | |
382 | ||
383 | void KalynaKeyExpand(uint64_t* key, kalyna_t* ctx) { | |
384 | uint64_t* kt = (uint64_t*) malloc(ctx->nb * sizeof(uint64_t)); | |
385 | KeyExpandKt(key, ctx, kt); | |
386 | KeyExpandEven(key, kt, ctx); | |
387 | KeyExpandOdd(ctx); | |
388 | free(kt); | |
389 | } | |
390 | ||
391 | ||
392 | void KalynaEncipher(uint64_t* plaintext, kalyna_t* ctx, uint64_t* ciphertext) { | |
393 | int round = 0; | |
394 | memcpy(ctx->state, plaintext, ctx->nb * sizeof(uint64_t)); | |
395 | ||
396 | AddRoundKey(round, ctx); | |
397 | for (round = 1; round < ctx->nr; ++round) { | |
398 | EncipherRound(ctx); | |
399 | XorRoundKey(round, ctx); | |
400 | } | |
401 | EncipherRound(ctx); | |
402 | AddRoundKey(ctx->nr, ctx); | |
403 | ||
404 | memcpy(ciphertext, ctx->state, ctx->nb * sizeof(uint64_t)); | |
405 | } | |
406 | ||
407 | void KalynaDecipher(uint64_t* ciphertext, kalyna_t* ctx, uint64_t* plaintext) { | |
408 | int round = ctx->nr; | |
409 | memcpy(ctx->state, ciphertext, ctx->nb * sizeof(uint64_t)); | |
410 | ||
411 | SubRoundKey(round, ctx); | |
412 | for (round = ctx->nr - 1; round > 0; --round) { | |
413 | DecipherRound(ctx); | |
414 | XorRoundKey(round, ctx); | |
415 | } | |
416 | DecipherRound(ctx); | |
417 | SubRoundKey(0, ctx); | |
418 | ||
419 | memcpy(plaintext, ctx->state, ctx->nb * sizeof(uint64_t)); | |
420 | } | |
421 | ||
422 | ||
423 | uint8_t* WordsToBytes(size_t length, uint64_t* words) { | |
424 | int i; | |
425 | uint8_t* bytes; | |
426 | if (IsBigEndian()) { | |
427 | for (i = 0; i < length; ++i) { | |
428 | words[i] = ReverseWord(words[i]); | |
429 | } | |
430 | } | |
431 | bytes = (uint8_t*)words; | |
432 | return bytes; | |
433 | } | |
434 | ||
435 | uint64_t* BytesToWords(size_t length, uint8_t* bytes) { | |
436 | int i; | |
437 | uint64_t* words = (uint64_t*)bytes; | |
438 | if (IsBigEndian()) { | |
439 | for (i = 0; i < length; ++i) { | |
440 | words[i] = ReverseWord(words[i]); | |
441 | } | |
442 | } | |
443 | return words; | |
444 | } | |
445 | ||
446 | ||
447 | uint64_t ReverseWord(uint64_t word) { | |
448 | int i; | |
449 | uint64_t reversed = 0; | |
450 | uint8_t* src = (uint8_t*)&word; | |
451 | uint8_t* dst = (uint8_t*)&reversed; | |
452 | ||
453 | for (i = 0; i < sizeof(uint64_t); ++i) { | |
454 | dst[i] = src[sizeof(uint64_t) - i]; | |
455 | } | |
456 | return reversed; | |
457 | } | |
458 | ||
459 | ||
460 | int IsBigEndian() { | |
461 | unsigned int num = 1; | |
462 | /* Check the least significant byte value to determine endianness */ | |
463 | return (*((uint8_t*)&num) == 0); | |
464 | } | |
465 | ||
466 | void PrintState(size_t length, uint64_t* state) { | |
467 | int i; | |
468 | for (i = length - 1; i >= 0; --i) { | |
469 | printf("%16.16llx", state[i]); | |
470 | } | |
471 | printf("\n"); | |
472 | } | |
473 |