aboutsummaryrefslogtreecommitdiffstats
path: root/src/tests
Commit message (Collapse)AuthorAgeFilesLines
* [test] Add generic tests for elliptic curve point multiplicationMichael Brown2025-01-222-0/+153
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Allow for relaxed Montgomery reductionMichael Brown2024-12-181-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Classic Montgomery reduction involves a single conditional subtraction to ensure that the result is strictly less than the modulus. When performing chains of Montgomery multiplications (potentially interspersed with additions and subtractions), it can be useful to work with values that are stored modulo some small multiple of the modulus, thereby allowing some reductions to be elided. Each addition and subtraction stage will increase this running multiple, and the following multiplication stages can be used to reduce the running multiple since the reduction carried out for multiplication products is generally strong enough to absorb some additional bits in the inputs. This approach is already used in the x25519 code, where multiplication takes two 258-bit inputs and produces a 257-bit output. Split out the conditional subtraction from bigint_montgomery() and provide a separate bigint_montgomery_relaxed() for callers who do not require immediate reduction to within the range of the modulus. Modular exponentiation could potentially make use of relaxed Montgomery multiplication, but this would require R>4N, i.e. that the two most significant bits of the modulus be zero. For both RSA and DHE, this would necessitate extending the modulus size by one element, which would negate any speed increase from omitting the conditional subtractions. We therefore retain the use of classic Montgomery reduction for modular exponentiation, apart from the final conversion out of Montgomery form. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Calculate inverse of modulus on demand in bigint_montgomery()Michael Brown2024-12-161-9/+2
| | | | | | | | | | | | | Reduce the number of parameters passed to bigint_montgomery() by calculating the inverse of the modulus modulo the element size on demand. Cache the result, since Montgomery reduction will be used repeatedly with the same modulus value. In all currently supported algorithms, the modulus is a public value (or a fixed value defined by specification) and so this non-constant timing does not leak any private information. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Remove obsolete bigint_mod_multiply()Michael Brown2024-11-281-188/+0
| | | | | | | | | | There is no further need for a standalone modular multiplication primitive, since the only consumer is modular exponentiation (which now uses Montgomery multiplication instead). Remove the now obsolete bigint_mod_multiply(). Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Use Montgomery reduction for modular exponentiationMichael Brown2024-11-281-2/+28
| | | | | | | | | | | | | | | | | Speed up modular exponentiation by using Montgomery reduction rather than direct modular reduction. Montgomery reduction in base 2^n requires the modulus to be coprime to 2^n, which would limit us to requiring that the modulus is an odd number. Extend the implementation to include support for exponentiation with even moduli via Garner's algorithm as described in "Montgomery reduction with even modulus" (Koç, 1994). Since almost all use cases for modular exponentation require a large prime (and hence odd) modulus, the support for even moduli could potentially be removed in future. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add bigint_montgomery() to perform Montgomery reductionMichael Brown2024-11-271-0/+76
| | | | | | | | | | Montgomery reduction is substantially faster than direct reduction, and is better suited for modular exponentiation operations. Add bigint_montgomery() to perform the Montgomery reduction operation (often referred to as "REDC"), along with some test vectors. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Use inverse size as effective size for bigint_mod_invert()Michael Brown2024-11-271-5/+10
| | | | | | | | | | | | Montgomery reduction requires only the least significant element of an inverse modulo 2^k, which in turn depends upon only the least significant element of the invertend. Use the inverse size (rather than the invertend size) as the effective size for bigint_mod_invert(). This eliminates around 97% of the loop iterations for a typical 2048-bit RSA modulus. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Eliminate temporary working space for bigint_mod_invert()Michael Brown2024-11-271-5/+19
| | | | | | | | | | With a slight modification to the algorithm to ignore bits of the residue that can never contribute to the result, it is possible to reuse the as-yet uncalculated portions of the inverse to hold the residue. This removes the requirement for additional temporary working space. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Eliminate temporary working space for bigint_reduce()Michael Brown2024-11-261-44/+40
| | | | | | | | | | | | | | | | Direct modular reduction is expected to be used in situations where there is no requirement to retain the original (unreduced) value. Modify the API for bigint_reduce() to reduce the value in place, (removing the separate result buffer), impose a constraint that the modulus and value have the same size, and require the modulus to be passed in writable memory (to allow for scaling in place). This removes the requirement for additional temporary working space. Reverse the order of arguments so that the constant input is first, to match the usage pattern for bigint_add() et al. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Expose carry flag from big integer addition and subtractionMichael Brown2024-11-261-23/+45
| | | | | | | | Expose the effective carry (or borrow) out flag from big integer addition and subtraction, and use this to elide an explicit bit test when performing x25519 reduction. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add bigint_mod_invert() to calculate inverse modulo a power of twoMichael Brown2024-10-211-0/+61
| | | | | | | | | | | | | | | | | Montgomery multiplication requires calculating the inverse of the modulus modulo a larger power of two. Add bigint_mod_invert() to calculate the inverse of any (odd) big integer modulo an arbitrary power of two, using a lightly modified version of the algorithm presented in "A New Algorithm for Inversion mod p^k (Koç, 2017)". The power of two is taken to be 2^k, where k is the number of bits available in the big integer representation of the invertend. The inverse modulo any smaller power of two may be obtained simply by masking off the relevant bits in the inverse. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Separate out bigint_reduce() from bigint_mod_multiply()Michael Brown2024-10-151-0/+86
| | | | | | | | | | | Faster modular multiplication algorithms such as Montgomery multiplication will still require the ability to perform a single direct modular reduction. Neaten up the implementation of direct reduction and split it out into a separate bigint_reduce() function, complete with its own unit tests. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Rename bigint_rol()/bigint_ror() to bigint_shl()/bigint_shr()Michael Brown2024-10-071-24/+24
| | | | | | | | | | | The big integer shift operations are misleadingly described as rotations since the original x86 implementations are essentially trivial loops around the relevant rotate-through-carry instruction. The overall operation performed is a shift rather than a rotation. Update the function names and descriptions to reflect this. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Eliminate temporary carry space for big integer multiplicationMichael Brown2024-09-271-9/+3
| | | | | | | | | | | | An n-bit multiplication product may be added to up to two n-bit integers without exceeding the range of a (2n)-bit integer: (2^n - 1)*(2^n - 1) + (2^n - 1) + (2^n - 1) = 2^(2n) - 1 Exploit this to perform big integer multiplication in constant time without requiring the caller to provide temporary carry space. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Use constant-time big integer multiplicationMichael Brown2024-09-231-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Big integer multiplication currently performs immediate carry propagation from each step of the long multiplication, relying on the fact that the overall result has a known maximum value to minimise the number of carries performed without ever needing to explicitly check against the result buffer size. This is not a constant-time algorithm, since the number of carries performed will be a function of the input values. We could make it constant-time by always continuing to propagate the carry until reaching the end of the result buffer, but this would introduce a large number of redundant zero carries. Require callers of bigint_multiply() to provide a temporary carry storage buffer, of the same size as the result buffer. This allows the carry-out from the accumulation of each double-element product to be accumulated in the temporary carry space, and then added in via a single call to bigint_add() after the multiplication is complete. Since the structure of big integer multiplication is identical across all current CPU architectures, provide a single shared implementation of bigint_multiply(). The architecture-specific operation then becomes the multiplication of two big integer elements and the accumulation of the double-element product. Note that any intermediate carry arising from accumulating the lower half of the double-element product may be added to the upper half of the double-element product without risk of overflow, since the result of multiplying two n-bit integers can never have all n bits set in its upper half. This simplifies the carry calculations for architectures such as RISC-V and LoongArch64 that do not have a carry flag. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Add tests for 64-bit logical and arithmetic shiftsMichael Brown2024-09-151-0/+117
| | | | | | | For some 32-bit CPUs, we need to provide implementations of 64-bit shifts as libgcc helper functions. Add test cases to cover these. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Add CMS decryption self-testsMichael Brown2024-08-291-2/+353
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Update CMS self-test terminologyMichael Brown2024-08-281-59/+58
| | | | | | | | Generalise CMS self-test data structure and macro names to refer to "messages" rather than "signatures", in preparation for adding image decryption tests. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Remove the concept of a public-key algorithm reusable contextMichael Brown2024-08-211-99/+43
| | | | | | | | | | | | | | | | | | | | | | | Instances of cipher and digest algorithms tend to get called repeatedly to process substantial amounts of data. This is not true for public-key algorithms, which tend to get called only once or twice for a given key. Simplify the public-key algorithm API so that there is no reusable algorithm context. In particular, this allows callers to omit the error handling currently required to handle memory allocation (or key parsing) errors from pubkey_init(), and to omit the cleanup calls to pubkey_final(). This change does remove the ability for a caller to distinguish between a verification failure due to a memory allocation failure and a verification failure due to a bad signature. This difference is not material in practice: in both cases, for whatever reason, the caller was unable to verify the signature and so cannot proceed further, and the cause of the error will be visible to the user via the return status code. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Generalise public-key algorithm tests and use okx()Michael Brown2024-08-183-309/+336
| | | | | | | | Generalise the existing support for performing RSA public-key encryption, decryption, signature, and verification tests, and update the code to use okx() for neater reporting of test results. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Pass asymmetric keys as ASN.1 cursorsMichael Brown2024-08-182-60/+45
| | | | | | | | | | | Asymmetric keys are invariably encountered within ASN.1 structures such as X.509 certificates, and the various large integers within an RSA key are themselves encoded using ASN.1. Simplify all code handling asymmetric keys by passing keys as a single ASN.1 cursor, rather than separate data and length pointers. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Generalise cms_signature to cms_messageMichael Brown2024-08-141-12/+12
| | | | | | | | | | | | | | | | | There is some exploitable similarity between the data structures used for representing CMS signatures and CMS encryption keys. In both cases, the CMS message fundamentally encodes a list of participants (either message signers or message recipients), where each participant has an associated certificate and an opaque octet string representing the signature or encrypted cipher key. The ASN.1 structures are not identical, but are sufficiently similar to be worth exploiting: for example, the SignerIdentifier and RecipientIdentifier data structures are defined identically. Rename data structures and functions, and add the concept of a CMS message type. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Pass image as parameter to CMS functionsMichael Brown2024-08-131-25/+61
| | | | | | | | | | | | | The cms_signature() and cms_verify() functions currently accept raw data pointers. This will not be possible for cms_decrypt(), which will need the ability to extract fragments of ASN.1 data from a potentially large image. Change cms_signature() and cms_verify() to accept an image as an input parameter, and move the responsibility for setting the image trust flag within cms_verify() since that now becomes a more natural fit. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [libc] Add stpcpy()Michael Brown2024-05-311-0/+18
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Add test cases for editable stringsMichael Brown2024-04-172-0/+199
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [settings] Expose current working URI and directory URI via settingsMichael Brown2024-03-191-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | iPXE maintains a concept of a current working URI, which is used when resolving relative URIs and allows scripts to download files using URIs relative to the script itself. There are situations in which it is valuable for a script to be able to access the URI explicitly as a string, not just implicitly as a base URI for subsequent downloads. For example, when booting a Fedora installer, the "inst.repo" command-line parameter may be used to pass the URI of the repository to the installer. Expose the current working URI as ${cwuri}. Since relative URIs may be constructed as strings only from a directory URI (not from a full URI), also expose the current working directory URI as ${cwduri}. This feature may be used as e.g. #!ipxe echo Booting from ${cwuri} prompt -k 0x197e -t 2000 Press F12 to install Fedora... || exit kernel images/pxeboot/vmlinux inst.repo=${cwduri} initrd images/pxeboot/initrd.img boot Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [settings] Add parsing for UUID and GUID settings typesMichael Brown2024-02-291-3/+11
| | | | | | | | | | | | The ":uuid" and ":guid" settings types are currently format-only: it is possible to format a setting as a UUID (via e.g. "show foo:uuid") but it is not currently possible to parse a string into a UUID setting (via e.g. "set foo:uuid 406343fe-998b-44be-8a28-44ca38cb202b"). Use uuid_aton() to implement parsing of these settings types, and add appropriate test cases for both. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [uuid] Add uuid_aton() to parse a UUID from a stringMichael Brown2024-02-292-0/+157
| | | | | | | | | | | | | Add uuid_aton() to parse a UUID value from a string (analogous to inet_aton(), inet6_aton(), sock_aton(), etc), treating it as a 32-digit hex string with optional hyphen separators. The placement of the separators is not checked: each byte within the hex string may be separated by a hyphen, or not separated at all. Add dedicated self-tests for UUID parsing and formatting (already partially covered by the ":uuid" and ":guid" settings self-tests). Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add implementation of MS-CHAPv2 authenticationmschapv2Michael Brown2024-02-222-0/+145
| | | | | | | | Add an implementation of the authentication portions of the MS-CHAPv2 algorithm as defined in RFC 2759, along with the single test vector provided therein. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add x509_is_self_signed() helper functionMichael Brown2024-02-151-0/+4
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add x509_truncate() to truncate a certificate chainMichael Brown2024-02-141-0/+13
| | | | | | | | | | | Downloading a cross-signed certificate chain to partially replace (rather than simply extend) an existing chain will require the ability to discard all certificates after a specified link in the chain. Extract the relevant logic from x509_free_chain() and expose it separately as x509_truncate(). Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [list] Add list_for_each_entry_safe_continue()Michael Brown2024-02-141-0/+32
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [list] Add list_is_head_entry()Michael Brown2024-02-141-0/+16
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add implementation of the DES cipherMichael Brown2024-02-072-0/+899
| | | | | | | | | | | | | | The DES block cipher dates back to the 1970s. It is no longer relevant for use in TLS cipher suites, but it is still used by the MS-CHAPv2 authentication protocol which remains unfortunately common for 802.1x port authentication. Add an implementation of the DES block cipher, complete with the extremely comprehensive test vectors published by NBS (the precursor to NIST) in the form of an utterly adorable typewritten and hand-drawn paper document. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Remove dummy initialisation vector for ECB-mode AES testsMichael Brown2024-02-071-8/+3
| | | | | | | | | | | | A block cipher in ECB mode has no concept of an initialisation vector, and any data provided to cipher_setiv() for an ECB cipher will be ignored. There is no requirement within our cipher algorithm abstraction for a dummy initialisation vector to be provided. Remove the entirely spurious dummy 16-byte initialisation vector from the ECB test cases. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Check for all-zeros result from X25519 key exchangeMichael Brown2024-01-301-6/+35
| | | | | | | | | | | | | RFC7748 states that it is entirely optional for X25519 Diffie-Hellman implementations to check whether or not the result is the all-zero value (indicating that an attacker sent a malicious public key with a small order). RFC8422 states that implementations in TLS must abort the handshake if the all-zero value is obtained. Return an error if the all-zero value is obtained, so that the TLS code will not require knowledge specific to the X25519 curve. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add X25519 key exchange algorithmMichael Brown2024-01-192-0/+572
| | | | | | | | | | | | | | | | | Add an implementation of the X25519 key exchange algorithm as defined in RFC7748. This implementation is inspired by and partially based upon the paper "Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography" by Martin Kleppmann, available for download from https://www.cl.cam.ac.uk/teaching/2122/Crypto/curve25519.pdf The underlying modular addition, subtraction, and multiplication operations are completely redesigned for substantially improved efficiency compared to the TweetNaCl implementation studied in that paper (approximately 5x-10x faster and with 70% less memory usage). Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [loong64] Replace broken big integer arithmetic implementationsMichael Brown2024-01-191-0/+9
| | | | | | | | | | | | | The slightly incomprehensible LoongArch64 implementation for bigint_subtract() is observed to produce incorrect results for some input values. Replace the suspicious LoongArch64 implementations of bigint_add(), bigint_subtract(), bigint_rol() and bigint_ror(), and add a test case for a subtraction that was producing an incorrect result with the previous implementation. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add bigint_swap() to conditionally swap big integersMichael Brown2024-01-191-0/+54
| | | | | | | Add a helper function bigint_swap() that can be used to conditionally swap a pair of big integers in constant time. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add bigint_copy() as a convenient wrapper macroMichael Brown2024-01-191-0/+10
| | | | | | | | | | | Big integers may be efficiently copied using bigint_shrink() (which will always copy only the size of the destination integer), but this is potentially confusing to a reader of the code. Provide bigint_copy() as an alias for bigint_shrink() so that the intention of the calling code may be more obvious. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Allow multiplicand and multiplier to differ in sizeMichael Brown2024-01-161-15/+24
| | | | | | | | | | | Big integer multiplication is currently used only as part of modular exponentiation, where both multiplicand and multiplier will be the same size. Relax this requirement to allow for the use of big integer multiplication in other contexts. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [crypto] Add support for PKCS#8 private key formatMichael Brown2023-06-021-1/+59
| | | | Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [params] Allow for arbitrary HTTP request headers to be specifiedMichael Brown2023-03-011-1/+12
| | | | | | | | | | | Extend the request parameter mechanism to allow for arbitrary HTTP headers to be specified via e.g.: params param --header Referer http://www.example.com imgfetch http://192.168.0.1/script.ipxe##params Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [params] Rename "form parameter" to "request parameter"Michael Brown2023-03-011-11/+11
| | | | | | | | Prepare for the parameter mechanism to be generalised to specifying request parameters that are passed via mechanisms other than an application/x-www-form-urlencoded form. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [rng] Allow for entropy sources that fail during startup testsMichael Brown2023-02-201-6/+20
| | | | | | | | | Provide per-source state variables for the repetition count test and adaptive proportion test, to allow for the situation in which an entropy source can be enabled but then fails during the startup tests, thereby requiring an alternative entropy source to be used. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [test] Include build architecture in test suite bannerMichael Brown2023-02-061-1/+1
| | | | | | | | | | | The test suites for the various architectures are often run back to back, and there is currently nothing to visually distinguish one test run from another. Include the architecture name within the self-test startup banner, to aid in visual identification of test results. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [tests] Verify ability to sleep the CPUnaptestMichael Brown2023-01-312-0/+54
| | | | | | | | | | | | | The self-test suite does not currently ever attempt to sleep the CPU. This is an operation that may fail (e.g. by attempting to execute a privileged instruction while running as a Linux userspace binary, or by halting the CPU with all interrupts disabled). Add a trivial self-test to exercise the ability to sleep the CPU without crashing or halting forever. Inspired-by: Xiaotian Wu <wuxiaotian@loongson.cn> Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [netdevice] Separate concept of scope ID from network device name indexMichael Brown2023-01-141-2/+2
| | | | | | | | | | | | | | | | | | | | | The network device index currently serves two purposes: acting as a sequential index for network device names ("net0", "net1", etc), and acting as an opaque unique integer identifier used in socket address scope IDs. There is no particular need for these usages to be linked, and it can lead to situations in which devices are named unexpectedly. For example: if a system has two network devices "net0" and "net1", a VLAN is created as "net1-42", and then a USB NIC is connected, then the USB NIC will be named "net3" rather than the expected "net2" since the VLAN device "net1-42" will have consumed an index. Separate the usages: rename the "index" field to "scope_id" (matching its one and only use case), and assign the name without reference to the scope ID by finding the first unused name. For consistency, assign the scope ID by similarly finding the first unused scope ID. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [tests] Verify ability to perform in-place encryption and decryptionMichael Brown2022-11-101-4/+6
| | | | | | | | | | TLS relies upon the ability of ciphers to perform in-place decryption, in order to avoid allocating additional I/O buffers for received data. Add verification of in-place encryption and decryption to the cipher self-tests. Signed-off-by: Michael Brown <mcb30@ipxe.org>
* [tests] Verify ability to reset cipher initialisation vectorMichael Brown2022-11-091-0/+38
| | | | | | | | | | TLS relies upon the ability to reuse a cipher by resetting only the initialisation vector while reusing the existing key. Add verification of resetting the initialisation vector to the cipher self-tests. Signed-off-by: Michael Brown <mcb30@ipxe.org>
generated by cgit (git 2.34.1) at 2025-02-24 08:21:42 +0000