Implemented umac.

17 files changed, 1718 insertions, 2 deletions

diff --git a/ChangeLog b/ChangeLog
index 015f3c08..b1137e3e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,18 @@
 2013-04-11  Niels Möller  <nisse@lysator.liu.se>
 
+	Initial implementation of umac.
+	* umac.h: New file.
+	* umac-nh.c: New file.
+	* umac-nh-n.c: New file.
+	* umac-poly64.c: New file.
+	* umac-poly128.c: New file.
+	* umac-l2.c: New file.
+	* umac-l3.c: New file.
+	* Makefile.in (nettle_SOURCES): Added umac source files.
+	(HEADERS): Added umac.h.
+	* testsuite/umac-test.c: New file.
+	* testsuite/Makefile.in (TS_NETTLE_SOURCES): Added umac-test.c.
+
 	* ecc-mul-a.c (ecc_mul_a): Avoid using mp_bitcnt_t, for
 	compatibility with older GMP versions.
 	* ecc-mul-g.c (ecc_mul_g): Likewise.
diff --git a/Makefile.in b/Makefile.in
index 0242f270..ae20a67c 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -96,6 +96,9 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c \
 		 serpent-set-key.c serpent-encrypt.c serpent-decrypt.c \
 		 serpent-meta.c \
 		 twofish.c twofish-meta.c \
+		 umac-nh.c umac-nh-n.c umac-l2.c umac-l3.c \
+		 umac-poly64.c umac-poly128.c umac-set-key.c \
+		 umac32.c umac64.c umac96.c umac128.c \
 		 yarrow256.c yarrow_key_event.c \
 		 buffer.c buffer-init.c realloc.c \
 		 nettle-meta-hashes.c nettle-meta-ciphers.c \
@@ -152,7 +155,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h bignum.h blowfish.h \
 	  pgp.h pkcs1.h realloc.h ripemd160.h rsa.h rsa-compat.h \
 	  salsa20.h sexp.h \
 	  serpent.h sha.h sha1.h sha2.h sha3.h twofish.h \
-	  yarrow.h
+	  umac.h yarrow.h
 
 INSTALL_HEADERS = $(HEADERS) nettle-stdint.h
 
diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make
index a935171d..93ba9a81 100644
--- a/testsuite/.test-rules.make
+++ b/testsuite/.test-rules.make
@@ -106,6 +106,9 @@ gcm-test$(EXEEXT): gcm-test.$(OBJEXT)
 hmac-test$(EXEEXT): hmac-test.$(OBJEXT)
 	$(LINK) hmac-test.$(OBJEXT) $(TEST_OBJS) -o hmac-test$(EXEEXT)
 
+umac-test$(EXEEXT): umac-test.$(OBJEXT)
+	$(LINK) umac-test.$(OBJEXT) $(TEST_OBJS) -o umac-test$(EXEEXT)
+
 meta-hash-test$(EXEEXT): meta-hash-test.$(OBJEXT)
 	$(LINK) meta-hash-test.$(OBJEXT) $(TEST_OBJS) -o meta-hash-test$(EXEEXT)
 
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index a155b447..91f6e2a3 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -25,7 +25,7 @@ TS_NETTLE_SOURCES = aes-test.c arcfour-test.c arctwo-test.c \
 		    sha3-384-test.c sha3-512-test.c \
 		    serpent-test.c twofish-test.c \
 		    knuth-lfib-test.c \
-		    cbc-test.c ctr-test.c gcm-test.c hmac-test.c \
+		    cbc-test.c ctr-test.c gcm-test.c hmac-test.c umac-test.c \
 		    meta-hash-test.c meta-cipher-test.c meta-armor-test.c \
 		    buffer-test.c yarrow-test.c pbkdf2-test.c
 
