Message Authentication

🔏 Poly1305 One-time Authenticator

Security Level 128-bit
Performance ⭐⭐⭐⭐⭐ Excellent
Quantum Resistant ❌ No
Standardization RFC 8439, RFC 7539

📋 Quick Navigation

📖 Overview 💻 Implementation 🔒 Security ⚡ Performance 🎯 Use Cases ⚖️ Comparison

📖 Overview

Poly1305 is a cryptographic message authentication code (MAC) designed by Daniel J. Bernstein. It's a one-time authenticator that provides extremely fast authentication while maintaining strong security guarantees. Poly1305 is designed to be used with a unique key for each message, making it ideal for high-performance applications like network protocols.

✨ Key Features

⚡

High Performance

Extremely fast computation on modern processors

🔑

One-time Security

Designed for use with unique keys per message

🛡️

Provable Security

Based on well-understood mathematical foundations

⏱️

Constant Time

Resistant to timing attacks when properly implemented

📋

Standardized

RFC 8439 (ChaCha20-Poly1305) and RFC 7539

🌐

Widely Adopted

Used in TLS 1.3, WireGuard, and modern protocols

🎯 Common Use Cases

🔐 Encryption & Authentication

  • AEAD Encryption: Combined with ChaCha20 for authenticated encryption
  • Network Protocols: High-speed packet authentication
  • Real-time Communications: Low-latency authentication

🌐 Protocol Integration

  • TLS 1.3: Cipher suite ChaCha20-Poly1305-SHA256
  • VPN Protocols: WireGuard uses ChaCha20-Poly1305
  • IoT Devices: Efficient authentication for resource-constrained devices

🔧 Algorithm Details

📊 Technical Parameters

Key Size
32 bytes (256 bits)
Authentication key length
Tag Size
16 bytes (128 bits)
Authentication tag length
Block Size
16 bytes
Processing block size
Prime
2^130 - 5
Modular arithmetic prime
Clamp Mask
0x0ffffffc0ffffffc0ffffffc0fffffff
Key clamping pattern

🛡️ Security Properties

🔒

Unforgeability

2^-128 forgery probability per attempt

🔑

Key Uniqueness

Each key must be used only once

💥

Collision Resistance

Based on polynomial evaluation security

⏱️

Side-channel Resistance

Constant-time implementation possible

🔬

Quantum Resistance

Classical security assumptions

🧮 Mathematical Foundation

Poly1305 is based on polynomial evaluation over a finite field:

tag = ((m₁ × r^n + m₂ × r^(n-1) + ... + mₙ × r + 1) mod (2^130 - 5)) + s
r Clamped authentication key
s One-time pad
mᵢ Message blocks interpreted as little-endian integers

💻 Implementation

Poly1305 provides a simple yet powerful API for high-speed message authentication. The key requirement is that each key must be used only once to maintain security guarantees.

🚀 Basic Usage

Simple Authentication Python
```python from metamui_crypto import Poly1305 # Generate a random 32-byte key (must be unique per message) key = Poly1305.generate_key() # Create authenticator instance poly = Poly1305(key) # Authenticate a message message = b"Hello, secure world!" tag = poly.authenticate(message) print(f"Message: {message}") print(f"Authentication tag: {tag.hex()}") # Verify the authentication tag is_valid = poly.verify(message, tag) print(f"Authentication valid: {is_valid}") ```
⚠️ Key Uniqueness: Each key must be used only once for security
🔒 Tag Size: Always produces 16-byte authentication tags

Advanced Usage with Key Derivation

from metamui_crypto import Poly1305, ChaCha20
import os

def secure_authenticate_with_nonce(master_key: bytes, nonce: bytes, message: bytes) -> bytes:
    """
    Authenticate message using Poly1305 with nonce-derived key.
    
    Args:
        master_key: 32-byte master key
        nonce: 12-byte nonce (must be unique)
        message: Message to authenticate
        
    Returns:
        16-byte authentication tag
    """
    # Derive one-time key using ChaCha20
    chacha = ChaCha20(master_key, nonce)
    poly_key = chacha.encrypt(b'\x00' * 32)  # Generate 32 zero bytes as key
    
    # Authenticate with derived key
    poly = Poly1305(poly_key)
    tag = poly.authenticate(message)
    
    # Clear sensitive key material
    poly_key = b'\x00' * len(poly_key)
    
    return tag

