Re: [PATCH 2/4] crypto: Add RSA support

[Jan Beulich <jbeulich@xxxxxxxx>]

On 06.05.2025 16:32, Ross Lagerwall wrote:
> In preparation for adding support for livepatch signing, add support for
> RSA crypto.

If this is needed just for live-patch, ...

> --- a/xen/common/Makefile
> +++ b/xen/common/Makefile
> @@ -28,6 +28,7 @@ obj-$(CONFIG_LIVEPATCH) += livepatch.o livepatch_elf.o
>  obj-$(CONFIG_LLC_COLORING) += llc-coloring.o
>  obj-$(CONFIG_VM_EVENT) += mem_access.o
>  obj-y += memory.o
> +obj-y += mpi.o

... why would this be obj-y? Same for rsa.o further down.

> --- /dev/null
> +++ b/xen/common/mpi.c
> @@ -0,0 +1,1724 @@
> +/* mpi-pow.c  -  MPI functions

Nit: This doesn't match the filename.

> + *   Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
> + *
> + * This file is part of GnuPG.
> + *
> + * GnuPG is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * GnuPG is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
> + *
> + * Note: This code is heavily based on the GNU MP Library.
> + *    Actually it's the same code with only minor changes in the
> + *    way the data is stored; this is to support the abstraction
> + *    of an optional secure memory allocation which may be used
> + *    to avoid revealing of sensitive data due to paging etc.
> + *    The GNU MP Library itself is published under the LGPL;
> + *    however I decided to publish this code under the plain GPL.
> + *
> + * mpi.c code extracted from linux @ eef0df6a5953, lib/mpi

I fear this line would go unnoticed with future changes, and hence go stale
rather easily. Menioning the origin in just the commit message ought to be
sufficient.

Btw - how heavily did you need to adjust the code to pass our Eclair scan?
Depending on that I then might raise the question of converting to proper
Xen style (it currently isn't even proper Linux style, afaict).

> + */
> +
> +#include <xen/mpi.h>
> +#include <xen/lib.h>
> +#include <xen/err.h>
> +#include <xen/xmalloc.h>
> +#include <xen/string.h>
> +#include <xen/bitops.h>
> +#include <xen/bug.h>

Please sort alphabetically. Same for the other new files.

