Mailing List Archive: Old bug in gcry_mpi_invm producing wrong result

Old bug in gcry_mpi_invm producing wrong result

Apr 22, 2022, 3:00 PM

Post #1 of 4 (374 views)

It says that InvMod(18446744073709551615,
340282366762482138434845932244680310781) is
170141183381241069226646338154899963903 but that's not true, because
170141183381241069226646338154899963903 * 18446744073709551615 %
340282366762482138434845932244680310781 is 4294967297, not 1.

It looks like this bug has been present at least since libgcrypt-1.2.0 from
2004.

#include <gcrypt.h>

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

int main(void)
{
gcry_mpi_t A;
gcry_mpi_t B;
gcry_mpi_t C;
gcry_error_t err;

CF_CHECK_EQ(err = gcry_mpi_scan(&A, GCRYMPI_FMT_HEX,
"ffffffffffffffff", 0, NULL), 0);
CF_CHECK_EQ(err = gcry_mpi_scan(&B, GCRYMPI_FMT_HEX,
"fffffffdfffffffffffffffffffffffd", 0, NULL), 0);
CF_CHECK_EQ(err = gcry_mpi_scan(&C, GCRYMPI_FMT_HEX, "1", 0, NULL), 0);
CF_CHECK_EQ(gcry_mpi_invm(C, A, B), 1);
printf("Inverse exists\n");
end:

return 0;
}

Re: Old bug in gcry_mpi_invm producing wrong result [ In reply to ]

gniibe at fsij

May 10, 2022, 12:05 AM

Post #2 of 4 (368 views)

Permalink

Guido Vranken wrote:
> It says that InvMod(18446744073709551615,
> 340282366762482138434845932244680310781) is
> 170141183381241069226646338154899963903 but that's not true, because
> 170141183381241069226646338154899963903 * 18446744073709551615 %
> 340282366762482138434845932244680310781 is 4294967297, not 1.

Thank you for your report. With libgcrypt 1.8, it works correctly.

It is tracked by: https://dev.gnupg.org/T5970

The fix I pushed is:

diff --git a/mpi/mpih-const-time.c b/mpi/mpih-const-time.c
index b527ad79..9d74d190 100644
--- a/mpi/mpih-const-time.c
+++ b/mpi/mpih-const-time.c
@@ -204,6 +204,13 @@ _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v)
is_all_zero &= (up[i] == 0);

if (is_all_zero)
- return up[0] - v;
+ {
+ if (up[0] < v)
+ return -1;
+ else if (up[0] > v)
+ return 1;
+ else
+ return 0;
+ }
return 1;
}

The expression of up[0] - v is only correct on 32-bit architecture.
It may return wrong result on 64-bit architecture.
--

_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@lists.gnupg.org
https://lists.gnupg.org/mailman/listinfo/gcrypt-devel

Re: Old bug in gcry_mpi_invm producing wrong result [ In reply to ]

gcrypt-devel at lists

May 10, 2022, 3:51 AM

Post #3 of 4 (368 views)

Permalink

Thank you. I have confirmed that your patch resolves the issue.

However I tried again with 1.8.0 and at that version, the reproducer prints
"Inverse exists".

On Tue, May 10, 2022 at 9:05 AM NIIBE Yutaka <gniibe@fsij.org> wrote:

> Guido Vranken wrote:
> > It says that InvMod(18446744073709551615,
> > 340282366762482138434845932244680310781) is
> > 170141183381241069226646338154899963903 but that's not true, because
> > 170141183381241069226646338154899963903 * 18446744073709551615 %
> > 340282366762482138434845932244680310781 is 4294967297, not 1.
>
> Thank you for your report. With libgcrypt 1.8, it works correctly.
>
> It is tracked by: https://dev.gnupg.org/T5970
>
> The fix I pushed is:
>
> diff --git a/mpi/mpih-const-time.c b/mpi/mpih-const-time.c
> index b527ad79..9d74d190 100644
> --- a/mpi/mpih-const-time.c
> +++ b/mpi/mpih-const-time.c
> @@ -204,6 +204,13 @@ _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize,
> unsigned long v)
> is_all_zero &= (up[i] == 0);
>
> if (is_all_zero)
> - return up[0] - v;
> + {
> + if (up[0] < v)
> + return -1;
> + else if (up[0] > v)
> + return 1;
> + else
> + return 0;
> + }
> return 1;
> }
>
>
>
> The expression of up[0] - v is only correct on 32-bit architecture.
> It may return wrong result on 64-bit architecture.
> --
>

Re: Old bug in gcry_mpi_invm producing wrong result [ In reply to ]

gniibe at fsij

May 10, 2022, 7:24 AM

Post #4 of 4 (368 views)

Permalink

Guido Vranken wrote:
> However I tried again with 1.8.0 and at that version, the reproducer prints
> "Inverse exists".

Ah, yes. You are right. I should have said specifically.

It was libgcrypt 1.8.6, which fixed the old bug for the return value of
gcry_mpi_invm. After that version, it works correctly (either 32-bit or
64-bit) in 1.8 series.

But by the commit of 128045a12139fe2e4be877df59da10c7d4857d9a, which is
included in libgcrypt 1.9.0 and later, it works incorrectly again (on
64-bit machine).

1.10.2 will include the fix.
--

_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@lists.gnupg.org
https://lists.gnupg.org/mailman/listinfo/gcrypt-devel