364 lines · 12.5 KB · Python
RawDownload
#!/usr/bin/env python3# SPDX-License-Identifier: GPL-2.0-or-later## Script that generates test vectors for the given hash function.## Requires that python-cryptography be installed.## Copyright 2025 Google LLC import cryptography.hazmat.primitives.ciphersimport cryptography.hazmat.primitives.cmacimport hashlibimport hmacimport sys DATA_LENS = [0, 1, 2, 3, 16, 32, 48, 49, 63, 64, 65, 127, 128, 129, 256, 511,             513, 1000, 3333, 4096, 4128, 4160, 4224, 16384] # Generate the given number of random bytes, using the length itself as the seed# for a simple linear congruential generator (LCG).  The C test code uses the# same LCG with the same seeding strategy to reconstruct the data, ensuring# reproducibility without explicitly storing the data in the test vectors.def rand_bytes(length):    seed = length    out = []    for _ in range(length):        seed = (seed * 25214903917 + 11) % 2**48        out.append((seed >> 16) % 256)    return bytes(out) AES_256_KEY_SIZE = 32 # AES-CMAC.  Just wraps the implementation from python-cryptography.class AesCmac:    def __init__(self, key):        aes = cryptography.hazmat.primitives.ciphers.algorithms.AES(key)        self.cmac = cryptography.hazmat.primitives.cmac.CMAC(aes)     def update(self, data):        self.cmac.update(data)     def digest(self):        return self.cmac.finalize() POLY1305_KEY_SIZE = 32 # A straightforward, unoptimized implementation of Poly1305.# Reference: https://cr.yp.to/mac/poly1305-20050329.pdfclass Poly1305:    def __init__(self, key):        assert len(key) == POLY1305_KEY_SIZE        self.h = 0        rclamp = 0x0ffffffc0ffffffc0ffffffc0fffffff        self.r = int.from_bytes(key[:16], byteorder='little') & rclamp        self.s = int.from_bytes(key[16:], byteorder='little')     # Note: this supports partial blocks only at the end.    def update(self, data):        for i in range(0, len(data), 16):            chunk = data[i:i+16]            c = int.from_bytes(chunk, byteorder='little') + 2**(8 * len(chunk))            self.h = ((self.h + c) * self.r) % (2**130 - 5)        return self     # Note: gen_additional_poly1305_testvecs() relies on this being    # nondestructive, i.e. not changing any field of self.    def digest(self):        m = (self.h + self.s) % 2**128        return m.to_bytes(16, byteorder='little') GHASH_POLY = sum((1 << i) for i in [128, 7, 2, 1, 0])GHASH_BLOCK_SIZE = 16 # A straightforward, unoptimized implementation of GHASH.class Ghash:     @staticmethod    def reflect_bits_in_bytes(v):        res = 0        for offs in range(0, 128, 8):            for bit in range(8):                if (v & (1 << (offs + bit))) != 0:                    res ^= 1 << (offs + 7 - bit)        return res     @staticmethod    def bytes_to_poly(data):        return Ghash.reflect_bits_in_bytes(int.from_bytes(data, byteorder='little'))     @staticmethod    def poly_to_bytes(poly):        return Ghash.reflect_bits_in_bytes(poly).to_bytes(16, byteorder='little')     def __init__(self, key):        assert len(key) == 16        self.h = Ghash.bytes_to_poly(key)        self.acc = 0     # Note: this supports partial blocks only at the end.    def update(self, data):        for i in range(0, len(data), 16):            # acc += block            self.acc ^= Ghash.bytes_to_poly(data[i:i+16])            # acc = (acc * h) mod GHASH_POLY            product = 0            for j in range(127, -1, -1):                if (self.h & (1 << j)) != 0:                    product ^= self.acc << j                if (product & (1 << (128 + j))) != 0:                    product ^= GHASH_POLY << j            self.acc = product        return self     def digest(self):        return Ghash.poly_to_bytes(self.acc) POLYVAL_POLY = sum((1 << i) for i in [128, 127, 126, 121, 0])POLYVAL_BLOCK_SIZE = 16 # A straightforward, unoptimized implementation of POLYVAL.# Reference: https://datatracker.ietf.org/doc/html/rfc8452class Polyval:    def __init__(self, key):        assert len(key) == 16        self.h = int.from_bytes(key, byteorder='little')        self.acc = 0     # Note: this supports partial blocks only at the end.    def update(self, data):        for i in range(0, len(data), 16):            # acc += block            self.acc ^= int.from_bytes(data[i:i+16], byteorder='little')            # acc = (acc * h * x^-128) mod POLYVAL_POLY            product = 0            for j in range(128):                if (self.h & (1 << j)) != 0:                    product ^= self.acc << j                if (product & (1 << j)) != 0:                    product ^= POLYVAL_POLY << j            self.acc = product >> 128        return self     def digest(self):        return self.acc.to_bytes(16, byteorder='little') def hash_init(alg):    # The keyed hash functions are assigned a fixed random key here, to present    # them as unkeyed hash functions.  This allows all the test cases for    # unkeyed hash functions to work on them.    if alg == 'aes-cmac':        return AesCmac(rand_bytes(AES_256_KEY_SIZE))    if alg == 'ghash':        return Ghash(rand_bytes(GHASH_BLOCK_SIZE))    if alg == 'poly1305':        return Poly1305(rand_bytes(POLY1305_KEY_SIZE))    if alg == 'polyval':        return Polyval(rand_bytes(POLYVAL_BLOCK_SIZE))    return hashlib.new(alg) def hash_update(ctx, data):    ctx.update(data) def hash_final(ctx):    return ctx.digest() def compute_hash(alg, data):    ctx = hash_init(alg)    hash_update(ctx, data)    return hash_final(ctx) def print_bytes(prefix, value, bytes_per_line):    for i in range(0, len(value), bytes_per_line):        line = prefix + ''.join(f'0x{b:02x}, ' for b in value[i:i+bytes_per_line])        print(f'{line.rstrip()}') def print_static_u8_array_definition(name, value):    print('')    print(f'static const u8 {name} = {{')    print_bytes('\t', value, 8)    print('};') def print_c_struct_u8_array_field(name, value):    print(f'\t\t.{name} = {{')    print_bytes('\t\t\t', value, 8)    print('\t\t},') def alg_digest_size_const(alg):    if alg == 'aes-cmac':        return 'AES_BLOCK_SIZE'    if alg.startswith('blake2'):        return f'{alg.upper()}_HASH_SIZE'    return f"{alg.upper().replace('-', '_')}_DIGEST_SIZE" def gen_unkeyed_testvecs(alg):    print('')    print('static const struct {')    print('\tsize_t data_len;')    print(f'\tu8 digest[{alg_digest_size_const(alg)}];')    print('} hash_testvecs[] = {')    for data_len in DATA_LENS:        data = rand_bytes(data_len)        print('\t{')        print(f'\t\t.data_len = {data_len},')        print_c_struct_u8_array_field('digest', compute_hash(alg, data))        print('\t},')    print('};')     data = rand_bytes(4096)    ctx = hash_init(alg)    for data_len in range(len(data) + 1):        hash_update(ctx, compute_hash(alg, data[:data_len]))    print_static_u8_array_definition(            f'hash_testvec_consolidated[{alg_digest_size_const(alg)}]',            hash_final(ctx)) def gen_additional_sha3_testvecs():    max_len = 4096    in_data = rand_bytes(max_len)    for alg in ['shake128', 'shake256']:        ctx = hashlib.new('sha3-256')        for in_len in range(max_len + 1):            out_len = (in_len * 293) % (max_len + 1)            out = hashlib.new(alg, data=in_data[:in_len]).digest(out_len)            ctx.update(out)        print_static_u8_array_definition(f'{alg}_testvec_consolidated[SHA3_256_DIGEST_SIZE]',                                         ctx.digest()) def gen_hmac_testvecs(alg):    ctx = hmac.new(rand_bytes(32), digestmod=alg)    data = rand_bytes(4096)    for data_len in range(len(data) + 1):        ctx.update(data[:data_len])        key_len = data_len % 293        key = rand_bytes(key_len)        mac = hmac.digest(key, data[:data_len], alg)        ctx.update(mac)    print_static_u8_array_definition(            f'hmac_testvec_consolidated[{alg.upper()}_DIGEST_SIZE]',            ctx.digest()) def gen_additional_blake2_testvecs(alg):    if alg == 'blake2s':        (max_key_size, max_hash_size) = (32, 32)    elif alg == 'blake2b':        (max_key_size, max_hash_size) = (64, 64)    else:        raise ValueError(f'Unsupported alg: {alg}')    hashes = b''    for key_len in range(max_key_size + 1):        for out_len in range(1, max_hash_size + 1):            h = hashlib.new(alg, digest_size=out_len, key=rand_bytes(key_len))            h.update(rand_bytes(100))            hashes += h.digest()    print_static_u8_array_definition(            f'{alg}_keyed_testvec_consolidated[{alg_digest_size_const(alg)}]',            compute_hash(alg, hashes)) def nh_extract_int(bytestr, pos, length):    assert pos % 8 == 0 and length % 8 == 0    return int.from_bytes(bytestr[pos//8 : pos//8 + length//8], byteorder='little') # The NH "almost-universal hash function" used in Adiantum.  This is a# straightforward translation of the pseudocode from Section 6.3 of the Adiantum# paper (https://eprint.iacr.org/2018/720.pdf), except the outer loop is omitted# because we assume len(msg) <= 1024.  (The kernel's nh() function is only# expected to handle up to 1024 bytes; it's just called repeatedly as needed.)def nh(key, msg):    (w, s, r, u) = (32, 2, 4, 8192)    l = 8 * len(msg)    assert l <= u    assert l % (2*s*w) == 0    h = bytes()    for i in range(0, 2*s*w*r, 2*s*w):        p = 0        for j in range(0, l, 2*s*w):            for k in range(0, w*s, w):                a0 = nh_extract_int(key, i + j + k, w)                a1 = nh_extract_int(key, i + j + k + s*w, w)                b0 = nh_extract_int(msg, j + k, w)                b1 = nh_extract_int(msg, j + k + s*w, w)                p += ((a0 + b0) % 2**w) * ((a1 + b1) % 2**w)        h += (p % 2**64).to_bytes(8, byteorder='little')    return h def gen_nh_testvecs():    NH_KEY_BYTES = 1072    NH_MESSAGE_BYTES = 1024    key = rand_bytes(NH_KEY_BYTES)    msg = rand_bytes(NH_MESSAGE_BYTES)    print_static_u8_array_definition('nh_test_key[NH_KEY_BYTES]', key)    print_static_u8_array_definition('nh_test_msg[NH_MESSAGE_BYTES]', msg)    for length in [16, 96, 256, 1024]:        print_static_u8_array_definition(f'nh_test_val{length}[NH_HASH_BYTES]',                                         nh(key, msg[:length])) def gen_additional_poly1305_testvecs():    key = b'\xff' * POLY1305_KEY_SIZE    data = b''    ctx = Poly1305(key)    for _ in range(32):        for j in range(0, 4097, 16):            ctx.update(b'\xff' * j)            data += ctx.digest()    print_static_u8_array_definition(            'poly1305_allones_macofmacs[POLY1305_DIGEST_SIZE]',            Poly1305(key).update(data).digest()) def gen_additional_ghash_testvecs():    key = b'\xff' * GHASH_BLOCK_SIZE    hashes = b''    for data_len in range(0, 4097, 16):        hashes += Ghash(key).update(b'\xff' * data_len).digest()    print_static_u8_array_definition(            'ghash_allones_hashofhashes[GHASH_DIGEST_SIZE]',            Ghash(key).update(hashes).digest()) def gen_additional_polyval_testvecs():    key = b'\xff' * POLYVAL_BLOCK_SIZE    hashes = b''    for data_len in range(0, 4097, 16):        hashes += Polyval(key).update(b'\xff' * data_len).digest()    print_static_u8_array_definition(            'polyval_allones_hashofhashes[POLYVAL_DIGEST_SIZE]',            Polyval(key).update(hashes).digest()) if len(sys.argv) != 2:    sys.stderr.write('Usage: gen-hash-testvecs.py ALGORITHM\n')    sys.stderr.write('ALGORITHM may be any supported by Python hashlib;\n')    sys.stderr.write('  or aes-cmac, ghash, nh, poly1305, polyval, or sha3.\n')    sys.stderr.write('Example: gen-hash-testvecs.py sha512\n')    sys.exit(1) alg = sys.argv[1]print('/* SPDX-License-Identifier: GPL-2.0-or-later */')print(f'/* This file was generated by: {sys.argv[0]} {" ".join(sys.argv[1:])} */')if alg == 'aes-cmac':    gen_unkeyed_testvecs(alg)elif alg.startswith('blake2'):    gen_unkeyed_testvecs(alg)    gen_additional_blake2_testvecs(alg)elif alg == 'ghash':    gen_unkeyed_testvecs(alg)    gen_additional_ghash_testvecs()elif alg == 'nh':    gen_nh_testvecs()elif alg == 'poly1305':    gen_unkeyed_testvecs(alg)    gen_additional_poly1305_testvecs()elif alg == 'polyval':    gen_unkeyed_testvecs(alg)    gen_additional_polyval_testvecs()elif alg == 'sha3':    print()    print('/* SHA3-256 test vectors */')    gen_unkeyed_testvecs('sha3-256')    print()    print('/* SHAKE test vectors */')    gen_additional_sha3_testvecs()elif alg == 'sm3':    gen_unkeyed_testvecs(alg)    # Kernel doesn't implement HMAC-SM3 library functions yet.else:    gen_unkeyed_testvecs(alg)    gen_hmac_testvecs(alg)