crypto/lrw.c

   1 /* LRW: as defined by Cyril Guyot in
   2  *      http://grouper.ieee.org/groups/1619/email/pdf00017.pdf
   3  *
   4  * Copyright (c) 2006 Rik Snel <rsnel@cube.dyndns.org>
   5  *
   6  * Based on ecb.c
   7  * Copyright (c) 2006 Herbert Xu <herbert@gondor.apana.org.au>
   8  *
   9  * This program is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the Free
  11  * Software Foundation; either version 2 of the License, or (at your option)
  12  * any later version.
  13  */
  14 /* This implementation is checked against the test vectors in the above
  15  * document and by a test vector provided by Ken Buchanan at
  16  * http://www.mail-archive.com/stds-p1619@listserv.ieee.org/msg00173.html
  17  *
  18  * The test vectors are included in the testing module tcrypt.[ch] */
  19
  20 #include <crypto/internal/skcipher.h>
  21 #include <crypto/scatterwalk.h>
  22 #include <linux/err.h>
  23 #include <linux/init.h>
  24 #include <linux/kernel.h>
  25 #include <linux/module.h>
  26 #include <linux/scatterlist.h>
  27 #include <linux/slab.h>
  28
  29 #include <crypto/b128ops.h>
  30 #include <crypto/gf128mul.h>
  31
  32 #define LRW_BUFFER_SIZE 128u
  33
  34 #define LRW_BLOCK_SIZE 16
  35
  36 struct priv {
  37         struct crypto_skcipher *child;
  38
  39         /*
  40          * optimizes multiplying a random (non incrementing, as at the
  41          * start of a new sector) value with key2, we could also have
  42          * used 4k optimization tables or no optimization at all. In the
  43          * latter case we would have to store key2 here
  44          */
  45         struct gf128mul_64k *table;
  46
  47         /*
  48          * stores:
  49          *  key2*{ 0,0,...0,0,0,0,1 }, key2*{ 0,0,...0,0,0,1,1 },
  50          *  key2*{ 0,0,...0,0,1,1,1 }, key2*{ 0,0,...0,1,1,1,1 }
  51          *  key2*{ 0,0,...1,1,1,1,1 }, etc
  52          * needed for optimized multiplication of incrementing values
  53          * with key2
  54          */
  55         be128 mulinc[128];
  56 };
  57
  58 struct rctx {
  59         be128 buf[LRW_BUFFER_SIZE / sizeof(be128)];
  60
  61         be128 t;
  62
  63         be128 *ext;
  64
  65         struct scatterlist srcbuf[2];
  66         struct scatterlist dstbuf[2];
  67         struct scatterlist *src;
  68         struct scatterlist *dst;
  69
  70         unsigned int left;
  71
  72         struct skcipher_request subreq;
  73 };
  74
  75 static inline void setbit128_bbe(void *b, int bit)
  76 {
  77         __set_bit(bit ^ (0x80 -
  78 #ifdef __BIG_ENDIAN
  79                          BITS_PER_LONG
  80 #else
  81                          BITS_PER_BYTE
  82 #endif
  83                         ), b);
  84 }
  85
  86 static int setkey(struct crypto_skcipher *parent, const u8 *key,
  87                   unsigned int keylen)
  88 {
  89         struct priv *ctx = crypto_skcipher_ctx(parent);
  90         struct crypto_skcipher *child = ctx->child;
  91         int err, bsize = LRW_BLOCK_SIZE;
  92         const u8 *tweak = key + keylen - bsize;
  93         be128 tmp = { 0 };
  94         int i;
  95
  96         crypto_skcipher_clear_flags(child, CRYPTO_TFM_REQ_MASK);
  97         crypto_skcipher_set_flags(child, crypto_skcipher_get_flags(parent) &
  98                                          CRYPTO_TFM_REQ_MASK);
  99         err = crypto_skcipher_setkey(child, key, keylen - bsize);
 100         crypto_skcipher_set_flags(parent, crypto_skcipher_get_flags(child) &
 101                                           CRYPTO_TFM_RES_MASK);
 102         if (err)
 103                 return err;
 104
 105         if (ctx->table)
 106                 gf128mul_free_64k(ctx->table);
 107
 108         /* initialize multiplication table for Key2 */
 109         ctx->table = gf128mul_init_64k_bbe((be128 *)tweak);
 110         if (!ctx->table)
 111                 return -ENOMEM;
 112
 113         /* initialize optimization table */
 114         for (i = 0; i < 128; i++) {
 115                 setbit128_bbe(&tmp, i);
 116                 ctx->mulinc[i] = tmp;
 117                 gf128mul_64k_bbe(&ctx->mulinc[i], ctx->table);
 118         }
 119
 120         return 0;
 121 }
 122
 123 static inline void inc(be128 *iv)
 124 {
 125         be64_add_cpu(&iv->b, 1);
 126         if (!iv->b)
 127                 be64_add_cpu(&iv->a, 1);
 128 }
 129
 130 /* this returns the number of consequative 1 bits starting
 131  * from the right, get_index128(00 00 00 00 00 00 ... 00 00 10 FB) = 2 */
 132 static inline int get_index128(be128 *block)
 133 {
 134         int x;
 135         __be32 *p = (__be32 *) block;
 136
 137         for (p += 3, x = 0; x < 128; p--, x += 32) {
 138                 u32 val = be32_to_cpup(p);
 139
 140                 if (!~val)
 141                         continue;
 142
 143                 return x + ffz(val);
 144         }
 145
 146         /*
 147          * If we get here, then x == 128 and we are incrementing the counter
 148          * from all ones to all zeros. This means we must return index 127, i.e.
 149          * the one corresponding to key2*{ 1,...,1 }.
 150          */
 151         return 127;
 152 }
 153
 154 static int post_crypt(struct skcipher_request *req)
 155 {
 156         struct rctx *rctx = skcipher_request_ctx(req);
 157         be128 *buf = rctx->ext ?: rctx->buf;
 158         struct skcipher_request *subreq;
 159         const int bs = LRW_BLOCK_SIZE;
 160         struct skcipher_walk w;
 161         struct scatterlist *sg;
 162         unsigned offset;
 163         int err;
 164
 165         subreq = &rctx->subreq;
 166         err = skcipher_walk_virt(&w, subreq, false);
 167
 168         while (w.nbytes) {
 169                 unsigned int avail = w.nbytes;
 170                 be128 *wdst;
 171
 172                 wdst = w.dst.virt.addr;
 173
 174                 do {
 175                         be128_xor(wdst, buf++, wdst);
 176                         wdst++;
 177                 } while ((avail -= bs) >= bs);
 178
 179                 err = skcipher_walk_done(&w, avail);
 180         }
 181
 182         rctx->left -= subreq->cryptlen;
 183
 184         if (err || !rctx->left)
 185                 goto out;
 186
 187         rctx->dst = rctx->dstbuf;
 188
 189         scatterwalk_done(&w.out, 0, 1);
 190         sg = w.out.sg;
 191         offset = w.out.offset;
 192
 193         if (rctx->dst != sg) {
 194                 rctx->dst[0] = *sg;
 195                 sg_unmark_end(rctx->dst);
 196                 scatterwalk_crypto_chain(rctx->dst, sg_next(sg), 2);
 197         }
 198         rctx->dst[0].length -= offset - sg->offset;
 199         rctx->dst[0].offset = offset;
 200
 201 out:
 202         return err;
 203 }
 204
 205 static int pre_crypt(struct skcipher_request *req)
 206 {
 207         struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req);
 208         struct rctx *rctx = skcipher_request_ctx(req);
 209         struct priv *ctx = crypto_skcipher_ctx(tfm);
 210         be128 *buf = rctx->ext ?: rctx->buf;
 211         struct skcipher_request *subreq;
 212         const int bs = LRW_BLOCK_SIZE;
 213         struct skcipher_walk w;
 214         struct scatterlist *sg;
 215         unsigned cryptlen;
 216         unsigned offset;
 217         be128 *iv;
 218         bool more;
 219         int err;
 220
 221         subreq = &rctx->subreq;
 222         skcipher_request_set_tfm(subreq, tfm);
 223
 224         cryptlen = subreq->cryptlen;
 225         more = rctx->left > cryptlen;
 226         if (!more)
 227                 cryptlen = rctx->left;
 228
 229         skcipher_request_set_crypt(subreq, rctx->src, rctx->dst,
 230                                    cryptlen, req->iv);
 231
 232         err = skcipher_walk_virt(&w, subreq, false);
 233         iv = w.iv;
 234
 235         while (w.nbytes) {
 236                 unsigned int avail = w.nbytes;
 237                 be128 *wsrc;
 238                 be128 *wdst;
 239
 240                 wsrc = w.src.virt.addr;
 241                 wdst = w.dst.virt.addr;
 242
 243                 do {
 244                         *buf++ = rctx->t;
 245                         be128_xor(wdst++, &rctx->t, wsrc++);
 246
 247                         /* T <- I*Key2, using the optimization
 248                          * discussed in the specification */
 249                         be128_xor(&rctx->t, &rctx->t,
 250                                   &ctx->mulinc[get_index128(iv)]);
 251                         inc(iv);
 252                 } while ((avail -= bs) >= bs);
 253
 254                 err = skcipher_walk_done(&w, avail);
 255         }
 256
 257         skcipher_request_set_tfm(subreq, ctx->child);
 258         skcipher_request_set_crypt(subreq, rctx->dst, rctx->dst,
 259                                    cryptlen, NULL);
 260
 261         if (err || !more)
 262                 goto out;
 263
 264         rctx->src = rctx->srcbuf;
 265
 266         scatterwalk_done(&w.in, 0, 1);
 267         sg = w.in.sg;
 268         offset = w.in.offset;
 269
 270         if (rctx->src != sg) {
 271                 rctx->src[0] = *sg;
 272                 sg_unmark_end(rctx->src);
 273                 scatterwalk_crypto_chain(rctx->src, sg_next(sg), 2);
 274         }
 275         rctx->src[0].length -= offset - sg->offset;
 276         rctx->src[0].offset = offset;
 277
 278 out:
 279         return err;
 280 }
 281
 282 static int init_crypt(struct skcipher_request *req, crypto_completion_t done)
 283 {
 284         struct priv *ctx = crypto_skcipher_ctx(crypto_skcipher_reqtfm(req));
 285         struct rctx *rctx = skcipher_request_ctx(req);
 286         struct skcipher_request *subreq;
 287         gfp_t gfp;
 288
 289         subreq = &rctx->subreq;
 290         skcipher_request_set_callback(subreq, req->base.flags, done, req);
 291
 292         gfp = req->base.flags & CRYPTO_TFM_REQ_MAY_SLEEP ? GFP_KERNEL :
 293                                                            GFP_ATOMIC;
 294         rctx->ext = NULL;
 295
 296         subreq->cryptlen = LRW_BUFFER_SIZE;
 297         if (req->cryptlen > LRW_BUFFER_SIZE) {
 298                 unsigned int n = min(req->cryptlen, (unsigned int)PAGE_SIZE);
 299
 300                 rctx->ext = kmalloc(n, gfp);
 301                 if (rctx->ext)
 302                         subreq->cryptlen = n;
 303         }
 304
 305         rctx->src = req->src;
 306         rctx->dst = req->dst;
 307         rctx->left = req->cryptlen;
 308
 309         /* calculate first value of T */
 310         memcpy(&rctx->t, req->iv, sizeof(rctx->t));
 311
 312         /* T <- I*Key2 */
 313         gf128mul_64k_bbe(&rctx->t, ctx->table);
 314
 315         return 0;
 316 }
 317
 318 static void exit_crypt(struct skcipher_request *req)
 319 {
 320         struct rctx *rctx = skcipher_request_ctx(req);
 321
 322         rctx->left = 0;
 323
 324         if (rctx->ext)
 325                 kzfree(rctx->ext);
 326 }
 327
 328 static int do_encrypt(struct skcipher_request *req, int err)
 329 {
 330         struct rctx *rctx = skcipher_request_ctx(req);
 331         struct skcipher_request *subreq;
 332
 333         subreq = &rctx->subreq;
 334
 335         while (!err && rctx->left) {
 336                 err = pre_crypt(req) ?:
 337                       crypto_skcipher_encrypt(subreq) ?:
 338                       post_crypt(req);
 339
 340                 if (err == -EINPROGRESS || err == -EBUSY)
 341                         return err;
 342         }
 343
 344         exit_crypt(req);
 345         return err;
 346 }
 347
 348 static void encrypt_done(struct crypto_async_request *areq, int err)
 349 {
 350         struct skcipher_request *req = areq->data;
 351         struct skcipher_request *subreq;
 352         struct rctx *rctx;
 353
 354         rctx = skcipher_request_ctx(req);
 355
 356         if (err == -EINPROGRESS) {
 357                 if (rctx->left != req->cryptlen)
 358                         return;
 359                 goto out;
 360         }
 361
 362         subreq = &rctx->subreq;
 363         subreq->base.flags &= CRYPTO_TFM_REQ_MAY_BACKLOG;
 364
 365         err = do_encrypt(req, err ?: post_crypt(req));
 366         if (rctx->left)
 367                 return;
 368
 369 out:
 370         skcipher_request_complete(req, err);
 371 }
 372
 373 static int encrypt(struct skcipher_request *req)
 374 {
 375         return do_encrypt(req, init_crypt(req, encrypt_done));
 376 }
 377
 378 static int do_decrypt(struct skcipher_request *req, int err)
 379 {
 380         struct rctx *rctx = skcipher_request_ctx(req);
 381         struct skcipher_request *subreq;
 382
 383         subreq = &rctx->subreq;
 384
 385         while (!err && rctx->left) {
 386                 err = pre_crypt(req) ?:
 387                       crypto_skcipher_decrypt(subreq) ?:
 388                       post_crypt(req);
 389
 390                 if (err == -EINPROGRESS || err == -EBUSY)
 391                         return err;
 392         }
 393
 394         exit_crypt(req);
 395         return err;
 396 }
 397
 398 static void decrypt_done(struct crypto_async_request *areq, int err)
 399 {
 400         struct skcipher_request *req = areq->data;
 401         struct skcipher_request *subreq;
 402         struct rctx *rctx;
 403
 404         rctx = skcipher_request_ctx(req);
 405
 406         if (err == -EINPROGRESS) {
 407                 if (rctx->left != req->cryptlen)
 408                         return;
 409                 goto out;
 410         }
 411
 412         subreq = &rctx->subreq;
 413         subreq->base.flags &= CRYPTO_TFM_REQ_MAY_BACKLOG;
 414
 415         err = do_decrypt(req, err ?: post_crypt(req));
 416         if (rctx->left)
 417                 return;
 418
 419 out:
 420         skcipher_request_complete(req, err);
 421 }
 422
 423 static int decrypt(struct skcipher_request *req)
 424 {
 425         return do_decrypt(req, init_crypt(req, decrypt_done));
 426 }
 427
 428 static int init_tfm(struct crypto_skcipher *tfm)
 429 {
 430         struct skcipher_instance *inst = skcipher_alg_instance(tfm);
 431         struct crypto_skcipher_spawn *spawn = skcipher_instance_ctx(inst);
 432         struct priv *ctx = crypto_skcipher_ctx(tfm);
 433         struct crypto_skcipher *cipher;
 434
 435         cipher = crypto_spawn_skcipher(spawn);
 436         if (IS_ERR(cipher))
 437                 return PTR_ERR(cipher);
 438
 439         ctx->child = cipher;
 440
 441         crypto_skcipher_set_reqsize(tfm, crypto_skcipher_reqsize(cipher) +
 442                                          sizeof(struct rctx));
 443
 444         return 0;
 445 }
 446
 447 static void exit_tfm(struct crypto_skcipher *tfm)
 448 {
 449         struct priv *ctx = crypto_skcipher_ctx(tfm);
 450
 451         if (ctx->table)
 452                 gf128mul_free_64k(ctx->table);
 453         crypto_free_skcipher(ctx->child);
 454 }
 455
 456 static void free_inst(struct skcipher_instance *inst)
 457 {
 458         crypto_drop_skcipher(skcipher_instance_ctx(inst));
 459         kfree(inst);
 460 }
 461
 462 static int create(struct crypto_template *tmpl, struct rtattr **tb)
 463 {
 464         struct crypto_skcipher_spawn *spawn;
 465         struct skcipher_instance *inst;
 466         struct crypto_attr_type *algt;
 467         struct skcipher_alg *alg;
 468         const char *cipher_name;
 469         char ecb_name[CRYPTO_MAX_ALG_NAME];
 470         int err;
 471
 472         algt = crypto_get_attr_type(tb);
 473         if (IS_ERR(algt))
 474                 return PTR_ERR(algt);
 475
 476         if ((algt->type ^ CRYPTO_ALG_TYPE_SKCIPHER) & algt->mask)
 477                 return -EINVAL;
 478
 479         cipher_name = crypto_attr_alg_name(tb[1]);
 480         if (IS_ERR(cipher_name))
 481                 return PTR_ERR(cipher_name);
 482
 483         inst = kzalloc(sizeof(*inst) + sizeof(*spawn), GFP_KERNEL);
 484         if (!inst)
 485                 return -ENOMEM;
 486
 487         spawn = skcipher_instance_ctx(inst);
 488
 489         crypto_set_skcipher_spawn(spawn, skcipher_crypto_instance(inst));
 490         err = crypto_grab_skcipher(spawn, cipher_name, 0,
 491                                    crypto_requires_sync(algt->type,
 492                                                         algt->mask));
 493         if (err == -ENOENT) {
 494                 err = -ENAMETOOLONG;
 495                 if (snprintf(ecb_name, CRYPTO_MAX_ALG_NAME, "ecb(%s)",
 496                              cipher_name) >= CRYPTO_MAX_ALG_NAME)
 497                         goto err_free_inst;
 498
 499                 err = crypto_grab_skcipher(spawn, ecb_name, 0,
 500                                            crypto_requires_sync(algt->type,
 501                                                                 algt->mask));
 502         }
 503
 504         if (err)
 505                 goto err_free_inst;
 506
 507         alg = crypto_skcipher_spawn_alg(spawn);
 508
 509         err = -EINVAL;
 510         if (alg->base.cra_blocksize != LRW_BLOCK_SIZE)
 511                 goto err_drop_spawn;
 512
 513         if (crypto_skcipher_alg_ivsize(alg))
 514                 goto err_drop_spawn;
 515
 516         err = crypto_inst_setname(skcipher_crypto_instance(inst), "lrw",
 517                                   &alg->base);
 518         if (err)
 519                 goto err_drop_spawn;
 520
 521         err = -EINVAL;
 522         cipher_name = alg->base.cra_name;
 523
 524         /* Alas we screwed up the naming so we have to mangle the
 525          * cipher name.
 526          */
 527         if (!strncmp(cipher_name, "ecb(", 4)) {
 528                 unsigned len;
 529
 530                 len = strlcpy(ecb_name, cipher_name + 4, sizeof(ecb_name));
 531                 if (len < 2 || len >= sizeof(ecb_name))
 532                         goto err_drop_spawn;
 533
 534                 if (ecb_name[len - 1] != ')')
 535                         goto err_drop_spawn;
 536
 537                 ecb_name[len - 1] = 0;
 538
 539                 if (snprintf(inst->alg.base.cra_name, CRYPTO_MAX_ALG_NAME,
 540                              "lrw(%s)", ecb_name) >= CRYPTO_MAX_ALG_NAME) {
 541                         err = -ENAMETOOLONG;
 542                         goto err_drop_spawn;
 543                 }
 544         } else
 545                 goto err_drop_spawn;
 546
 547         inst->alg.base.cra_flags = alg->base.cra_flags & CRYPTO_ALG_ASYNC;
 548         inst->alg.base.cra_priority = alg->base.cra_priority;
 549         inst->alg.base.cra_blocksize = LRW_BLOCK_SIZE;
 550         inst->alg.base.cra_alignmask = alg->base.cra_alignmask |
 551                                        (__alignof__(u64) - 1);
 552
 553         inst->alg.ivsize = LRW_BLOCK_SIZE;
 554         inst->alg.min_keysize = crypto_skcipher_alg_min_keysize(alg) +
 555                                 LRW_BLOCK_SIZE;
 556         inst->alg.max_keysize = crypto_skcipher_alg_max_keysize(alg) +
 557                                 LRW_BLOCK_SIZE;
 558
 559         inst->alg.base.cra_ctxsize = sizeof(struct priv);
 560
 561         inst->alg.init = init_tfm;
 562         inst->alg.exit = exit_tfm;
 563
 564         inst->alg.setkey = setkey;
 565         inst->alg.encrypt = encrypt;
 566         inst->alg.decrypt = decrypt;
 567
 568         inst->free = free_inst;
 569
 570         err = skcipher_register_instance(tmpl, inst);
 571         if (err)
 572                 goto err_drop_spawn;
 573
 574 out:
 575         return err;
 576
 577 err_drop_spawn:
 578         crypto_drop_skcipher(spawn);
 579 err_free_inst:
 580         kfree(inst);
 581         goto out;
 582 }
 583
 584 static struct crypto_template crypto_tmpl = {
 585         .name = "lrw",
 586         .create = create,
 587         .module = THIS_MODULE,
 588 };
 589
 590 static int __init crypto_module_init(void)
 591 {
 592         return crypto_register_template(&crypto_tmpl);
 593 }
 594
 595 static void __exit crypto_module_exit(void)
 596 {
 597         crypto_unregister_template(&crypto_tmpl);
 598 }
 599
 600 module_init(crypto_module_init);
 601 module_exit(crypto_module_exit);
 602
 603 MODULE_LICENSE("GPL");
 604 MODULE_DESCRIPTION("LRW block cipher mode");
 605 MODULE_ALIAS_CRYPTO("lrw");