Mercurial > dropbear
view libtommath/bn_mp_prime_frobenius_underwood.c @ 1788:1fc0012b9c38
Fix handling of replies to global requests (#112)
The current code assumes that all global requests want / need a reply.
This isn't always true and the request itself indicates if it wants a
reply or not.
It causes a specific problem with [email protected] messages.
These are sent by OpenSSH after authentication to inform the client of
potential other host keys for the host. This can be used to add a new
type of host key or to rotate host keys.
The initial information message from the server is sent as a global
request, but with want_reply set to false. This means that the server
doesn't expect an answer to this message. Instead the client needs to
send a prove request as a reply if it wants to receive proof of
ownership for the host keys.
The bug doesn't cause any current problems with due to how OpenSSH
treats receiving the failure message. It instead treats it as a
keepalive message and further ignores it.
Arguably this is a protocol violation though of Dropbear and it is only
accidental that it doesn't cause a problem with OpenSSH.
The bug was found when adding host keys support to libssh, which is more
strict protocol wise and treats the unexpected failure message an error,
also see https://gitlab.com/libssh/libssh-mirror/-/merge_requests/145
for more information.
The fix here is to honor the want_reply flag in the global request and
to only send a reply if the other side expects a reply.
author | Dirkjan Bussink <d.bussink@gmail.com> |
---|---|
date | Thu, 10 Dec 2020 16:13:13 +0100 |
parents | 1051e4eea25a |
children |
line wrap: on
line source
#include "tommath_private.h" #ifdef BN_MP_PRIME_FROBENIUS_UNDERWOOD_C /* LibTomMath, multiple-precision integer library -- Tom St Denis */ /* SPDX-License-Identifier: Unlicense */ /* * See file bn_mp_prime_is_prime.c or the documentation in doc/bn.tex for the details */ #ifndef LTM_USE_ONLY_MR #ifdef MP_8BIT /* * floor of positive solution of * (2^16)-1 = (a+4)*(2*a+5) * TODO: Both values are smaller than N^(1/4), would have to use a bigint * for a instead but any a biger than about 120 are already so rare that * it is possible to ignore them and still get enough pseudoprimes. * But it is still a restriction of the set of available pseudoprimes * which makes this implementation less secure if used stand-alone. */ #define LTM_FROBENIUS_UNDERWOOD_A 177 #else #define LTM_FROBENIUS_UNDERWOOD_A 32764 #endif mp_err mp_prime_frobenius_underwood(const mp_int *N, mp_bool *result) { mp_int T1z, T2z, Np1z, sz, tz; int a, ap2, length, i, j; mp_err err; *result = MP_NO; if ((err = mp_init_multi(&T1z, &T2z, &Np1z, &sz, &tz, NULL)) != MP_OKAY) { return err; } for (a = 0; a < LTM_FROBENIUS_UNDERWOOD_A; a++) { /* TODO: That's ugly! No, really, it is! */ if ((a==2) || (a==4) || (a==7) || (a==8) || (a==10) || (a==14) || (a==18) || (a==23) || (a==26) || (a==28)) { continue; } /* (32764^2 - 4) < 2^31, no bigint for >MP_8BIT needed) */ mp_set_u32(&T1z, (uint32_t)a); if ((err = mp_sqr(&T1z, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_sub_d(&T1z, 4uL, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_kronecker(&T1z, N, &j)) != MP_OKAY) goto LBL_FU_ERR; if (j == -1) { break; } if (j == 0) { /* composite */ goto LBL_FU_ERR; } } /* Tell it a composite and set return value accordingly */ if (a >= LTM_FROBENIUS_UNDERWOOD_A) { err = MP_ITER; goto LBL_FU_ERR; } /* Composite if N and (a+4)*(2*a+5) are not coprime */ mp_set_u32(&T1z, (uint32_t)((a+4)*((2*a)+5))); if ((err = mp_gcd(N, &T1z, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if (!((T1z.used == 1) && (T1z.dp[0] == 1u))) goto LBL_FU_ERR; ap2 = a + 2; if ((err = mp_add_d(N, 1uL, &Np1z)) != MP_OKAY) goto LBL_FU_ERR; mp_set(&sz, 1uL); mp_set(&tz, 2uL); length = mp_count_bits(&Np1z); for (i = length - 2; i >= 0; i--) { /* * temp = (sz*(a*sz+2*tz))%N; * tz = ((tz-sz)*(tz+sz))%N; * sz = temp; */ if ((err = mp_mul_2(&tz, &T2z)) != MP_OKAY) goto LBL_FU_ERR; /* a = 0 at about 50% of the cases (non-square and odd input) */ if (a != 0) { if ((err = mp_mul_d(&sz, (mp_digit)a, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_add(&T1z, &T2z, &T2z)) != MP_OKAY) goto LBL_FU_ERR; } if ((err = mp_mul(&T2z, &sz, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_sub(&tz, &sz, &T2z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_add(&sz, &tz, &sz)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_mul(&sz, &T2z, &tz)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_mod(&tz, N, &tz)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_mod(&T1z, N, &sz)) != MP_OKAY) goto LBL_FU_ERR; if (s_mp_get_bit(&Np1z, (unsigned int)i) == MP_YES) { /* * temp = (a+2) * sz + tz * tz = 2 * tz - sz * sz = temp */ if (a == 0) { if ((err = mp_mul_2(&sz, &T1z)) != MP_OKAY) goto LBL_FU_ERR; } else { if ((err = mp_mul_d(&sz, (mp_digit)ap2, &T1z)) != MP_OKAY) goto LBL_FU_ERR; } if ((err = mp_add(&T1z, &tz, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_mul_2(&tz, &T2z)) != MP_OKAY) goto LBL_FU_ERR; if ((err = mp_sub(&T2z, &sz, &tz)) != MP_OKAY) goto LBL_FU_ERR; mp_exch(&sz, &T1z); } } mp_set_u32(&T1z, (uint32_t)((2 * a) + 5)); if ((err = mp_mod(&T1z, N, &T1z)) != MP_OKAY) goto LBL_FU_ERR; if (MP_IS_ZERO(&sz) && (mp_cmp(&tz, &T1z) == MP_EQ)) { *result = MP_YES; } LBL_FU_ERR: mp_clear_multi(&tz, &sz, &Np1z, &T2z, &T1z, NULL); return err; } #endif #endif