# Example usage
master_key = os.urandom(32)
nonce = os.urandom(12)
message = b"Confidential data requiring authentication"

tag = secure_authenticate_with_nonce(master_key, nonce, message)
print(f"Derived key authentication tag: {tag.hex()}")

Batch Authentication

from metamui_crypto import Poly1305
import os

def authenticate_multiple_messages(messages: list[bytes]) -> list[tuple[bytes, bytes]]:
    """
    Authenticate multiple messages with unique keys.
    
    Args:
        messages: List of messages to authenticate
        
    Returns:
        List of (key, tag) tuples for each message
    """
    results = []
    
    for message in messages:
        # Generate unique key for each message
        key = Poly1305.generate_key()
        poly = Poly1305(key)
        tag = poly.authenticate(message)
        
        results.append((key, tag))
        print(f"Message: {message[:20]}... -> Tag: {tag.hex()[:16]}...")
    
    return results

# Example with multiple messages
messages = [
    b"First message to authenticate",
    b"Second message with different content",
    b"Third message for batch processing"
]

auth_data = authenticate_multiple_messages(messages)
print(f"Authenticated {len(auth_data)} messages")

Integration with ChaCha20-Poly1305 AEAD

from metamui_crypto import ChaCha20Poly1305
import os

def aead_encrypt_decrypt_example():
    """
    Demonstrate ChaCha20-Poly1305 AEAD usage.
    """
    # Generate key and nonce
    key = os.urandom(32)
    nonce = os.urandom(12)
    
    # Additional authenticated data (not encrypted)
    aad = b"protocol_version=1.0,timestamp=1234567890"
    
    # Message to encrypt and authenticate
    plaintext = b"Secret message requiring both confidentiality and authenticity"
    
    # Create AEAD instance
    aead = ChaCha20Poly1305(key)
    
    # Encrypt and authenticate
    ciphertext, tag = aead.encrypt(nonce, plaintext, aad)
    
    print(f"Plaintext: {plaintext}")
    print(f"AAD: {aad}")
    print(f"Ciphertext: {ciphertext.hex()}")
    print(f"Auth tag: {tag.hex()}")
    
    # Decrypt and verify
    try:
        decrypted = aead.decrypt(nonce, ciphertext, tag, aad)
        print(f"Decrypted: {decrypted}")
        print("Authentication and decryption successful!")
    except ValueError as e:
        print(f"Authentication failed: {e}")

aead_encrypt_decrypt_example()

Security Considerations

Critical Requirements

  1. Key Uniqueness: Each Poly1305 key MUST be used only once
  2. Key Generation: Use cryptographically secure random number generator
  3. Key Clamping: Implementation must properly clamp the key
  4. Constant Time: Avoid timing side-channels in verification
  5. Key Derivation: When reusing master keys, derive unique sub-keys

Implementation Guidelines

from metamui_crypto import Poly1305
import secrets
import hmac

class SecurePoly1305:
    """
    Secure wrapper for Poly1305 with proper key management.
    """
    
    def __init__(self, master_key: bytes):
        if len(master_key) != 32:
            raise ValueError("Master key must be 32 bytes")
        self._master_key = master_key
        self._used_nonces = set()
    
    def authenticate_with_nonce(self, nonce: bytes, message: bytes) -> bytes:
        """
        Authenticate message with nonce-derived key.
        
        Args:
            nonce: Unique nonce (recommended 16+ bytes)
            message: Message to authenticate
            
        Returns:
            Authentication tag
        """
        if nonce in self._used_nonces:
            raise ValueError("Nonce reuse detected - security violation!")
        
        # Derive unique key using HKDF-like construction
        derived_key = hmac.new(
            self._master_key,
            b"poly1305-key" + nonce,
            digestmod='sha256'
        ).digest()
        
        # Authenticate with derived key
        poly = Poly1305(derived_key)
        tag = poly.authenticate(message)
        
        # Track nonce usage
        self._used_nonces.add(nonce)
        
        # Clear derived key
        derived_key = b'\x00' * len(derived_key)
        
        return tag
    
    def verify_with_nonce(self, nonce: bytes, message: bytes, tag: bytes) -> bool:
        """
        Verify authentication tag with nonce-derived key.
        """
        # Re-derive the same key
        derived_key = hmac.new(
            self._master_key,
            b"poly1305-key" + nonce,
            digestmod='sha256'
        ).digest()
        
        # Verify with derived key
        poly = Poly1305(derived_key)
        is_valid = poly.verify(message, tag)
        
        # Clear derived key
        derived_key = b'\x00' * len(derived_key)
        
        return is_valid

