Closed guidovranken closed 2 years ago
Agreed it's a bug!
I never really cared about the bounds and it should be fairly easy to fix. Thanks! :)
It now hangs:
#include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t A, B, R1, R2, R3;
bn_null(A); bn_new(A);
bn_null(B); bn_new(B);
bn_null(R1); bn_new(R1);
bn_null(R2); bn_new(R2);
bn_null(R3); bn_new(R3);
const char* s1 = "555555555555555550000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000081624404648562574776480988416386318723821493777533412583444266365419065804535170339197542765321752482359143484437390596115585268050595800018570555555555555555555555555555500000000000000000000000000000000000000000000000000000";
const char* s2 = "66666666666666666666666666660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001123911187445684340258072669751633781322533717977849594343489334935505860661000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036363310000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000031696932928800000000000000000000000000000000000000";
bn_read_str(A, s1, strlen(s1), 10);
bn_read_str(B, s2, strlen(s2), 10);
bn_gcd_ext_stein(R1, R2, R3, A, B);
bn_free(A);
bn_free(B);
bn_free(R1);
bn_free(R2);
bn_free(R3);
return 0;
}
I pushed a not very robust heuristic to fix this later case in 94e5653d78e12af59077176c8612f4209ad8c50b to see how it goes. Notice that I also did a minor refactoring of the configuration and now the function is called bn_gcd_ext_binar
to match the rest of the library.
This one still hangs:
#include <relic_conf.h>
#include <relic.h>
int main(void)
{
if ( core_init() != RLC_OK ) abort();
bn_t A, B, R1, R2, R3;
bn_null(A); bn_new(A);
bn_null(B); bn_new(B);
bn_null(R1); bn_new(R1);
bn_null(R2); bn_new(R2);
bn_null(R3); bn_new(R3);
const char* s1 = "7000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
const char* s2 = "800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
bn_read_str(A, s1, strlen(s1), 10);
bn_read_str(B, s2, strlen(s2), 10);
bn_gcd_ext_binar(R1, R2, R3, A, B);
bn_free(A);
bn_free(B);
bn_free(R1);
bn_free(R2);
bn_free(R3);
return 0;
}
I just pushed another, more principled, attempt.
I can't find any more issues. I've enabled the function in my fuzzer: https://github.com/guidovranken/cryptofuzz/commit/947c568da669d082b99fca175d2ff15c83cf25e5 If there is anything else, OSS-Fuzz will notify us.
This prints:
But if you comment out
bn_gcd_ext
and uncommentbn_gcd_ext_stein
, it prints:Both of these are correct in that they satisfy the equation
X*A + Y*B == GCD(A,B)
.While Bezout coefficients for a given
GCD(A,B)
are not unique, it is my understanding that the particular values returned by the extended GCD algorithm are unique.Specifically, if my reading of Wikipedia is correct, they must satisfy:
The result returned by
bn_gcd_ext_stein
does not satisfy these constraints. Python:Can you confirm this is a bug?