From nobody Thu Dec 18 05:05:05 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1746807555; cv=none; d=zohomail.com; s=zohoarc; b=F4Z1Zm2Lx70r8qVANHqOyDGY6MiiuleA2BQcFIiV8Ahx0DjP+9tKuR8h7Tdi0g8chvZ8AGsyCX/xIEfNd6fnf8CZDUTSt2lK4KoAwWSGN9vxPpAytvDw2Our2PJQJM4pzscQk7FbzCxyECsX0hpyJvBfOsegBWVFbt9UYNRV7fs= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1746807555; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=CQp/dECIkzIFiolzpT72X9wuTH17rT3cBg1gE2cfj5s=; b=hmUNlr4LZtFiHDJ1lZt7GXoF47+74RjbDeBhjMKr0HEVrJo0FdyRp6zu5NJorjcp6In9WYyLqUZ6Rk3d6+s92OxwMhnYgJTu6nvKwf8HclTsyCAXe0kKEgXPZROFEa4YuRe34KVDn8SvgdYgtlje1xa7Cv3/lURrBvzwSWbLBmk= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 17468075556271001.4347472643474; Fri, 9 May 2025 09:19:15 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.980225.1366691 (Exim 4.92) (envelope-from ) id 1uDQR7-0006Gq-5H; Fri, 09 May 2025 16:18:57 +0000 Received: by outflank-mailman (output) from mailman id 980225.1366691; Fri, 09 May 2025 16:18:57 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uDQR7-0006Gj-2M; Fri, 09 May 2025 16:18:57 +0000 Received: by outflank-mailman (input) for mailman id 980225; Fri, 09 May 2025 16:18:56 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uDQR6-0006Gd-66 for xen-devel@lists.xenproject.org; Fri, 09 May 2025 16:18:56 +0000 Received: from mail-ej1-x62e.google.com (mail-ej1-x62e.google.com [2a00:1450:4864:20::62e]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 4dafddab-2cf1-11f0-9eb4-5ba50f476ded; Fri, 09 May 2025 18:18:55 +0200 (CEST) Received: by mail-ej1-x62e.google.com with SMTP id a640c23a62f3a-ac3b12e8518so461367766b.0 for ; Fri, 09 May 2025 09:18:55 -0700 (PDT) Received: from rossla-pc.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad2197463edsm171155266b.105.2025.05.09.09.18.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 09 May 2025 09:18:53 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 4dafddab-2cf1-11f0-9eb4-5ba50f476ded DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1746807534; x=1747412334; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=CQp/dECIkzIFiolzpT72X9wuTH17rT3cBg1gE2cfj5s=; b=WOP3JfvUpJDube1XTndd2ZVol1A8ZpFpErYBN6i2lCJthl4Vlfqg7LXg+KWCwyQj2w a5m3Q3TRVl9HRIgfTPf6DjpKTbThfgCbMe9lXbhJtg4DOM4IpOC1SfchYydzV5wXZGlH jOYmfI9OP9wFnHpK7Y1HKXJolgEk1nvE6riZs= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746807534; x=1747412334; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CQp/dECIkzIFiolzpT72X9wuTH17rT3cBg1gE2cfj5s=; b=S4DNPTxzSRbpDHrvTAvRzwyan7h2s8izQTjER/eZtd2gyMfgT4qD0bkRJrkgQS0axW cu0SEbPwf1UTM0VX97/y5D64x+2/f7OvH2zV2vRJm+R7gVsc6hNRLIvF0YY1HJs+yIX0 u+M7w/qgsv7KZYb3ZGbpQRMOA2qhs0s1bViDgkOR3GX5czM0wndUi23Dgv7Xz97q8eft YWnG+4AJdIw4GOEcuzxATwoLrAcUDjMRmsD9qps1fm2t73WrwqNyBuHHsE7YCRkQxG+d kYBfnYBfBRXoPEantXH99KK9wZiPDQlKHiopDN1K+eaejO4/X3ocnppuZ9VUqQqNhXse xUJg== X-Gm-Message-State: AOJu0YzeAAhIHghL5L+a82EIaxn2iWgLkKFgo9pUJrPGYG+jCxhpMmRF msWywJgjrNuP0jmUeqoXpo+itTesPBpPnnpvlVZczmBbHDaqaO+Sc8HcOA8N7l5scAbC10mSPOw = X-Gm-Gg: ASbGncubtcFberrXoQd2EiJQzGpgjhVSkJ8D4ISlq3tdSfFGriMazOOJFkqvWMaQcsi jRSDHIX5RcOI6nOH6rXuEZm61yUvTX0g36ri6XYLUUUxQahxJwKyc4aEK0nFM0PcuNMq99nxndD G3dB3zz5XUeSy/gd29yV61TDPCJm+MgLbHV3b7NRa3WWv3nBqN6Hu59/41QSyYIOYRTfFWjkvZq PzCs6vI6vLW04H030WZGlGv6k33Gl9cpgMszwrjEuGoSuL3DdDhaxVlFgvRmMBf0/V9sLBWzxcp gv3FFXRQztFmkkLeh+1bkCkY9xMkfO3QsJcDhWuUru+AfgOfDZMiDMtWvD0D2nDGz18tRUC0Qds = X-Google-Smtp-Source: AGHT+IFeFh0zbvzD87+1cpjr/b8zShG/gnOAdP5Syn5KzgmAtHV2xFsIb3qXc7NRFrsESHnTs2oHEw== X-Received: by 2002:a17:906:6b91:b0:ad2:1f65:8562 with SMTP id a640c23a62f3a-ad21f658724mr219650466b.14.1746807534186; Fri, 09 May 2025 09:18:54 -0700 (PDT) From: Ross Lagerwall To: xen-devel@lists.xenproject.org Cc: Ross Lagerwall , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= Subject: [PATCH 1/4] docs: Introduce live patch signing Date: Fri, 9 May 2025 17:18:46 +0100 Message-ID: <20250509161846.45851-1-ross.lagerwall@citrix.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250506143218.1782603-1-ross.lagerwall@citrix.com> References: <20250506143218.1782603-1-ross.lagerwall@citrix.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1746807556686019000 Content-Type: text/plain; charset="utf-8" Remove a never-implemented description of live patch signing from the TODO section and document signing as implemented by the following patches. Signed-off-by: Ross Lagerwall --- docs/misc/livepatch.pandoc | 104 ++++++++++++++++++------------------- 1 file changed, 52 insertions(+), 52 deletions(-) diff --git a/docs/misc/livepatch.pandoc b/docs/misc/livepatch.pandoc index 04dd5ed7b271..66141586b605 100644 --- a/docs/misc/livepatch.pandoc +++ b/docs/misc/livepatch.pandoc @@ -917,6 +917,58 @@ The normal sequence of events is to: 3. *XEN_SYSCTL_LIVEPATCH_ACTION* with *LIVEPATCH_ACTION_APPLY* to apply t= he patch. 4. *XEN_SYSCTL_LIVEPATCH_GET* to check the `->rc`. If in *-XEN_EAGAIN* sp= in. If zero exit with success. =20 +## Signature Checking + +While loading live patches would generally be restricted to a privileged +process in dom0, in certain cases signature checking in Xen may be require= d. +For example, when Secure Boot is enabled live patches need to be verified +before being loaded. + +Xen live patches are ELF binaries but there is no standardized mechanism f= or +signing ELF binaries. One approach used by Linux is to append a signature = to +the end of the binary, outside of the ELF container. While this works, it = tends +to be fragile since tools that handle ELF binaries do not correctly handle= the +signature. Instead, the approach taken here is to use an ELF note for the +signature. + +The ELF note section name shall be `.note.Xen.signature` with note name `X= en` +and type `0`. + +The note data shall contain a header followed by the signature data: + + #define SIGNATURE_SUPPORTED_VERION 1 + #define SIGNATURE_ALGORITHM_RSA 0 + #define SIGNATURE_HASH_SHA256 0 + struct payload_signature { + uint16_t version; + uint8_t algo; /* Public-key crypto algorithm */ + uint8_t hash; /* Digest algorithm */ + uint32_t sig_len; /* Length of signature data */ + }; + +To sign a live patch: + +1) Add a new note section with a populated payload signature and zeroed out + signature. +2) Generate a detached signature over the entire binary. +3) Fill in the signature in the note section. + +During live patch load, Xen shall verify the signature using the following +steps: + +1) Copy the signature out of the note section. +2) Zero the signature. +3) Generate a detached signature over the entire binary. +4) Compare against the signature from (1). + +Initially, to avoid including DER / X.509 parsing of certificates, handling +chains, etc. Xen shall verify signatures against a compiled in RSA key in +exponent/modulus form. However, it may be extended in future to support ot= her +types of signatures and key types. + +Support of signatures in Xen and in live patches is optional. However, cer= tain +features such as Secure Boot may require live patches to be signed. + =20 ## Addendum =20 @@ -1178,58 +1230,6 @@ the function itself. Similar considerations are true to a lesser extent for \__FILE__, but it could be argued that file renaming should be done outside of hotpatches. =20 -## Signature checking requirements. - -The signature checking requires that the layout of the data in memory -**MUST** be same for signature to be verified. This means that the payload -data layout in ELF format **MUST** match what the hypervisor would be -expecting such that it can properly do signature verification. - -The signature is based on the all of the payloads continuously laid out -in memory. The signature is to be appended at the end of the ELF payload -prefixed with the string '`~Module signature appended~\n`', followed by -an signature header then followed by the signature, key identifier, and si= gners -name. - -Specifically the signature header would be: - - #define PKEY_ALGO_DSA 0 - #define PKEY_ALGO_RSA 1 - - #define PKEY_ID_PGP 0 /* OpenPGP generated key ID */ - #define PKEY_ID_X509 1 /* X.509 arbitrary subjectKeyIdentifier = */ - - #define HASH_ALGO_MD4 0 - #define HASH_ALGO_MD5 1 - #define HASH_ALGO_SHA1 2 - #define HASH_ALGO_RIPE_MD_160 3 - #define HASH_ALGO_SHA256 4 - #define HASH_ALGO_SHA384 5 - #define HASH_ALGO_SHA512 6 - #define HASH_ALGO_SHA224 7 - #define HASH_ALGO_RIPE_MD_128 8 - #define HASH_ALGO_RIPE_MD_256 9 - #define HASH_ALGO_RIPE_MD_320 10 - #define HASH_ALGO_WP_256 11 - #define HASH_ALGO_WP_384 12 - #define HASH_ALGO_WP_512 13 - #define HASH_ALGO_TGR_128 14 - #define HASH_ALGO_TGR_160 15 - #define HASH_ALGO_TGR_192 16 - - struct elf_payload_signature { - u8 algo; /* Public-key crypto algorithm PKEY_ALGO_*. */ - u8 hash; /* Digest algorithm: HASH_ALGO_*. */ - u8 id_type; /* Key identifier type PKEY_ID*. */ - u8 signer_len; /* Length of signer's name */ - u8 key_id_len; /* Length of key identifier */ - u8 __pad[3]; - __be32 sig_len; /* Length of signature data */ - }; - -(Note that this has been borrowed from Linux module signature code.). - - ### .bss and .data sections. =20 In place patching writable data is not suitable as it is unclear what shou= ld be done --=20 2.49.0 From nobody Thu Dec 18 05:05:05 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1746541985; cv=none; d=zohomail.com; s=zohoarc; b=KETIpnuYwiK0PFgC68w4jHK6y3YlKc4sOWn5BVD8ya/8YGOto8P+ZQLMTjkQsJvIiL8Up1ZDHOyGe3JW82emUCpmVW7SachsehwWbh6rGTcU9GRLuAsurk9C+fxEQ4NFlThb0oIl1lWxNsKYvLtujuQVGyo3f+yTJpadUVqOSX8= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1746541985; h=Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=bGQj8XO9xK1XWcKjxy5tWwgI9dG4aXp1v1X5ZUMFZno=; b=SelWQ6MKUe/nwLIQQxIHOTQFvZvjD8fOd9mR5TeiCT+on5VCfdNSkeCADvJwP0VIpwxYKRAhV5ODXyBVknuiR9mr0WbvmExboTZS0/DGm7cxQnsMyLT+8KPUwIlRDtpQp+vLH1OcYd98yH72Fj2U5Li3HkS9bRhtE0oIt9yAXMc= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1746541985741940.022793819801; Tue, 6 May 2025 07:33:05 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.977410.1364433 (Exim 4.92) (envelope-from ) id 1uCJLp-0001Bw-V5; Tue, 06 May 2025 14:32:53 +0000 Received: by outflank-mailman (output) from mailman id 977410.1364433; Tue, 06 May 2025 14:32:53 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uCJLp-0001Bn-Ro; Tue, 06 May 2025 14:32:53 +0000 Received: by outflank-mailman (input) for mailman id 977410; Tue, 06 May 2025 14:32:52 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uCJLo-0000Py-7Y for xen-devel@lists.xenproject.org; Tue, 06 May 2025 14:32:52 +0000 Received: from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com [2a00:1450:4864:20::62a]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id fd8cce18-2a86-11f0-9eb4-5ba50f476ded; Tue, 06 May 2025 16:32:51 +0200 (CEST) Received: by mail-ej1-x62a.google.com with SMTP id a640c23a62f3a-ac3eb3fdd2eso226359866b.0 for ; Tue, 06 May 2025 07:32:51 -0700 (PDT) Received: from rossla-pc.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad1894c0356sm711598966b.100.2025.05.06.07.32.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 May 2025 07:32:50 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: fd8cce18-2a86-11f0-9eb4-5ba50f476ded DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1746541971; x=1747146771; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=bGQj8XO9xK1XWcKjxy5tWwgI9dG4aXp1v1X5ZUMFZno=; b=Hm5unEdNknoyiEVsKUFmqE9a9k61o+cZbe7XbYKw+mR7g50LdQwSGYj+GWP4zTThbf yrCoMR6wmdKtVOTQGEJVPcOw9zB4eWLLq9o9QYPmQLZiKbM8NaRBaEDl+M0rLs7afj26 P1I5BHVpoqkAMG7bI3UwdF2fPJLXiAHb0vc6I= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746541971; x=1747146771; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=bGQj8XO9xK1XWcKjxy5tWwgI9dG4aXp1v1X5ZUMFZno=; b=YZKJuebUHvphP+Bqdm9J5Xnwf62xGgtA3R0aV/pRfQSOIA0jd/1rZW0xsHArND6lQA bX7H+XdCA4eqF91Ig18e1gwW6DNUDREvpdg6yoV/qiexX3NCjQvNR53zaj0hal5kpP1e Gjf3GCUVyRGBCCycmj8pa9kY9ZX2NO+E6EzbFOLfoMAJUMYWCEE/5JLJlZMpSMTXA2da ClX0CWVN12WiZM+Tjc8kvf1DUPAwwOoZ4n2EAk8kqO4d/Ay8PveE4ham8FIT+W02gHD7 zPNTOa6q70XUxBBUREzcD1aUijDunVwIDd4JEIosog5/E7W4NTjcHLpi61EitAw6K947 96VA== X-Forwarded-Encrypted: i=1; AJvYcCVAVWCRwTFyCybE36FPy3LStE5za66LcZ6cumVu9xra0QHDMPl22F0YcQBLUDvJmm4D3T4tg5uW4dw=@lists.xenproject.org X-Gm-Message-State: AOJu0YyXWN/FAGytXEvL0QdlkdrGTq4Ew4mbnRybAk9a34fz8HRmyIgL IaEDLPMLv1xqdv3NZuFrcn7HJsg71fcS0/pe5Jg/w6tiv0sXzEvydLNqvKRLOQ== X-Gm-Gg: ASbGncvEeE7BkouMmri+84/AKqKf/6pUKlM+t6VwJRuqrHzXcYdNUalGpYuIKyii/2X iwZADSQOtj0rMIEeF8LViKdQ5B6CmVuN8raOgacz0xZH8S+FiRk48kmb5FgPbqDAyIwEYM/SDOG 1WDu0mScs/mWcd8sdsklzHNm8I2Yj1NFBznUSJoJTx86ItG46xWDGUwQ9n0jJvgeSkTYynqRD8u m2/3rD9DkyFcrEftzokB6jdnMdfP8XmqWDJL/oFdwVmqcapP4G0kcYPJRwAb/LgAt/j3ZI81GTS Eri1cNZ1mriQ8Q+VAGLTqRAofB6DWdB9NTlNp9qfHmHVKKXysuH7N/ll0iISgLAn X-Google-Smtp-Source: AGHT+IGMF0oOg/WWjkkwCL2mmKhmU6bGYpiURlETPFlS+B8s9Ga0O9y4iOwSh+qxOLprOxov9mTd1Q== X-Received: by 2002:a17:907:94d0:b0:ace:be7c:11da with SMTP id a640c23a62f3a-ad17b5dd7d5mr1554351366b.33.1746541970551; Tue, 06 May 2025 07:32:50 -0700 (PDT) From: Ross Lagerwall To: Xen-devel , xen-devel@lists.xenproject.org Cc: Ross Lagerwall , Andrew Cooper , Anthony PERARD , Michal Orzel , Jan Beulich , Julien Grall , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= , Stefano Stabellini Subject: [PATCH 2/4] crypto: Add RSA support Date: Tue, 6 May 2025 15:32:14 +0100 Message-ID: <20250506143218.1782603-3-ross.lagerwall@citrix.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250506143218.1782603-1-ross.lagerwall@citrix.com> References: <20250506143218.1782603-1-ross.lagerwall@citrix.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1746541988264019000 In preparation for adding support for livepatch signing, add support for RSA crypto. The RSA code is extracted from Nettle at tag nettle_3.2_release_20160128 (https://git.lysator.liu.se/nettle/nettle). The MPI code is extracted from Linux at commit eef0df6a5953 (lib/mpi/*). Signed-off-by: Ross Lagerwall --- xen/common/Makefile | 1 + xen/common/mpi.c | 1724 +++++++++++++++++++++++++++++++++++++++++ xen/crypto/Makefile | 1 + xen/crypto/rsa.c | 194 +++++ xen/include/xen/mpi.h | 63 ++ xen/include/xen/rsa.h | 72 ++ 6 files changed, 2055 insertions(+) create mode 100644 xen/common/mpi.c create mode 100644 xen/crypto/rsa.c create mode 100644 xen/include/xen/mpi.h create mode 100644 xen/include/xen/rsa.h diff --git a/xen/common/Makefile b/xen/common/Makefile index 98f08730563f..ece6548bb072 100644 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -28,6 +28,7 @@ obj-$(CONFIG_LIVEPATCH) +=3D livepatch.o livepatch_elf.o obj-$(CONFIG_LLC_COLORING) +=3D llc-coloring.o obj-$(CONFIG_VM_EVENT) +=3D mem_access.o obj-y +=3D memory.o +obj-y +=3D mpi.o obj-y +=3D multicall.o obj-y +=3D notifier.o obj-$(CONFIG_NUMA) +=3D numa.o diff --git a/xen/common/mpi.c b/xen/common/mpi.c new file mode 100644 index 000000000000..e3e3ecd42283 --- /dev/null +++ b/xen/common/mpi.c @@ -0,0 +1,1724 @@ +/* mpi-pow.c - MPI functions + * 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, U= SA + * + * 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 + */ + +#include +#include +#include +#include +#include +#include +#include + +#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; \ + for (_i =3D 0; _i < (n); _i++) \ + (d)[_i] =3D (s)[_i]; \ + } while (0) + +#define MPN_COPY_DECR(d, s, n) \ + do { \ + mpi_size_t _i; \ + for (_i =3D (n)-1; _i >=3D 0; _i--) \ + (d)[_i] =3D (s)[_i]; \ + } while (0) + +/* Zero N limbs at D */ +#define MPN_ZERO(d, n) \ + do { \ + int _i; \ + for (_i =3D 0; _i < (n); _i++) \ + (d)[_i] =3D 0; \ + } while (0) + +#define MPN_NORMALIZE(d, n) \ + do { \ + while ((n) > 0) { \ + if ((d)[(n)-1]) \ + break; \ + (n)--; \ + } \ + } while (0) + +#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ + do { \ + if ((size) < KARATSUBA_THRESHOLD) \ + mul_n_basecase(prodp, up, vp, size); \ + else \ + mul_n(prodp, up, vp, size, tspace); \ + } while (0); + +#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \ + do { \ + if ((size) < KARATSUBA_THRESHOLD) \ + mpih_sqr_n_basecase(prodp, up, size); \ + else \ + mpih_sqr_n(prodp, up, size, tspace); \ + } while (0); + +#define add_ssaaaa(sh, sl, ah, al, bh, bl) \ +do { \ + mpi_limb_t __x; \ + __x =3D (al) + (bl); \ + (sh) =3D (ah) + (bh) + (__x < (al)); \ + (sl) =3D __x; \ +} while (0) + +#define sub_ddmmss(sh, sl, ah, al, bh, bl) \ +do { \ + mpi_limb_t __x; \ + __x =3D (al) - (bl); \ + (sh) =3D (ah) - (bh) - (__x > (al)); \ + (sl) =3D __x; \ +} while (0) + +#define __ll_B ((mpi_limb_t) 1 << (BITS_PER_MPI_LIMB / 2)) +#define __ll_lowpart(t) ((mpi_limb_t) (t) & (__ll_B - 1)) +#define __ll_highpart(t) ((mpi_limb_t) (t) >> (BITS_PER_MPI_LIMB / 2)) + +#define umul_ppmm(w1, w0, u, v) \ +do { \ + mpi_limb_t __x0, __x1, __x2, __x3; \ + unsigned int __ul, __vl, __uh, __vh; \ + mpi_limb_t __u =3D (u), __v =3D (v); \ + \ + __ul =3D __ll_lowpart(__u); \ + __uh =3D __ll_highpart(__u); \ + __vl =3D __ll_lowpart(__v); \ + __vh =3D __ll_highpart(__v); \ + \ + __x0 =3D (mpi_limb_t) __ul * __vl; \ + __x1 =3D (mpi_limb_t) __ul * __vh; \ + __x2 =3D (mpi_limb_t) __uh * __vl; \ + __x3 =3D (mpi_limb_t) __uh * __vh; \ + \ + __x1 +=3D __ll_highpart(__x0);/* this can't give carry */ \ + __x1 +=3D __x2; /* but this indeed can */ \ + if (__x1 < __x2) /* did we get it? */ \ + __x3 +=3D __ll_B; /* yes, add it in the proper pos. */ \ + \ + (w1) =3D __x3 + __ll_highpart(__x1); \ + (w0) =3D (__ll_lowpart(__x1) << BITS_PER_MPI_LIMB/2) + __ll_lowpart(__x0)= ; \ +} while (0) + +#define udiv_qrnnd(q, r, n1, n0, d) \ +do { \ + mpi_limb_t __d1, __d0, __q1, __q0, __r1, __r0, __m; \ + __d1 =3D __ll_highpart(d); \ + __d0 =3D __ll_lowpart(d); \ + \ + __r1 =3D (n1) % __d1; \ + __q1 =3D (n1) / __d1; \ + __m =3D (mpi_limb_t) __q1 * __d0; \ + __r1 =3D __r1 * __ll_B | __ll_highpart(n0); \ + if (__r1 < __m) { \ + __q1--, __r1 +=3D (d); \ + if (__r1 >=3D (d)) /* i.e. we didn't get carry when adding to __r1 */ \ + if (__r1 < __m) \ + __q1--, __r1 +=3D (d); \ + } \ + __r1 -=3D __m; \ + \ + __r0 =3D __r1 % __d1; \ + __q0 =3D __r1 / __d1; \ + __m =3D (mpi_limb_t) __q0 * __d0; \ + __r0 =3D __r0 * __ll_B | __ll_lowpart(n0); \ + if (__r0 < __m) { \ + __q0--, __r0 +=3D (d); \ + if (__r0 >=3D (d)) \ + if (__r0 < __m) \ + __q0--, __r0 +=3D (d); \ + } \ + __r0 -=3D __m; \ + \ + (q) =3D (mpi_limb_t) __q1 * __ll_B | __q0; \ + (r) =3D __r0; \ +} while (0) + +struct karatsuba_ctx { + struct karatsuba_ctx *next; + mpi_ptr_t tspace; + mpi_size_t tspace_size; + mpi_ptr_t tp; + mpi_size_t tp_size; +}; + +static void mpi_normalize(MPI a); +static mpi_limb_t mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); +static mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs, + mpi_ptr_t np, mpi_size_t nsize, + mpi_ptr_t dp, mpi_size_t dsize); +static mpi_limb_t mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t us= ize, + unsigned cnt); +static void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs); +static mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs); +static void mpi_free_limb_space(mpi_ptr_t a); +static mpi_limb_t mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); +static int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result); +static mpi_limb_t mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t us= ize, + unsigned cnt); +static int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t si= ze); +static void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, + mpi_ptr_t tspace); +static mpi_limb_t mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size); +static mpi_limb_t mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size); +static mpi_limb_t mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb); +static void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx); +static void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t = size); +static int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, + mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, + struct karatsuba_ctx *ctx); +static int mpi_resize(MPI a, unsigned nlimbs); + +/** + * count_leading_zeros - Count the number of zeros from the MSB back + * @x: The value + * + * Count the number of leading zeros from the MSB going towards the LSB in= @x. + * + * If the MSB of @x is set, the result is 0. + * If only the LSB of @x is set, then the result is BITS_PER_LONG-1. + * If @x is 0 then the result is BITS_PER_LONG. + */ +static inline int count_leading_zeros(unsigned long x) +{ + if (sizeof(x) =3D=3D 4) + return BITS_PER_LONG - fls(x); + else + return BITS_PER_LONG - fls64(x); +} + +static mpi_limb_t +mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t x; + + x =3D *s1_ptr++; + s2_limb +=3D x; + *res_ptr++ =3D s2_limb; + if (s2_limb < x) { /* sum is less than the left operand: handle carry */ + while (--s1_size) { + x =3D *s1_ptr++ + 1; /* add carry */ + *res_ptr++ =3D x; /* and store */ + if (x) /* not 0 (no overflow): we can stop */ + goto leave; + } + return 1; /* return carry (size of s1 to small) */ + } + +leave: + if (res_ptr !=3D s1_ptr) { /* not the same variable */ + mpi_size_t i; /* copy the rest */ + for (i =3D 0; i < s1_size - 1; i++) + res_ptr[i] =3D s1_ptr[i]; + } + return 0; /* no carry */ +} + +static mpi_limb_t +mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t x; + + x =3D *s1_ptr++; + s2_limb =3D x - s2_limb; + *res_ptr++ =3D s2_limb; + if (s2_limb > x) { + while (--s1_size) { + x =3D *s1_ptr++; + *res_ptr++ =3D x - 1; + if (x) + goto leave; + } + return 1; + } + +leave: + if (res_ptr !=3D s1_ptr) { + mpi_size_t i; + for (i =3D 0; i < s1_size - 1; i++) + res_ptr[i] =3D s1_ptr[i]; + } + return 0; +} + +static mpi_limb_t +mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_ptr_t s2_ptr, mpi_size_t s2_size) +{ + mpi_limb_t cy =3D 0; + + if (s2_size) + cy =3D mpihelp_sub_n(res_ptr, s1_ptr, s2_ptr, s2_size); + + if (s1_size - s2_size) + cy =3D mpihelp_sub_1(res_ptr + s2_size, s1_ptr + s2_size, + s1_size - s2_size, cy); + return cy; +} + +static mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs) +{ + size_t len =3D nlimbs * sizeof(mpi_limb_t); + + if (!len) + return NULL; + + return xmalloc_bytes(len); +} + +static void mpi_free_limb_space(mpi_ptr_t a) +{ + if (!a) + return; + + xfree(a); +} + +/**************** + * Resize the array of A to NLIMBS. the additional space is cleared + * (set to 0) [done by m_realloc()] + */ +static int mpi_resize(MPI a, unsigned nlimbs) +{ + void *p; + + if (nlimbs <=3D a->alloced) + return 0; /* no need to do it */ + + if (a->d) { + p =3D xmalloc_array(mpi_limb_t, nlimbs); + if (!p) + return -ENOMEM; + memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t)); + xfree(a->d); + a->d =3D p; + } else { + a->d =3D xzalloc_array(mpi_limb_t, nlimbs); + if (!a->d) + return -ENOMEM; + } + a->alloced =3D nlimbs; + return 0; +} + +/**************** + * RES =3D BASE ^ EXP mod MOD + */ +int mpi_powm(MPI res, MPI base, MPI exp, MPI mod) +{ + mpi_ptr_t mp_marker =3D NULL, bp_marker =3D NULL, ep_marker =3D NULL; + mpi_ptr_t xp_marker =3D NULL; + mpi_ptr_t tspace =3D NULL; + mpi_ptr_t rp, ep, mp, bp; + mpi_size_t esize, msize, bsize, rsize; + int msign, bsign, rsign; + mpi_size_t size; + int mod_shift_cnt; + int negative_result; + int assign_rp =3D 0; + mpi_size_t tsize =3D 0; /* to avoid compiler warning */ + /* fixme: we should check that the warning is void */ + int rc =3D -ENOMEM; + + esize =3D exp->nlimbs; + msize =3D mod->nlimbs; + size =3D 2 * msize; + msign =3D mod->sign; + + rp =3D res->d; + ep =3D exp->d; + + if (!msize) + return -EINVAL; + + if (!esize) { + /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 + * depending on if MOD equals 1. */ + rp[0] =3D 1; + res->nlimbs =3D (msize =3D=3D 1 && mod->d[0] =3D=3D 1) ? 0 : 1; + res->sign =3D 0; + goto leave; + } + + /* Normalize MOD (i.e. make its most significant bit set) as required by + * mpn_divrem. This will make the intermediate values in the calculation + * slightly larger, but the correct result is obtained after a final + * reduction using the original MOD value. */ + mp =3D mp_marker =3D mpi_alloc_limb_space(msize); + if (!mp) + goto enomem; + mod_shift_cnt =3D count_leading_zeros(mod->d[msize - 1]); + if (mod_shift_cnt) + mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); + else + MPN_COPY(mp, mod->d, msize); + + bsize =3D base->nlimbs; + bsign =3D base->sign; + if (bsize > msize) { /* The base is larger than the module. Reduce it. */ + /* Allocate (BSIZE + 1) with space for remainder and quotient. + * (The quotient is (bsize - msize + 1) limbs.) */ + bp =3D bp_marker =3D mpi_alloc_limb_space(bsize + 1); + if (!bp) + goto enomem; + MPN_COPY(bp, base->d, bsize); + /* We don't care about the quotient, store it above the remainder, + * at BP + MSIZE. */ + mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); + bsize =3D msize; + /* Canonicalize the base, since we are going to multiply with it + * quite a few times. */ + MPN_NORMALIZE(bp, bsize); + } else + bp =3D base->d; + + if (!bsize) { + res->nlimbs =3D 0; + res->sign =3D 0; + goto leave; + } + + if (res->alloced < size) { + /* We have to allocate more space for RES. If any of the input + * parameters are identical to RES, defer deallocation of the old + * space. */ + if (rp =3D=3D ep || rp =3D=3D mp || rp =3D=3D bp) { + rp =3D mpi_alloc_limb_space(size); + if (!rp) + goto enomem; + assign_rp =3D 1; + } else { + if (mpi_resize(res, size) < 0) + goto enomem; + rp =3D res->d; + } + } else { /* Make BASE, EXP and MOD not overlap with RES. */ + if (rp =3D=3D bp) { + /* RES and BASE are identical. Allocate temp. space for BASE. */ + BUG_ON(bp_marker); + bp =3D bp_marker =3D mpi_alloc_limb_space(bsize); + if (!bp) + goto enomem; + MPN_COPY(bp, rp, bsize); + } + if (rp =3D=3D ep) { + /* RES and EXP are identical. Allocate temp. space for EXP. */ + ep =3D ep_marker =3D mpi_alloc_limb_space(esize); + if (!ep) + goto enomem; + MPN_COPY(ep, rp, esize); + } + if (rp =3D=3D mp) { + /* RES and MOD are identical. Allocate temporary space for MOD. */ + BUG_ON(mp_marker); + mp =3D mp_marker =3D mpi_alloc_limb_space(msize); + if (!mp) + goto enomem; + MPN_COPY(mp, rp, msize); + } + } + + MPN_COPY(rp, bp, bsize); + rsize =3D bsize; + rsign =3D bsign; + + { + mpi_size_t i; + mpi_ptr_t xp; + int c; + mpi_limb_t e; + mpi_limb_t carry_limb; + struct karatsuba_ctx karactx; + + xp =3D xp_marker =3D mpi_alloc_limb_space(2 * (msize + 1)); + if (!xp) + goto enomem; + + memset(&karactx, 0, sizeof karactx); + negative_result =3D (ep[0] & 1) && base->sign; + + i =3D esize - 1; + e =3D ep[i]; + c =3D count_leading_zeros(e); + e =3D (e << c) << 1; /* shift the exp bits to the left, lose msb */ + c =3D BITS_PER_MPI_LIMB - 1 - c; + + /* Main loop. + * + * Make the result be pointed to alternately by XP and RP. This + * helps us avoid block copying, which would otherwise be necessary + * with the overlap restrictions of mpihelp_divmod. With 50% probability + * the result after this loop will be in the area originally pointed + * by RP (=3D=3DRES->d), and with 50% probability in the area originally + * pointed to by XP. + */ + + for (;;) { + while (c) { + mpi_ptr_t tp; + mpi_size_t xsize; + + /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ + if (rsize < KARATSUBA_THRESHOLD) + mpih_sqr_n_basecase(xp, rp, rsize); + else { + if (!tspace) { + tsize =3D 2 * rsize; + tspace =3D + mpi_alloc_limb_space(tsize); + if (!tspace) + goto enomem; + } else if (tsize < (2 * rsize)) { + mpi_free_limb_space(tspace); + tsize =3D 2 * rsize; + tspace =3D + mpi_alloc_limb_space(tsize); + if (!tspace) + goto enomem; + } + mpih_sqr_n(xp, rp, rsize, tspace); + } + + xsize =3D 2 * rsize; + if (xsize > msize) { + mpihelp_divrem(xp + msize, 0, xp, xsize, + mp, msize); + xsize =3D msize; + } + + tp =3D rp; + rp =3D xp; + xp =3D tp; + rsize =3D xsize; + + if ((mpi_limb_signed_t) e < 0) { + /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ + if (bsize < KARATSUBA_THRESHOLD) { + mpi_limb_t tmp; + if (mpihelp_mul + (xp, rp, rsize, bp, bsize, + &tmp) < 0) + goto enomem; + } else { + if (mpihelp_mul_karatsuba_case + (xp, rp, rsize, bp, bsize, + &karactx) < 0) + goto enomem; + } + + xsize =3D rsize + bsize; + if (xsize > msize) { + mpihelp_divrem(xp + msize, 0, + xp, xsize, mp, + msize); + xsize =3D msize; + } + + tp =3D rp; + rp =3D xp; + xp =3D tp; + rsize =3D xsize; + } + e <<=3D 1; + c--; + } + + i--; + if (i < 0) + break; + e =3D ep[i]; + c =3D BITS_PER_MPI_LIMB; + } + + /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT + * steps. Adjust the result by reducing it with the original MOD. + * + * Also make sure the result is put in RES->d (where it already + * might be, see above). + */ + if (mod_shift_cnt) { + carry_limb =3D + mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); + rp =3D res->d; + if (carry_limb) { + rp[rsize] =3D carry_limb; + rsize++; + } + } else { + MPN_COPY(res->d, rp, rsize); + rp =3D res->d; + } + + if (rsize >=3D msize) { + mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); + rsize =3D msize; + } + + /* Remove any leading zero words from the result. */ + if (mod_shift_cnt) + mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); + MPN_NORMALIZE(rp, rsize); + + mpihelp_release_karatsuba_ctx(&karactx); + } + + if (negative_result && rsize) { + if (mod_shift_cnt) + mpihelp_rshift(mp, mp, msize, mod_shift_cnt); + mpihelp_sub(rp, mp, msize, rp, rsize); + rsize =3D msize; + rsign =3D msign; + MPN_NORMALIZE(rp, rsize); + } + res->nlimbs =3D rsize; + res->sign =3D rsign; + +leave: + rc =3D 0; +enomem: + if (assign_rp) + mpi_assign_limb_space(res, rp, size); + if (mp_marker) + mpi_free_limb_space(mp_marker); + if (bp_marker) + mpi_free_limb_space(bp_marker); + if (ep_marker) + mpi_free_limb_space(ep_marker); + if (xp_marker) + mpi_free_limb_space(xp_marker); + if (tspace) + mpi_free_limb_space(tspace); + return rc; +} + +/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by = VP), + * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are + * always stored. Return the most significant limb. + * + * Argument constraints: + * 1. PRODP !=3D UP and PRODP !=3D VP, i.e. the destination + * must be distinct from the multiplier and the multiplicand. + * + * + * Handle simple cases with traditional multiplication. + * + * This is the most critical code of multiplication. All multiplies rely + * on this, both small and huge. Small ones arrive here immediately. Huge + * ones arrive here as this is the base case for Karatsuba's recursive + * algorithm below. + */ + +static mpi_limb_t +mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t siz= e) +{ + mpi_size_t i; + mpi_limb_t cy; + mpi_limb_t v_limb; + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb =3D vp[0]; + if (v_limb <=3D 1) { + if (v_limb =3D=3D 1) + MPN_COPY(prodp, up, size); + else + MPN_ZERO(prodp, size); + cy =3D 0; + } else + cy =3D mpihelp_mul_1(prodp, up, size, v_limb); + + prodp[size] =3D cy; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for (i =3D 1; i < size; i++) { + v_limb =3D vp[i]; + if (v_limb <=3D 1) { + cy =3D 0; + if (v_limb =3D=3D 1) + cy =3D mpihelp_add_n(prodp, prodp, up, size); + } else + cy =3D mpihelp_addmul_1(prodp, up, size, v_limb); + + prodp[size] =3D cy; + prodp++; + } + + return cy; +} + +static void +mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, + mpi_size_t size, mpi_ptr_t tspace) +{ + if (size & 1) { + /* The size is odd, and the code below doesn't handle that. + * Multiply the least significant (size - 1) limbs with a recursive + * call, and handle the most significant limb of S1 and S2 + * separately. + * A slightly faster way to do this would be to make the Karatsuba + * code below behave as if the size were even, and let it check for + * odd size in the end. I.e., in essence move this code to the end. + * Doing so would save us a recursive call, and potentially make the + * stack grow a lot less. + */ + mpi_size_t esize =3D size - 1; /* even size */ + mpi_limb_t cy_limb; + + MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace); + cy_limb =3D mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]); + prodp[esize + esize] =3D cy_limb; + cy_limb =3D mpihelp_addmul_1(prodp + esize, vp, size, up[esize]); + prodp[esize + size] =3D cy_limb; + } else { + /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm. + * + * Split U in two pieces, U1 and U0, such that + * U =3D U0 + U1*(B**n), + * and V in V1 and V0, such that + * V =3D V0 + V1*(B**n). + * + * UV is then computed recursively using the identity + * + * 2n n n n + * UV =3D (B + B )U V + B (U -U )(V -V ) + (B + 1)U V + * 1 1 1 0 0 1 0 0 + * + * Where B =3D 2**BITS_PER_MP_LIMB. + */ + mpi_size_t hsize =3D size >> 1; + mpi_limb_t cy; + int negflg; + + /* Product H. ________________ ________________ + * |_____U1 x V1____||____U0 x V0_____| + * Put result in upper part of PROD and pass low part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, + tspace); + + /* Product M. ________________ + * |_(U1-U0)(V0-V1)_| + */ + if (mpihelp_cmp(up + hsize, up, hsize) >=3D 0) { + mpihelp_sub_n(prodp, up + hsize, up, hsize); + negflg =3D 0; + } else { + mpihelp_sub_n(prodp, up, up + hsize, hsize); + negflg =3D 1; + } + if (mpihelp_cmp(vp + hsize, vp, hsize) >=3D 0) { + mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize); + negflg ^=3D 1; + } else { + mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize); + /* No change of NEGFLG. */ + } + /* Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, + tspace + size); + + /* Add/copy product H. */ + MPN_COPY(prodp + hsize, prodp + size, hsize); + cy =3D mpihelp_add_n(prodp + size, prodp + size, + prodp + size + hsize, hsize); + + /* Add product M (if NEGFLG M is a negative number) */ + if (negflg) + cy -=3D + mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, + size); + else + cy +=3D + mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, + size); + + /* Product L. ________________ ________________ + * |________________||____U0 x V0_____| + * Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. + */ + MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size); + + /* Add/copy Product L (twice) */ + + cy +=3D mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size); + if (cy) + mpihelp_add_1(prodp + hsize + size, + prodp + hsize + size, hsize, cy); + + MPN_COPY(prodp, tspace, hsize); + cy =3D mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize, + hsize); + if (cy) + mpihelp_add_1(prodp + size, prodp + size, size, 1); + } +} + +static void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t = size) +{ + mpi_size_t i; + mpi_limb_t cy_limb; + mpi_limb_t v_limb; + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb =3D up[0]; + if (v_limb <=3D 1) { + if (v_limb =3D=3D 1) + MPN_COPY(prodp, up, size); + else + MPN_ZERO(prodp, size); + cy_limb =3D 0; + } else + cy_limb =3D mpihelp_mul_1(prodp, up, size, v_limb); + + prodp[size] =3D cy_limb; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for (i =3D 1; i < size; i++) { + v_limb =3D up[i]; + if (v_limb <=3D 1) { + cy_limb =3D 0; + if (v_limb =3D=3D 1) + cy_limb =3D mpihelp_add_n(prodp, prodp, up, size); + } else + cy_limb =3D mpihelp_addmul_1(prodp, up, size, v_limb); + + prodp[size] =3D cy_limb; + prodp++; + } +} + +static void +mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspac= e) +{ + if (size & 1) { + /* The size is odd, and the code below doesn't handle that. + * Multiply the least significant (size - 1) limbs with a recursive + * call, and handle the most significant limb of S1 and S2 + * separately. + * A slightly faster way to do this would be to make the Karatsuba + * code below behave as if the size were even, and let it check for + * odd size in the end. I.e., in essence move this code to the end. + * Doing so would save us a recursive call, and potentially make the + * stack grow a lot less. + */ + mpi_size_t esize =3D size - 1; /* even size */ + mpi_limb_t cy_limb; + + MPN_SQR_N_RECURSE(prodp, up, esize, tspace); + cy_limb =3D mpihelp_addmul_1(prodp + esize, up, esize, up[esize]); + prodp[esize + esize] =3D cy_limb; + cy_limb =3D mpihelp_addmul_1(prodp + esize, up, size, up[esize]); + + prodp[esize + size] =3D cy_limb; + } else { + mpi_size_t hsize =3D size >> 1; + mpi_limb_t cy; + + /* Product H. ________________ ________________ + * |_____U1 x U1____||____U0 x U0_____| + * Put result in upper part of PROD and pass low part of TSPACE + * as new TSPACE. + */ + MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace); + + /* Product M. ________________ + * |_(U1-U0)(U0-U1)_| + */ + if (mpihelp_cmp(up + hsize, up, hsize) >=3D 0) + mpihelp_sub_n(prodp, up + hsize, up, hsize); + else + mpihelp_sub_n(prodp, up, up + hsize, hsize); + + /* Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. */ + MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size); + + /* Add/copy product H */ + MPN_COPY(prodp + hsize, prodp + size, hsize); + cy =3D mpihelp_add_n(prodp + size, prodp + size, + prodp + size + hsize, hsize); + + /* Add product M (if NEGFLG M is a negative number). */ + cy -=3D mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size); + + /* Product L. ________________ ________________ + * |________________||____U0 x U0_____| + * Read temporary operands from low part of PROD. + * Put result in low part of TSPACE using upper part of TSPACE + * as new TSPACE. */ + MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size); + + /* Add/copy Product L (twice). */ + cy +=3D mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size); + if (cy) + mpihelp_add_1(prodp + hsize + size, + prodp + hsize + size, hsize, cy); + + MPN_COPY(prodp, tspace, hsize); + cy =3D mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize, + hsize); + if (cy) + mpihelp_add_1(prodp + size, prodp + size, size, 1); + } +} + +static int +mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, + mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, + struct karatsuba_ctx *ctx) +{ + mpi_limb_t cy; + + if (!ctx->tspace || ctx->tspace_size < vsize) { + if (ctx->tspace) + mpi_free_limb_space(ctx->tspace); + ctx->tspace =3D mpi_alloc_limb_space(2 * vsize); + if (!ctx->tspace) + return -ENOMEM; + ctx->tspace_size =3D vsize; + } + + MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace); + + prodp +=3D vsize; + up +=3D vsize; + usize -=3D vsize; + if (usize >=3D vsize) { + if (!ctx->tp || ctx->tp_size < vsize) { + if (ctx->tp) + mpi_free_limb_space(ctx->tp); + ctx->tp =3D mpi_alloc_limb_space(2 * vsize); + if (!ctx->tp) { + if (ctx->tspace) + mpi_free_limb_space(ctx->tspace); + ctx->tspace =3D NULL; + return -ENOMEM; + } + ctx->tp_size =3D vsize; + } + + do { + MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace); + cy =3D mpihelp_add_n(prodp, prodp, ctx->tp, vsize); + mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize, + cy); + prodp +=3D vsize; + up +=3D vsize; + usize -=3D vsize; + } while (usize >=3D vsize); + } + + if (usize) { + if (usize < KARATSUBA_THRESHOLD) { + mpi_limb_t tmp; + if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp) + < 0) + return -ENOMEM; + } else { + if (!ctx->next) { + ctx->next =3D xzalloc(struct karatsuba_ctx); + if (!ctx->next) + return -ENOMEM; + } + if (mpihelp_mul_karatsuba_case(ctx->tspace, + vp, vsize, + up, usize, + ctx->next) < 0) + return -ENOMEM; + } + + cy =3D mpihelp_add_n(prodp, prodp, ctx->tspace, vsize); + mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy); + } + + return 0; +} + +static void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx) +{ + struct karatsuba_ctx *ctx2; + + if (ctx->tp) + mpi_free_limb_space(ctx->tp); + if (ctx->tspace) + mpi_free_limb_space(ctx->tspace); + for (ctx =3D ctx->next; ctx; ctx =3D ctx2) { + ctx2 =3D ctx->next; + if (ctx->tp) + mpi_free_limb_space(ctx->tp); + if (ctx->tspace) + mpi_free_limb_space(ctx->tspace); + xfree(ctx); + } +} + +/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs) + * and v (pointed to by VP, with VSIZE limbs), and store the result at + * PRODP. USIZE + VSIZE limbs are always stored, but if the input + * operands are normalized. Return the most significant limb of the + * result. + * + * NOTE: The space pointed to by PRODP is overwritten before finished + * with U and V, so overlap is an error. + * + * Argument constraints: + * 1. USIZE >=3D VSIZE. + * 2. PRODP !=3D UP and PRODP !=3D VP, i.e. the destination + * must be distinct from the multiplier and the multiplicand. + */ + +static int +mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, + mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result) +{ + mpi_ptr_t prod_endp =3D prodp + usize + vsize - 1; + mpi_limb_t cy; + struct karatsuba_ctx ctx; + + if (vsize < KARATSUBA_THRESHOLD) { + mpi_size_t i; + mpi_limb_t v_limb; + + if (!vsize) { + *_result =3D 0; + return 0; + } + + /* Multiply by the first limb in V separately, as the result can be + * stored (not added) to PROD. We also avoid a loop for zeroing. */ + v_limb =3D vp[0]; + if (v_limb <=3D 1) { + if (v_limb =3D=3D 1) + MPN_COPY(prodp, up, usize); + else + MPN_ZERO(prodp, usize); + cy =3D 0; + } else + cy =3D mpihelp_mul_1(prodp, up, usize, v_limb); + + prodp[usize] =3D cy; + prodp++; + + /* For each iteration in the outer loop, multiply one limb from + * U with one limb from V, and add it to PROD. */ + for (i =3D 1; i < vsize; i++) { + v_limb =3D vp[i]; + if (v_limb <=3D 1) { + cy =3D 0; + if (v_limb =3D=3D 1) + cy =3D mpihelp_add_n(prodp, prodp, up, + usize); + } else + cy =3D mpihelp_addmul_1(prodp, up, usize, v_limb); + + prodp[usize] =3D cy; + prodp++; + } + + *_result =3D cy; + return 0; + } + + memset(&ctx, 0, sizeof ctx); + if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0) + return -ENOMEM; + mpihelp_release_karatsuba_ctx(&ctx); + *_result =3D *prod_endp; + return 0; +} + +static mpi_limb_t +mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, + mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + + /* The loop counter and index J goes from -S1_SIZE to -1. This way + * the loop becomes faster. */ + j =3D -s1_size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -=3D j; + res_ptr -=3D j; + + cy_limb =3D 0; + do { + umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb); + prod_low +=3D cy_limb; + cy_limb =3D (prod_low < cy_limb ? 1 : 0) + prod_high; + res_ptr[j] =3D prod_low; + } while (++j); + + return cy_limb; +} + +static mpi_limb_t +mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size) +{ + mpi_limb_t x, y, cy; + mpi_size_t j; + + /* The loop counter and index J goes from -SIZE to -1. This way + the loop becomes faster. */ + j =3D -size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -=3D j; + s2_ptr -=3D j; + res_ptr -=3D j; + + cy =3D 0; + do { + y =3D s2_ptr[j]; + x =3D s1_ptr[j]; + y +=3D cy; /* add previous carry to one addend */ + cy =3D y < cy; /* get out carry from that addition */ + y +=3D x; /* add other addend */ + cy +=3D y < x; /* get out carry from that add, combine */ + res_ptr[j] =3D y; + } while (++j); + + return cy; +} + +/* Shift U (pointed to by UP and USIZE digits long) CNT bits to the left + * and store the USIZE least significant digits of the result at WP. + * Return the bits shifted out from the most significant digit. + * + * Argument constraints: + * 1. 0 < CNT < BITS_PER_MP_LIMB + * 2. If the result is to be written over the input, WP must be >=3D UP. + */ + +static mpi_limb_t +mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned int = cnt) +{ + mpi_limb_t high_limb, low_limb; + unsigned sh_1, sh_2; + mpi_size_t i; + mpi_limb_t retval; + + sh_1 =3D cnt; + wp +=3D 1; + sh_2 =3D BITS_PER_MPI_LIMB - sh_1; + i =3D usize - 1; + low_limb =3D up[i]; + retval =3D low_limb >> sh_2; + high_limb =3D low_limb; + while (--i >=3D 0) { + low_limb =3D up[i]; + wp[i] =3D (high_limb << sh_1) | (low_limb >> sh_2); + high_limb =3D low_limb; + } + wp[i] =3D high_limb << sh_1; + + return retval; +} + +static mpi_limb_t +mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + mpi_limb_t x; + + /* The loop counter and index J goes from -SIZE to -1. This way + * the loop becomes faster. */ + j =3D -s1_size; + res_ptr -=3D j; + s1_ptr -=3D j; + + cy_limb =3D 0; + do { + umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb); + + prod_low +=3D cy_limb; + cy_limb =3D (prod_low < cy_limb ? 1 : 0) + prod_high; + + x =3D res_ptr[j]; + prod_low =3D x + prod_low; + cy_limb +=3D prod_low < x ? 1 : 0; + res_ptr[j] =3D prod_low; + } while (++j); + return cy_limb; +} + +static mpi_limb_t +mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_ptr_t s2_ptr, mpi_size_t size) +{ + mpi_limb_t x, y, cy; + mpi_size_t j; + + /* The loop counter and index J goes from -SIZE to -1. This way + the loop becomes faster. */ + j =3D -size; + + /* Offset the base pointers to compensate for the negative indices. */ + s1_ptr -=3D j; + s2_ptr -=3D j; + res_ptr -=3D j; + + cy =3D 0; + do { + y =3D s2_ptr[j]; + x =3D s1_ptr[j]; + y +=3D cy; /* add previous carry to subtrahend */ + cy =3D y < cy; /* get out carry from that addition */ + y =3D x - y; /* main subtract */ + cy +=3D y > x; /* get out carry from the subtract, combine */ + res_ptr[j] =3D y; + } while (++j); + + return cy; +} + +/**************** + * Compare OP1_PTR/OP1_SIZE with OP2_PTR/OP2_SIZE. + * There are no restrictions on the relative sizes of + * the two arguments. + * Return 1 if OP1 > OP2, 0 if they are equal, and -1 if OP1 < OP2. + */ +static int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t si= ze) +{ + mpi_size_t i; + mpi_limb_t op1_word, op2_word; + + for (i =3D size - 1; i >=3D 0; i--) { + op1_word =3D op1_ptr[i]; + op2_word =3D op2_ptr[i]; + if (op1_word !=3D op2_word) + goto diff; + } + return 0; + +diff: + /* This can *not* be simplified to + * op2_word - op2_word + * since that expression might give signed overflow. */ + return (op1_word > op2_word) ? 1 : -1; +} + +static void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs) +{ + mpi_free_limb_space(a->d); + a->d =3D ap; + a->alloced =3D nlimbs; +} + +/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right + * and store the USIZE least significant limbs of the result at WP. + * The bits shifted out to the right are returned. + * + * Argument constraints: + * 1. 0 < CNT < BITS_PER_MP_LIMB + * 2. If the result is to be written over the input, WP must be <=3D UP. + */ + +static mpi_limb_t +mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt) +{ + mpi_limb_t high_limb, low_limb; + unsigned sh_1, sh_2; + mpi_size_t i; + mpi_limb_t retval; + + sh_1 =3D cnt; + wp -=3D 1; + sh_2 =3D BITS_PER_MPI_LIMB - sh_1; + high_limb =3D up[0]; + retval =3D high_limb << sh_2; + low_limb =3D high_limb; + for (i =3D 1; i < usize; i++) { + high_limb =3D up[i]; + wp[i] =3D (low_limb >> sh_1) | (high_limb << sh_2); + low_limb =3D high_limb; + } + wp[i] =3D low_limb >> sh_1; + + return retval; +} + +/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write + * the NSIZE-DSIZE least significant quotient limbs at QP + * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is + * non-zero, generate that many fraction bits and append them after the + * other quotient limbs. + * Return the most significant limb of the quotient, this is always 0 or 1. + * + * Preconditions: + * 0. NSIZE >=3D DSIZE. + * 1. The most significant bit of the divisor must be set. + * 2. QP must either not overlap with the input operands at all, or + * QP + DSIZE >=3D NP must hold true. (This means that it's + * possible to put the quotient in the high part of NUM, right after the + * remainder in NUM. + * 3. NSIZE >=3D DSIZE, even if QEXTRA_LIMBS is non-zero. + */ + +static mpi_limb_t +mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs, + mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize) +{ + mpi_limb_t most_significant_q_limb =3D 0; + + switch (dsize) { + case 0: + /* We are asked to divide by zero, so go ahead and do it! (To make + the compiler not remove this statement, return the value.) */ + /* + * existing clients of this function have been modified + * not to call it with dsize =3D=3D 0, so this should not happen + */ + return 1 / dsize; + + case 1: + { + mpi_size_t i; + mpi_limb_t n1; + mpi_limb_t d; + + d =3D dp[0]; + n1 =3D np[nsize - 1]; + + if (n1 >=3D d) { + n1 -=3D d; + most_significant_q_limb =3D 1; + } + + qp +=3D qextra_limbs; + for (i =3D nsize - 2; i >=3D 0; i--) + udiv_qrnnd(qp[i], n1, n1, np[i], d); + qp -=3D qextra_limbs; + + for (i =3D qextra_limbs - 1; i >=3D 0; i--) + udiv_qrnnd(qp[i], n1, n1, 0, d); + + np[0] =3D n1; + } + break; + + case 2: + { + mpi_size_t i; + mpi_limb_t n1, n0, n2; + mpi_limb_t d1, d0; + + np +=3D nsize - 2; + d1 =3D dp[1]; + d0 =3D dp[0]; + n1 =3D np[1]; + n0 =3D np[0]; + + if (n1 >=3D d1 && (n1 > d1 || n0 >=3D d0)) { + sub_ddmmss(n1, n0, n1, n0, d1, d0); + most_significant_q_limb =3D 1; + } + + for (i =3D qextra_limbs + nsize - 2 - 1; i >=3D 0; i--) { + mpi_limb_t q; + mpi_limb_t r; + + if (i >=3D qextra_limbs) + np--; + else + np[0] =3D 0; + + if (n1 =3D=3D d1) { + /* Q should be either 111..111 or 111..110. Need special + * treatment of this rare case as normal division would + * give overflow. */ + q =3D ~(mpi_limb_t) 0; + + r =3D n0 + d1; + if (r < d1) { /* Carry in the addition? */ + add_ssaaaa(n1, n0, r - d0, + np[0], 0, d0); + qp[i] =3D q; + continue; + } + n1 =3D d0 - (d0 !=3D 0 ? 1 : 0); + n0 =3D -d0; + } else { + udiv_qrnnd(q, r, n1, n0, d1); + umul_ppmm(n1, n0, d0, q); + } + + n2 =3D np[0]; +q_test: + if (n1 > r || (n1 =3D=3D r && n0 > n2)) { + /* The estimated Q was too large. */ + q--; + sub_ddmmss(n1, n0, n1, n0, 0, d0); + r +=3D d1; + if (r >=3D d1) /* If not carry, test Q again. */ + goto q_test; + } + + qp[i] =3D q; + sub_ddmmss(n1, n0, r, n2, n1, n0); + } + np[1] =3D n1; + np[0] =3D n0; + } + break; + + default: + { + mpi_size_t i; + mpi_limb_t dX, d1, n0; + + np +=3D nsize - dsize; + dX =3D dp[dsize - 1]; + d1 =3D dp[dsize - 2]; + n0 =3D np[dsize - 1]; + + if (n0 >=3D dX) { + if (n0 > dX + || mpihelp_cmp(np, dp, dsize - 1) >=3D 0) { + mpihelp_sub_n(np, np, dp, dsize); + n0 =3D np[dsize - 1]; + most_significant_q_limb =3D 1; + } + } + + for (i =3D qextra_limbs + nsize - dsize - 1; i >=3D 0; i--) { + mpi_limb_t q; + mpi_limb_t n1, n2; + mpi_limb_t cy_limb; + + if (i >=3D qextra_limbs) { + np--; + n2 =3D np[dsize]; + } else { + n2 =3D np[dsize - 1]; + MPN_COPY_DECR(np + 1, np, dsize - 1); + np[0] =3D 0; + } + + if (n0 =3D=3D dX) { + /* This might over-estimate q, but it's probably not worth + * the extra code here to find out. */ + q =3D ~(mpi_limb_t) 0; + } else { + mpi_limb_t r; + + udiv_qrnnd(q, r, n0, np[dsize - 1], dX); + umul_ppmm(n1, n0, d1, q); + + while (n1 > r + || (n1 =3D=3D r + && n0 > np[dsize - 2])) { + q--; + r +=3D dX; + if (r < dX) /* I.e. "carry in previous addition?" */ + break; + n1 -=3D n0 < d1; + n0 -=3D d1; + } + } + + /* Possible optimization: We already have (q * n0) and (1 * n1) + * after the calculation of q. Taking advantage of that, we + * could make this loop make two iterations less. */ + cy_limb =3D mpihelp_submul_1(np, dp, dsize, q); + + if (n2 !=3D cy_limb) { + mpihelp_add_n(np, np, dp, dsize); + q--; + } + + qp[i] =3D q; + n0 =3D np[dsize - 1]; + } + } + } + + return most_significant_q_limb; +} + +static mpi_limb_t +mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, + mpi_size_t s1_size, mpi_limb_t s2_limb) +{ + mpi_limb_t cy_limb; + mpi_size_t j; + mpi_limb_t prod_high, prod_low; + mpi_limb_t x; + + /* The loop counter and index J goes from -SIZE to -1. This way + * the loop becomes faster. */ + j =3D -s1_size; + res_ptr -=3D j; + s1_ptr -=3D j; + + cy_limb =3D 0; + do { + umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb); + + prod_low +=3D cy_limb; + cy_limb =3D (prod_low < cy_limb ? 1 : 0) + prod_high; + + x =3D res_ptr[j]; + prod_low =3D x - prod_low; + cy_limb +=3D prod_low > x ? 1 : 0; + res_ptr[j] =3D prod_low; + } while (++j); + + return cy_limb; +} + +/** + * mpi_read_raw_data - Read a raw byte stream as a positive integer + * @xbuffer: The data to read + * @nbytes: The amount of data to read + */ +MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes) +{ + const uint8_t *buffer =3D xbuffer; + int i, j; + unsigned nbits, nlimbs; + mpi_limb_t a; + MPI val =3D NULL; + + while (nbytes > 0 && buffer[0] =3D=3D 0) { + buffer++; + nbytes--; + } + + nbits =3D nbytes * 8; + if (nbits > MAX_EXTERN_MPI_BITS) { + printk("MPI: mpi too large (%u bits)\n", nbits); + return NULL; + } + if (nbytes > 0) + nbits -=3D count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8); + + nlimbs =3D DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); + val =3D mpi_alloc(nlimbs); + if (!val) + return NULL; + val->nbits =3D nbits; + val->sign =3D 0; + val->nlimbs =3D nlimbs; + + if (nbytes > 0) { + i =3D BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; + i %=3D BYTES_PER_MPI_LIMB; + for (j =3D nlimbs; j > 0; j--) { + a =3D 0; + for (; i < BYTES_PER_MPI_LIMB; i++) { + a <<=3D 8; + a |=3D *buffer++; + } + i =3D 0; + val->d[j - 1] =3D a; + } + } + return val; +} + +/**************** + * Note: It was a bad idea to use the number of limbs to allocate + * because on a alpha the limbs are large but we normally need + * integers of n bits - So we should chnage this to bits (or bytes). + * + * But mpi_alloc is used in a lot of places :-) + */ +MPI mpi_alloc(unsigned nlimbs) +{ + MPI a; + + a =3D xmalloc(struct mpi); + if (!a) + return a; + + if (nlimbs) { + a->d =3D mpi_alloc_limb_space(nlimbs); + if (!a->d) { + xfree(a); + return NULL; + } + } else { + a->d =3D NULL; + } + + a->alloced =3D nlimbs; + a->nlimbs =3D 0; + a->sign =3D 0; + a->flags =3D 0; + a->nbits =3D 0; + return a; +} + +void mpi_free(MPI a) +{ + if (!a) + return; + + if (a->flags & 4) + xfree(a->d); + else + mpi_free_limb_space(a->d); + + if (a->flags & ~7) + printk("invalid flag value in mpi\n"); + xfree(a); +} + +int mpi_cmp_ui(MPI u, unsigned long v) +{ + mpi_limb_t limb =3D v; + + mpi_normalize(u); + if (!u->nlimbs && !limb) + return 0; + if (u->sign) + return -1; + if (u->nlimbs > 1) + return 1; + + if (u->d[0] =3D=3D limb) + return 0; + else if (u->d[0] > limb) + return 1; + else + return -1; +} + +int mpi_cmp(MPI u, MPI v) +{ + mpi_size_t usize, vsize; + int cmp; + + mpi_normalize(u); + mpi_normalize(v); + usize =3D u->nlimbs; + vsize =3D v->nlimbs; + if (!u->sign && v->sign) + return 1; + if (u->sign && !v->sign) + return -1; + if (usize !=3D vsize && !u->sign && !v->sign) + return usize - vsize; + if (usize !=3D vsize && u->sign && v->sign) + return vsize - usize; + if (!usize) + return 0; + cmp =3D mpihelp_cmp(u->d, v->d, usize); + if (u->sign) + return -cmp; + return cmp; +} + +/**************** + * Sometimes we have MSL (most significant limbs) which are 0; + * this is for some reasons not good, so this function removes them. + */ +static void mpi_normalize(MPI a) +{ + for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--) + ; +} + +/**************** + * Return the number of bits in A. + */ +unsigned mpi_get_nbits(MPI a) +{ + unsigned n; + + mpi_normalize(a); + + if (a->nlimbs) { + mpi_limb_t alimb =3D a->d[a->nlimbs - 1]; + if (alimb) + n =3D count_leading_zeros(alimb); + else + n =3D BITS_PER_MPI_LIMB; + n =3D BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB; + } else + n =3D 0; + return n; +} + +int mpi_test_bit(MPI a, unsigned int n) +{ + unsigned int limbno, bitno; + mpi_limb_t limb; + + limbno =3D n / BITS_PER_MPI_LIMB; + bitno =3D n % BITS_PER_MPI_LIMB; + + if (limbno >=3D a->nlimbs) + return 0; /* too far left: this is a 0 */ + limb =3D a->d[limbno]; + return (limb & (((mpi_limb_t)1) << bitno))? 1: 0; +} diff --git a/xen/crypto/Makefile b/xen/crypto/Makefile index db29655333a3..d88374ddf221 100644 --- a/xen/crypto/Makefile +++ b/xen/crypto/Makefile @@ -1,2 +1,3 @@ obj-y +=3D rijndael.o +obj-y +=3D rsa.o obj-y +=3D vmac.o diff --git a/xen/crypto/rsa.c b/xen/crypto/rsa.c new file mode 100644 index 000000000000..eff32222fe3b --- /dev/null +++ b/xen/crypto/rsa.c @@ -0,0 +1,194 @@ +/* rsa.c + + The RSA publickey algorithm. + + Copyright (C) 2001 Niels M=C3=B6ller + + 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 +#include +#include +#include +#include + +void rsa_public_key_init(struct rsa_public_key *key) +{ + key->n =3D NULL; + key->e =3D NULL; + key->size =3D 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) =3D=3D 0 ) + return 0; + + size =3D (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 =3D 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 *buf= fer, + 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 =3D key_size - digest_size - id_size; + + memcpy(buffer + j, id, id_size); + buffer[0] =3D 0; + buffer[1] =3D 1; + buffer[j - 1] =3D 0; + + ASSERT(j >=3D 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 ::=3D + * {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[] =3D +{ + /* 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 =3D xmalloc_bytes(key_size); + if ( !buf ) + return -ENOMEM; + + ptr =3D 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 =3D 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 <=3D s < n */ + if ( mpi_cmp_ui(s, 0) < 0 || mpi_cmp(s, key->n) >=3D 0 ) + return -EINVAL; + + m1 =3D mpi_alloc(key->size / BYTES_PER_MPI_LIMB); + if ( !m1 ) + return -ENOMEM; + + /* (2) m =3D s^e mod n */ + ret =3D mpi_powm(m1, s, key->e, key->n); + if ( ret ) + goto out; + + ret =3D mpi_cmp (m, m1) ? -EINVAL : 0; + +out: + mpi_free(m1); + return ret; +} + +int rsa_sha256_verify(const struct rsa_public_key *key, + struct sha2_256_state *hash, MPI s) +{ + int ret; + MPI m; + + ret =3D pkcs1_rsa_sha256_encode(&m, key->size, hash); + if ( ret ) + return ret; + + ret =3D rsa_verify(key, m, s); + + mpi_free(m); + + return ret; +} diff --git a/xen/include/xen/mpi.h b/xen/include/xen/mpi.h new file mode 100644 index 000000000000..987971b848e8 --- /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. + * + * 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, U= SA + * + * 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 + +#include + +#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) */ + int sign; /* indicates a negative number */ + unsigned flags; /* bit 0: array must be allocated in secure memory= space */ + /* bit 1: not used */ + /* bit 2: the limb is a pointer to some m_alloced data */ + mpi_limb_t *d; /* array with the limbs */ +}; + +typedef struct mpi *MPI; + +MPI mpi_alloc(unsigned nlimbs); +void mpi_free(MPI a); +MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes); +int mpi_powm(MPI res, MPI base, MPI exp, MPI mod); +int mpi_cmp_ui(MPI u, unsigned long v); +int mpi_cmp(MPI u, MPI v); +unsigned mpi_get_nbits(MPI a); +int mpi_test_bit(MPI a, unsigned int n); + +#endif /* MPI_H */ diff --git a/xen/include/xen/rsa.h b/xen/include/xen/rsa.h new file mode 100644 index 000000000000..13b5ebe9a1e6 --- /dev/null +++ b/xen/include/xen/rsa.h @@ -0,0 +1,72 @@ +/* rsa.h + + The RSA publickey algorithm. + + Copyright (C) 2001, 2002 Niels M=C3=B6ller + + 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/. +*/ +=20 +#ifndef RSA_H +#define RSA_H + +#include +#include +#include + +/* + * This limit is somewhat arbitrary. Technically, the smallest modulo + * which makes sense at all is 15 =3D 3*5, phi(15) =3D 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 =3D 21, phi(21) =3D 12, and e = =3D + * 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, + MPI signature); + +#endif /* RSA_H */ --=20 2.49.0 From nobody Thu Dec 18 05:05:05 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1746541996; cv=none; d=zohomail.com; s=zohoarc; b=cYOeUuA7M0Im9UdzeCoRNmPZp4kiIlAm+wfxKi/+5ch3pMgGVlRsa6Pj8qIRGOSXqeMwIO1J/4FAW6C8P1OvBdNtr7RptbnQFmJIMuiGKJkNMQlOfcGYzfZMtucNoiYW3JlAAz2Ck+CXKy2B8jHEt250qS4FyldfVwbHwsrd+jg= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1746541996; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=9eYdqxJiuFt77CPqaijLabp59oslkZaSZ7TfPtEsR98=; b=d8dg20xgplRcZasdhZUvAfkpfVORLm9Jq7Gy3hUmvB8uyQRxqRdDidM0osiKO8/0/s9i9PNap4kHcOnwutWNb5BKuAeGpMce8618UBjOQ+ZjJZkNudRwlIpAlhBUeXeE2J5u2eGAfGIPIv7EvU+iMEqKpKyZV5vOqizK8F66S8s= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 17465419960581.0885855041615287; Tue, 6 May 2025 07:33:16 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.977422.1364458 (Exim 4.92) (envelope-from ) id 1uCJM1-00024A-3S; Tue, 06 May 2025 14:33:05 +0000 Received: by outflank-mailman (output) from mailman id 977422.1364458; Tue, 06 May 2025 14:33:05 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uCJM0-00023h-VT; Tue, 06 May 2025 14:33:04 +0000 Received: by outflank-mailman (input) for mailman id 977422; Tue, 06 May 2025 14:33:03 +0000 Received: from se1-gles-flk1-in.inumbo.com ([94.247.172.50] helo=se1-gles-flk1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uCJLz-0000Q4-Qm for xen-devel@lists.xen.org; Tue, 06 May 2025 14:33:03 +0000 Received: from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com [2a00:1450:4864:20::62a]) by se1-gles-flk1.inumbo.com (Halon) with ESMTPS id 03d7f82e-2a87-11f0-9ffb-bf95429c2676; Tue, 06 May 2025 16:33:02 +0200 (CEST) Received: by mail-ej1-x62a.google.com with SMTP id a640c23a62f3a-ad1d1f57a01so267621066b.2 for ; Tue, 06 May 2025 07:33:02 -0700 (PDT) Received: from rossla-pc.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad1894c0356sm711598966b.100.2025.05.06.07.33.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 May 2025 07:33:00 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 03d7f82e-2a87-11f0-9ffb-bf95429c2676 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1746541981; x=1747146781; darn=lists.xen.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=9eYdqxJiuFt77CPqaijLabp59oslkZaSZ7TfPtEsR98=; b=RG8Tko5AN79qhEwbcEXi2O/naV+30YqIqq//N68nl99Ti1IOE8+YYKc98K9sxzWRrg LKU36Zm7qnMwdJGlFt8xQ2LMtqlFqb/LG45MrpclchRLzg6D1HM8ChwjjIDXg9wpKCcV CTWPeEuZuJ40XFVBT0m8jrPON5layqLHCa6yA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746541981; x=1747146781; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=9eYdqxJiuFt77CPqaijLabp59oslkZaSZ7TfPtEsR98=; b=Ag8QwmyOhfoSAh2Lud0PkZWbuVbIczKxDZPyEOtyr5T+wGFCQ9kleih6X9VrPfdAAd zPA8X2zAZ2N+GipUmTZRDpFtVCmORAb3qMt10hmR7phgFscnVoGel4zcUecdo7EPXfyu 0HYvjaV85t2xE4IiSqbYq5/y86QtqL36VEGKxfiTYNWCnw4xQmdNFU4AXvRHGdQybarq zpV63mT0MMPFQm9Ju71gWLUp3f93cV2a45k3Rf2YJsjKWf/6ARtrTq9Td6jFXLvRajtw NyaHbQEJTQPIv5ncpG7wWSDTzpT+WNm8mattaOlxfetFD4tA1glO/z1HQMaPr6smo96Q 7Q6A== X-Gm-Message-State: AOJu0Yw7qFYDyBwXXRjo65uARfx2DlCWDlkrDeAXWQYF7fS7N3ls1EpW LnLWGGzWR1uLGMtreFDlxcbPu6VkWqlTp5WGVmRDRqaqCZ5W6GTZLr53DgONA5sQOBgew9B7YPQ = X-Gm-Gg: ASbGncuP7mizN/bmggUVhSvy47SV/rDiExgTcUH7T1vRQBayYQ8KY13Cayz0RC/SA1A /l2mBml2aAIUkz2k1TaQSUy3e5BM8/va0Aj4TEkPIhefxY0fFfdvfao03Z3LG8zVnF8kAqOKa7L Hsf/fNtyTqCArFLl6pNS3N6BYkylInxXBS3qYfo2VaDlsjcTPvkizmAM+MeBjcsV9ihj0nW8yhG KWDwPhuUePR6WvpYTB7+5nYJc5jvXuFfdLVGSfeUwbmvlH7EHbuRxsIqkRDZy81+W0HpcSQ8bFX d1gOMlVxLq6VW3pCI1ksxqwR2ETXBcdvZclPRHWy/plz7G6QsteSEQf0ctGTcsS2 X-Google-Smtp-Source: AGHT+IEiXGDQDlvPzzGzGCTZWf6cD7XqhHvy9Fd20UQ8ONMR3GNj0HjnJ8ERzNht3teHeTivvJGHcA== X-Received: by 2002:a17:907:3d8c:b0:acb:4f4a:cbd0 with SMTP id a640c23a62f3a-ad17b5ad337mr1566316466b.14.1746541981299; Tue, 06 May 2025 07:33:01 -0700 (PDT) From: Ross Lagerwall To: Xen-devel , xen-devel@lists.xenproject.org Cc: Kevin Lampis , Andrew Cooper , Anthony PERARD , Michal Orzel , Jan Beulich , Julien Grall , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= , Stefano Stabellini , Ross Lagerwall Subject: [PATCH 3/4] livepatch: Embed public key in Xen Date: Tue, 6 May 2025 15:32:15 +0100 Message-ID: <20250506143218.1782603-4-ross.lagerwall@citrix.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250506143218.1782603-1-ross.lagerwall@citrix.com> References: <20250506143218.1782603-1-ross.lagerwall@citrix.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1746541997232019000 Content-Type: text/plain; charset="utf-8" From: Kevin Lampis Make it possible to embed a public key in Xen to be used when verifying live patch payloads. Inclusion of the public key is optional. To avoid needing to include a DER / X.509 parser in the hypervisor, the public key is unpacked at build time and included in a form that is convenient for the hypervisor to consume. This is different approach from that used by Linux which embeds the entire X.509 certificate and builds in a parser for it. A suitable key can be created using openssl: openssl req -x509 -newkey rsa:2048 -keyout priv.pem -out pub.pem \ -sha256 -days 3650 -nodes \ -subj "/C=3DXX/ST=3DStateName/L=3DCityName/O=3DCompanyName/OU=3DCompany= SectionName/CN=3DCommonNameOrHostname" openssl x509 -inform PEM -in pub.pem -outform PEM -pubkey -nocert -out cryp= to/signing_key.pem Signed-off-by: Kevin Lampis Signed-off-by: Ross Lagerwall --- xen/common/Kconfig | 18 ++++++++++++++++++ xen/common/Makefile | 2 +- xen/common/livepatch.c | 41 ++++++++++++++++++++++++++++++++++++++++ xen/crypto/Makefile | 14 +++++++++++++- xen/tools/extract-key.py | 37 ++++++++++++++++++++++++++++++++++++ 5 files changed, 110 insertions(+), 2 deletions(-) create mode 100755 xen/tools/extract-key.py diff --git a/xen/common/Kconfig b/xen/common/Kconfig index 4bec78c6f267..e3e4fe2f3477 100644 --- a/xen/common/Kconfig +++ b/xen/common/Kconfig @@ -481,6 +481,24 @@ config LIVEPATCH =20 If unsure, say Y. =20 +config PAYLOAD_SIGNING + bool "Verify signed LivePatch payloads" + depends on LIVEPATCH + select CRYPTO + help + Verify signed LivePatch payloads using an RSA public key built + into the Xen hypervisor. Selecting this option requires a + public key in PEM format to be available for embedding during + the build. + +config PAYLOAD_SIG_KEY + string "File name of payload signing public key" + default "signing_key.pem" + depends on PAYLOAD_SIGNING + help + The file name of an RSA public key in PEM format to be used for + verifying signed LivePatch payloads. + config FAST_SYMBOL_LOOKUP bool "Fast symbol lookup (bigger binary)" default y diff --git a/xen/common/Makefile b/xen/common/Makefile index ece6548bb072..c75cbfa868a0 100644 --- a/xen/common/Makefile +++ b/xen/common/Makefile @@ -28,7 +28,7 @@ obj-$(CONFIG_LIVEPATCH) +=3D livepatch.o livepatch_elf.o obj-$(CONFIG_LLC_COLORING) +=3D llc-coloring.o obj-$(CONFIG_VM_EVENT) +=3D mem_access.o obj-y +=3D memory.o -obj-y +=3D mpi.o +obj-$(CONFIG_PAYLOAD_SIGNING) +=3D mpi.o obj-y +=3D multicall.o obj-y +=3D notifier.o obj-$(CONFIG_NUMA) +=3D numa.o diff --git a/xen/common/livepatch.c b/xen/common/livepatch.c index be9b7e367553..947d05671b4f 100644 --- a/xen/common/livepatch.c +++ b/xen/common/livepatch.c @@ -11,6 +11,8 @@ #include #include #include +#include +#include #include #include #include @@ -73,6 +75,12 @@ static struct livepatch_work livepatch_work; static DEFINE_PER_CPU(bool, work_to_do); static DEFINE_PER_CPU(struct tasklet, livepatch_tasklet); =20 +#ifdef CONFIG_PAYLOAD_SIGNING +/* The public key contained with Xen used to verify payload signatures. */ +extern const uint8_t xen_livepatch_key_data[]; +static struct rsa_public_key builtin_payload_key; +#endif + static int get_name(const struct xen_livepatch_name *name, char *n) { if ( !name->size || name->size > XEN_LIVEPATCH_NAME_SIZE ) @@ -2287,6 +2295,34 @@ static void cf_check livepatch_printall(unsigned cha= r key) spin_unlock(&payload_lock); } =20 +#ifdef CONFIG_PAYLOAD_SIGNING +static int __init load_builtin_payload_key(void) +{ + const uint8_t *ptr; + uint32_t len; + + rsa_public_key_init(&builtin_payload_key); + + ptr =3D xen_livepatch_key_data; + + memcpy(&len, ptr, sizeof(len)); + ptr +=3D sizeof(len); + builtin_payload_key.n =3D mpi_read_raw_data(ptr, len); + ptr +=3D len; + + memcpy(&len, ptr, sizeof(len)); + ptr +=3D sizeof(len); + builtin_payload_key.e =3D mpi_read_raw_data(ptr, len); + + return rsa_public_key_prepare(&builtin_payload_key); +} +#else +static int __init load_builtin_payload_key(void) +{ + return 0; +} +#endif + static int cf_check cpu_callback( struct notifier_block *nfb, unsigned long action, void *hcpu) { @@ -2305,6 +2341,11 @@ static struct notifier_block cpu_nfb =3D { static int __init cf_check livepatch_init(void) { unsigned int cpu; + int err; + + err =3D load_builtin_payload_key(); + if (err) + return err; =20 for_each_online_cpu ( cpu ) { diff --git a/xen/crypto/Makefile b/xen/crypto/Makefile index d88374ddf221..e81302d7cd54 100644 --- a/xen/crypto/Makefile +++ b/xen/crypto/Makefile @@ -1,3 +1,15 @@ obj-y +=3D rijndael.o -obj-y +=3D rsa.o +obj-$(CONFIG_PAYLOAD_SIGNING) +=3D rsa.o obj-y +=3D vmac.o + +obj-$(CONFIG_PAYLOAD_SIGNING) +=3D builtin_payload_key.o + +ifeq ($(CONFIG_PAYLOAD_SIGNING),y) +key_path :=3D $(srctree)/crypto/$(patsubst "%",%,$(CONFIG_PAYLOAD_SIG_KEY)) +$(obj)/builtin_payload_key.bin: $(key_path) $(srctree)/tools/extract-key.py + $(srctree)/tools/extract-key.py < $< > $@.new + $(call move-if-changed,$@.new,$@) + +$(obj)/builtin_payload_key.S: $(srctree)/tools/binfile $(obj)/builtin_payl= oad_key.bin FORCE + $(call if_changed,binfile,$(obj)/builtin_payload_key.bin xen_livepatch_ke= y_data) +endif diff --git a/xen/tools/extract-key.py b/xen/tools/extract-key.py new file mode 100755 index 000000000000..2980264b757d --- /dev/null +++ b/xen/tools/extract-key.py @@ -0,0 +1,37 @@ +#!/usr/bin/env python3 + +# SPDX-License-Identifier: GPL-2.0 + +import binascii +import struct +import sys +import subprocess +import re + +# Decode a certificate into a format suitable for embedding in Xen. + +out =3D subprocess.check_output(['openssl', 'rsa', '-pubin', '-inform', 'P= EM', + '-noout', '-text'], stdin=3Dsys.stdin, + universal_newlines=3DTrue) +combined =3D '' +for line in out.split('\n'): + line =3D line.rstrip() + if line.startswith(' '): + combined +=3D line.strip().replace(':', '') + match =3D re.match(r'Exponent: .* \(0x(.*)\)', line) + if match: + e =3D match.group(1) + +n =3D combined.lstrip('0') +if len(n) % 2 =3D=3D 1: + n =3D '0' + n +n =3D binascii.unhexlify(n) +e =3D e.lstrip('0') +if len(e) % 2 =3D=3D 1: + e =3D '0' + e +e =3D binascii.unhexlify(e) + +sys.stdout.buffer.write(struct.pack('I', len(n))) +sys.stdout.buffer.write(n) +sys.stdout.buffer.write(struct.pack('I', len(e))) +sys.stdout.buffer.write(e) --=20 2.49.0 From nobody Thu Dec 18 05:05:05 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) client-ip=192.237.175.120; envelope-from=xen-devel-bounces@lists.xenproject.org; helo=lists.xenproject.org; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass(p=reject dis=none) header.from=citrix.com ARC-Seal: i=1; a=rsa-sha256; t=1746807649; cv=none; d=zohomail.com; s=zohoarc; b=GpnAWro4/4cg6Otplw/oM4nyxThmuSUmZRQzLfXb91K6TE/hjslxH8yy2b3zPyw9vT9N/xnjG/QWUw5ev2yVcQTiwfXmdf88TMQ3KqWnugN1eA8GI1WkevsganpF4vcZvWMgf59VklaiXd2NZLLjxtKCUqM418QfhnbI2NwnDQc= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1746807649; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=F/h+K9CEtvQx2D7M8j4k6bSPS6DyqWmWkp0jPmeHtdI=; b=cTXgwK6zcYUK5F3DzuV0U+7cBAW/w+XuBg+9aczYCatBfHNFqFcoGor55HYF4XKtBmkoUvkxQt0WpnLZdOdrVq/iCUYL+Oh39CjBbfPNGiM/tJbrLs9Tw4kIr2MI4j4dKY2BQsbc76LLDDlPDKsibRiNu+MCiubcOi0q7kuqozk= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of lists.xenproject.org designates 192.237.175.120 as permitted sender) smtp.mailfrom=xen-devel-bounces@lists.xenproject.org; dmarc=pass header.from= (p=reject dis=none) Return-Path: Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) by mx.zohomail.com with SMTPS id 1746807649730573.7414946888146; Fri, 9 May 2025 09:20:49 -0700 (PDT) Received: from list by lists.xenproject.org with outflank-mailman.980234.1366700 (Exim 4.92) (envelope-from ) id 1uDQSc-0007iQ-Fk; Fri, 09 May 2025 16:20:30 +0000 Received: by outflank-mailman (output) from mailman id 980234.1366700; Fri, 09 May 2025 16:20:30 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uDQSc-0007iJ-D1; Fri, 09 May 2025 16:20:30 +0000 Received: by outflank-mailman (input) for mailman id 980234; Fri, 09 May 2025 16:20:29 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1uDQSb-0007iD-FD for xen-devel@lists.xenproject.org; Fri, 09 May 2025 16:20:29 +0000 Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com [2a00:1450:4864:20::52b]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 85792ee8-2cf1-11f0-9eb4-5ba50f476ded; Fri, 09 May 2025 18:20:28 +0200 (CEST) Received: by mail-ed1-x52b.google.com with SMTP id 4fb4d7f45d1cf-5fbfa0a7d2cso3894639a12.1 for ; Fri, 09 May 2025 09:20:28 -0700 (PDT) Received: from rossla-pc.eng.citrite.net ([185.25.67.249]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad21934de87sm171631166b.74.2025.05.09.09.20.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 09 May 2025 09:20:27 -0700 (PDT) X-Outflank-Mailman: Message body and most headers restored to incoming version X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 85792ee8-2cf1-11f0-9eb4-5ba50f476ded DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=citrix.com; s=google; t=1746807628; x=1747412428; darn=lists.xenproject.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=F/h+K9CEtvQx2D7M8j4k6bSPS6DyqWmWkp0jPmeHtdI=; b=fPc/HuYW00vSiUb8DCdI+r8gmxm9MofkzL8rb9B2FKZD/3zsUSXfRks9ayugxcjGGN /zzb4lTfmjbsguUc+8WE3DMW9/sN+3x1YPzV2GAY746EjAa37OhX6AgvEMG+qJ8IG9KD zKCTZzFMkcPPH445tJGfmWYqr5ccrYhsNQWwc= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746807628; x=1747412428; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=F/h+K9CEtvQx2D7M8j4k6bSPS6DyqWmWkp0jPmeHtdI=; b=qP0WHo6etUdK3vCAyQ8qgr+Z8isCaHEyUhQ+LzlOYDaer7eqAGbr0L7f/y2Ygao+C9 8ua0LolZE25SGcoRTqVZrqIFgI6hTYmxVXzGIs0PxpAlwzSougtnO1qmbisXTD+xpvaG eCs8gJkmECuYSYoVwT7v6VCrNV2Vs5IdVJW+h058Nkgco/TBM3uf+EZQ0GCkIEL6j9jj HFQXM9JpPMpdcjRZI3t4Gd1l/7EQ7AYROkle6Tb+bu4hRlxycZ+baVa2VyiS54ULdPbc 2UmOx7VjeotOjHL5B3yjoTQuVZIU44KcHocu3Jhn5vDchMLQdxH8Wa6QFA1yCzhf2PCX HINQ== X-Gm-Message-State: AOJu0YzWx3HmXG3kZEGARLoykYXdEBOy/pXaBJSbarKUw4KnN7JGk1/e jCOuzC1j/+T1BHf7Zd8IJqZSqwdi0YNOkBmdZJVKbqOpKcD8TrZ72eVCQLEs/OILvXUspuHqivU = X-Gm-Gg: ASbGncvDsq8S55BY/5LzhXE80cNcivNyl7otaqbQr0H/ywnr1Pvj9JWUOHX8rBiTP5p LGRDRPlLgJLGsg76wSoiZttmlwnZvC9shRGPswVwVqmElas9syNvrwR1lxe4X3RPcGjT8zQZmuA OfXgeULnOQSbTPWAyhn0Xj6U9YbYTd6Frh2z+Lf0JJPJcg8yqqkxjUs4+cAagi8V0DNDwNqsG26 FZtJ3yi9yueLE5qhN+Q7hx6b0hlMNO2s9Vr3/7Whz/zZtkhvm70P3AtZOZ2TDqUBs5noUShxYbn HCWej0rwLzE3wzEglrNMMnzCDFU8UUnku823hnO/UJO0K1Swz01q38c9uSkVmxWoVmGWFHzsFXk = X-Google-Smtp-Source: AGHT+IFdxgMF1hWlw7F8AdxydqCoeJDiOqkj3myWL0NwNW0Guhy93AI+I59zq4XemUrcQMG84YIQVA== X-Received: by 2002:a17:906:6a88:b0:ad2:1d12:fd68 with SMTP id a640c23a62f3a-ad21d1301c2mr259337066b.48.1746807627750; Fri, 09 May 2025 09:20:27 -0700 (PDT) From: Ross Lagerwall To: xen-devel@lists.xenproject.org Cc: Jennifer Herbert , =?UTF-8?q?Roger=20Pau=20Monn=C3=A9?= , Ross Lagerwall Subject: [PATCH 4/4] livepatch: Verify livepatch signatures Date: Fri, 9 May 2025 17:20:16 +0100 Message-ID: <20250509162016.45931-1-ross.lagerwall@citrix.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250506143218.1782603-1-ross.lagerwall@citrix.com> References: <20250506143218.1782603-1-ross.lagerwall@citrix.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ZohoMail-DKIM: pass (identity @citrix.com) X-ZM-MESSAGEID: 1746807650926019000 Content-Type: text/plain; charset="utf-8" From: Jennifer Herbert Verify livepatch signatures against the embedded public key in Xen. Failing to verify does not prevent the livepatch from being loaded. In future, this will be changed for certain cases (e.g. when Secure Boot is enabled). Signed-off-by: Jennifer Herbert Signed-off-by: Ross Lagerwall --- xen/common/livepatch.c | 134 ++++++++++++++++++++++++++++++++ xen/common/livepatch_elf.c | 55 +++++++++++++ xen/include/xen/livepatch.h | 5 ++ xen/include/xen/livepatch_elf.h | 18 +++++ 4 files changed, 212 insertions(+) diff --git a/xen/common/livepatch.c b/xen/common/livepatch.c index 947d05671b4f..dd3532b7bbee 100644 --- a/xen/common/livepatch.c +++ b/xen/common/livepatch.c @@ -81,6 +81,9 @@ extern const uint8_t xen_livepatch_key_data[]; static struct rsa_public_key builtin_payload_key; #endif =20 +static int check_signature(const struct livepatch_elf *elf, void *raw, + size_t size); + static int get_name(const struct xen_livepatch_name *name, char *n) { if ( !name->size || name->size > XEN_LIVEPATCH_NAME_SIZE ) @@ -1164,6 +1167,8 @@ static int load_payload_data(struct payload *payload,= void *raw, size_t len) if ( rc ) goto out; =20 + check_signature(&elf, raw, len); + rc =3D move_payload(payload, &elf); if ( rc ) goto out; @@ -1204,6 +1209,135 @@ static int load_payload_data(struct payload *payloa= d, void *raw, size_t len) return rc; } =20 +#ifdef CONFIG_PAYLOAD_SIGNING + +#define MAX_SIG_NOTE_SIZE 1024 + +struct payload_signature { + uint16_t version; + uint8_t algo; /* Public-key crypto algorithm */ + uint8_t hash; /* Digest algorithm */ + uint32_t sig_len; /* Length of signature data */ +}; + +static int check_rsa_sha256_signature(void *data, size_t datalen, + void *sig, uint32_t siglen) +{ + struct sha2_256_state hash; + MPI s; + int rc; + + s =3D mpi_read_raw_data(sig, siglen); + if ( !s ) + { + printk(XENLOG_ERR LIVEPATCH "Failed to mpi_read_raw_data\n"); + return -ENOMEM; + } + + sha2_256_init(&hash); + sha2_256_update(&hash, data, datalen); + + rc =3D rsa_sha256_verify(&builtin_payload_key, &hash, s); + if ( rc ) + printk(XENLOG_ERR LIVEPATCH "rsa_sha256_verify failed: %d\n", rc); + + mpi_free(s); + + return rc; +} + +static int check_signature(const struct livepatch_elf *elf, void *raw, + size_t size) +{ + static const char notename[] =3D "Xen"; + struct payload_signature *siginfo; + livepatch_elf_note note; + size_t nsize; + int rc; + + rc =3D livepatch_elf_note_by_names(elf, ELF_XEN_SIGNATURE, notename, 0, + ¬e); + if ( rc ) + { + dprintk(XENLOG_DEBUG, LIVEPATCH "%s: Signature not present\n", + elf->name); + return rc; + } + + /* We expect only one signature, find a second is an error! */ + rc =3D livepatch_elf_next_note_by_name(notename, 0, ¬e); + if ( rc !=3D -ENOENT ) + { + if ( rc ) + { + printk(XENLOG_ERR LIVEPATCH + "Error while checking for notes! err =3D %d\n", rc); + return rc; + } + else + { + printk(XENLOG_ERR LIVEPATCH + "Error, found second signature note! There can be only = one!\n"); + return -EINVAL; + } + } + + nsize =3D note.size; + if ( nsize <=3D sizeof(*siginfo) || nsize >=3D MAX_SIG_NOTE_SIZE ) + { + printk(XENLOG_ERR LIVEPATCH "Invalid signature note size: %zu\n", + nsize); + return -EINVAL; + } + + siginfo =3D xmalloc_bytes(nsize); + if ( !siginfo ) + return -ENOMEM; + + memcpy(siginfo, note.data, nsize); + + if ( siginfo->version !=3D SIGNATURE_SUPPORTED_VERION ) + { + printk(XENLOG_ERR LIVEPATCH "Bad signature version %u\n", siginfo->= version); + rc =3D -EINVAL; + goto out; + } + + if ( siginfo->sig_len =3D=3D 0 || + nsize - sizeof(*siginfo) < siginfo->sig_len ) + { + printk(XENLOG_ERR LIVEPATCH + "Payload signature size bad. ns=3D%zu si=3D%u\n", + nsize, siginfo->sig_len); + rc =3D -EINVAL; + goto out; + } + + if ( siginfo->algo !=3D SIGNATURE_ALGORITHM_RSA || + siginfo->hash !=3D SIGNATURE_HASH_SHA256 ) + { + printk(XENLOG_ERR LIVEPATCH "Bad payload signature: v:%u, a:%u, h:= %u\n", + siginfo->version, siginfo->algo, siginfo->hash); + rc =3D -EINVAL; + goto out; + } + + /* Remove signature from data, as can't be verified with it. */ + memset((void *)note.data + sizeof(*siginfo), 0, siginfo->sig_len); + rc =3D check_rsa_sha256_signature(raw, size, siginfo + 1, siginfo->sig= _len); + +out: + xfree(siginfo); + return rc; +} +#else +static int check_signature(const struct livepatch_elf *elf, void *raw, + size_t size) +{ + return -EINVAL; +} +#endif + static int livepatch_upload(struct xen_sysctl_livepatch_upload *upload) { struct payload *data, *found; diff --git a/xen/common/livepatch_elf.c b/xen/common/livepatch_elf.c index 25ce1bd5a0ad..b27c4524611d 100644 --- a/xen/common/livepatch_elf.c +++ b/xen/common/livepatch_elf.c @@ -23,6 +23,61 @@ livepatch_elf_sec_by_name(const struct livepatch_elf *el= f, return NULL; } =20 +int livepatch_elf_note_by_names(const struct livepatch_elf *elf, + const char *sec_name, const char *note_nam= e, + const unsigned int type, + livepatch_elf_note *note) +{ + const struct livepatch_elf_sec *sec =3D livepatch_elf_sec_by_name(elf, + sec_n= ame); + if ( !sec ) + return -ENOENT; + + note->end =3D sec->addr + sec->sec->sh_size; + note->next =3D sec->addr; + + return livepatch_elf_next_note_by_name(note_name, type, note); +} + +int livepatch_elf_next_note_by_name(const char *note_name, + const unsigned int type, + livepatch_elf_note *note) +{ + const Elf_Note *pkd_note =3D note->next; + size_t notenamelen =3D strlen(note_name) + 1; + size_t note_hd_size; + size_t note_size; + size_t remaining; + + while ( (void *)pkd_note < note->end ) + { + + remaining =3D note->end - (void *)pkd_note; + if ( remaining < sizeof(livepatch_elf_note) ) + return -EINVAL; + + note_hd_size =3D sizeof(Elf_Note) + ((pkd_note->namesz + 3) & ~0x= 3); + note_size =3D note_hd_size + ((pkd_note->descsz + 3) & ~0x3); + if ( remaining < note_size ) + return -EINVAL; + + if ( notenamelen =3D=3D pkd_note->namesz && + !memcmp(note_name, (const void *) pkd_note + sizeof(Elf_Note= ), + notenamelen) && + (type =3D=3D -1 || pkd_note->type =3D=3D type) ) + { + note->size =3D pkd_note->descsz; + note->type =3D pkd_note->type; + note->data =3D (void *)pkd_note + note_hd_size; + note->next =3D (void *)pkd_note + note_size; + return 0; + } + pkd_note =3D (void *)pkd_note + note_size; + } + + return -ENOENT; +} + static int elf_verify_strtab(const struct livepatch_elf_sec *sec) { const Elf_Shdr *s; diff --git a/xen/include/xen/livepatch.h b/xen/include/xen/livepatch.h index d074a5bebecc..23bef334d24f 100644 --- a/xen/include/xen/livepatch.h +++ b/xen/include/xen/livepatch.h @@ -38,6 +38,7 @@ struct xen_sysctl_livepatch_op; #define ELF_LIVEPATCH_DEPENDS ".livepatch.depends" #define ELF_LIVEPATCH_XEN_DEPENDS ".livepatch.xen_depends" #define ELF_BUILD_ID_NOTE ".note.gnu.build-id" +#define ELF_XEN_SIGNATURE ".note.Xen.signature" #define ELF_LIVEPATCH_LOAD_HOOKS ".livepatch.hooks.load" #define ELF_LIVEPATCH_UNLOAD_HOOKS ".livepatch.hooks.unload" #define ELF_LIVEPATCH_PREAPPLY_HOOK ".livepatch.hooks.preapply" @@ -49,6 +50,10 @@ struct xen_sysctl_livepatch_op; /* Arbitrary limit for payload size and .bss section size. */ #define LIVEPATCH_MAX_SIZE MB(2) =20 +#define SIGNATURE_SUPPORTED_VERION 1 +#define SIGNATURE_ALGORITHM_RSA 0 +#define SIGNATURE_HASH_SHA256 0 + struct livepatch_symbol { const char *name; unsigned long value; diff --git a/xen/include/xen/livepatch_elf.h b/xen/include/xen/livepatch_el= f.h index 842111e14518..04611bac410e 100644 --- a/xen/include/xen/livepatch_elf.h +++ b/xen/include/xen/livepatch_elf.h @@ -39,6 +39,16 @@ struct livepatch_elf { unsigned int symtab_idx; }; =20 +typedef struct { + uint32_t size; /* Note size */ + uint32_t type; /* Note type */ + const void *data; /* Pointer to note */ + + /* Private */ + const Elf_Note *next; + const void *end; +} livepatch_elf_note; + const struct livepatch_elf_sec * livepatch_elf_sec_by_name(const struct livepatch_elf *elf, const char *name); @@ -48,6 +58,14 @@ void livepatch_elf_free(struct livepatch_elf *elf); int livepatch_elf_resolve_symbols(struct livepatch_elf *elf); int livepatch_elf_perform_relocs(struct livepatch_elf *elf); =20 +int livepatch_elf_note_by_names(const struct livepatch_elf *elf, + const char *sec_name, const char *note_nam= e, + const unsigned int type, + livepatch_elf_note *note); +int livepatch_elf_next_note_by_name(const char *note_name, + const unsigned int type, + livepatch_elf_note *note); + static inline bool livepatch_elf_ignore_section(const Elf_Shdr *sec) { return !(sec->sh_flags & SHF_ALLOC); --=20 2.49.0