# Example secure usage
master_key = secrets.token_bytes(32)
secure_poly = SecurePoly1305(master_key)

# Authenticate with unique nonces
nonce1 = secrets.token_bytes(16)
nonce2 = secrets.token_bytes(16)

message1 = b"First message"
message2 = b"Second message"

tag1 = secure_poly.authenticate_with_nonce(nonce1, message1)
tag2 = secure_poly.authenticate_with_nonce(nonce2, message2)

# Verify
valid1 = secure_poly.verify_with_nonce(nonce1, message1, tag1)
valid2 = secure_poly.verify_with_nonce(nonce2, message2, tag2)

print(f"Message 1 valid: {valid1}")
print(f"Message 2 valid: {valid2}")

Common Vulnerabilities

  1. Key Reuse: Using same key for multiple messages
  2. Weak Key Generation: Using predictable or low-entropy keys
  3. Timing Attacks: Non-constant-time verification
  4. Key Exposure: Storing keys in memory too long
  5. Nonce Collision: Reusing nonces in key derivation

Performance Analysis

Benchmarks

Performance measurements on modern hardware:

Platform Speed (cycles/byte) Throughput (GB/s)
Intel x64 0.63 4.8
ARM64 0.85 3.5
ARM32 2.1 1.4
RISC-V 1.8 1.7

Optimization Techniques

from metamui_crypto import Poly1305
import time

def benchmark_poly1305():
    """
    Benchmark Poly1305 performance with different message sizes.
    """
    key = Poly1305.generate_key()
    poly = Poly1305(key)
    
    sizes = [64, 256, 1024, 4096, 16384, 65536]
    
    for size in sizes:
        message = b'A' * size
        
        # Warm up
        for _ in range(100):
            poly.authenticate(message)
        
        # Benchmark
        start_time = time.perf_counter()
        iterations = 1000
        
        for _ in range(iterations):
            tag = poly.authenticate(message)
        
        end_time = time.perf_counter()
        
        total_time = end_time - start_time
        throughput = (size * iterations) / total_time / (1024 * 1024)  # MB/s
        
        print(f"Size: {size:6d} bytes, Throughput: {throughput:8.2f} MB/s")

benchmark_poly1305()

Use Cases and Examples

Network Protocol Authentication

from metamui_crypto import Poly1305
import struct
import socket

class AuthenticatedUDPSocket:
    """
    UDP socket with Poly1305 authentication.
    """
    
    def __init__(self, shared_key: bytes):
        self.socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
        self.shared_key = shared_key
        self.sequence_number = 0
    
    def send_authenticated(self, data: bytes, address: tuple):
        """
        Send data with authentication tag.
        """
        # Create packet header
        seq_num = self.sequence_number
        self.sequence_number += 1
        
        # Derive unique key from sequence number
        key_material = struct.pack('<Q', seq_num) + self.shared_key
        derived_key = hmac.new(
            self.shared_key,
            key_material,
            digestmod='sha256'
        ).digest()
        
        # Authenticate packet
        poly = Poly1305(derived_key)
        packet = struct.pack('<Q', seq_num) + data
        tag = poly.authenticate(packet)
        
        # Send packet with tag
        authenticated_packet = packet + tag
        self.socket.sendto(authenticated_packet, address)
        
        print(f"Sent packet {seq_num} with authentication")
    
    def receive_authenticated(self) -> tuple[bytes, tuple]:
        """
        Receive and verify authenticated data.
        """
        authenticated_packet, address = self.socket.recvfrom(4096)
        
        if len(authenticated_packet) < 24:  # 8 bytes seq + 16 bytes tag minimum
            raise ValueError("Packet too short")
        
        # Split packet and tag
        packet = authenticated_packet[:-16]
        tag = authenticated_packet[-16:]
        
        # Extract sequence number
        seq_num = struct.unpack('<Q', packet[:8])[0]
        
        # Derive same key
        key_material = struct.pack('<Q', seq_num) + self.shared_key
        derived_key = hmac.new(
            self.shared_key,
            key_material,
            digestmod='sha256'
        ).digest()
        
        # Verify authentication
        poly = Poly1305(derived_key)
        if not poly.verify(packet, tag):
            raise ValueError("Authentication failed")
        
        # Return data without sequence number
        data = packet[8:]
        print(f"Received authenticated packet {seq_num}")
        
        return data, address

