LUT-SHA256: Arithmetic-Free Execution of SHA-256 through Chained Look-Up Tables

Abstract

This work presents LUT-SHA256, an alternative execution architecture for theSHA-256 compression function in which no arithmetic, logical, or shiftoperation is ever applied to message data. The proposal rests on twostructural theorems: addition modulo 2^32 is reformulated as a four-stagechain of tabulated byte-additions with explicit carry propagation (TADDC),and cyclic rotations and logical shifts are expressed as byte recombinationthrough displacement tables. A functional-decomposition argument yields fullequivalence with FIPS 180-4, verified against standard vectors, block-boundarycases, and BIP39-derived inputs. A progressive compression of the table set(v2.0-v2.4) reduces memory by up to 58% and lookups per block by up to 41%,including a zero-block master schedule for PBKDF2/BIP39 workloads. Becausedata only appears as table indices, the architecture exhibits a distinctiveside-channel surface: a vulnerability ladder (V1.0-V1.7) is formalized andleakage thresholds are quantified with the SMT solver Z3, showing that asingle leaked addition per round inverts the compression algebraically whilecarry-bit leakage alone does not. Hardware implications for FPGAs, secureelements, and compute-in-memory are discussed. [Spanish abstract]Se presenta LUT-SHA256, una arquitectura alternativa de ejecución de SHA-256en la que ninguna operación aritmética, lógica o de desplazamiento se aplicasobre los datos del mensaje: los bytes actúan únicamente como índices detablas precomputadas. Dos teoremas estructurales — la suma módulo 2^32 comocadena de acarreos tabulados (TADDC) y las rotaciones como recombinación debytes (TROT) — junto con un teorema de equivalencia demuestran la identidadde resultados con FIPS 180-4, verificada experimentalmente. Se documenta unacompresión progresiva (v2.0-v2.4, hasta -58% de memoria y -41% de búsquedas)y una escalera de vulnerabilidad de canal lateral (V1.0-V1.7) cuantificadacon el solver SMT Z3. Se discuten implicaciones para FPGAs, elementosseguros y compute-in-memory.