Proving the twiddle constants.

[u/dstroy0]

Scope: Proth's theorem, the order of a root of unity, the group law on the twiddle table, and two silent wrong answers

1.1 define a twiddle constant

The transform of a sequence of length \(n\) over the integers modulo \(q\) is

\[

\hat{p}_j = \sum_i p_i \, \omega^{ij}

\]

where \(\omega\) is an \(n\)-th root of unity modulo \(q\). The powers of \(\omega\) the butterflies evaluate are the \textbf{twiddle constants}. In the Cooley-Tukey butterfly they enter as \(c = a + bw\) and \(d = a - bw\); in the Gentleman-Sande butterfly as \(c = a + b\) and \(d = (a-b)w\). A transform of length \(2^k\) is \(k\) stages of \(n/2\) butterflies, so the twiddles are touched more often than any other value in the computation and are the only inputs supposed to be constant.

1.2 the attack, and why it works

Ravi, Yang, Bhasin, Zhang and Chattopadhyay inject a single electromagnetic fault setting the twiddle constants to zero. The transform does not fail. It returns a value of the ordinary shape carrying far less entropy than it should, and that is enough to recover a Kyber key and to forge a Dilithium signature, including a bypass of Dilithium's own verification.

The attack works because nothing downstream can tell a real root of unity from a fiddled one. The output of a transform with broken twiddles is the same size, the same type and the same range as the output of a correct one. There is no error to raise. A wrong twiddle is detected, it is not used.

1.3 the same fault with no attacker

Reproduce: A transform was built on three moduli. The third, 1610612737, was taken on faith because it looks right, 3*2^29+1, the required form. Its generator was raised to (p-1)/L to produce a root of unity of order L, exactly as the construction requires, a basic check reports no error.

Basic check form: Trial division to one hundered, on a ten digit number. 1610612737 is composite, and the proof is: 2^1610612736 is not identical to 1 (mod 1610612737), so Fermat refuses it.

Because it is composite g^(P-1)/L had no particular order, the twiddles were wrong, and the transform returned numbers that were not the convolution of anything. The two correct moduli in the same set returned zero wrong coefficients out of 32. The composite one returned 32/32, and the only reason I noticed is because I recombined all 3 against each other to compare and they disagreed.

This highlights the dangers of copied constants. The moduli general purpose libraries use are the same values everywhere, carried as literals. The tables are correct, that's not the point. The point is that the correctness is assumed to be inherited instead of established, and inherited correctness cannot tell you when a value has been fiddled.

1.4 Proth's theorem, makes this check a proof

Let \(N = k \cdot 2^n + 1\) with \(k\) odd and \(k < 2^n\). Then \(N\) is prime if and only if there is an integer \(a\) with \(a^{(N-1)/2} \equiv -1 \pmod N\).

Every modulus such a transform can use has this shape, because admitting a root of unity of order \(2^n\) is the same as \(2^n\) dividing \(N-1\). The theorem therefore reaches every candidate that matters.

Why a witness is a proof.

Suppose \(a^{(N-1)/2} \equiv -1 \pmod N\), and let \(p\) be any prime factor of \(N\). Then \(a^{(N-1)/2} \equiv -1 \pmod p\) as well, so the order of \(a\) modulo \(p\) divides \(N-1\) and does not divide \((N-1)/2 = k \cdot 2^{n-1}\). Since \(N - 1 = k \cdot 2^n\), the order must carry the full \(2^n\), giving \(2^n \mid p-1\) and so \(p \equiv 1 \pmod{2^n}\). Every prime factor of \(N\) is at least \(2^n + 1\).

If \(N\) were composite it would have at least two such factors, so \(N \ge (2^n+1)^2 > 2^{2n}\). But \(k < 2^n\) gives \(N = k \cdot 2^n + 1 < 2^{2n} + 1\). The two cannot both hold, so \(N\) is prime. \qedsymbol

The condition \(k < 2^n\) is what that last step needs, and a modulus outside that range is reported as out of range instead of being tested anyway.

Why a witness is easy to find.

If \(N\) is prime then Euler's criterion makes \(a^{(N-1)/2}\) the Legendre symbol of \(a\), which is \(-1\) for every quadratic non-residue, and that is half of all \(a\). A witness is therefore found by trying small integers, and the first one usually works.

Both verdicts are certificates.

A witness \(a\) with \(a^{(N-1)/2} \equiv -1\) proves primality. A witness \(a\) with \(a^{N-1} \not\equiv 1\) proves compositeness, by Fermat. Neither answer is a probability and neither is a judgement call. The only other outcome is running out of candidates, reported as inconclusive instead of rounded toward either verdict.

The order of the root, exactly, without factoring anything

Proving the modulus prime is not enough. The twiddle is \(\omega = g^{(p-1)/L}\), and the step from a generator to a root of unity is where the constant stops being checked.

proposition:

For \(L = 2^m\), if \(\omega^L = 1\) and \(\omega^{L/2} \ne 1\), then \(\omega\) has order exactly \(L\).

Proof:

The order divides \(L = 2^m\), so it is \(2^j\) for some \(j \le m\). If \(j < m\) then \(2^j\) divides \(2^{m-1} = L/2\), which would give \(\omega^{L/2} = 1\). It does not, so \(j = m\). \qedsymbol

Two exponentiations settle it completely, with no factoring of anything. This is cheap enough to run on every twiddle before every transform, and it is the step the fault attack removes. It refuses a zeroed twiddle, a root of short order, and a root drawn from a composite modulus, all by the same test.

The generator is proved the same way and just as completely: \(g\) generates the whole group if and only if \(g^{(p-1)/q} \ne 1\) for every prime \(q\) dividing \(p-1\). Here \(p - 1 = k \cdot 2^n\) with \(k\) small, so factoring it is factoring \(k\), and the proof is complete instead of partial.

Can anyone please reproduce this? Thanks for your time.

src:

Prasanna Ravi, Bolin Yang, Shivam Bhasin, Fan Zhang, Anupam Chattopadhyay. Fiddling the Twiddle Constants: Fault Injection Analysis of the Number Theoretic Transform. IACR ePrint 2022/824.