limited randomness in SMAUG-T software

[D. J. Bernstein]

Inspecting thousands of secret keys generated by the (reference and
optimized) SMAUG-T software shows that their nonzero coefficients are
always at positions 1, 10, 16, etc. Three examples appear below. The
signs are random, but the known positions reduce the secret from 512
dimensions (for SMAUG-T128) to 140 dimensions, which is not secure
against lattice attacks.

Fixing the previously mentioned 0xfffffffff bug changes the positions to
a different set of 140 positions: 4, 7, 8, 13, etc. These positions are
explained by the code setting res[div] where div is set to non-random
values, namely

* first 1+((2^32-1) mod (512-140)),
* then 1+((2^32-1) mod (512-139)),
* etc.

The code also moves previously initialized res entries to the end of the
array. There are many collisions in these particular div values (e.g.,
there are 14 occurrences of 256, coming from many divisors of 2^32-256),
producing the pileup visible near the end in the examples below.

Specifically, deg in the following code comes from randomness but div
doesn't:

uint32_t deg = buf[i];
uint32_t remain;
remain = 0xfffffffff / (DIMENSION - hmwt + pos);
div = 0xffffffff - remain * (DIMENSION - hmwt + pos);
div++;
if (((0xffffffff - div) > deg) && (pos < hmwt)) {
res[DIMENSION - hmwt + pos] = res[div];
res[div] =
((buf[(xof_block * 32 + (i >> 4))] >> (i & 0x0f)) & 0x02) - 1;
pos++;
} else {
garbage = res[div];
garbage =
((buf[(xof_block * 32 + (i >> 4))] >> (i & 0x0f)) & 0x02) - 1;
}

Some lucky keys might have the "(0xffffffff - div) > deg" test in the
code fail, producing a different position, but 0xffffffff - div is very
close to 2^32, so this will not happen often.

The algorithm in the specification (Figure 2 on page 12) is different
from the code and doesn't work at all: "buf[idx] / i" in the spec is
almost always out of range. Probably the intent of the specification was
"buf[idx] mod i", and the code should similarly use

res[deg % (DIMENSION - hmwt + pos)]

instead of each occurrence of res[div]. Note that divisions require care
to implement in constant time.

---D. J. Bernstein and Tanja Lange

.-........-.....+...+.-...-...+.....-........+.....+.-......-...+.....+....+.+...+..........-+..-...+...........-.+...-........-+....-..+...--..........-....-.......-...+..+...........-.+...-.....-...........--......+...+.....+.....+...+...+....+..-.......+...+..........+........+...+.-.+.+..+..-.....+.............+.........-.-.......+.+....-+.+.....-........-...-+.....+...+..+.-..+........++.-...+........+..-...-+....-.+...--+.+++--........++++.++++.+..-.+.+--...+.++--.-.-+++-.++.+..--.-+++-.--+--.-..-+.--
.+........-.....-...+.+...+...+.....-........+.....-.+......+...+.....+....-.-...-..........-+..-...+...........-.+...-........-+....+..-...+-..........+....+.......+...+..-...........+.+...-.....-...........++......-...+.....-.....+...+...+....-..-.......-...-..........-........-...+.+.-.-..-..-.....-.............-.........-.-.......+.+....--.+.....+........-...-+.....-...+..-.+..+........++.-...-........-..+...-+....+.+...+--.--+++........----.++--.-..-.-.+--...-.-+-+.-.++-++.++.-..++.-++--.+-+-+.+..+-.+-
.-........+.....-...-.+...+...-.....+........-.....+.-......-...+.....+....-.+...+..........+-..-...+...........+.-...+........-+....+..-...--..........-....-.......+...+..+...........+.+...-.....+...........++......-...-.....+.....+...-...+....-..+.......-...-..........-........+...-.+.+.-..-..+.....-.............+.........+.-.......-.-....-+.+.....-........-...-+.....+...-..-.-..-........--.+...-........+..+...-+....-.+...++-.++-+-........-++-.+-++.+..+.-.-+-...+.-++-.-.+-+--.+-.-..-+.-----.-----.-..-+.+-

[Hyoeun Seong]

Dear all, 

We first thank D. J. Bernstein for pointing this out. 

We updated the key generation implementation on March 20, in the public git repository of SMAUG-T. The secret key is now sampled as intended, but is not yet constant-time. 

Please see here for more details and our plans for an upcomming update. 

Best Regards, 

Team SMAUG-T

2024년 5월 11일 토요일 오후 7시 13분 7초 UTC+9에 D. J. Bernstein님이 작성:

[Nari Lee]

Dear SMAUG-T team,

We noticed an error in hwt.c in your revised implementation, version 3.0.1:

...

        deg = deg / remain;
        if (((0xffffffff - div) > deg) && pos < hmwt) {
            res[DIMENSION - hmwt + pos] = res[deg];
...

The inequality  0xffffffff - div > deg  will always be satisfied as  deg = deg / remain,  which will result in no rejection.
For an instance of SMAUG-T-128,  0xffffffff - div > 0xffffffff -372  and   0 <= (deg/remain) <= 372,  therefore  0xffffffff - div > deg/remain.

The following can be used to fix it.
...

        if (((0xffffffff - div) > deg) && pos < hmwt) {
            deg = deg / remain;
            res[DIMENSION - hmwt + pos] = res[deg];
...


Additionally, we observed an error in the specification specifying HWT in Fig. 2.

        line 9: degree = buf[idx] / i

It should be the following:

        line 9: degree = buf[idx] / div

         

All the best,

Moon Sung Lee, Nari Lee, and Hansol Ryu