out of bounds memory read potential in cttk_i31_rsh

[tobycmurray]

Against commit 1d592024398f06c8eda1d325bdbd105ac32d92b3

cttk_i31_rsh seems to read memory out-of-bounds, depending on what parameters it is called with.

The following test-case demonstrates the issue:

#include <stdio.h>
#include <stdlib.h>
#include "inc/cttk.h"

int main() {
  /* n = 4294967295, v = 18446744073709551615 */
  uint32_t a[4];
  int64_t v = 18446744073709551615;
  uint32_t b[4];
  uint32_t n = 4294967295;
  cttk_i31_init(a,60);
  cttk_i31_init(b,60);
  printf("n = %u, v = %llu\n",n,v);
  cttk_i31_set_s64(a,v);
  cttk_i31_rsh(b,a,n);
  return 0;  // Values other than 0 and -1 are reserved for future use.
}

When run with AddressSanitizer (ASAN) manifests the issue

=================================================================
==58607==ERROR: AddressSanitizer: SEGV on unknown address 0x000326fdb9d4 (pc 0x000100e851d6 bp 0x000305f57730 sp 0x000305f574c0 T0)
==58607==The signal is caused by a READ memory access.
    #0 0x100e851d6 in genrsh int31.c:1719
    #1 0x100e8496f in cttk_i31_rsh int31.c:1840
    #2 0x100e71380 in main test_rsh_main.c:15
    #3 0x2010364fd in start+0x1cd (dyld:x86_64+0x54fd) (BuildId: 7de33963bbc53996ba6ef1d562c17c9532000000200000000100000000020c00)
    #4 0x201030fff  (<unknown module>)

This potential issue was found using the Underflow tool (https://bitbucket.org/covern/underflow) and the test-case generated with the help of libFuzzer and ASAN.

[pornin]

It's probably because of the test there: https://github.com/pornin/CTTK/blob/master/src/int31.c#L1697 If the shift count (n) is larger than the bit length then the result is 0 or -1 (depending on the source sign) but the check uses n+1, and in your test case n is 0xFFFFFFFF so n+1 overflows the 32 bits. This is an edge case that should, in practice, be harmless, but for completeness I should fix it anyway.