lib/crypto/poly1305.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Poly1305 authenticator algorithm, RFC7539
   4  *
   5  * Copyright (C) 2015 Martin Willi
   6  *
   7  * Based on public domain code by Andrew Moon and Daniel J. Bernstein.
   8  */
   9
  10 #include <crypto/internal/poly1305.h>
  11 #include <linux/kernel.h>
  12 #include <linux/module.h>
  13 #include <asm/unaligned.h>
  14
  15 static inline u64 mlt(u64 a, u64 b)
  16 {
  17         return a * b;
  18 }
  19
  20 static inline u32 sr(u64 v, u_char n)
  21 {
  22         return v >> n;
  23 }
  24
  25 static inline u32 and(u32 v, u32 mask)
  26 {
  27         return v & mask;
  28 }
  29
  30 void poly1305_core_setkey(struct poly1305_key *key, const u8 *raw_key)
  31 {
  32         /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
  33         key->r[0] = (get_unaligned_le32(raw_key +  0) >> 0) & 0x3ffffff;
  34         key->r[1] = (get_unaligned_le32(raw_key +  3) >> 2) & 0x3ffff03;
  35         key->r[2] = (get_unaligned_le32(raw_key +  6) >> 4) & 0x3ffc0ff;
  36         key->r[3] = (get_unaligned_le32(raw_key +  9) >> 6) & 0x3f03fff;
  37         key->r[4] = (get_unaligned_le32(raw_key + 12) >> 8) & 0x00fffff;
  38 }
  39 EXPORT_SYMBOL_GPL(poly1305_core_setkey);
  40
  41 void poly1305_core_blocks(struct poly1305_state *state,
  42                           const struct poly1305_key *key, const void *src,
  43                           unsigned int nblocks, u32 hibit)
  44 {
  45         u32 r0, r1, r2, r3, r4;
  46         u32 s1, s2, s3, s4;
  47         u32 h0, h1, h2, h3, h4;
  48         u64 d0, d1, d2, d3, d4;
  49
  50         if (!nblocks)
  51                 return;
  52
  53         r0 = key->r[0];
  54         r1 = key->r[1];
  55         r2 = key->r[2];
  56         r3 = key->r[3];
  57         r4 = key->r[4];
  58
  59         s1 = r1 * 5;
  60         s2 = r2 * 5;
  61         s3 = r3 * 5;
  62         s4 = r4 * 5;
  63
  64         h0 = state->h[0];
  65         h1 = state->h[1];
  66         h2 = state->h[2];
  67         h3 = state->h[3];
  68         h4 = state->h[4];
  69
  70         do {
  71                 /* h += m[i] */
  72                 h0 += (get_unaligned_le32(src +  0) >> 0) & 0x3ffffff;
  73                 h1 += (get_unaligned_le32(src +  3) >> 2) & 0x3ffffff;
  74                 h2 += (get_unaligned_le32(src +  6) >> 4) & 0x3ffffff;
  75                 h3 += (get_unaligned_le32(src +  9) >> 6) & 0x3ffffff;
  76                 h4 += (get_unaligned_le32(src + 12) >> 8) | (hibit << 24);
  77
  78                 /* h *= r */
  79                 d0 = mlt(h0, r0) + mlt(h1, s4) + mlt(h2, s3) +
  80                      mlt(h3, s2) + mlt(h4, s1);
  81                 d1 = mlt(h0, r1) + mlt(h1, r0) + mlt(h2, s4) +
  82                      mlt(h3, s3) + mlt(h4, s2);
  83                 d2 = mlt(h0, r2) + mlt(h1, r1) + mlt(h2, r0) +
  84                      mlt(h3, s4) + mlt(h4, s3);
  85                 d3 = mlt(h0, r3) + mlt(h1, r2) + mlt(h2, r1) +
  86                      mlt(h3, r0) + mlt(h4, s4);
  87                 d4 = mlt(h0, r4) + mlt(h1, r3) + mlt(h2, r2) +
  88                      mlt(h3, r1) + mlt(h4, r0);
  89
  90                 /* (partial) h %= p */
  91                 d1 += sr(d0, 26);     h0 = and(d0, 0x3ffffff);
  92                 d2 += sr(d1, 26);     h1 = and(d1, 0x3ffffff);
  93                 d3 += sr(d2, 26);     h2 = and(d2, 0x3ffffff);
  94                 d4 += sr(d3, 26);     h3 = and(d3, 0x3ffffff);
  95                 h0 += sr(d4, 26) * 5; h4 = and(d4, 0x3ffffff);
  96                 h1 += h0 >> 26;       h0 = h0 & 0x3ffffff;
  97
  98                 src += POLY1305_BLOCK_SIZE;
  99         } while (--nblocks);
 100
 101         state->h[0] = h0;
 102         state->h[1] = h1;
 103         state->h[2] = h2;
 104         state->h[3] = h3;
 105         state->h[4] = h4;
 106 }
 107 EXPORT_SYMBOL_GPL(poly1305_core_blocks);
 108
 109 void poly1305_core_emit(const struct poly1305_state *state, void *dst)
 110 {
 111         u32 h0, h1, h2, h3, h4;
 112         u32 g0, g1, g2, g3, g4;
 113         u32 mask;
 114
 115         /* fully carry h */
 116         h0 = state->h[0];
 117         h1 = state->h[1];
 118         h2 = state->h[2];
 119         h3 = state->h[3];
 120         h4 = state->h[4];
 121
 122         h2 += (h1 >> 26);     h1 = h1 & 0x3ffffff;
 123         h3 += (h2 >> 26);     h2 = h2 & 0x3ffffff;
 124         h4 += (h3 >> 26);     h3 = h3 & 0x3ffffff;
 125         h0 += (h4 >> 26) * 5; h4 = h4 & 0x3ffffff;
 126         h1 += (h0 >> 26);     h0 = h0 & 0x3ffffff;
 127
 128         /* compute h + -p */
 129         g0 = h0 + 5;
 130         g1 = h1 + (g0 >> 26);             g0 &= 0x3ffffff;
 131         g2 = h2 + (g1 >> 26);             g1 &= 0x3ffffff;
 132         g3 = h3 + (g2 >> 26);             g2 &= 0x3ffffff;
 133         g4 = h4 + (g3 >> 26) - (1 << 26); g3 &= 0x3ffffff;
 134
 135         /* select h if h < p, or h + -p if h >= p */
 136         mask = (g4 >> ((sizeof(u32) * 8) - 1)) - 1;
 137         g0 &= mask;
 138         g1 &= mask;
 139         g2 &= mask;
 140         g3 &= mask;
 141         g4 &= mask;
 142         mask = ~mask;
 143         h0 = (h0 & mask) | g0;
 144         h1 = (h1 & mask) | g1;
 145         h2 = (h2 & mask) | g2;
 146         h3 = (h3 & mask) | g3;
 147         h4 = (h4 & mask) | g4;
 148
 149         /* h = h % (2^128) */
 150         put_unaligned_le32((h0 >>  0) | (h1 << 26), dst +  0);
 151         put_unaligned_le32((h1 >>  6) | (h2 << 20), dst +  4);
 152         put_unaligned_le32((h2 >> 12) | (h3 << 14), dst +  8);
 153         put_unaligned_le32((h3 >> 18) | (h4 <<  8), dst + 12);
 154 }
 155 EXPORT_SYMBOL_GPL(poly1305_core_emit);
 156
 157 void poly1305_init_generic(struct poly1305_desc_ctx *desc, const u8 *key)
 158 {
 159         poly1305_core_setkey(desc->r, key);
 160         desc->s[0] = get_unaligned_le32(key + 16);
 161         desc->s[1] = get_unaligned_le32(key + 20);
 162         desc->s[2] = get_unaligned_le32(key + 24);
 163         desc->s[3] = get_unaligned_le32(key + 28);
 164         poly1305_core_init(&desc->h);
 165         desc->buflen = 0;
 166         desc->sset = true;
 167         desc->rset = 1;
 168 }
 169 EXPORT_SYMBOL_GPL(poly1305_init_generic);
 170
 171 void poly1305_update_generic(struct poly1305_desc_ctx *desc, const u8 *src,
 172                              unsigned int nbytes)
 173 {
 174         unsigned int bytes;
 175
 176         if (unlikely(desc->buflen)) {
 177                 bytes = min(nbytes, POLY1305_BLOCK_SIZE - desc->buflen);
 178                 memcpy(desc->buf + desc->buflen, src, bytes);
 179                 src += bytes;
 180                 nbytes -= bytes;
 181                 desc->buflen += bytes;
 182
 183                 if (desc->buflen == POLY1305_BLOCK_SIZE) {
 184                         poly1305_core_blocks(&desc->h, desc->r, desc->buf, 1, 1);
 185                         desc->buflen = 0;
 186                 }
 187         }
 188
 189         if (likely(nbytes >= POLY1305_BLOCK_SIZE)) {
 190                 poly1305_core_blocks(&desc->h, desc->r, src,
 191                                      nbytes / POLY1305_BLOCK_SIZE, 1);
 192                 src += nbytes - (nbytes % POLY1305_BLOCK_SIZE);
 193                 nbytes %= POLY1305_BLOCK_SIZE;
 194         }
 195
 196         if (unlikely(nbytes)) {
 197                 desc->buflen = nbytes;
 198                 memcpy(desc->buf, src, nbytes);
 199         }
 200 }
 201 EXPORT_SYMBOL_GPL(poly1305_update_generic);
 202
 203 void poly1305_final_generic(struct poly1305_desc_ctx *desc, u8 *dst)
 204 {
 205         __le32 digest[4];
 206         u64 f = 0;
 207
 208         if (unlikely(desc->buflen)) {
 209                 desc->buf[desc->buflen++] = 1;
 210                 memset(desc->buf + desc->buflen, 0,
 211                        POLY1305_BLOCK_SIZE - desc->buflen);
 212                 poly1305_core_blocks(&desc->h, desc->r, desc->buf, 1, 0);
 213         }
 214
 215         poly1305_core_emit(&desc->h, digest);
 216
 217         /* mac = (h + s) % (2^128) */
 218         f = (f >> 32) + le32_to_cpu(digest[0]) + desc->s[0];
 219         put_unaligned_le32(f, dst + 0);
 220         f = (f >> 32) + le32_to_cpu(digest[1]) + desc->s[1];
 221         put_unaligned_le32(f, dst + 4);
 222         f = (f >> 32) + le32_to_cpu(digest[2]) + desc->s[2];
 223         put_unaligned_le32(f, dst + 8);
 224         f = (f >> 32) + le32_to_cpu(digest[3]) + desc->s[3];
 225         put_unaligned_le32(f, dst + 12);
 226
 227         *desc = (struct poly1305_desc_ctx){};
 228 }
 229 EXPORT_SYMBOL_GPL(poly1305_final_generic);
 230
 231 MODULE_LICENSE("GPL");
 232 MODULE_AUTHOR("Martin Willi <martin@strongswan.org>");