# Example usage
import secrets
shared_key = secrets.token_bytes(32)
auth_socket = AuthenticatedUDPSocket(shared_key)

File Integrity Protection

from metamui_crypto import Poly1305
import os
import json

class FileIntegrityManager:
    """
    Manage file integrity using Poly1305 authentication.
    """
    
    def __init__(self, master_key: bytes):
        self.master_key = master_key
        self.integrity_db = {}
    
    def protect_file(self, filepath: str) -> str:
        """
        Generate integrity tag for file.
        
        Returns:
            Hex-encoded authentication tag
        """
        # Read file content
        with open(filepath, 'rb') as f:
            content = f.read()
        
        # Get file metadata
        stat = os.stat(filepath)
        metadata = {
            'size': stat.st_size,
            'mtime': stat.st_mtime,
            'mode': stat.st_mode
        }
        
        # Create authentication input
        auth_input = json.dumps(metadata, sort_keys=True).encode() + content
        
        # Derive file-specific key
        file_key = hmac.new(
            self.master_key,
            filepath.encode() + b"file-integrity",
            digestmod='sha256'
        ).digest()
        
        # Generate authentication tag
        poly = Poly1305(file_key)
        tag = poly.authenticate(auth_input)
        
        # Store in database
        tag_hex = tag.hex()
        self.integrity_db[filepath] = {
            'tag': tag_hex,
            'metadata': metadata
        }
        
        return tag_hex
    
    def verify_file(self, filepath: str) -> bool:
        """
        Verify file integrity.
        """
        if filepath not in self.integrity_db:
            return False
        
        try:
            # Read current file
            with open(filepath, 'rb') as f:
                content = f.read()
            
            # Get current metadata
            stat = os.stat(filepath)
            current_metadata = {
                'size': stat.st_size,
                'mtime': stat.st_mtime,
                'mode': stat.st_mode
            }
            
            # Check if metadata changed
            stored_metadata = self.integrity_db[filepath]['metadata']
            if current_metadata != stored_metadata:
                return False
            
            # Recreate authentication input
            auth_input = json.dumps(current_metadata, sort_keys=True).encode() + content
            
            # Derive same key
            file_key = hmac.new(
                self.master_key,
                filepath.encode() + b"file-integrity",
                digestmod='sha256'
            ).digest()
            
            # Verify tag
            poly = Poly1305(file_key)
            stored_tag = bytes.fromhex(self.integrity_db[filepath]['tag'])
            
            return poly.verify(auth_input, stored_tag)
            
        except (OSError, ValueError):
            return False
    
    def save_database(self, db_path: str):
        """Save integrity database to file."""
        with open(db_path, 'w') as f:
            json.dump(self.integrity_db, f, indent=2)
    
    def load_database(self, db_path: str):
        """Load integrity database from file."""
        with open(db_path, 'r') as f:
            self.integrity_db = json.load(f)

# Example usage
master_key = secrets.token_bytes(32)
integrity_mgr = FileIntegrityManager(master_key)

# Protect important files
important_files = [
    "config.json",
    "database.db",
    "certificates/server.crt"
]

for filepath in important_files:
    if os.path.exists(filepath):
        tag = integrity_mgr.protect_file(filepath)
        print(f"Protected {filepath}: {tag[:16]}...")

# Later, verify integrity
for filepath in important_files:
    if os.path.exists(filepath):
        is_valid = integrity_mgr.verify_file(filepath)
        print(f"File {filepath}: {'VALID' if is_valid else 'CORRUPTED'}")

Comparison with Other MACs

Poly1305 vs HMAC

Aspect Poly1305 HMAC-SHA256
Speed ~4.8 GB/s ~1.2 GB/s
Key Usage One-time only Reusable
Tag Size 16 bytes 32 bytes (truncatable)
Security Basis Polynomial evaluation Hash function
Standardization RFC 8439 RFC 2104, FIPS 198-1

Poly1305 vs GCM

Aspect Poly1305 AES-GCM
Algorithm Type Universal hash Galois field multiplication
Performance Faster on most platforms Hardware accelerated on some
Key Schedule None required AES key schedule
Parallelization Limited Highly parallelizable
Side-channel Resistance Good with proper implementation Requires careful implementation

