unifdef BN_RECURSION

This removes a bunch of incomplete and scary code, which potentially leaks
secrets and is not constant time. A performance gain is achieved on arm64
for sizes that we care about, while a minimal decrease in performance is
noted for larger sizes on some other platforms.

While we will potentially reimplement Karatsuba (or Toom-Cook) at a later
date, it will be easier and safer to do it from a clean slate.

ok tb@

5 files changed, 5 insertions, 594 deletions

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index bb85ea442c..53b109bd8a 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn.h,v 1.61 2023/04/16 09:13:46 tb Exp $ */
+/* $OpenBSD: bn.h,v 1.62 2023/04/19 10:51:22 jsing Exp $ */
 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -138,12 +138,6 @@
 extern "C" {
 #endif
 
-#ifndef OPENSSL_SMALL_FOOTPRINT
-#define BN_MUL_COMBA
-#define BN_SQR_COMBA
-#define BN_RECURSION
-#endif
-
 /* This next option uses the C libraries (2 word)/(1 word) function.
  * If it is not defined, I use my C version (which is slower).
  * The reason for this flag is that when the particular C compiler
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index f25caa04af..89664fbb97 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_lib.c,v 1.81 2023/04/14 11:04:24 jsing Exp $ */
+/* $OpenBSD: bn_lib.c,v 1.82 2023/04/19 10:51:22 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -735,54 +735,6 @@ BN_set_negative(BIGNUM *bn, int neg)
         bn->neg = ~BN_is_zero(bn) & bn_ct_ne_zero(neg);
 }
 
-int
-bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
-{
-        int i;
-        BN_ULONG aa, bb;
-
-        aa = a[n - 1];
-        bb = b[n - 1];
-        if (aa != bb)
-                return ((aa > bb) ? 1 : -1);
-        for (i = n - 2; i >= 0; i--) {
-                aa = a[i];
-                bb = b[i];
-                if (aa != bb)
-                        return ((aa > bb) ? 1 : -1);
-        }
-        return (0);
-}
-
-/* Here follows a specialised variants of bn_cmp_words().  It has the
-   property of performing the operation on arrays of different sizes.
-   The sizes of those arrays is expressed through cl, which is the
-   common length ( basicall, min(len(a),len(b)) ), and dl, which is the
-   delta between the two lengths, calculated as len(a)-len(b).
-   All lengths are the number of BN_ULONGs...  */
-
-int
-bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
-{
-        int n, i;
-
-        n = cl - 1;
-
-        if (dl < 0) {
-                for (i = dl; i < 0; i++) {
-                        if (b[n - i] != 0)
-                                return -1; /* a < b */
-                }
-        }
-        if (dl > 0) {
-                for (i = dl; i > 0; i--) {
-                        if (a[n + i] != 0)
-                                return 1; /* a > b */
-                }
-        }
-        return bn_cmp_words(a, b, cl);
-}
-
 /*
  * Constant-time conditional swap of a and b.
  * a and b are swapped if condition is not 0.
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 4912ae96f3..5e85dfc3de 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_local.h,v 1.18 2023/03/27 08:37:33 tb Exp $ */
+/* $OpenBSD: bn_local.h,v 1.19 2023/04/19 10:51:22 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -256,14 +256,6 @@ void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp);
 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a);
 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a);
 
-int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n);
-int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
-    int cl, int dl);
-void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
-    int dna, int dnb, BN_ULONG *t);
-void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
-    int n, int tna, int tnb, BN_ULONG *t);
-void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t);
 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
     const BN_ULONG *np, const BN_ULONG *n0, int num);
 
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index fe3f29617f..118e8cddc5 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_mul.c,v 1.36 2023/03/30 14:28:56 tb Exp $ */
+/* $OpenBSD: bn_mul.c,v 1.37 2023/04/19 10:51:22 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -313,323 +313,8 @@ bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
         }
 }
 
-#ifdef BN_RECURSION
-/* Karatsuba recursive multiplication algorithm
- * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
-
-/* r is 2*n2 words in size,
- * a and b are both n2 words in size.
- * n2 must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n2 words in size
- * We calculate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-/* dnX may not be positive, but n2/2+dnX has to be */
-void
-bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna,
-    int dnb, BN_ULONG *t)
-{
-        int n = n2 / 2, c1, c2;
-        int tna = n + dna, tnb = n + dnb;
-        unsigned int neg, zero;
-        BN_ULONG ln, lo, *p;
-
-# ifdef BN_MUL_COMBA
-#  if 0
-        if (n2 == 4) {
-                bn_mul_comba4(r, a, b);
-                return;
-        }
-#  endif
-        /* Only call bn_mul_comba 8 if n2 == 8 and the
-         * two arrays are complete [steve]
-         */
-        if (n2 == 8 && dna == 0 && dnb == 0) {
-                bn_mul_comba8(r, a, b);
-                return;
-        }
-# endif /* BN_MUL_COMBA */
-        /* Else do normal multiply */
-        if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
-                bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
-                if ((dna + dnb) < 0)
-                        memset(&r[2*n2 + dna + dnb], 0,
-                            sizeof(BN_ULONG) * -(dna + dnb));
-                return;
-        }
-        /* r=(a[0]-a[1])*(b[1]-b[0]) */
-        c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
-        c2 = bn_cmp_part_words(&(b[n]), b,tnb, tnb - n);
-        zero = neg = 0;
-        switch (c1 * 3 + c2) {
-        case -4:
-                bn_sub(t, n, &a[n], tna, a, n); /* - */
-                bn_sub(&t[n], n, b, n, &b[n], tnb);     /* - */
-                break;
-        case -3:
-                zero = 1;
-                break;
-        case -2:
-                bn_sub(t, n, &a[n], tna, a, n); /* - */
-                bn_sub(&t[n], n, &b[n], tnb, b, n);     /* + */
-                neg = 1;
-                break;
-        case -1:
-        case 0:
-        case 1:
-                zero = 1;
-                break;
-        case 2:
-                bn_sub(t, n, a, n, &a[n], tna); /* + */
-                bn_sub(&t[n], n, b, n, &b[n], tnb);     /* - */
-                neg = 1;
-                break;
-        case 3:
-                zero = 1;
-                break;
-        case 4:
-                bn_sub(t, n, a, n, &a[n], tna);
-                bn_sub(&t[n], n, &b[n], tnb, b, n);
-                break;
-        }
-
-# ifdef BN_MUL_COMBA
-        if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take
-                                               extra args to do this well */
-        {
-                if (!zero)
-                        bn_mul_comba4(&(t[n2]), t, &(t[n]));
-                else
-                        memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG));
-
-                bn_mul_comba4(r, a, b);
-                bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
-        } else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could
-                                                    take extra args to do this
-                                                    well */
-        {
-                if (!zero)
-                        bn_mul_comba8(&(t[n2]), t, &(t[n]));
-                else
-                        memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG));
-
-                bn_mul_comba8(r, a, b);
-                bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
-        } else
-# endif /* BN_MUL_COMBA */
-        {
-                p = &(t[n2 * 2]);
-                if (!zero)
-                        bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
-                else
-                        memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
-                bn_mul_recursive(r, a, b, n, 0, 0, p);
-                bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
-        }
-
-        /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
-         * r[10] holds (a[0]*b[0])
-         * r[32] holds (b[1]*b[1])
-         */
-
-        c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
-
-        if (neg) /* if t[32] is negative */
-        {
-                c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
-        } else {
-                /* Might have a carry */
-                c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
-        }
-
-        /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
-         * r[10] holds (a[0]*b[0])
-         * r[32] holds (b[1]*b[1])
-         * c1 holds the carry bits
-         */
-        c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
-        if (c1) {
-                p = &(r[n + n2]);
-                lo= *p;
-                ln = (lo + c1) & BN_MASK2;
-                *p = ln;
-
-                /* The overflow will stop before we over write
-                 * words we should not overwrite */
-                if (ln < (BN_ULONG)c1) {
-                        do {
-                                p++;
-                                lo= *p;
-                                ln = (lo + 1) & BN_MASK2;
-                                *p = ln;
-                        } while (ln == 0);
-                }
-        }
-}
-
-/* n+tn is the word length
- * t needs to be n*4 is size, as does r */
-/* tnX may not be negative but less than n */
-void
-bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna,
-    int tnb, BN_ULONG *t)
-{
-        int i, j, n2 = n * 2;
-        int c1, c2, neg;
-        BN_ULONG ln, lo, *p;
-
-        if (n < 8) {
-                bn_mul_normal(r, a, n + tna, b, n + tnb);
-                return;
-        }
-
-        /* r=(a[0]-a[1])*(b[1]-b[0]) */
-        c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
-        c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
-        neg = 0;
-        switch (c1 * 3 + c2) {
-        case -4:
-                bn_sub(t, n, &a[n], tna, a, n);         /* - */
-                bn_sub(&t[n], n, b, n, &b[n], tnb);     /* - */
-                break;
-        case -3:
-                /* break; */
-        case -2:
-                bn_sub(t, n, &a[n], tna, a, n);         /* - */
-                bn_sub(&t[n], n, &b[n], tnb, b, n);     /* + */
-                neg = 1;
-                break;
-        case -1:
-        case 0:
-        case 1:
-                /* break; */
-        case 2:
-                bn_sub(t, n, a, n, &a[n], tna);         /* + */
-                bn_sub(&t[n], n, b, n, &b[n], tnb);     /* - */
-                neg = 1;
-                break;
-        case 3:
-                /* break; */
-        case 4:
-                bn_sub(t, n, a, n, &a[n], tna);
-                bn_sub(&t[n], n, &b[n], tnb, b, n);
-                break;
-        }
-                /* The zero case isn't yet implemented here. The speedup
-                   would probably be negligible. */
-# if 0
-        if (n == 4) {
-                bn_mul_comba4(&(t[n2]), t, &(t[n]));
-                bn_mul_comba4(r, a, b);
-                bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
-                memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2));
-        } else
-# endif
-                if (n == 8) {
-                bn_mul_comba8(&(t[n2]), t, &(t[n]));
-                bn_mul_comba8(r, a, b);
-                bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
-                memset(&(r[n2 + tna + tnb]), 0,
-                    sizeof(BN_ULONG) * (n2 - tna - tnb));
-        } else {
-                p = &(t[n2*2]);
-                bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
-                bn_mul_recursive(r, a, b, n, 0, 0, p);
-                i = n / 2;
-                /* If there is only a bottom half to the number,
-                 * just do it */
-                if (tna > tnb)
-                        j = tna - i;
-                else
-                        j = tnb - i;
-                if (j == 0) {
-                        bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
-                            i, tna - i, tnb - i, p);
-                        memset(&(r[n2 + i * 2]), 0,
-                            sizeof(BN_ULONG) * (n2 - i * 2));
-                }
-                else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
-                {
-                        bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
-                            i, tna - i, tnb - i, p);
-                        memset(&(r[n2 + tna + tnb]), 0,
-                            sizeof(BN_ULONG) * (n2 - tna - tnb));
-                }
-                else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
-                {
-                        memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2);
-                        if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL &&
-                            tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
-                                bn_mul_normal(&(r[n2]), &(a[n]), tna,
-                                    &(b[n]), tnb);
-                        } else {
-                                for (;;) {
-                                        i /= 2;
-                                        /* these simplified conditions work
-                                         * exclusively because difference
-                                         * between tna and tnb is 1 or 0 */
-                                        if (i < tna || i < tnb) {
-                                                bn_mul_part_recursive(&(r[n2]),
-                                                    &(a[n]), &(b[n]), i,
-                                                    tna - i, tnb - i, p);
-                                                break;
-                                        } else if (i == tna || i == tnb) {
-                                                bn_mul_recursive(&(r[n2]),
-                                                    &(a[n]), &(b[n]), i,
-                                                    tna - i, tnb - i, p);
-                                                break;
-                                        }
-                                }
-                        }
-                }
-        }
-
-        /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
-         * r[10] holds (a[0]*b[0])
-         * r[32] holds (b[1]*b[1])
-         */
-
-        c1 = (int)(bn_add_words(t, r,&(r[n2]), n2));
-
-        if (neg) /* if t[32] is negative */
-        {
-                c1 -= (int)(bn_sub_words(&(t[n2]), t,&(t[n2]), n2));
-        } else {
-                /* Might have a carry */
-                c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
-        }
-
-        /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
-         * r[10] holds (a[0]*b[0])
-         * r[32] holds (b[1]*b[1])
-         * c1 holds the carry bits
-         */
-        c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
-        if (c1) {
-                p = &(r[n + n2]);
-                lo= *p;
-                ln = (lo + c1)&BN_MASK2;
-                *p = ln;
-
-                /* The overflow will stop before we over write
-                 * words we should not overwrite */
-                if (ln < (BN_ULONG)c1) {
-                        do {
-                                p++;
-                                lo= *p;
-                                ln = (lo + 1) & BN_MASK2;
-                                *p = ln;
-                        } while (ln == 0);
-                }
-        }
-}
-#endif /* BN_RECURSION */
 
 #ifndef HAVE_BN_MUL
