Welcome to little lamb

Code » limb » commit f660142

Add poly1305.h & related functions

author Olivier Brunel
2023-04-28 19:04:26 UTC
committer Olivier Brunel
2023-05-20 18:06:38 UTC
parent 241529d25ac1fbf568a4a2234516492c17e0aae5

Add poly1305.h & related functions

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;
+    }
+}