Migration Guide

From HMAC to Poly1305

# Before: HMAC-based authentication
import hmac
import hashlib

def hmac_authenticate(key: bytes, message: bytes) -> bytes:
    return hmac.new(key, message, hashlib.sha256).digest()

def hmac_verify(key: bytes, message: bytes, tag: bytes) -> bool:
    expected = hmac_authenticate(key, message)
    return hmac.compare_digest(expected, tag)

# After: Poly1305 with proper key derivation
from metamui_crypto import Poly1305
import secrets

def poly1305_authenticate(master_key: bytes, nonce: bytes, message: bytes) -> bytes:
    # Derive one-time key
    derived_key = hmac.new(
        master_key,
        b"poly1305-v1" + nonce,
        hashlib.sha256
    ).digest()
    
    poly = Poly1305(derived_key)
    return poly.authenticate(message)

def poly1305_verify(master_key: bytes, nonce: bytes, message: bytes, tag: bytes) -> bool:
    # Derive same key
    derived_key = hmac.new(
        master_key,
        b"poly1305-v1" + nonce,
        hashlib.sha256
    ).digest()
    
    poly = Poly1305(derived_key)
    return poly.verify(message, tag)

# Migration example
master_key = secrets.token_bytes(32)
nonce = secrets.token_bytes(16)
message = b"Message to authenticate"

# Old way
hmac_tag = hmac_authenticate(master_key, message)

# New way
poly_tag = poly1305_authenticate(master_key, nonce, message)

print(f"HMAC tag: {hmac_tag.hex()}")
print(f"Poly1305 tag: {poly_tag.hex()}")

Test Vectors

RFC 8439 Test Vectors

def test_rfc8439_vectors():
    """
    Test vectors from RFC 8439 Section 2.5.2
    """
    # Test vector 1
    key = bytes.fromhex(
        "85d6be7857556d337f4452fe42d506a8"
        "0103808afb0db2fd4abff6af4149f51b"
    )
    
    message = b"Cryptographic Forum Research Group"
    
    expected_tag = bytes.fromhex("a8061dc1305136c6c22b8baf0c0127a9")
    
    poly = Poly1305(key)
    computed_tag = poly.authenticate(message)
    
    assert computed_tag == expected_tag, f"Expected {expected_tag.hex()}, got {computed_tag.hex()}"
    
    # Test verification
    assert poly.verify(message, expected_tag)
    
    print("RFC 8439 test vector passed!")

def test_additional_vectors():
    """
    Additional test vectors for edge cases.
    """
    # Empty message
    key = b'\x00' * 32
    poly = Poly1305(key)
    
    empty_tag = poly.authenticate(b"")
    assert len(empty_tag) == 16
    assert poly.verify(b"", empty_tag)
    
    # Single byte message
    single_byte_tag = poly.authenticate(b"\x01")
    assert poly.verify(b"\x01", single_byte_tag)
    
    # Maximum length message (simulated)
    large_message = b"A" * 1000000
    large_tag = poly.authenticate(large_message)
    assert poly.verify(large_message, large_tag)
    
    print("Additional test vectors passed!")

# Run tests
test_rfc8439_vectors()
test_additional_vectors()

References

Standards and Specifications

  • RFC 8439: ChaCha20 and Poly1305 for IETF Protocols
  • RFC 7539: ChaCha20 and Poly1305 for IETF Protocols (obsoleted by RFC 8439)
  • IRTF CFRG: Crypto Forum Research Group specifications

Academic Papers

  • “The Poly1305-AES message-authentication code” by Daniel J. Bernstein
  • “Cryptographic competitions” - CAESAR competition documentation
  • “High-speed cryptography in characteristic 2” - Polynomial evaluation security

Implementation References

  • libsodium: Reference implementation
  • BoringSSL: Google’s implementation
  • OpenSSL: Standard library implementation
  • Rust crypto: RustCrypto implementation

Security Analysis

  • “Security of the Poly1305 MAC” - Formal security proofs
  • “Timing attacks on implementations” - Side-channel analysis
  • “Post-quantum security” - Quantum resistance analysis

This documentation is part of the MetaMUI Crypto Primitives library. For more information, see the main documentation or visit our GitHub repository.