-#ifndef BN_RECURSION
 int
 bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
 {
@@ -638,112 +323,6 @@ bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
         return 1;
 }
 
-#else /* BN_RECURSION */
-int
-bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
-{
-        BIGNUM *t = NULL;
-        int al, bl, i, k;
-        int j = 0;
-        int ret = 0;
-
-        BN_CTX_start(ctx);
-
-        al = a->top;
-        bl = b->top;
-
-        i = al - bl;
-
-        if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
-                if (i >= -1 && i <= 1) {
-                        /* Find out the power of two lower or equal
-                           to the longest of the two numbers */
-                        if (i >= 0) {
-                                j = BN_num_bits_word((BN_ULONG)al);
-                        }
-                        if (i == -1) {
-                                j = BN_num_bits_word((BN_ULONG)bl);
-                        }
-                        j = 1 << (j - 1);
-                        assert(j <= al || j <= bl);
-                        k = j + j;
-                        if ((t = BN_CTX_get(ctx)) == NULL)
-                                goto err;
-                        if (al > j || bl > j) {
-                                if (!bn_wexpand(t, k * 4))
-                                        goto err;
-                                if (!bn_wexpand(r, k * 4))
-                                        goto err;
-                                bn_mul_part_recursive(r->d, a->d, b->d,
-                                    j, al - j, bl - j, t->d);
-                        }
-                        else    /* al <= j || bl <= j */
-                        {
-                                if (!bn_wexpand(t, k * 2))
-                                        goto err;
-                                if (!bn_wexpand(r, k * 2))
-                                        goto err;
-                                bn_mul_recursive(r->d, a->d, b->d,
-                                    j, al - j, bl - j, t->d);
-                        }
-                        r->top = rn;
-                        goto end;
-                }
-#if 0
-                if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
-                        BIGNUM *tmp_bn = (BIGNUM *)b;
-                        if (!bn_wexpand(tmp_bn, al))
-                                goto err;
-                        tmp_bn->d[bl] = 0;
-                        bl++;
-                        i--;
-                } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
-                        BIGNUM *tmp_bn = (BIGNUM *)a;
-                        if (!bn_wexpand(tmp_bn, bl))
-                                goto err;
-                        tmp_bn->d[al] = 0;
-                        al++;
-                        i++;
-                }
-                if (i == 0) {
-                        /* symmetric and > 4 */
-                        /* 16 or larger */
-                        j = BN_num_bits_word((BN_ULONG)al);
-                        j = 1 << (j - 1);
-                        k = j + j;
-                        if ((t = BN_CTX_get(ctx)) == NULL)
-                                goto err;
-                        if (al == j) /* exact multiple */
-                        {
-                                if (!bn_wexpand(t, k * 2))
-                                        goto err;
-                                if (!bn_wexpand(r, k * 2))
-                                        goto err;
-                                bn_mul_recursive(r->d, a->d, b->d, al, t->d);
-                        } else {
-                                if (!bn_wexpand(t, k * 4))
-                                        goto err;
-                                if (!bn_wexpand(r, k * 4))
-                                        goto err;
-                                bn_mul_part_recursive(r->d, a->d, b->d,
-                                    al - j, j, t->d);
-                        }
-                        r->top = top;
-                        goto end;
-                }
-#endif
-        }
-
-        bn_mul_normal(r->d, a->d, al, b->d, bl);
-
- end:
-        ret = 1;
- err:
-        BN_CTX_end(ctx);
-
-        return ret;
-}
-#endif /* BN_RECURSION */
 #endif /* HAVE_BN_MUL */
 
 int
