chiark - git - mdw - kalyna-python/blob - ref/kalyna.c

   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