> +#define MAX_EXTERN_MPI_BITS 16384
> +
> +/* Define it to a value which is good on most machines.
> + * tested 4, 16, 32 and 64, where 16 gave the best performance when
> + * checking a 768 and a 1024 bit ElGamal signature.
> + * (wk 22.12.97) */
> +#define KARATSUBA_THRESHOLD 16
> +
> +typedef mpi_limb_t *mpi_ptr_t;       /* pointer to a limb */
> +typedef int mpi_size_t;              /* (must be a signed type) */
> +
> +/* Copy N limbs from S to D.  */
> +#define MPN_COPY(d, s, n) \
> +     do {                                    \
> +             mpi_size_t _i;                  \

With this and ...

> +             for (_i = 0; _i < (n); _i++)    \
> +                     (d)[_i] = (s)[_i];      \
> +     } while (0)
> +
> +#define MPN_COPY_DECR(d, s, n) \
> +     do {                                    \
> +             mpi_size_t _i;                  \

... this I wonder why ...

> +             for (_i = (n)-1; _i >= 0; _i--) \
> +                     (d)[_i] = (s)[_i];      \
> +     } while (0)
> +
> +/* Zero N limbs at D */
> +#define MPN_ZERO(d, n) \
> +     do {                                    \
> +             int  _i;                        \

... this is plain int. There are apparently many similar issue.

>[...]
> +leave:

Here and elsewhere - labels indented by at least one blank, please.

> --- /dev/null
> +++ b/xen/crypto/rsa.c
> @@ -0,0 +1,194 @@
> +/* rsa.c
> +
> +   The RSA publickey algorithm.
> +
> +   Copyright (C) 2001 Niels Möller
> +
> +   This file is part of GNU Nettle.
> +
> +   GNU Nettle is free software: you can redistribute it and/or
> +   modify it under the terms of either:
> +
> +     * the GNU Lesser General Public License as published by the Free
> +       Software Foundation; either version 3 of the License, or (at your
> +       option) any later version.
> +
> +   or
> +
> +     * the GNU General Public License as published by the Free
> +       Software Foundation; either version 2 of the License, or (at your
> +       option) any later version.
> +
> +   or both in parallel, as here.
> +
> +   GNU Nettle is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   General Public License for more details.
> +
> +   You should have received copies of the GNU General Public License and
> +   the GNU Lesser General Public License along with this program.  If
> +   not, see http://www.gnu.org/licenses/.
> +*/
> +
> +#include <xen/rsa.h>
> +#include <xen/lib.h>
> +#include <xen/err.h>
> +#include <xen/bug.h>
> +#include <xen/string.h>
> +
> +void rsa_public_key_init(struct rsa_public_key *key)
> +{
> +    key->n = NULL;
> +    key->e = NULL;
> +    key->size = 0;
> +}
> +
> +/*
> + * Computes the size, in octets, of the modulo. Returns 0 if the
> + * modulo is too small to be useful, or otherwise appears invalid.
> + */
> +static size_t rsa_check_size(MPI n)
> +{
> +    /* Round upwards */
> +    size_t size;
> +
> +    /* Even moduli are invalid */
> +    if ( mpi_test_bit(n, 0) == 0 )
> +        return 0;
> +
> +    size = (mpi_get_nbits(n) + 7) / 8;
> +
> +    if ( size < RSA_MINIMUM_N_OCTETS )
> +        return 0;
> +
> +    return size;
> +}
> +
> +int rsa_public_key_prepare(struct rsa_public_key *key)
> +{
> +    if ( !key->n || !key->e || key->size )
> +        return -EINVAL;
> +
> +    key->size = rsa_check_size(key->n);
> +
> +    return key->size > 0 ? 0 : -EINVAL;
> +}
> +
> +/*
> + * Formats the PKCS#1 padding, of the form
> + *
> + *   0x00 0x01 0xff ... 0xff 0x00 id ...digest...
> + *
> + * where the 0xff ... 0xff part consists of at least 8 octets. The
> + * total size equals the octet size of n.
> + */
> +static uint8_t *pkcs1_signature_prefix(unsigned int key_size, uint8_t 
> *buffer,
> +                                       unsigned int id_size, const uint8_t 
> *id,
> +                                       unsigned int digest_size)
> +{
> +    unsigned int j;
> +
> +    if ( key_size < 11 + id_size + digest_size )
> +        return NULL;
> +
> +    j = key_size - digest_size - id_size;
> +
> +    memcpy(buffer + j, id, id_size);
> +    buffer[0] = 0;
> +    buffer[1] = 1;
> +    buffer[j - 1] = 0;
> +
> +    ASSERT(j >= 11);
> +    memset(buffer + 2, 0xff, j - 3);
> +
> +    return buffer + j + id_size;
> +}
> +
> +/*
> + * From RFC 3447, Public-Key Cryptography Standards (PKCS) #1: RSA
> + * Cryptography Specifications Version 2.1.
> + *
> + *     id-sha256    OBJECT IDENTIFIER ::=
> + *       {joint-iso-itu-t(2) country(16) us(840) organization(1)
> + *         gov(101) csor(3) nistalgorithm(4) hashalgs(2) 1}
> + */
> +static const uint8_t
> +sha256_prefix[] =
> +{
> +  /* 19 octets prefix, 32 octets hash, total 51 */
> +  0x30,      49, /* SEQUENCE */
> +    0x30,    13, /* SEQUENCE */
> +      0x06,   9, /* OBJECT IDENTIFIER */
> +        0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01,
> +      0x05,   0, /* NULL */
> +    0x04,    32  /* OCTET STRING */
> +      /* Here comes the raw hash value */
> +};
> +
> +static int pkcs1_rsa_sha256_encode(MPI *m, size_t key_size,
> +                                   struct sha2_256_state *hash)
> +{
> +    uint8_t *ptr;
> +    uint8_t *buf;
> +
> +    buf = xmalloc_bytes(key_size);
> +    if ( !buf )
> +        return -ENOMEM;
> +
> +    ptr = pkcs1_signature_prefix(key_size, buf,
> +                                 sizeof(sha256_prefix), sha256_prefix,
> +                                 SHA2_256_DIGEST_SIZE);
> +    if ( !ptr )
> +    {
> +        xfree(buf);
> +        return -EINVAL;
> +    }
> +
> +    sha2_256_final(hash, ptr);
> +    *m = mpi_read_raw_data(buf, key_size);
> +    xfree(buf);
> +    return 0;
> +}
> +
> +static int rsa_verify(const struct rsa_public_key *key, MPI m, MPI s)
> +{
> +    int ret;
> +    MPI m1;
> +
> +    /* (1) Validate 0 <= s < n */
> +    if ( mpi_cmp_ui(s, 0) < 0 || mpi_cmp(s, key->n) >= 0 )
> +        return -EINVAL;
> +
> +    m1 = mpi_alloc(key->size / BYTES_PER_MPI_LIMB);
> +    if ( !m1 )
> +        return -ENOMEM;
> +
> +    /* (2) m = s^e mod n */
> +    ret = mpi_powm(m1, s, key->e, key->n);
> +    if ( ret )
> +        goto out;
> +
> +    ret = mpi_cmp (m, m1) ? -EINVAL : 0;

You look to have striven to convert this file to Xen style; there's a stray
blank here, though.

> --- /dev/null
> +++ b/xen/include/xen/mpi.h
> @@ -0,0 +1,63 @@
> +/* mpi.h  -  Multi Precision Integers
> + *        Copyright (C) 1994, 1996, 1998, 1999,
> + *                    2000, 2001 Free Software Foundation, Inc.
> + *
> + * This file is part of GNUPG.
> + *
> + * GNUPG is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.

While this may want to remain, accompany it with an SPDX header? (Same
elsewhere perhaps.)

> + * GNUPG is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
> + *
> + * Note: This code is heavily based on the GNU MP Library.
> + *         Actually it's the same code with only minor changes in the
> + *         way the data is stored; this is to support the abstraction
> + *         of an optional secure memory allocation which may be used
> + *         to avoid revealing of sensitive data due to paging etc.
> + *         The GNU MP Library itself is published under the LGPL;
> + *         however I decided to publish this code under the plain GPL.
> + */
> +
> +#ifndef MPI_H
> +#define MPI_H

This imo wants at least a XEN_ prefix. Same in rsa.h.

> +#include <xen/types.h>
> +
> +#define BYTES_PER_MPI_LIMB      (BITS_PER_LONG / 8)
> +#define BITS_PER_MPI_LIMB       BITS_PER_LONG
> +
> +typedef unsigned long int mpi_limb_t;
> +typedef signed long int mpi_limb_signed_t;
> +
> +struct mpi {
> +    int alloced;        /* array size (# of allocated limbs) */
> +    int nlimbs;         /* number of valid limbs */
> +    int nbits;          /* the real number of valid bits (info only) */

I understand the goal likely is to not meaningfully change the original, but
none of these look like they can hold negative values, and ...

> +    int sign;           /* indicates a negative number */

... this one looks like it's a boolean.

> +    unsigned flags;     /* bit 0: array must be allocated in secure memory 
> space */

In Xen we use "unsigned int", not plain "unsigned".

> +    /* bit 1: not used */
> +    /* bit 2: the limb is a pointer to some m_alloced data */

I think these comments would better be padded to align with the earlier one.
The individual bits likely also want corresponding #define-s.

> --- /dev/null
> +++ b/xen/include/xen/rsa.h
> @@ -0,0 +1,72 @@
> +/* rsa.h
> +
> +   The RSA publickey algorithm.
> +
> +   Copyright (C) 2001, 2002 Niels Möller
> +
> +   This file is part of GNU Nettle.
> +
> +   GNU Nettle is free software: you can redistribute it and/or
> +   modify it under the terms of either:
> +
> +     * the GNU Lesser General Public License as published by the Free
> +       Software Foundation; either version 3 of the License, or (at your
> +       option) any later version.
> +
> +   or
> +
> +     * the GNU General Public License as published by the Free
> +       Software Foundation; either version 2 of the License, or (at your
> +       option) any later version.
> +
> +   or both in parallel, as here.
> +
> +   GNU Nettle is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   General Public License for more details.
> +
> +   You should have received copies of the GNU General Public License and
> +   the GNU Lesser General Public License along with this program.  If
> +   not, see http://www.gnu.org/licenses/.
> +*/
> + 
> +#ifndef RSA_H
> +#define RSA_H
> +
> +#include <xen/mpi.h>
> +#include <xen/sha2.h>

This isn't needed here, is it? All you need is ...

> +#include <xen/types.h>
> +
> +/*
> + * This limit is somewhat arbitrary. Technically, the smallest modulo
> + * which makes sense at all is 15 = 3*5, phi(15) = 8, size 4 bits. But
> + * for ridiculously small keys, not all odd e are possible (e.g., for
> + * 5 bits, the only possible modulo is 3*7 = 21, phi(21) = 12, and e =
> + * 3 don't work). The smallest size that makes sense with pkcs#1, and
> + * which allows RSA encryption of one byte messages, is 12 octets, 89
> + * bits.
> + */
> +#define RSA_MINIMUM_N_OCTETS 12
> +#define RSA_MINIMUM_N_BITS (8 * RSA_MINIMUM_N_OCTETS - 7)
> +
> +struct rsa_public_key
> +{
> +    /*
> +     * Size of the modulo, in octets. This is also the size of all
> +     * signatures that are created or verified with this key.
> +     */
> +    size_t size;
> +    MPI n; /* Modulo */
> +    MPI e; /* Public exponent */
> +};
> +
> +void rsa_public_key_init(struct rsa_public_key *key);
> +
> +int rsa_public_key_prepare(struct rsa_public_key *key);
> +
> +int rsa_sha256_verify(const struct rsa_public_key *key,
> +                      struct sha2_256_state *hash,

... a forward decl of this type.

Jan