diff --git a/src/lib/libcrypto/bn/bn_sqr.c b/src/lib/libcrypto/bn/bn_sqr.c
index d5da775200..d414800feb 100644
--- a/src/lib/libcrypto/bn/bn_sqr.c
+++ b/src/lib/libcrypto/bn/bn_sqr.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_sqr.c,v 1.29 2023/03/30 14:28:56 tb Exp $ */
+/* $OpenBSD: bn_sqr.c,v 1.30 2023/04/19 10:51:22 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -228,90 +228,6 @@ bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp)
         bn_add_words(r, r, tmp, max);
 }
 
-#ifdef BN_RECURSION
-/* r is 2*n words in size,
- * a and b are both n words in size.    (There's not actually a 'b' here ...)
- * n must be a power of 2.
- * We multiply and return the result.
- * t must be 2*n words in size
- * We calculate
- * a[0]*b[0]
- * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
- * a[1]*b[1]
- */
-void
-bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
-{
-        int n = n2 / 2;
-        int zero, c1;
-        BN_ULONG ln, lo, *p;
-
-        if (n2 == 4) {
-                bn_sqr_comba4(r, a);
-                return;
-        } else if (n2 == 8) {
-                bn_sqr_comba8(r, a);
-                return;
-        }
-        if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) {
-                bn_sqr_normal(r, a, n2, t);
-                return;
-        }
-        /* r=(a[0]-a[1])*(a[1]-a[0]) */
-        c1 = bn_cmp_words(a, &(a[n]), n);
-        zero = 0;
-        if (c1 > 0)
-                bn_sub_words(t, a, &(a[n]), n);
-        else if (c1 < 0)
-                bn_sub_words(t, &(a[n]), a, n);
-        else
-                zero = 1;
-
-        /* The result will always be negative unless it is zero */
-        p = &(t[n2*2]);
-
-        if (!zero)
-                bn_sqr_recursive(&(t[n2]), t, n, p);
-        else
-                memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
-        bn_sqr_recursive(r, a, n, p);
-        bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
-
-        /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
-         * r[10] holds (a[0]*b[0])
-         * r[32] holds (b[1]*b[1])
-         */
-
-        c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
-
-        /* t[32] is negative */
-        c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
-
-        /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
-         * r[10] holds (a[0]*a[0])
-         * r[32] holds (a[1]*a[1])
-         * c1 holds the carry bits
-         */
-        c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
-        if (c1) {
-                p = &(r[n + n2]);
-                lo= *p;
-                ln = (lo + c1) & BN_MASK2;
-                *p = ln;
-
-                /* The overflow will stop before we over write
-                 * words we should not overwrite */
-                if (ln < (BN_ULONG)c1) {
-                        do {
-                                p++;
-                                lo= *p;
-                                ln = (lo + 1) & BN_MASK2;
-                                *p = ln;
-                        } while (ln == 0);
-                }
-        }
-}
-#endif
 
 /*
  * bn_sqr() computes a * a, storing the result in r. The caller must ensure that
@@ -330,31 +246,9 @@ bn_sqr(BIGNUM *r, const BIGNUM *a, int rn, BN_CTX *ctx)
         if ((tmp = BN_CTX_get(ctx)) == NULL)
                 goto err;
 
-#if defined(BN_RECURSION)
-        if (a->top < BN_SQR_RECURSIVE_SIZE_NORMAL) {
-                BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
-                bn_sqr_normal(r->d, a->d, a->top, t);
-        } else {
-                int j, k;
-
-                j = BN_num_bits_word((BN_ULONG)a->top);
-                j = 1 << (j - 1);
-                k = j + j;
-                if (a->top == j) {
-                        if (!bn_wexpand(tmp, k * 2))
-                                goto err;
-                        bn_sqr_recursive(r->d, a->d, a->top, tmp->d);
-                } else {
-                        if (!bn_wexpand(tmp, rn))
-                                goto err;
-                        bn_sqr_normal(r->d, a->d, a->top, tmp->d);
-                }
-        }
-#else
         if (!bn_wexpand(tmp, rn))
                 goto err;
         bn_sqr_normal(r->d, a->d, a->top, tmp->d);
-#endif
 
         ret = 1;