undefined behavior in shamir unbitslice()

[invd]

During security research for SatoshiLabs on the Trezor firmware, I recently discovered an undefined behaviour edge case via (1 << 31) in the following line for unbitslice(): https://github.com/dsprenkels/sss/blob/b3ac4e75d44f68693aba9f938382018527b1a223/hazmat.c#L59

UndefinedBehaviorSanitizer: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'

Please see the main bug report for details of the issue and two proposed patches. Note that our unbitslice() variant has a dynamic length parameter, but is called with len = 32 in this context and should be functionally identical.

@dsprenkels : we're interested if you can confirm the issue. Which patch do you prefer? Thanks!

[dsprenkels]

@invd Thank you for the bug report! Sorry for acting on it after such a long time, I have been on vacation.

I feel that the real bug here is that (1 << arr_idx) is an int, instead of a uint32_t, but that does not matter for the fix.

I would personally prefer first fix:

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

[dsprenkels]

Note: We should also fix the bitslice part of this bug located at:

https://github.com/dsprenkels/sss/blob/b3ac4e75d44f68693aba9f938382018527b1a223/hazmat.c#L43

[andrewkozlik]

Note: We should also fix the bitslice part of this bug located at:

https://github.com/dsprenkels/sss/blob/b3ac4e75d44f68693aba9f938382018527b1a223/hazmat.c#L43

Technically this is OK, because bit_idx is at most 7 and the minimum size of int is 16 bits. But I agree it would be more readable and consistent to write it in the other form.

[invd]

@dsprenkels: no problem for the delay! I agree with @andrewkozlik for the patch consideration. We have the proposed patch in the linked Trezor issue.

[prusnak]

For reference - here's the patch we merged to Trezor codebase: https://github.com/trezor/trezor-firmware/commit/5429acdb7f5dc465e7cc6efc19079237dde93667