Poly1163

A high-performance polynomial-based message authentication code (MAC) implementation in Zig, based on polynomial evaluation modulo prime 2^116 - 3.

Features

• Cryptographic MAC: Provides message authentication using polynomial evaluation
• Simple API: Easy-to-use interface for authentication and verification
• Incremental processing: Support for streaming large messages
• Zero dependencies: Pure Zig implementation using only the standard library

Algorithm Overview

Poly1163 uses polynomial evaluation over a large prime field (2^116 - 3) to compute authentication tags:

1. Key derivation: 256-bit key split into:

   • r: 112-bit polynomial evaluation key (clamped for security)
   • s: 128-bit final masking key (blind)

2. Message processing: Messages are processed in 14-byte blocks, with each block:

   • Converted to a 112-bit integer (little-endian)
   • Added with a high bit set for domain separation
   • Accumulated using polynomial evaluation: acc = (acc + block) * r mod p

3. Finalization: The accumulator is masked with s to produce the final 128-bit tag

Installation

Add to your build.zig.zon:

.dependencies = .{
    .poly1163 = .{
        .path = "path/to/zig-poly1163",
    },
},

Usage

Basic Authentication

const std = @import("std");
const poly1163 = @import("poly1163");

// Generate or load a 256-bit secret key
var key: [32]u8 = undefined;
std.crypto.random.bytes(&key);

// Authenticate a message
const message = "Hello, World!";
const tag = poly1163.authenticate(key, message);

// Tag is a 16-byte authentication code
std.debug.print("Tag: {x}\n", .{std.fmt.fmtSliceHexLower(&tag)});

Incremental Processing

For large messages or streaming data:

var poly = poly1163.Poly1163.init(key);

// Process data in chunks
poly.update(chunk1);
poly.update(chunk2);
poly.update(chunk3);

// Get the final tag
const tag = poly.final();

Tag Verification

// Verify a received tag
var poly = poly1163.Poly1163.init(key);
poly.update(message);

if (poly.verify(received_tag)) {
    // Message is authentic
} else {
    // Authentication failed - message may be tampered
}

API Reference

Types

• Poly1163: Main struct for incremental MAC computation
• KEY_SIZE = 32: Size of the secret key in bytes
• TAG_SIZE = 16: Size of the authentication tag in bytes

Functions

Poly1163.init(key: [32]u8) Poly1163

Initialize a new Poly1163 instance with a secret key.

Poly1163.update(self: *Poly1163, data: []const u8) void

Process message data incrementally. Can be called multiple times.

Poly1163.final(self: *Poly1163) [16]u8

Finalize and return the authentication tag.

Poly1163.verify(self: *Poly1163, expected_tag: [16]u8) bool

Verify an authentication tag against the expected value.

authenticate(key: [32]u8, message: []const u8) [16]u8

One-shot function to authenticate a complete message.

Security Considerations

• Key management: Keys must be kept secret and generated using a cryptographically secure random number generator
• Tag truncation: Never truncate tags; always use the full 16 bytes
• Nonce/sequence numbers: For protection against replay attacks, include a nonce or sequence number in the authenticated message
• Not encryption: Poly1163 provides authentication only, not confidentiality. Combine with encryption for full protection

Building and Testing

Build the project

zig build

Run tests

zig build test

Run demo

zig build run

Run benchmarks

zig build benchmark

Run compatibility tests

zig build test-compat

Run test vectors

zig build test-vectors

Implementation Details

• Prime modulus: 2^116 - 3 (chosen for efficient reduction)
• Block size: 14 bytes (112 bits)
• Key clamping: Specific bits cleared in r to ensure uniform distribution and prevent weak keys
• Padding: Each block includes a high bit (bit 112) to prevent extension attacks
• Arithmetic: Uses efficient modular reduction with SIMD vector operations for performance