author | Olivier Brunel
<jjk@jjacky.com> 2023-04-28 19:04:26 UTC |
committer | Olivier Brunel
<jjk@jjacky.com> 2023-05-20 18:06:38 UTC |
parent | 241529d25ac1fbf568a4a2234516492c17e0aae5 |
meta/AUTHORS | +1 | -0 |
src/doc/hmac.h/hmac.3.md | +1 | -1 |
src/doc/poly1305.h.0.md | +35 | -0 |
src/doc/poly1305.h/poly1305_init.3.md | +39 | -0 |
src/include/poly1305.h | +14 | -0 |
src/liblimb/include/limb/poly1305.h | +27 | -0 |
src/liblimb/poly1305.h/poly1305_blocks.c | +70 | -0 |
src/liblimb/poly1305.h/poly1305_final.c | +73 | -0 |
src/liblimb/poly1305.h/poly1305_init.c | +32 | -0 |
src/liblimb/poly1305.h/poly1305_update.c | +44 | -0 |
diff --git a/meta/AUTHORS b/meta/AUTHORS index 88fcb48..441b9c3 100644 --- a/meta/AUTHORS +++ b/meta/AUTHORS @@ -3,6 +3,7 @@ Main author: Contributors: * Aleksey Kravchenko <rhash.admin@gmail.com> [sha3] +* Andrew Moon [poly1305] * Bob Jenkins [hlookup] * Samuel Neves [blake3] * Jack O'Connor [blake3] diff --git a/src/doc/hmac.h/hmac.3.md b/src/doc/hmac.h/hmac.3.md index c794238..481b604 100644 --- a/src/doc/hmac.h/hmac.3.md +++ b/src/doc/hmac.h/hmac.3.md @@ -49,4 +49,4 @@ int main(void) # SEE ALSO -[pbkdf2](3) +[pbkdf2](3), [poly1305_init](3) diff --git a/src/doc/poly1305.h.0.md b/src/doc/poly1305.h.0.md new file mode 100644 index 0000000..abffbca --- /dev/null +++ b/src/doc/poly1305.h.0.md @@ -0,0 +1,35 @@ +% limb manual +% poly1305.h(0) + +# NAME + +poly1305.h - Poly1305 authentication + +# SYNOPSIS + + #include <limb/poly1305.h> + +# DESCRIPTION + +This header defines the required function to compute Poly1305-based MAC of +messages. + +## Types + +The following types are defined : + +: *poly1305_ctx* +:: An opaque structure to be given to the functions below. + +## Functions + +The following functions are defined : + +: [poly1305_init](3) +:: To initialize a poly1305 context. + +: [poly1305_update](3) +:: To feed data into a poly1305 context. + +: [poly1305_final](3) +:: To obtain the HMAC from a poly1305 context. diff --git a/src/doc/poly1305.h/poly1305_init.3.md b/src/doc/poly1305.h/poly1305_init.3.md new file mode 100644 index 0000000..2808036 --- /dev/null +++ b/src/doc/poly1305.h/poly1305_init.3.md @@ -0,0 +1,39 @@ +% limb manual +% poly1305_init(3) + +# NAME + +poly1305\_init, poly1305\_update, poly1305\_final - compute Poly1305-based MAC +of a message + +# SYNOPSIS + + #include <limb/poly1305.h> + +```pre hl +void poly1305_init(const void *<em>key</em>, void *<em>ctx</em>) +void poly1305_update(const void *<em>msg</em>, size_t <em>mlen</em>, void *<em>ctx</em>) +void poly1305_final(void *<em>dst</em>, void *<em>ctx</em>) +``` + +# DESCRIPTION + +The `poly1305_init`() function initializes the given poly1305 context `ctx` to +compute a Poly1305-based message authentication code. + +This implementation is conform to [RFC 8439][rfc8439], as such the key pointed +to by `key` must be 256bit/32 bytes long. + +[rfc8439] (https://datatracker.ietf.org/doc/html/rfc8439) + + +The `poly1305_upate`() function feeds the specified chunk of data pointed by +`msg` of length `mlen` (in bytes) to be hashed into the given `ctx`. You can +call this function as many times as needed. + +The `poly1305_final`() function stores the computed MAC from `ctx` in binary +form into `dst`, which must be able to store 16 bytes. + +# SEE ALSO + +[hmac](3) diff --git a/src/include/poly1305.h b/src/include/poly1305.h new file mode 100644 index 0000000..c95b399 --- /dev/null +++ b/src/include/poly1305.h @@ -0,0 +1,14 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef LIMB_LIMB_POLY1305_H +#define LIMB_LIMB_POLY1305_H + +#include <limb/gccattributes.h> +#include <limb/u32.h> + +#define U32(n) (* (u32 * ) u32_le(n)) + +extern void poly1305_blocks(const u8 *msg, size_t mlen, poly1305_ctx *ctx) gccattr_hidden; + +#endif /* LIMB_LIMB_POLY1305_H */ diff --git a/src/liblimb/include/limb/poly1305.h b/src/liblimb/include/limb/poly1305.h new file mode 100644 index 0000000..f5c92d4 --- /dev/null +++ b/src/liblimb/include/limb/poly1305.h @@ -0,0 +1,27 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef LIMB_POLY1305_H +#define LIMB_POLY1305_H + +#include <stddef.h> /* size_t */ +#include <limb/int.h> + +#define POLY1305_BLOCKSIZE 16 + +struct poly1305_ctx { + u32 r[5]; + u32 s[5]; + u32 a[5]; + size_t leftover; + u8 buf[POLY1305_BLOCKSIZE]; + u8 final; +}; + +typedef struct poly1305_ctx poly1305_ctx; + +extern void poly1305_init(const void *key, void *ctx); +extern void poly1305_update(const void *msg, size_t mlen, void *ctx); +extern void poly1305_final(void *dst, void *ctx); + +#endif /* LIMB_POLY1305_H */ diff --git a/src/liblimb/poly1305.h/poly1305_blocks.c b/src/liblimb/poly1305.h/poly1305_blocks.c new file mode 100644 index 0000000..d424f21 --- /dev/null +++ b/src/liblimb/poly1305.h/poly1305_blocks.c @@ -0,0 +1,70 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* Based on poly1305-donna + * Copyright (C) 2016 Andrew Moon */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#include <string.h> +#include <limb/poly1305.h> +#include "poly1305.h" + +void +poly1305_blocks(const u8 *msg, size_t mlen, struct poly1305_ctx *ctx) +{ + const u32 hibit = (ctx->final) ? 0 : (U32_C(1) << 24); /* 1 << 128 */ + u32 r0, r1, r2, r3, r4; + u32 s1, s2, s3, s4; + u32 a0, a1, a2, a3, a4; + u64 d0, d1, d2, d3, d4; + u32 c; + + r0 = ctx->r[0]; + r1 = ctx->r[1]; + r2 = ctx->r[2]; + r3 = ctx->r[3]; + r4 = ctx->r[4]; + + s1 = r1 * 5; + s2 = r2 * 5; + s3 = r3 * 5; + s4 = r4 * 5; + + a0 = ctx->a[0]; + a1 = ctx->a[1]; + a2 = ctx->a[2]; + a3 = ctx->a[3]; + a4 = ctx->a[4]; + + while (mlen >= POLY1305_BLOCKSIZE) { + /* a += msg[i] */ + a0 += (U32(msg + 0) ) & 0x03ffffff; + a1 += (U32(msg + 3) >> 2) & 0x03ffffff; + a2 += (U32(msg + 6) >> 4) & 0x03ffffff; + a3 += (U32(msg + 9) >> 6) & 0x03ffffff; + a4 += (U32(msg + 12) >> 8) | hibit; + + /* a *= r */ + d0 = ((u64) a0 * r0) + ((u64) a1 * s4) + ((u64) a2 * s3) + ((u64) a3 * s2) + ((u64) a4 * s1); + d1 = ((u64) a0 * r1) + ((u64) a1 * r0) + ((u64) a2 * s4) + ((u64) a3 * s3) + ((u64) a4 * s2); + d2 = ((u64) a0 * r2) + ((u64) a1 * r1) + ((u64) a2 * r0) + ((u64) a3 * s4) + ((u64) a4 * s3); + d3 = ((u64) a0 * r3) + ((u64) a1 * r2) + ((u64) a2 * r1) + ((u64) a3 * r0) + ((u64) a4 * s4); + d4 = ((u64) a0 * r4) + ((u64) a1 * r3) + ((u64) a2 * r2) + ((u64) a3 * r1) + ((u64) a4 * r0); + + /* (partial) a %= p */ + c = (u32) (d0 >> 26); a0 = (u32) d0 & 0x3ffffff; + d1 += c; c = (u32) (d1 >> 26); a1 = (u32) d1 & 0x3ffffff; + d2 += c; c = (u32) (d2 >> 26); a2 = (u32) d2 & 0x3ffffff; + d3 += c; c = (u32) (d3 >> 26); a3 = (u32) d3 & 0x3ffffff; + d4 += c; c = (u32) (d4 >> 26); a4 = (u32) d4 & 0x3ffffff; + a0 += c * 5; c = (u32) (a0 >> 26); a0 = (u32) a0 & 0x3ffffff; + a1 += c; + + mlen -= POLY1305_BLOCKSIZE; + msg += POLY1305_BLOCKSIZE; + } + + ctx->a[0] = a0; + ctx->a[1] = a1; + ctx->a[2] = a2; + ctx->a[3] = a3; + ctx->a[4] = a4; +} diff --git a/src/liblimb/poly1305.h/poly1305_final.c b/src/liblimb/poly1305.h/poly1305_final.c new file mode 100644 index 0000000..a474382 --- /dev/null +++ b/src/liblimb/poly1305.h/poly1305_final.c @@ -0,0 +1,73 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* Based on poly1305-donna + * Copyright (C) 2016 Andrew Moon */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#include <string.h> +#include <limb/poly1305.h> +#include "poly1305.h" + +void +poly1305_final(void *dst_, void *ctx_) +{ + struct poly1305_ctx *ctx = ctx_; + u8 *dst = dst_; + + u32 g0, g1, g2, g3, g4; + u32 c; + u64 f; + u32 mask; + + /* process remaining block */ + if (ctx->leftover) { + size_t i = ctx->leftover; + ctx->buf[i++] = 1; + memset(ctx->buf + i, 0, POLY1305_BLOCKSIZE - i); + ctx->final = 1; + poly1305_blocks(ctx->buf, POLY1305_BLOCKSIZE, ctx); + } + + /* fully carry a */ + c = ctx->a[1] >> 26; ctx->a[1] = ctx->a[1] & 0x03ffffff; + ctx->a[2] += c ; c = ctx->a[2] >> 26; ctx->a[2] = ctx->a[2] & 0x03ffffff; + ctx->a[3] += c ; c = ctx->a[3] >> 26; ctx->a[3] = ctx->a[3] & 0x03ffffff; + ctx->a[4] += c ; c = ctx->a[4] >> 26; ctx->a[4] = ctx->a[4] & 0x03ffffff; + ctx->a[0] += c * 5; c = ctx->a[0] >> 26; ctx->a[0] = ctx->a[0] & 0x03ffffff; + ctx->a[1] += c; + + /* compute a + -p */ + g0 = ctx->a[0] + 5; c = g0 >> 26; g0 &= 0x03ffffff; + g1 = ctx->a[1] + c; c = g1 >> 26; g1 &= 0x03ffffff; + g2 = ctx->a[2] + c; c = g2 >> 26; g2 &= 0x03ffffff; + g3 = ctx->a[3] + c; c = g3 >> 26; g3 &= 0x03ffffff; + g4 = ctx->a[4] + c - (U32_C(1) << 26); + + /* select a if a < p, or a + -p if a >= p */ + mask = (g4 >> ((sizeof(u32) * 8) - 1)) - 1; + g0 &= mask; + g1 &= mask; + g2 &= mask; + g3 &= mask; + g4 &= mask; + mask = ~mask; + ctx->a[0] = (ctx->a[0] & mask) | g0; + ctx->a[1] = (ctx->a[1] & mask) | g1; + ctx->a[2] = (ctx->a[2] & mask) | g2; + ctx->a[3] = (ctx->a[3] & mask) | g3; + ctx->a[4] = (ctx->a[4] & mask) | g4; + + /* a = a % (2^128) */ + ctx->a[0] = ((ctx->a[0] ) | (ctx->a[1] << 26)) & 0xffffffff; + ctx->a[1] = ((ctx->a[1] >> 6) | (ctx->a[2] << 20)) & 0xffffffff; + ctx->a[2] = ((ctx->a[2] >> 12) | (ctx->a[3] << 14)) & 0xffffffff; + ctx->a[3] = ((ctx->a[3] >> 18) | (ctx->a[4] << 8)) & 0xffffffff; + + /* mac = (a + s) % (2^128) */ + f = (u64) ctx->a[0] + ctx->s[0]; ctx->a[0] = (u32) f; + f = (u64) ctx->a[1] + ctx->s[1] + (f >> 32); ctx->a[1] = (u32) f; + f = (u64) ctx->a[2] + ctx->s[2] + (f >> 32); ctx->a[2] = (u32) f; + f = (u64) ctx->a[3] + ctx->s[3] + (f >> 32); ctx->a[3] = (u32) f; + + memcpy(dst, ctx->a, 4 * sizeof(*ctx->a)); + u32pa_le(dst, 4); +} diff --git a/src/liblimb/poly1305.h/poly1305_init.c b/src/liblimb/poly1305.h/poly1305_init.c new file mode 100644 index 0000000..a491930 --- /dev/null +++ b/src/liblimb/poly1305.h/poly1305_init.c @@ -0,0 +1,32 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* Based on poly1305-donna + * Copyright (C) 2016 Andrew Moon */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#include <string.h> +#include <limb/poly1305.h> +#include "poly1305.h" + +void +poly1305_init(const void *key_, void *ctx_) +{ + struct poly1305_ctx *ctx = ctx_; + const u8 *key = key_; + + /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */ + ctx->r[0] = (U32(key + 0) ) & 0x03ffffff; + ctx->r[1] = (U32(key + 3) >> 2) & 0x03ffff03; + ctx->r[2] = (U32(key + 6) >> 4) & 0x03ffc0ff; + ctx->r[3] = (U32(key + 9) >> 6) & 0x03f03fff; + ctx->r[4] = (U32(key + 12) >> 8) & 0x000fffff; + + /* s */ + memcpy(ctx->s, key + 16, 16); + u32pa_le(ctx->s, 4); + + /* a = 0 */ + ctx->a[0] = ctx->a[1] = ctx->a[2] = ctx->a[3] = ctx->a[4] = 0; + + ctx->leftover = 0; + ctx->final = 0; +} diff --git a/src/liblimb/poly1305.h/poly1305_update.c b/src/liblimb/poly1305.h/poly1305_update.c new file mode 100644 index 0000000..112eac3 --- /dev/null +++ b/src/liblimb/poly1305.h/poly1305_update.c @@ -0,0 +1,44 @@ +/* This file is part of limb https://lila.oss/limb + * Copyright (C) 2023 Olivier Brunel jjk@jjacky.com */ +/* Based on poly1305-donna + * Copyright (C) 2016 Andrew Moon */ +/* SPDX-License-Identifier: GPL-2.0-only */ +#include <string.h> +#include <limb/poly1305.h> +#include "poly1305.h" + +void +poly1305_update(const void *msg_, size_t mlen, void *ctx_) +{ + struct poly1305_ctx *ctx = ctx_; + const u8 *msg = msg_; + + /* handle leftover */ + if (ctx->leftover) { + size_t want = POLY1305_BLOCKSIZE - ctx->leftover; + if (want > mlen) + want = mlen; + memcpy(ctx->buf + ctx->leftover, msg, want); + mlen -= want; + msg += want; + ctx->leftover += want; + if (ctx->leftover < POLY1305_BLOCKSIZE) + return; + poly1305_blocks(ctx->buf, POLY1305_BLOCKSIZE, ctx); + ctx->leftover = 0; + } + + /* process full blocks */ + if (mlen >= POLY1305_BLOCKSIZE) { + size_t want = (mlen & ~(POLY1305_BLOCKSIZE - 1)); + poly1305_blocks(msg, want, ctx); + mlen -= want; + msg += want; + } + + /* store leftover */ + if (mlen) { + memcpy(ctx->buf + ctx->leftover, msg, mlen); + ctx->leftover += mlen; + } +}