Sporadic errors in FrodoKEM on PPC

[baentsch]

I ran some tests using qemu-ppc64le and was able to reproduce the issue, although the failures appear to be very sporadic:

https://github.com/aidenfoxivey/liboqs/actions/runs/16788186098/job/47547291113

Using the same compiler configuration, Valgrind consistently reports issues in encaps/decaps (also in the Frodo-SHAKE versions, which neverthless appear to return the correct results):

/home/liboqs/build# valgrind tests/test_kem_mem FrodoKEM-640-AES 1
==82868== Invalid read of size 8
==82868==    at 0x1147D0: OQS_KEM_frodokem_640_aes_encaps (kem.c:151)
==82868==    by 0x10C397: kem_test_correctness (test_kem_mem.c:93)
==82868==  Address 0x1ffeffffb0 is on thread 1's stack
==82868==  320 bytes below stack pointer
...

These errors disappear when auto-vectorization is disabled in the frodo_sample_n function using: #pragma GCC optimize("no-tree-vectorize")

I’m not certain about the root cause yet. My current guess is that there’s a subtle aliasing or alignment issue:

• ppc64le vector instructions typically require 16- or 32-byte alignment.
• Frodo code contains several pointer casts (e.g., 16->32 bits, 8->16 bits) that might be tricky with strict aliasing rules, which I believe are used in the liboqs builds.

Originally posted by @bhess in #2068

[dstebila]

Tagging @patricklonga to see if he has any insights.

[ode]

Tried my hand at this since I was also working on #2192

I managed to reproduce the issue on qemu and pin down the exact instructions causing invalid memory reads using vgdb. Noting down observations and hypotheses with a heads-up that I'm not too familiar with powerpc asm and could very well be wrong.

    clear_bytes(shake_input_seedSE, 1 + CRYPTO_BYTES);
   382b4:	11 00 80 38 	li      r4,17
   382b8:	78 db 63 7f 	mr      r3,r27
   382bc:	ed 02 fd 4b 	bl      85a8 <OQS_MEM_cleanse+0x8>
   382c0:	00 00 00 60 	nop
    return OQS_SUCCESS;
}
   382c4:	00 00 20 39 	li      r9,0
   382c8:	30 00 5f 39 	addi    r10,r31,48
   382cc:	18 c8 29 61 	ori     r9,r9,51224
   382d0:	14 52 29 7d 	add     r9,r9,r10
   382d4:	00 00 49 e9 	ld      r10,0(r9)
   382d8:	f0 8f 2d e9 	ld      r9,-28688(r13)
   382dc:	79 4a 4a 7d 	xor.    r10,r10,r9
   382e0:	00 00 20 39 	li      r9,0
   382e4:	8c 00 82 40 	bne     38370 <OQS_KEM_efrodokem_640_aes_encaps+0x1140>
   382e8:	00 00 61 e9 	ld      r11,0(r1)
   382ec:	00 00 60 38 	li      r3,0
   382f0:	78 5b 61 7d 	mr      r1,r11
   382f4:	c9 fe 8b f6 	lxv     vs52,-320(r11) <--- invalid read
   382f8:	d9 fe ab f6 	lxv     vs53,-304(r11) <--- invalid read
   382fc:	e9 fe cb f6 	lxv     vs54,-288(r11)
   38300:	f9 fe eb f6 	lxv     vs55,-272(r11)
   38304:	10 00 01 e8 	ld      r0,16(r1)

• Invalid reads happen in the function epilogue after return; this is likelier to be due to a compiler bug than an issue with Frodo code
• PPC uses r1 as the stack pointer and its ABI defines a 288 byte red zone. Since valgrind stops complaining about invalid reads from 382fc, this is probably red zone related

Probable root cause:

1. Registers of the caller function are saved to the stack if the called function (encaps/decaps) uses them
2. High usage of VSX registers - which are 16 bytes each - in encaps/decaps means the program has to save more than 288 bytes on stack
3. After the function returns, the program attempts to restore caller's registers from the stack, finding itself beyond the red zone

This should only be problematic if the caller function also uses vector registers heavily and an interrupt is triggered before they are restored