openssl: BN_mod_inverse incorrect result when parameters are aliased

#include <openssl/bn.h>

#define CF_CHECK_NE(expr, res) if ( (expr) == (res) ) { goto end; }

int main(void)
{
    char* str = NULL;
    BIGNUM* a = BN_new();
    BIGNUM* b = BN_new();
    BN_CTX* ctx = BN_CTX_new();
    CF_CHECK_NE(BN_dec2bn(&a, "5193817943"), 0);
    CF_CHECK_NE(BN_dec2bn(&b, "3259122431"), 0);
    CF_CHECK_NE(BN_mod_inverse(b, a, b, ctx), NULL);
    str = BN_bn2dec(b);
    printf("%s\n", str);
end:
    BN_free(a);
    BN_free(b);
    BN_CTX_free(ctx);
    OPENSSL_free(str);
    return 0;
}

This prints 0 but should print 2609653924. Note that in the call to BN_mod_inverse, the result is the same pointer as the modulus. The documentation explicitly states that “r may be the same BIGNUM as a or n.”.

This also affects @davidben and @botovq.

About this issue

Original URL
State: closed
Created a year ago
Comments: 19 (19 by maintainers)

Commits related to this issue

Make BN_mod_inverse() deal with repeated arguments BN_nnmod() can deal with the situation that the first and the second arguments are the same, but it cannot deal with the first and the second argume... — committed to google/boringssl by botovq a year ago
Fix variable reuse in BN_mod_inverse() The somewhat strange calculation m = a^{-1} (mod m) can return 0. This breaks because of BN_nnmod() having delicate semantics of which variable can be reused. B... — committed to openbsd/src by botovq a year ago
Fix variable reuse in BN_mod_inverse() The somewhat strange calculation m = a^{-1} (mod m) can return 0. This breaks because of BN_nnmod() having delicate semantics of which variable can be reused. B... — committed to libressl/openbsd by deleted user a year ago
Fix BN_nnmod and BN_mod_inverse incorrect result When r aliases d the result may be wrong, since d is overwritten by BN_mod but it may still be used later. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix BN_nnmod and BN_mod_inverse incorrect result When r aliases d the result may be wrong, since d is overwritten by BN_mod but it may still be used later. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix BN_mod_exp_simple incorrect result Likewise BN_mod_exp_simple overwrites the modulus m or the exponent p with the result r too early. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix incorrect result of BN_mod_sub_quick Fix also possible BN_mod_sub_quick aliasing issues of r and m parameters. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix variable reuse in BN_mod_inverse() The somewhat strange calculation m = a^{-1} (mod m) can return 0. This breaks because of BN_nnmod() having delicate semantics of which variable can be reused. B... — committed to libressl/openbsd by deleted user a year ago
Make BN_mod_inverse() deal with repeated arguments BN_nnmod() can deal with the situation that the first and the second arguments are the same, but it cannot deal with the first and the second argume... — committed to dkostic/aws-lc by botovq a year ago
Make BN_mod_inverse() deal with repeated arguments BN_nnmod() can deal with the situation that the first and the second arguments are the same, but it cannot deal with the first and the second argume... — committed to dkostic/aws-lc by botovq a year ago
Make BN_mod_inverse() deal with repeated arguments BN_nnmod() can deal with the situation that the first and the second arguments are the same, but it cannot deal with the first and the second argume... — committed to dkostic/aws-lc by botovq a year ago
Make BN_mod_inverse() deal with repeated arguments BN_nnmod() can deal with the situation that the first and the second arguments are the same, but it cannot deal with the first and the second argume... — committed to dkostic/aws-lc by botovq a year ago
bn: Properly error out if aliasing return value with modulus Fixes #21110 — committed to t8m/openssl by t8m 8 months ago
bn: Properly error out if aliasing return value with modulus Test case amended from code initially written by Bernd Edlinger. Fixes #21110 — committed to t8m/openssl by t8m 8 months ago
bn: Properly error out if aliasing return value with modulus Test case amended from code initially written by Bernd Edlinger. Fixes #21110 Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com> Reviewe... — committed to openssl/openssl by t8m 8 months ago
bn: Properly error out if aliasing return value with modulus Test case amended from code initially written by Bernd Edlinger. Fixes #21110 Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com> Reviewe... — committed to openssl/openssl by t8m 8 months ago
bn: Properly error out if aliasing return value with modulus Test case amended from code initially written by Bernd Edlinger. Fixes #21110 Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com> Reviewe... — committed to openssl/openssl by t8m 8 months ago
Fix BN_nnmod and BN_mod_inverse incorrect result When r aliases d the result may be wrong, since d is overwritten by BN_mod but it may still be used later. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix BN_mod_exp_recp and BN_mod_exp_simple incorrect result Likewise BN_mod_exp_simple overwrites the modulus m or the exponent p with the result r too early. However BN_mod_exp_recp fails only when ... — committed to bernd-edlinger/openssl by bernd-edlinger a year ago
Fix incorrect result of BN_mod_sub_quick Fix also possible BN_mod_sub_quick aliasing issues of r and m parameters. Fixes #21110 — committed to bernd-edlinger/openssl by bernd-edlinger a year ago

Most upvoted comments

Yes, I’ve added them to #21124 as separate commits.

bernd-edlinger on Jun 6, 2023

If you have such a list, then I think it would be worthwhile. As you note, aliasing is bad – it should either be fixed, return an error or minimally be documented. This is one thing FORTRAN got right grin

The only ones I’ve found so far are BN_mod_exp_simple and BN_mod_sub_quick

guidovranken on Jun 5, 2023