diff --git a/testsuite/umac-test.c b/testsuite/umac-test.c
new file mode 100644
index 00000000..4694b0c2
--- /dev/null
+++ b/testsuite/umac-test.c
@@ -0,0 +1,313 @@
+#include "testutils.h"
+#include "umac.h"
+
+static void
+test_umac (const struct tstring *key,
+	   const struct tstring *nonce,
+	   const struct tstring *msg,
+	   unsigned length,
+	   const struct tstring *ref32,
+	   const struct tstring *ref64,
+	   const struct tstring *ref128)
+{
+  struct umac32_ctx ctx32;
+  struct umac64_ctx ctx64;
+  struct umac96_ctx ctx96;
+  struct umac128_ctx ctx128;
+
+  unsigned i;
+  uint8_t tag[16];
+
+  ASSERT (key->length == UMAC_KEY_SIZE);
+  ASSERT (ref32->length == 4);
+  ASSERT (ref64->length == 8);
+  ASSERT (ref128->length == 16);
+
+  umac32_set_key (&ctx32, key->data);
+  umac32_set_nonce (&ctx32, nonce->length, nonce->data);
+
+  for (i = length; i > msg->length; i-= msg->length)
+    umac32_update (&ctx32, msg->length, msg->data);
+  umac32_update (&ctx32, i, msg->data);
+
+  umac32_digest (&ctx32, 4, tag);
+  if (memcmp (tag, ref32->data, 4) != 0)
+    {
+      printf ("umac32 failed\n");
+      printf ("msg: "); print_hex (msg->length, msg->data);
+      printf ("length: %u\n", length);
+      printf ("tag: "); print_hex (4, tag);
+      printf ("ref: "); print_hex (ref32->length, ref32->data);
+      abort ();
+    }
+
+  umac64_set_key (&ctx64, key->data);
+  umac64_set_nonce (&ctx64, nonce->length, nonce->data);
+
+  for (i = length; i > msg->length; i-= msg->length)
+    umac64_update (&ctx64, msg->length, msg->data);
+  umac64_update (&ctx64, i, msg->data);
+
+  umac64_digest (&ctx64, 8, tag);
+  if (memcmp (tag, ref64->data, 8) != 0)
+    {
+      printf ("umac64 failed\n");
+      printf ("msg: "); print_hex (msg->length, msg->data);
+      printf ("length: %u\n", length);
+      printf ("tag: "); print_hex (8, tag);
+      printf ("ref: "); print_hex (ref64->length, ref64->data);
+      abort ();
+    }
+
+  umac96_set_key (&ctx96, key->data);
+  umac96_set_nonce (&ctx96, nonce->length, nonce->data);
+
+  for (i = length; i > msg->length; i-= msg->length)
+    umac96_update (&ctx96, msg->length, msg->data);
+  umac96_update (&ctx96, i, msg->data);
+
+  umac96_digest (&ctx96, 12, tag);
+  if (memcmp (tag, ref128->data, 12) != 0)
+    {
+      printf ("umac96 failed\n");
+      printf ("msg: "); print_hex (msg->length, msg->data);
+      printf ("length: %u\n", length);
+      printf ("tag: "); print_hex (12, tag);
+      printf ("ref: "); print_hex (12, ref128->data);
+      abort ();
+    }
+
+  umac128_set_key (&ctx128, key->data);
+  umac128_set_nonce (&ctx128, nonce->length, nonce->data);
+
+  for (i = length; i > msg->length; i-= msg->length)
+    umac128_update (&ctx128, msg->length, msg->data);
+  umac128_update (&ctx128, i, msg->data);
+
+  umac128_digest (&ctx128, 16, tag);
+  if (memcmp (tag, ref128->data, 16) != 0)
+    {
+      printf ("umac128 failed\n");
+      printf ("msg: "); print_hex (msg->length, msg->data);
+      printf ("length: %u\n", length);
+      printf ("tag: "); print_hex (16, tag);
+      printf ("ref: "); print_hex (ref128->length, ref128->data);
+      abort ();
+    }
+}
+
+void
+test_main(void)
+{
+  /* From RFC 4418 (except that it lacks the last 32 bits of 128-bit
+     tags) */
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA(""), 0,
+	     SHEX("113145FB"),
+	     SHEX("6E155FAD26900BE1"),
+	     SHEX("32fedb100c79ad58f07ff7643cc60465"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("a"), 3,
+	     SHEX("3B91D102"),
+	     SHEX("44B5CB542F220104"),
+	     SHEX("185e4fe905cba7bd85e4c2dc3d117d8d"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("a"), 1<<10,
+	     SHEX("599B350B"),
+	     SHEX("26BF2F5D60118BD9"),
+	     SHEX("7a54abe04af82d60fb298c3cbd195bcb"));
+
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("aaaaaaaa"), 1<<15,
+	     SHEX("58DCF532"),
+	     SHEX("27F8EF643B0D118D"),
+	     SHEX("7b136bd911e4b734286ef2be501f2c3c"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("aaaaaaaa"), 1<<20,
+	     SHEX("DB6364D1"),
+	     SHEX("A4477E87E9F55853"),
+	     SHEX("f8acfa3ac31cfeea047f7b115b03bef5"));
+  /* Needs POLY128 */
+  /* For the 'a' * 2^25 testcase, see errata
+     http://fastcrypto.org/umac/rfc4418.errata.txt */
+  test_umac (SDATA("abcdefghijklmnop"), SDATA ("bcdefghi"),
+	     SDATA ("aaaaaaaa"), 1<<25,
+	     SHEX("85EE5CAE"),
+	     SHEX("FACA46F856E9B45F"),
+	     SHEX("a621c2457c0012e64f3fdae9e7e1870c"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA ("bcdefghi"),
+	     SDATA ("abc"), 3,
+	     SHEX("ABF3A3A0"),
+	     SHEX("D4D7B9F6BD4FBFCF"),
+	     SHEX("883c3d4b97a61976ffcf232308cba5a5"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA ("bcdefghi"),
+	     SDATA ("abc"), 1500,
+	     SHEX("ABEB3C8B"),
+	     SHEX("D4CF26DDEFD5C01A"),
+	     SHEX("8824a260c53c66a36c9260a62cb83aa1"));
+
+  /* Tests exercising various sizes of nonce and data: All nonce
+     lengths from 1 to 16 bytes. Data sizes chosen for testing for
+     various off-by-one errors,
+
+       0, 1, 2, 3, 4,
+       1020, 1021, 1022, 1023, 1024, 1025, 1026, 1027,
+       2046, 2047, 2048, 2049, 2050
+       16777212, 16777213, 16777214, 16777215, 16777216, 16777217,
+       16778239, 16778240, 16778241, 16778242, 16778243, 16778244
+  */
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("b"),
+	     SDATA("defdefdefdefdef"), 0,
+	     SHEX("3a58486b"),
+	     SHEX("9e38f67da91a08d9"),
+	     SHEX("9e38f67da91a08d9c980f4db4089c877"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bc"),
+	     SDATA("defdefdefdefdef"), 1,
+	     SHEX("d86b1512"),
+	     SHEX("fb0e207971b8e66a"),
+	     SHEX("ef406c2ec70d0222f59e860eabb79ed0"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcd"),
+	     SDATA("defdefdefdefdef"), 2,
+	     SHEX("1ae6e02d"),
+	     SHEX("1ae6e02d73aa9ab2"),
+	     SHEX("1ae6e02d73aa9ab2a27fb89e014dc07b"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcde"),
+	     SDATA("defdefdefdefdef"), 3,
+	     SHEX("e8c1eb59"),
+	     SHEX("c81cf22342e84302"),
+	     SHEX("82626d0d575e01038e5e2cc6408216f5"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdef"),
+	     SDATA("defdefdefdefdef"), 4,
+	     SHEX("8950f0d3"),
+	     SHEX("aba003e7bd673cc3"),
+	     SHEX("aba003e7bd673cc368ba8513cecf2e7c"));
+
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefg"),
+	     SDATA("defdefdefdefdef"), 1020,
+	     SHEX("7412167c"),
+	     SHEX("f98828a161bb4ae3"),
+	     SHEX("d8b4811f747d588d7a913360960de7cf"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefgh"),
+	     SDATA("defdefdefdefdef"), 1021,
+	     SHEX("2d54936b"),
+	     SHEX("2d54936be5bff72d"),
+	     SHEX("2d54936be5bff72d2e1052361163b474"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("defdefdefdefdef"), 1022,
+	     SHEX("53ca8dd2"),
+	     SHEX("2cee9784556387b3"),
+	     SHEX("700513397f8a210a98938d3e7ac3bd88"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghij"),
+	     SDATA("defdefdefdefdef"), 1023,
+	     SHEX("26cc58df"),
+	     SHEX("24ac4284ca371f42"),
+	     SHEX("24ac4284ca371f4280f60bd274633d67"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijk"),
+	     SDATA("defdefdefdefdef"), 1024,
+	     SHEX("3cada45a"),
+	     SHEX("64c6a0fd14615a76"),
+	     SHEX("abc223116cedd2db5af365e641a97539"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijkl"),
+	     SDATA("defdefdefdefdef"), 1025,
+	     SHEX("93251e18"),
+	     SHEX("93251e18e56bbdc4"),
+	     SHEX("93251e18e56bbdc457de556f95c59931"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklm"),
+	     SDATA("defdefdefdefdef"), 1026,
+	     SHEX("24a4c3ab"),
+	     SHEX("5d98bd8dfaf16352"),
+	     SHEX("c1298672e52386753383a15ed58c0e42"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmn"),
+	     SDATA("defdefdefdefdef"), 1027,
+	     SHEX("e7e98945"),
+	     SHEX("5b0557c9fdcf661b"),
+	     SHEX("5b0557c9fdcf661b1758efc603516ebe"));
+
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmno"),
+	     SDATA("defdefdefdefdef"), 2046,
+	     SHEX("e12ddc9f"),
+	     SHEX("65e85d47447c2277"),
+	     SHEX("16bb5183017826ed47c9995c1e5834f3"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmnop"),
+	     SDATA("defdefdefdefdef"), 2047,
+	     SHEX("34d723a6"),
+	     SHEX("34d723a6cb1676d3"),
+	     SHEX("34d723a6cb1676d3547a5064dc5b0a37"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmnopq"),
+	     SDATA("defdefdefdefdef"), 2048,
+	     SHEX("21fd8802"),
+	     SHEX("3968d5d0af147884"),
+	     SHEX("84565620def1e3a614d274e87626f215"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("b"),
+	     SDATA("defdefdefdefdef"), 2049,
+	     SHEX("097e5abd"),
+	     SHEX("ad1ee4ab606061c5"),
+	     SHEX("ad1ee4ab606061c55e0d2ecfee59940a"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bc"),
+	     SDATA("defdefdefdefdef"), 2050,
+	     SHEX("a03a7fe9"),
+	     SHEX("835f4a8242100055"),
+	     SHEX("971106d5f4a5e41dce40a91704cfe1f3"));
+
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcd"),
+	     SDATA("defdefdefdefdef"), 16777212,
+	     SHEX("7ef41cf3"),
+	     SHEX("7ef41cf351960aaf"),
+	     SHEX("7ef41cf351960aaf729bb19fcee7d8c4"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcde"),
+	     SDATA("defdefdefdefdef"), 16777213,
+	     SHEX("8bf81932"),
+	     SHEX("ab250048807ff640"),
+	     SHEX("e15b9f6695c9b441de035e9b10b8ac32"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdef"),
+	     SDATA("defdefdefdefdef"), 16777214,
+	     SHEX("ddb2f0ab"),
+	     SHEX("ff42039fcfe1248e"),
+	     SHEX("ff42039fcfe1248e36c19efed14d7140"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefg"),
+	     SDATA("defdefdefdefdef"), 16777215,
+	     SHEX("e67ad507"),
+	     SHEX("6be0ebda623d76df"),
+	     SHEX("4adc426477fb64b1ce5afd76d505f048"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefgh"),
+	     SDATA("defdefdefdefdef"), 16777216,
+	     SHEX("42d8562a"),
+	     SHEX("42d8562a224a9e9a"),
+	     SHEX("42d8562a224a9e9a75c2f85d39462d07"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghi"),
+	     SDATA("defdefdefdefdef"), 16777217,
+	     SHEX("486b138d"),
+	     SHEX("374f09dbb0b84b88"),
+	     SHEX("6ba48d669a51ed3195ebc2aa562ee71b"));
+
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghij"),
+	     SDATA("defdefdefdefdef"), 16778239,
+	     SHEX("850cb2c5"),
+	     SHEX("876ca89ed045777b"),
+	     SHEX("876ca89ed045777bf7efa7934e1758c2"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijk"),
+	     SDATA("defdefdefdefdef"), 16778240,
+	     SHEX("b9fc4f81"),
+	     SHEX("e1974b26fb35f2c6"),
+	     SHEX("2e93c8ca83b97a6b1a21082e2a4c540d"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijkl"),
+	     SDATA("defdefdefdefdef"), 16778241,
+	     SHEX("ffced8f2"),
+	     SHEX("ffced8f2494d85bf"),
+	     SHEX("ffced8f2494d85bf0cb39408ddfe0295"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklm"),
+	     SDATA("defdefdefdefdef"), 16778242,
+	     SHEX("1c99c5fb"),
+	     SHEX("65a5bbdda3b85368"),
+	     SHEX("f9148022bc6ab64f019e9db83704c17b"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmn"),
+	     SDATA("defdefdefdefdef"), 16778243,
+	     SHEX("ec304be9"),
+	     SHEX("50dc9565fbfc4884"),
+	     SHEX(" 50dc9565fbfc48844a4be34403804605"));
+  test_umac (SDATA("abcdefghijklmnop"), SDATA("bcdefghijklmno"),
+	     SDATA("defdefdefdefdef"), 16778244,
+	     SHEX("8034e26f"),
+	     SHEX("04f163b7c2d5d849"),
+	     SHEX("77a26f7387d1dcd39378a3220652cff7"));
+}
diff --git a/umac-l2.c b/umac-l2.c
new file mode 100644
index 00000000..7fa5650b
--- /dev/null
+++ b/umac-l2.c
@@ -0,0 +1,143 @@
+/* umac-l2.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+/* Same mask applied to low and high halves */
+#define KEY_MASK 0x01ffffffUL
+
+#if WORDS_BIGENDIAN
+#define BE_SWAP32(x) x
+#else
+#define BE_SWAP32(x)				\
+  ((ROTL32(8,  x) & 0x00FF00FFUL) |		\
+   (ROTL32(24, x) & 0xFF00FF00UL))
+#endif
+
+void
+_umac_l2_init (unsigned size, uint32_t *k)
+{
+  unsigned i;
+  for (i = 0; i < size; i++)
+    {
+      uint32_t w = k[i];
+      w = BE_SWAP32 (w);
+      k[i] = w & KEY_MASK;
+    }
+}
+
+void
+_umac_l2(const uint32_t *key, uint64_t *state, unsigned n,
+	 unsigned count, uint64_t *prev, const uint64_t *m)
+{
+  unsigned i;
+
+  if (count == 0)
+    memcpy (prev, m, n * sizeof(*m));
+  else if (count == 1)
+    for (i = 0; i < n; i++, key += 6)
+      {
+	uint64_t y = _umac_poly64 (key[0], key[1], 1, prev[i]);
+	state[2*i+1] = _umac_poly64 (key[0], key[1], y, m[i]);
+      }
+  else if (count < UMAC_POLY64_BLOCKS)
+    for (i = 0; i < n; i++, key += 6)
+      state[2*i+1] = _umac_poly64 (key[0], key[1], state[2*i+1], m[i]);
+  else if (count % 2 == 0)
+    {
+      if (count == UMAC_POLY64_BLOCKS)
+	for (i = 0, key += 2; i < n; i++, key += 6)
+	  {
+	    uint64_t y = state[2*i+1];
+	    if (y >= UMAC_P64)
+	      y -= UMAC_P64;
+	    state[2*i] = 0;
+	    state[2*i+1] = 1;
+
+	    _umac_poly128 (key, state + 2*i, 0, y);
+	    memcpy (prev, m, n * sizeof(*m));
+	  }
+      memcpy (prev, m, n * sizeof(*m));
+    }
+  else
+    for (i = 0, key += 2; i < n; i++, key += 6)
+      _umac_poly128 (key, state + 2*i, prev[i], m[i]);
+}
+
+void
+_umac_l2_final(const uint32_t *key, uint64_t *state, unsigned n,
+	       unsigned count, uint64_t *prev)
+{
+  unsigned i;
+
+  assert (count > 0);
+  if (count == 1)
+    for (i = 0; i < n; i++)
+      {
+	*state++ = 0;
+	*state++ = *prev++;
+      }
+  else if (count <= UMAC_POLY64_BLOCKS)
+    for (i = 0; i < n; i++)
+      {
+	uint64_t y;
+	*state++ = 0;
+
+	y = *state;
+	if (y >= UMAC_P64)
+	  y -= UMAC_P64;
+	*state++ = y;
+      }
+  else
+    {
+      uint64_t pad = (uint64_t) 1 << 63;
+      if (count % 2 == 1)
+	for (i = 0, key += 2; i < n; i++, key += 6)
+	  _umac_poly128 (key, state + 2*i, prev[i], pad);
+      else
+	for (i = 0, key += 2; i < n; i++, key += 6)
+	  _umac_poly128 (key, state + 2*i, pad, 0);
+
+      for (i = 0; i < n; i++, state += 2)
+	{
+	  uint64_t yh, yl;
+
+	  yh = state[0];
+	  yl = state[1];
+	  if (yh == UMAC_P128_HI && yl >= UMAC_P128_LO)
+	    {
+	      state[0] = 0;
+	      state[1] = yl -= UMAC_P128_LO;
+	    }
+	}
+    }
+}
diff --git a/umac-l3.c b/umac-l3.c
new file mode 100644
index 00000000..7a13847e
--- /dev/null
+++ b/umac-l3.c
@@ -0,0 +1,87 @@
+/* umac-l3.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "umac.h"
+
+#include "macros.h"
+
+/* 2^36 - 5 */
+#define P 0x0000000FFFFFFFFBULL
+
+#if WORDS_BIGENDIAN
+#define BE_SWAP64(x) x
+#else
+#define BE_SWAP64(x)				\
+  (((x & 0xff) << 56)				\
+   | ((x & 0xff00) << 40)			\
+   | ((x & 0xff0000) << 24)			\
+   | ((x & 0xff000000) << 8)			\
+   | ((x >> 8) & 0xff000000)			\
+   | ((x >> 24) & 0xff0000)			\
+   | ((x >> 40) & 0xff00)			\
+   | (x >> 56) )
+#endif
+
+void
+_umac_l3_init (unsigned size, uint64_t *k)
+{
+  unsigned i;
+  for (i = 0; i < size; i++)
+    {
+      uint64_t w = k[i];
+      w = BE_SWAP64 (w);
+      k[i] = w % P;
+    }
+}
+
+static uint64_t
+umac_l3_word (const uint64_t *k, uint64_t w)
+{
+  unsigned i;
+  uint64_t y;
+
+  /* Since it's easiest to process the input word from the low end,
+   * loop over keys in reverse order. */
+
+  for (i = y = 0; i < 4; i++, w >>= 16)
+    y += (w & 0xffff) * k[3-i];
+
+  return y;
+}
+
+uint32_t
+_umac_l3 (const uint64_t *key_1, uint32_t key_2, const uint64_t *m)
+{
+  uint32_t y = (umac_l3_word (key_1, m[0])
+		+ umac_l3_word (key_1 + 4, m[1])) % P;
+  y ^= key_2;
+#if !WORDS_BIGENDIAN
+  y = ((ROTL32(8,  y) & 0x00FF00FFUL)
+       | (ROTL32(24, y) & 0xFF00FF00UL));
+#endif
+  return y;
+}
diff --git a/umac-nh-n.c b/umac-nh-n.c
new file mode 100644
index 00000000..953fb2f6
--- /dev/null
+++ b/umac-nh-n.c
@@ -0,0 +1,38 @@
+/* umac-nh-n.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "umac.h"
+
+/* FIXME: Single pass over the input */
+void
+_umac_nh_n (uint64_t *out, unsigned n, const uint32_t *key,
+	    unsigned length, const uint8_t *msg)
+{
+  unsigned i;
+   for (i = 0; i < n; i++)
+     out[i] = _umac_nh (key + 4*i, length, msg);
+}
diff --git a/umac-nh.c b/umac-nh.c
new file mode 100644
index 00000000..837590a0
--- /dev/null
+++ b/umac-nh.c
@@ -0,0 +1,59 @@
+/* umac-nh.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "umac.h"
+#include "macros.h"
+
+uint64_t
+_umac_nh (const uint32_t *key, unsigned length, const uint8_t *msg)
+{
+  uint64_t y;
+
+  assert (length > 0);
+  assert (length <= 1024);
+  assert (length % 32 == 0);
+  for (y = 0; length > 0; length -= 32, msg += 32, key += 8)
+    {
+      uint32_t a, b;
+      a = LE_READ_UINT32 (msg)      + key[0];
+      b = LE_READ_UINT32 (msg + 16) + key[4];
+      y += (uint64_t) a * b;
+      a = LE_READ_UINT32 (msg +  4) + key[1];
+      b = LE_READ_UINT32 (msg + 20) + key[5];
+      y += (uint64_t) a * b;
+      a = LE_READ_UINT32 (msg +  8) + key[2];
+      b = LE_READ_UINT32 (msg + 24) + key[6];
+      y += (uint64_t) a * b;
+      a = LE_READ_UINT32 (msg + 12) + key[3];
+      b = LE_READ_UINT32 (msg + 28) + key[7];
+      y += (uint64_t) a * b;
+    }
+
+  return y;
+}
diff --git a/umac-poly128.c b/umac-poly128.c
new file mode 100644
index 00000000..0c0f0a73
--- /dev/null
+++ b/umac-poly128.c
@@ -0,0 +1,140 @@
+/* umac-poly128.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "umac.h"
+
+#define HI(x) (x >> 32)
+#define LO(x) (x & 0xffffffffUL)
+
+static void
+poly128_mul (const uint32_t *k, uint64_t *y)
+{
+  uint64_t y0,y1,y2,y3,p0,p1,p2,p3,m0,m1,m2;
+  y0 = LO (y[1]);
+  y1 = HI (y[1]);
+  y2 = LO (y[0]);
+  y3 = HI (y[0]);
+
+  p0 = y0 * k[3];
+  m0 = y0 * k[2] + y1 * k[3];
+  p1 = y0 * k[1] + y1 * k[2] + y2 * k[3];
+  m1 = y0 * k[0] + y1 * k[1] + y2 * k[2] + y3 * k[3];
+  p2 = y1 * k[0] + y2 * k[1] + y3 * k[2];
+  m2 = y2 * k[0] + y3 * k[1];
+  p3 = y3 * k[0];
+
+  /* Collaps to 4 64-bit words,
+     +---+---+---+---+
+     | p3| p2| p1| p0|
+     +-+-+-+-+-+-+-+-+
+    +  | m2| m1| m0|
+    -+-+-+-+-+-+-+-+-+
+  */
+  /* But it's convenient to reduce (p3,p2,p1,p0) and (m2,m1,m0) mod p first.*/
+  m1 += UMAC_P128_OFFSET * HI(p3);
+  p1 += UMAC_P128_OFFSET * (LO(p3) + HI(m2));
+  m0 += UMAC_P128_OFFSET * (HI(p2) + LO(m2));
+  p0 += UMAC_P128_OFFSET * (LO(p2) + HI(m1));
+
+  /* Left to add
+     +---+---+
+     | p1| p0|
+     +-+-+-+-+
+     m1| m0|
+     +-+---+
+  */
+  /* First add high parts, with no possibilities for carries */
+  p1 += m0 >> 32;
+
+  m0 <<= 32;
+  m1 <<= 32;
+
+  /* Remains:
+     +---+---+
+     | p1| p0|
+     +-+-+---+
+    +| m1| m0|
+    -+---+---+
+  */
+  p0 += m0;
+  p1 += (p0 < m0);
+  p1 += m1;
+  if (p1 < m1)
+    {
+      p0 += UMAC_P128_OFFSET;
+      p1 += (p0 < UMAC_P128_OFFSET);
+    }
+
+  y[0] = p1;
+  y[1] = p0;
+}
+
+void
+_umac_poly128 (const uint32_t *k, uint64_t *y, uint64_t mh, uint64_t ml)
+{
+  uint64_t yh, yl, cy;
+
+  if ( (mh >> 32) == 0xffffffff)
+    {
+      poly128_mul (k, y);
+      if (y[1] > 0)
+	y[1]--;
+      else if (y[0] > 0)
+	{
+	  y[0]--;
+	  y[1] = UMAC_P128_HI;
+	}
+      else
+	{
+	  y[0] = UMAC_P128_HI;
+	  y[1] = UMAC_P128_LO-1;
+	}
+
+      mh -= (ml < UMAC_P128_OFFSET);
+      ml -= UMAC_P128_OFFSET;
+    }
+  assert (mh < UMAC_P128_HI || ml < UMAC_P128_LO);
+
+  poly128_mul (k, y);
+  yl = y[1] + ml;
+  cy = (yl < ml);
+  yh = y[0] + cy;
+  cy = (yh < cy);
+  yh += mh;
+  cy += (yh < mh);
+  assert (cy <= 1);
+  if (cy)
+    {
+      yl += UMAC_P128_OFFSET;
+      yh += yl < UMAC_P128_OFFSET;
+    }
+
+  y[0] = yh;
+  y[1] = yl;
+}
diff --git a/umac-poly64.c b/umac-poly64.c
new file mode 100644
index 00000000..bb4cb32c
--- /dev/null
+++ b/umac-poly64.c
@@ -0,0 +1,74 @@
+/* umac-poly64.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "umac.h"
+
+static uint64_t
+poly64_mul (uint32_t kh, uint32_t kl, uint64_t y)
+{
+  uint64_t yl, yh, pl, ph, ml, mh;
+  yl = y & 0xffffffff;
+  yh = y >> 32;
+  pl = yl * kl;
+  ph = yh * kh;
+  ml = yh * kl + yl * kh; /* No overflow, thanks to special form */
+  mh = ml >> 32;
+  ml <<= 32;
+  pl += ml;
+  ph += mh + (pl < ml);
+
+  /* Reduce, using 2^64 = UMAC_P64_OFFSET (mod p) */
+  assert (ph < ((uint64_t) 1 << 57));
+  ph *= UMAC_P64_OFFSET;
+  pl += ph;
+  if (pl < ph)
+    pl += UMAC_P64_OFFSET;
+
+  return pl;
+}
+
+uint64_t
+_umac_poly64 (uint32_t kh, uint32_t kl, uint64_t y, uint64_t m)
+{
+  if ( (m >> 32) == 0xffffffff)
+    {
+      y = poly64_mul (kh, kl, y);
+      if (y == 0)
+	y = UMAC_P64 - 1;
+      else
+	y--;
+      m -= UMAC_P64_OFFSET;
+    }
+  y = poly64_mul (kh, kl, y);
+  y += m;
+  if (y < m)
+    y += UMAC_P64_OFFSET;
+
+  return y;
+}
diff --git a/umac-set-key.c b/umac-set-key.c
new file mode 100644
index 00000000..c1f79687
--- /dev/null
+++ b/umac-set-key.c
@@ -0,0 +1,98 @@
+/* umac-set-key.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+static void
+umac_kdf (struct aes_ctx *aes, unsigned index, unsigned length, uint8_t *dst)
+{
+  uint8_t block[AES_BLOCK_SIZE];
+  uint64_t count;
+  WRITE_UINT64 (block, (uint64_t) index);
+  for (count = 1; length >= AES_BLOCK_SIZE;
+       length -= AES_BLOCK_SIZE, dst += AES_BLOCK_SIZE, count++)
+    {
+      WRITE_UINT64 (block + 8, count);
+      aes_encrypt (aes, AES_BLOCK_SIZE, dst, block);
+    }
+  if (length > 0)
+    {
+      WRITE_UINT64 (block + 8, count);
+      aes_encrypt (aes, AES_BLOCK_SIZE, block, block);
+      memcpy (dst, block, length);
+    }
+}
+
+#if WORDS_BIGENDIAN
+#define BE_SWAP32(x) x
+#define BE_SWAP32_N(x)
+#else
+#define BE_SWAP32(x)				\
+  ((ROTL32(8,  x) & 0x00FF00FFUL) |		\
+   (ROTL32(24, x) & 0xFF00FF00UL))
+#define BE_SWAP32_N(n, x) do {			\
+  unsigned be_i;				\
+  for (be_i = 0; be_i < n; be_i++)		\
+    {						\
+      uint32_t be_x = (x)[be_i];		\
+      (x)[be_i] = BE_SWAP32 (be_x);		\
+    }						\
+  } while (0)
+#endif
+
+void
+_umac_set_key (uint32_t *l1_key, uint32_t *l2_key,
+	       uint64_t *l3_key1, uint32_t *l3_key2,
+	       struct aes_ctx *aes, const uint8_t *key, unsigned n)
+{
+  unsigned size;
+  uint8_t buffer[UMAC_KEY_SIZE];
+
+  aes_set_encrypt_key (aes, UMAC_KEY_SIZE, key);
+
+  size = UMAC_BLOCK_SIZE / 4 + 4*(n-1);
+  umac_kdf (aes, 1, size * sizeof(uint32_t), (uint8_t *) l1_key);
+  BE_SWAP32_N (size, l1_key);
+
+  size = 6*n;
+  umac_kdf (aes, 2, size * sizeof(uint32_t), (uint8_t *) l2_key);
+  _umac_l2_init (size, l2_key);
+
+  size = 8*n;
+  umac_kdf (aes, 3, size * sizeof(uint64_t), (uint8_t *) l3_key1);
+  _umac_l3_init (size, l3_key1);
+
+  umac_kdf (aes, 4, n * sizeof(uint32_t), (uint8_t *) l3_key2);
+  BE_SWAP32_N (n, l3_key2);
+
+  umac_kdf (aes, 0, UMAC_KEY_SIZE, buffer);
+  aes_set_encrypt_key (aes, UMAC_KEY_SIZE, buffer);
+}
diff --git a/umac.h b/umac.h
new file mode 100644
index 00000000..415d797f
--- /dev/null
+++ b/umac.h
@@ -0,0 +1,230 @@
+/* umac.h
+ *
+ * UMAC message authentication code (RFC-4418).
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#ifndef NETTLE_UMAC_H_INCLUDED
+#define NETTLE_UMAC_H_INCLUDED
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Namespace mangling */
+#define umac32_set_key  nettle_umac32_set_key
+#define umac64_set_key  nettle_umac64_set_key
+#define umac96_set_key  nettle_umac96_set_key
+#define umac128_set_key nettle_umac128_set_key
+#define umac32_set_nonce  nettle_umac32_set_nonce
+#define umac64_set_nonce  nettle_umac64_set_nonce
+#define umac96_set_nonce  nettle_umac96_set_nonce
+#define umac128_set_nonce nettle_umac128_set_nonce
+#define umac32_update  nettle_umac32_update
+#define umac64_update  nettle_umac64_update
+#define umac96_update  nettle_umac96_update
+#define umac128_update nettle_umac128_update
+#define umac32_digest  nettle_umac32_digest
+#define umac64_digest  nettle_umac64_digest
+#define umac96_digest  nettle_umac96_digest
+#define umac128_digest nettle_umac128_digest
+#define _umac_set_key _nettle_umac_set_key
+#define _umac_nh _nettle_umac_nh
+#define _umac_nh_n _nettle_umac_nh_n
+#define _umac_poly64 _nettle_umac_poly64
+#define _umac_poly128 _nettle_umac_poly128
+#define _umac_l2_init _nettle_umac_l2_init
+#define _umac_l2 _nettle_umac_l2
+#define _umac_l2_final _nettle_umac_l2_final
+#define _umac_l3_init _nettle_umac_l3_init
+#define _umac_l3 _nettle_umac_l3
+
+#include "nettle-types.h"
+#include "aes.h"
+
+#define UMAC_BLOCK_SIZE 1024
+#define UMAC_KEY_SIZE 16
+
+/* Subkeys and state for UMAC with tag size 32*n bits. */
+#define _UMAC_STATE(n)					\
+  uint32_t l1_key[UMAC_BLOCK_SIZE/4 + 4*((n)-1)];	\
+  /* Keys in 32-bit pieces, high first */		\
+  uint32_t l2_key[6*(n)];				\
+  uint64_t l3_key1[8*(n)];				\
+  uint32_t l3_key2[(n)];				\
+  /* AES cipher for encrypting the nonce */		\
+  struct aes_ctx pdf_key;				\
+  /* Buffer l1 output for one block.			\
+     FIXME: Make part of l2 state? */			\
+  uint64_t l1_out[(n)];					\
+  /* For both poly64-hashing and poly128 hashing */	\
+  uint64_t l2_state[2*(n)];				\
+  /* Input to the pdf_key, zero-padded and low bits	\
+     cleared if appropriate. */				\
+  uint8_t nonce[AES_BLOCK_SIZE];			\
+  unsigned short nonce_length; /* For incrementing */	\
+  /* Buffering */					\
+  /* Complete blocks processed */			\
+  unsigned count;					\
+  unsigned index;					\
+  uint8_t block[UMAC_BLOCK_SIZE];
+
+#define _UMAC_NONCE_CACHED 0x80
+
+struct umac32_ctx
+{
+  _UMAC_STATE(1);
+  unsigned short nonce_low; /* Low bits, plus some flag for the pad cache. */
+  /* Previous padding block */
+  uint32_t pad_cache[AES_BLOCK_SIZE / 4];
+};
+
+struct umac64_ctx
+{
+  _UMAC_STATE(2);
+  int nonce_low; /* Low bits, plus some flag for the pad cache. */
+  /* Previous padding block */
+  uint32_t pad_cache[AES_BLOCK_SIZE/4];
+};
+
+struct umac96_ctx
+{
+  _UMAC_STATE(3);
+};
+
+struct umac128_ctx
+{
+  _UMAC_STATE(4);
+};
+
+/* The _set_key function initialize the nonce to zero. */
+void
+umac32_set_key (struct umac32_ctx *ctx, const uint8_t *key);
+void
+umac64_set_key (struct umac64_ctx *ctx, const uint8_t *key);
+void
+umac96_set_key (struct umac96_ctx *ctx, const uint8_t *key);
+void
+umac128_set_key (struct umac128_ctx *ctx, const uint8_t *key);
+
+/* Optional, if not used, messages get incrementing nonces starting from zero. */
+void
+umac32_set_nonce (struct umac32_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce);
+void
+umac64_set_nonce (struct umac64_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce);
+void
+umac96_set_nonce (struct umac96_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce);
+void
+umac128_set_nonce (struct umac128_ctx *ctx,
+		   unsigned nonce_length, const uint8_t *nonce);
+
+void
+umac32_update (struct umac32_ctx *ctx,
+	       unsigned length, const uint8_t *data);
+void
+umac64_update (struct umac64_ctx *ctx,
+	       unsigned length, const uint8_t *data);
+void
+umac96_update (struct umac96_ctx *ctx,
+	       unsigned length, const uint8_t *data);
+void
+umac128_update (struct umac128_ctx *ctx,
+		unsigned length, const uint8_t *data);
+
+/* The _digest functions increment the nonce */
+void
+umac32_digest (struct umac32_ctx *ctx,
+	       unsigned length, uint8_t *digest);
+void
+umac64_digest (struct umac64_ctx *ctx,
+	       unsigned length, uint8_t *digest);
+void
+umac96_digest (struct umac96_ctx *ctx,
+	       unsigned length, uint8_t *digest);
+void
+umac128_digest (struct umac128_ctx *ctx,
+		unsigned length, uint8_t *digest);
+
+
+/* Internal functions */
+#define UMAC_POLY64_BLOCKS 16384
+
+#define UMAC_P64_OFFSET 59
+#define UMAC_P64 (- (uint64_t) UMAC_P64_OFFSET)
+
+#define UMAC_P128_OFFSET 159
+#define UMAC_P128_HI (~(uint64_t) 0)
+#define UMAC_P128_LO (-(uint64_t) UMAC_P128_OFFSET)
+
+void
+_umac_set_key (uint32_t *l1_key, uint32_t *l2_key,
+	       uint64_t *l3_key1, uint32_t *l3_key2,
+	       struct aes_ctx *pad, const uint8_t *key, unsigned n);
+
+uint64_t
+_umac_nh (const uint32_t *key, unsigned length, const uint8_t *msg);
+
+/* Equivalent to
+
+   for (i = 0; i < n; i++)
+     out[i] = _umac_nh (key + 4*i, length, msg);
+
+   but processing input only once.
+*/
+void
+_umac_nh_n (uint64_t *out, unsigned n, const uint32_t *key,
+	    unsigned length, const uint8_t *msg);
+
+/* Returns y*k + m (mod p), including "marker" processing. Return
+   value is *not* in canonical representation, and must be normalized
+   before the output is used. */
+uint64_t
+_umac_poly64 (uint32_t kh, uint32_t kl, uint64_t y, uint64_t m);
+
+void
+_umac_poly128 (const uint32_t *k, uint64_t *y, uint64_t mh, uint64_t ml);
+
+void
+_umac_l2_init (unsigned size, uint32_t *k);
+
+void
+_umac_l2(const uint32_t *key, uint64_t *state, unsigned n,
+	 unsigned count, uint64_t *prev, const uint64_t *m);
+
+void
+_umac_l2_final(const uint32_t *key, uint64_t *state, unsigned n,
+	       unsigned count, uint64_t *prev);
+
+void
+_umac_l3_init (unsigned size, uint64_t *k);
+
+uint32_t
+_umac_l3 (const uint64_t *key_1, uint32_t key_2, const uint64_t *m);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* NETTLE_UMAC_H_INCLUDED */
diff --git a/umac128.c b/umac128.c
new file mode 100644
index 00000000..c4a6dbb5
--- /dev/null
+++ b/umac128.c
@@ -0,0 +1,126 @@
+/* umac128.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+void
+umac128_set_key (struct umac128_ctx *ctx, const uint8_t *key)
+{
+  _umac_set_key (ctx->l1_key, ctx->l2_key, ctx->l3_key1, ctx->l3_key2,
+		 &ctx->pdf_key, key, 4);
+
+  /* Clear nonce */
+  memset (ctx->nonce, 0, sizeof(ctx->nonce));
+  ctx->nonce_length = sizeof(ctx->nonce);
+
+  /* Initialize buffer */
+  ctx->count = ctx->index = 0;
+}
+
+void
+umac128_set_nonce (struct umac128_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce)
+{
+  assert (nonce_length > 0);
+  assert (nonce_length <= AES_BLOCK_SIZE);
+
+  memcpy (ctx->nonce, nonce, nonce_length);
+  memset (ctx->nonce + nonce_length, 0, AES_BLOCK_SIZE - nonce_length);
+
+  ctx->nonce_length = nonce_length;
+}
+
+#define UMAC128_BLOCK(ctx, block) do {					\
+    uint64_t __umac128_y[4];						\
+    _umac_nh_n (__umac128_y, 4, ctx->l1_key, UMAC_BLOCK_SIZE, block);	\
+    __umac128_y[0] += 8*UMAC_BLOCK_SIZE;				\
+    __umac128_y[1] += 8*UMAC_BLOCK_SIZE;				\
+    __umac128_y[2] += 8*UMAC_BLOCK_SIZE;				\
+    __umac128_y[3] += 8*UMAC_BLOCK_SIZE;				\
+    _umac_l2 (ctx->l2_key, ctx->l2_state, 4, ctx->count++,		\
+	      ctx->l1_out, __umac128_y);				\
+  } while (0)
+
+void
+umac128_update (struct umac128_ctx *ctx,
+	       unsigned length, const uint8_t *data)
+{
+  MD_UPDATE (ctx, length, data, UMAC128_BLOCK, (void)0);
+}
+
+
+void
+umac128_digest (struct umac128_ctx *ctx,
+	       unsigned length, uint8_t *digest)
+{
+  uint32_t tag[4];
+  unsigned i;
+
+  assert (length > 0);
+  assert (length <= 16);
+
+  if (ctx->index > 0 || ctx->count == 0)
+    {
+      /* Zero pad to multiple of 32 */
+      uint64_t y[4];
+      unsigned pad = (ctx->index > 0) ? 31 & - ctx->index : 32;
+      memset (ctx->block + ctx->index, 0, pad);
+
+      _umac_nh_n (y, 4, ctx->l1_key, ctx->index + pad, ctx->block);
+      y[0] += 8 * ctx->index;
+      y[1] += 8 * ctx->index;
+      y[2] += 8 * ctx->index;
+      y[3] += 8 * ctx->index;
+      _umac_l2 (ctx->l2_key, ctx->l2_state, 4, ctx->count++,
+		ctx->l1_out, y);
+    }
+  assert (ctx->count > 0);
+
+  aes_encrypt (&ctx->pdf_key, AES_BLOCK_SIZE,
+	       (uint8_t *) tag, ctx->nonce);
+
+  /* Increment nonce */
+  i = ctx->nonce_length - 1;
+  if (++ctx->nonce[i] == 0)
+    while (i > 0)
+      if (++ctx->nonce[--i] == 0)
+	break;
+
+  _umac_l2_final (ctx->l2_key, ctx->l2_state, 4, ctx->count, ctx->l1_out);
+  for (i = 0; i < 4; i++)
+    tag[i] ^= _umac_l3 (ctx->l3_key1 + 8*i, ctx->l3_key2[i], ctx->l2_state + 2*i);
+
+  memcpy (digest, tag, length);
+
+  /* Reinitialize */
+  ctx->count = ctx->index = 0;
+}
diff --git a/umac32.c b/umac32.c
new file mode 100644
index 00000000..00ba2f7a
--- /dev/null
+++ b/umac32.c
@@ -0,0 +1,130 @@
+/* umac32.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+void
+umac32_set_key (struct umac32_ctx *ctx, const uint8_t *key)
+{
+  _umac_set_key (ctx->l1_key, ctx->l2_key, ctx->l3_key1, ctx->l3_key2,
+		 &ctx->pdf_key, key, 1);
+
+  /* Clear nonce */
+  memset (ctx->nonce, 0, sizeof(ctx->nonce));
+  ctx->nonce_low = 0;
+  ctx->nonce_length = sizeof(ctx->nonce);
+
+  /* Initialize buffer */
+  ctx->count = ctx->index = 0;
+}
+
+void
+umac32_set_nonce (struct umac32_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce)
+{
+  assert (nonce_length > 0);
+  assert (nonce_length <= AES_BLOCK_SIZE);
+
+  memcpy (ctx->nonce, nonce, nonce_length);
+  memset (ctx->nonce + nonce_length, 0, AES_BLOCK_SIZE - nonce_length);
+
+  ctx->nonce_low = ctx->nonce[nonce_length - 1] & 3;
+  ctx->nonce[nonce_length - 1] &= ~3;
+  ctx->nonce_length = nonce_length;
+}
+
+#define UMAC32_BLOCK(ctx, block) do {					\
+    uint64_t __umac32_y							\
+      = _umac_nh (ctx->l1_key, UMAC_BLOCK_SIZE, block)			\
+      + 8*UMAC_BLOCK_SIZE ;						\
+    _umac_l2 (ctx->l2_key, ctx->l2_state, 1, ctx->count++,		\
+	      ctx->l1_out, &__umac32_y);				\
+  } while (0)
+
+void
+umac32_update (struct umac32_ctx *ctx,
+	       unsigned length, const uint8_t *data)
+{
+  MD_UPDATE (ctx, length, data, UMAC32_BLOCK, (void)0);
+}
+
+
+void
+umac32_digest (struct umac32_ctx *ctx,
+	       unsigned length, uint8_t *digest)
+{
+  uint32_t pad;
+
+  assert (length > 0);
+  assert (length <= 4);
+
+  if (ctx->index > 0 || ctx->count == 0)
+    {
+      /* Zero pad to multiple of 32 */
+      uint64_t y;
+      unsigned pad = (ctx->index > 0) ? 31 & - ctx->index : 32;
+      memset (ctx->block + ctx->index, 0, pad);
+
+      y = _umac_nh (ctx->l1_key, ctx->index + pad, ctx->block)
+	+ 8 * ctx->index;
+      _umac_l2 (ctx->l2_key, ctx->l2_state, 1, ctx->count++,
+		ctx->l1_out, &y);
+    }
+  assert (ctx->count > 0);
+  if ( !(ctx->nonce_low & _UMAC_NONCE_CACHED))
+    aes_encrypt (&ctx->pdf_key, AES_BLOCK_SIZE,
+		 (uint8_t *) ctx->pad_cache, ctx->nonce);
+
+  pad = ctx->pad_cache[ctx->nonce_low & 3];
+
+  /* Increment nonce */
+  ctx->nonce_low++;
+  if ( !(ctx->nonce_low & 3))
+    {
+      unsigned i = ctx->nonce_length - 1;
+
+      ctx->nonce_low = 0;
+      ctx->nonce[i] += 4;
+
+      if (ctx->nonce[i] == 0)
+	while (i > 0)
+	  if (++ctx->nonce[--i] == 0)
+	    break;
+    }
+
+  _umac_l2_final (ctx->l2_key, ctx->l2_state, 1, ctx->count, ctx->l1_out);
+  pad ^= _umac_l3 (ctx->l3_key1, ctx->l3_key2[0], ctx->l2_state);
+  memcpy (digest, &pad, length);
+
+  /* Reinitialize */
+  ctx->count = ctx->index = 0;
+}
diff --git a/umac64.c b/umac64.c
new file mode 100644
index 00000000..015cefd0
--- /dev/null
+++ b/umac64.c
@@ -0,0 +1,135 @@
+/* umac64.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+void
+umac64_set_key (struct umac64_ctx *ctx, const uint8_t *key)
+{
+  _umac_set_key (ctx->l1_key, ctx->l2_key, ctx->l3_key1, ctx->l3_key2,
+		 &ctx->pdf_key, key, 2);
+
+  /* Clear nonce */
+  memset (ctx->nonce, 0, sizeof(ctx->nonce));
+  ctx->nonce_low = 0;
+  ctx->nonce_length = sizeof(ctx->nonce);
+
+  /* Initialize buffer */
+  ctx->count = ctx->index = 0;
+}
+
+void
+umac64_set_nonce (struct umac64_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce)
+{
+  assert (nonce_length > 0);
+  assert (nonce_length <= AES_BLOCK_SIZE);
+
+  memcpy (ctx->nonce, nonce, nonce_length);
+  memset (ctx->nonce + nonce_length, 0, AES_BLOCK_SIZE - nonce_length);
+
+  ctx->nonce_low = ctx->nonce[nonce_length - 1] & 1;
+  ctx->nonce[nonce_length - 1] &= ~1;
+  ctx->nonce_length = nonce_length;
+}
+
+#define UMAC64_BLOCK(ctx, block) do {					\
+    uint64_t __umac64_y[2];						\
+    _umac_nh_n (__umac64_y, 2, ctx->l1_key, UMAC_BLOCK_SIZE, block);	\
+    __umac64_y[0] += 8*UMAC_BLOCK_SIZE;					\
+    __umac64_y[1] += 8*UMAC_BLOCK_SIZE;					\
+    _umac_l2 (ctx->l2_key, ctx->l2_state, 2, ctx->count++,		\
+	      ctx->l1_out, __umac64_y);					\
+  } while (0)
+
+void
+umac64_update (struct umac64_ctx *ctx,
+	       unsigned length, const uint8_t *data)
+{
+  MD_UPDATE (ctx, length, data, UMAC64_BLOCK, (void)0);
+}
+
+
+void
+umac64_digest (struct umac64_ctx *ctx,
+	       unsigned length, uint8_t *digest)
+{
+  uint32_t tag[2];
+  uint32_t *pad;
+
+  assert (length > 0);
+  assert (length <= 8);
+
+  if (ctx->index > 0 || ctx->count == 0)
+    {
+      /* Zero pad to multiple of 32 */
+      uint64_t y[2];
+      unsigned pad = (ctx->index > 0) ? 31 & - ctx->index : 32;
+      memset (ctx->block + ctx->index, 0, pad);
+
+      _umac_nh_n (y, 2, ctx->l1_key, ctx->index + pad, ctx->block);
+      y[0] += 8 * ctx->index;
+      y[1] += 8 * ctx->index;
+      _umac_l2 (ctx->l2_key, ctx->l2_state, 2, ctx->count++,
+		ctx->l1_out, y);
+    }
+  assert (ctx->count > 0);
+  if ( !(ctx->nonce_low & _UMAC_NONCE_CACHED))
+    aes_encrypt (&ctx->pdf_key, AES_BLOCK_SIZE,
+		 (uint8_t *) ctx->pad_cache, ctx->nonce);
+
+  pad = ctx->pad_cache + 2*(ctx->nonce_low & 1);
+
+  /* Increment nonce */
+  ctx->nonce_low++;
+  if ( !(ctx->nonce_low & 1))
+    {
+      unsigned i = ctx->nonce_length - 1;
+
+      ctx->nonce_low = 0;
+      ctx->nonce[i] += 2;
+
+      if (ctx->nonce[i] == 0)
+	while (i > 0)
+	  if (++ctx->nonce[--i] == 0)
+	    break;
+    }
+
+  _umac_l2_final (ctx->l2_key, ctx->l2_state, 2, ctx->count, ctx->l1_out);
+  tag[0] = pad[0] ^ _umac_l3 (ctx->l3_key1, ctx->l3_key2[0], ctx->l2_state);
+  tag[1] = pad[1] ^ _umac_l3 (ctx->l3_key1 + 8, ctx->l3_key2[1],
+			      ctx->l2_state + 2);
+  memcpy (digest, tag, length);
+
+  /* Reinitialize */
+  ctx->count = ctx->index = 0;
+}
diff --git a/umac96.c b/umac96.c
new file mode 100644
index 00000000..ab7b33fa
--- /dev/null
+++ b/umac96.c
@@ -0,0 +1,124 @@
+/* umac96.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h>
+
+#include "umac.h"
+
+#include "macros.h"
+
+void
+umac96_set_key (struct umac96_ctx *ctx, const uint8_t *key)
+{
+  _umac_set_key (ctx->l1_key, ctx->l2_key, ctx->l3_key1, ctx->l3_key2,
+		 &ctx->pdf_key, key, 3);
+
+  /* Clear nonce */
+  memset (ctx->nonce, 0, sizeof(ctx->nonce));
+  ctx->nonce_length = sizeof(ctx->nonce);
+
+  /* Initialize buffer */
+  ctx->count = ctx->index = 0;
+}
+
+void
+umac96_set_nonce (struct umac96_ctx *ctx,
+		  unsigned nonce_length, const uint8_t *nonce)
+{
+  assert (nonce_length > 0);
+  assert (nonce_length <= AES_BLOCK_SIZE);
+
+  memcpy (ctx->nonce, nonce, nonce_length);
+  memset (ctx->nonce + nonce_length, 0, AES_BLOCK_SIZE - nonce_length);
+
+  ctx->nonce_length = nonce_length;
+}
+
+#define UMAC96_BLOCK(ctx, block) do {					\
+    uint64_t __umac96_y[3];						\
+    _umac_nh_n (__umac96_y, 3, ctx->l1_key, UMAC_BLOCK_SIZE, block);	\
+    __umac96_y[0] += 8*UMAC_BLOCK_SIZE;					\
+    __umac96_y[1] += 8*UMAC_BLOCK_SIZE;					\
+    __umac96_y[2] += 8*UMAC_BLOCK_SIZE;					\
+    _umac_l2 (ctx->l2_key, ctx->l2_state, 3, ctx->count++,		\
+	      ctx->l1_out, __umac96_y);					\
+  } while (0)
+
+void
+umac96_update (struct umac96_ctx *ctx,
+	       unsigned length, const uint8_t *data)
+{
+  MD_UPDATE (ctx, length, data, UMAC96_BLOCK, (void)0);
+}
+
+
+void
+umac96_digest (struct umac96_ctx *ctx,
+	       unsigned length, uint8_t *digest)
+{
+  uint32_t tag[4];
+  unsigned i;
+
+  assert (length > 0);
+  assert (length <= 12);
+
+  if (ctx->index > 0 || ctx->count == 0)
+    {
+      /* Zero pad to multiple of 32 */
+      uint64_t y[3];
+      unsigned pad = (ctx->index > 0) ? 31 & - ctx->index : 32;
+      memset (ctx->block + ctx->index, 0, pad);
+
+      _umac_nh_n (y, 3, ctx->l1_key, ctx->index + pad, ctx->block);
+      y[0] += 8 * ctx->index;
+      y[1] += 8 * ctx->index;
+      y[2] += 8 * ctx->index;
+      _umac_l2 (ctx->l2_key, ctx->l2_state, 3, ctx->count++,
+		ctx->l1_out, y);
+    }
+  assert (ctx->count > 0);
+
+  aes_encrypt (&ctx->pdf_key, AES_BLOCK_SIZE,
+	       (uint8_t *) tag, ctx->nonce);
+
+  /* Increment nonce */
+  i = ctx->nonce_length - 1;
+  if (++ctx->nonce[i] == 0)
+    while (i > 0)
+      if (++ctx->nonce[--i] == 0)
+	break;
+
+  _umac_l2_final (ctx->l2_key, ctx->l2_state, 3, ctx->count, ctx->l1_out);
+  for (i = 0; i < 3; i++)
+    tag[i] ^= _umac_l3 (ctx->l3_key1 + 8*i, ctx->l3_key2[i], ctx->l2_state + 2*i);
+
+  memcpy (digest, tag, length);
+
+  /* Reinitialize */
+  ctx->count = ctx->index = 0;
+}