undefined behavior in shamir unbitslice()

UB in unbitslice()

During fuzzing, I've discovered an edge case in the shamir crypto code:

https://github.com/trezor/trezor-firmware/blob/741fca01567151fa9dad2e9d25db7236169fb697/crypto/shamir.c#L64

shamir.c:64:32: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shamir.c:64:32 in

The problem here is that (1 << arr_idx) is undefined for arr_idx = 31 due to C integer handling.

Upstream

This appears to be a problem in the upstream code as well: https://github.com/dsprenkels/sss/blob/b3ac4e75d44f68693aba9f938382018527b1a223/hazmat.c#L59

I've reported it there as https://github.com/dsprenkels/sss/issues/36.

Proposed patch

@andrewkozlik has reviewed this issue and proposes

r[arr_idx] |= ((cur >> arr_idx) & 1) << bit_idx;

as a solution. Alternatively, we can do the following:

r[arr_idx] |= ((cur & ((uint32_t)1 << arr_idx)) >> arr_idx) << bit_idx;

which is closer to the original line, but less readable.

Impact

In a brief function test under x86_64 and clang, the undefined behaviour did not change the results of the computation, but this can vary across platforms and compilers.

Debugging

Some additional debugging information:

(gdb) print arr_idx
$1 = 31
(gdb) print bit_idx
$2 = 0
(gdb) print cur
$3 = 3617546517
(gdb) print len
$4 = 32

# result after executing the affected line
(gdb) print r[arr_idx]
$5 = 1 '\001'

Categorization

At the moment, I see this as a somewhat low-priority bug in core / crypto that affects only the T2 and has no known practical impact.

trezor / trezor-firmware