HuFu: Big-flipping forgeries and buffer overflows

[Markku-Juhani O. Saarinen]

Hello Again,

The candidate HuFu allows signature forgeries by bit flipping of specific bits of the signature encoding. This technically breaks the proposal's strong unforgeability (SUF-CMA) security claim (Section 2.2.)

For example, given the count = 0 test vector for Level 1 HuFu ( PQCsignKAT_11417440.rsp ), we may change bit 4 of byte 820 from 14 to 04:

sm = 09649401450 .. 54E2D7[14]3C2DCF .. 93BC06BC3041C66
sm = 09649401450 .. 54E2D7[04]3C2DCF .. 93BC06BC3041C66

Both signatures verify. Five other signature bits can be changed without causing the signature to be rejected -- or a more severe malfunction (see below). A brief investigation seems to point to unspecified/ambiguous encoding of the bits between the rANS "high" and "low" portions.

The signature verification code of HuFu also contains buffer overflow vulnerabilities. One is remarkably similar to the one in Haetae (resembling Heartbleed) from a "forensic" perspective -- even though the authorship appears to be completely different.

File `HuFu-noKATs/HuFu/Reference_Implementation/crypto_sign/HuFu_NIST1/sign.c`, function `crypto_sign_open()`:

```
220:    // recover sig_len
221:    unsigned sig_len = ((unsigned)sm[0] << 8) | sm[1];
222:    *mlen = smlen - sig_len - PARAM_SALT_BYTES - 2;
223:    
224:    // Step 6: recover u
225:    uint8_t mexp[*mlen+PARAM_SALT_BYTES];
226:    memcpy(mexp , sm + 2 + sig_len, *mlen+PARAM_SALT_BYTES);
227:    memcpy(m, mexp, *mlen);

```

We observe that the 16-bit length variable `sig_len` decoded on line 221 is not checked but used in an address computation at line 226. This is a critical-level remote code execution and/or sensitive data leak vulnerability if instantiated in an application.

This is not an exhaustive list of vulnerabilities -- there appear to be additional problems at the end of the signature (I have an untriaged buffer overflow with bit flips there), and I did examine the public key encoding (which is also attacker-controlled in server applications) apart from finding that it can also be modified without affecting the signature verification result (no attention paid to BUFF.)

Cheers,

markku

[Delong Ran]

Dear Markku,

Thanks for your feedback on the security flaws in our implementation.

We have investigated the bit-flipping attack, and discovered that it is caused by the non-uniqueness of rANS coding instead of boundary ambiguity. This attack can also affect HAETAE: for example, changing byte 1318 in the first test vector of HAETAE-Level2 from "BFA81C51[A3]CF7B" to "BFA81C51[9E]CF7B" would create a forgery. To prevent this attack, we have added sanity checks to the rANS decoder to ensure that the messages and codings are bijective. The performance overhead of this patch is negligible. Details are shown in this report: http://123.56.244.4/rANS.pdf

To defend the length modification attack, we have removed the length field and padded the rANS coding to a fixed length.

Regarding the BUFF transformations, we have encountered a severe performance degrades due to the large size of HuFu’s public key (1~3MB): 1.35x~1.64x for sign, 2.21x~3.30x for verify. Therefore, we are still looking for a more efficient method for BUFF.

The updated codes and docs can be found at http://123.56.244.4/HuFu-v1.1.0.zip . We would appreciate your further insights.

Regards,
Delong Ran, on behalf of the HuFu Team

[Georg Land]

Dear Markku, dear Delong Ran, dear all,

thank you for your interest and valuable examination of Haetae! We just released a new version of our reference implementation to address the issues raised in the pqc-forum and other bugs we identified in the meantime. The reference implementation, an AVX2 optimized version and an up-to-date specification with more detailed explanations of several implementation aspects can be found at:

https://kpqc.cryptolab.co.kr/haetae

Additionally, a version for embedded devices featuring the Cortex-M4 will be available via the pqm4 framework. To mitigate the bit-flipping attack demonstrated by Markku for HuFU and by Delong Ran for Haetae, we relied on the excellent report on rANS for signature compression provided by the Hufu team. Simultaneously, we addressed the memory safety issues presented previously by Markku. We drastically reduced the size of the precomputation tables for the rANS encoding, by minimizing the symbol space via rejection of very rare symbols. Some modifications led to changes in the distributions of the size of the compressed values, we therefore adapted the signature sizes slightly.

The HAETAE Team