1
0
mirror of https://git.tartarus.org/simon/putty.git synced 2025-01-09 17:38:00 +00:00
Commit Graph

59 Commits

Author SHA1 Message Date
Simon Tatham
f6f9848465 Add support for HMAC-SHA512.
I saw a post on comp.security.ssh just now where someone had
encountered an SSH server that would _only_ speak that, which makes it
worth bothering to implement.

The totally obvious implementation works, and passes the test cases
from RFC 6234.

(cherry picked from commit b77e985513)
2023-04-23 13:24:19 +01:00
Jacob Nevins
b760a2a040 Use correct date in cert check error.
When a host certificate was used outside its valid date range, we were
displaying the current time where we meant to show the relevant bound of
the validity range.

(cherry picked from commit 68db3d195d)
2023-04-19 14:19:34 +01:00
Simon Tatham
2222cd104d AES-GCM NEON: cope with missing vaddq_p128.
In some compilers (I'm told clang 10, in particular), the NEON
intrinsic vaddq_p128 is missing, even though its input type poly128_t
is provided.

vaddq_p128 is just an XOR of two vector registers, so that's easy to
work around by casting to a more mundane type and back. Added a
configure-time test for that intrinsic, and a workaround to be used in
its absence.
2022-10-12 20:01:58 +01:00
Simon Tatham
258a36be31 Change priority of new Diffie-Hellman groups.
In the initial commit 031d86ed5b that introduced them, I
accidentally put them below the 'warn about insecurity' line, which I
didn't mean to. Moved them up to just above the existing group14.

Also, I've arranged them in a slightly weird order, so that the most
preferred group of this collection is the medium-sized group16,
followed by the larger ones (17 and 18) and then the smaller 15.
Rationale: larger is better _until_ it starts costing way too much CPU
time, and group18 can grind quite painfully on a slow machine. (And of
course users are free to reconfigure if they have different
preferences.)

This isn't really ideal, of course. The idea that you might not want
to use group18 *because it's slow* contradicts the basic concept of
PuTTY's current crypto-preferences UI, which assumes that you rank
things by security, which is why there's a dividing line below which
things are assumed insecure. I hope that in a future release we'll
rework the UI so that you can express more subtle ideas of what crypto
you do and don't like. But this will do for the moment.

The GSS versions of the same DH methods are reordered similarly.
2022-09-12 09:34:01 +01:00
Simon Tatham
bbd46afd91 opensshcert_components: switch expiry times to UTC.
Jacob points out that the output of 'puttygen --dump', where the
key_components are used, is much more likely to need to be machine-
than human-readable, and so it makes more sense to use a date/time
format that's invariant under external changes such as locale.

(He also points out that Windows's time zone description strings are
overly verbose!)
2022-09-12 09:34:01 +01:00
Jacob Nevins
5fdfe5ac83 Standardise RFC URLs in docs and comments.
(Plus one internet-draft URL.)
2022-09-11 23:59:12 +01:00
Jacob Nevins
25ef6a233a Remove a stray FIXME, added in 840043f06e.
Simon tells me he was pondering whether chacha20-poly1305 could be
reworked to use the new facilities, but on reflection there's no way to
use it to improve matters.
2022-09-11 22:17:46 +01:00
Simon Tatham
1f6d93f0c8 Fix a batch of resource leaks spotted by Coverity. 2022-09-07 14:28:52 +01:00
Simon Tatham
9a84a89c32 Add a batch of missing 'static's. 2022-09-03 12:02:48 +01:00
Simon Tatham
40dfbeba41 Fix aes-select.c macros again.
I decided that the 'namemaker' system introduced recently in commit
fbb979aa98 was just too marginal to be sensible, and it's easier
to simply quote the full SSH id for each protocol.

Also, included an empty argument at the end of each macro invocation,
so that the variadic "..." is never completely missing.
2022-09-03 11:59:12 +01:00
Simon Tatham
fbb979aa98 Fix AES build on real Visual Studio.
Apparently a nasty trick I did in one of the selector vtable macros
was not acceptable to VS, which thinks that "string" ? NULL : NULL is
not a constant expression - it can't tell that the string literal has
a non-null value _or_ that it doesn't matter whether the value is null
or not.

Redone the vtable name construction in a way that depends only on the
actual preprocessor, not on the followup C expression semantics.
2022-09-02 18:23:08 +01:00
Simon Tatham
cec8c87626 Support elliptic-curve Diffie-Hellman GSS KEX.
This is surprisingly simple, because it wasn't necessary to touch the
GSS parts at all. Nothing changes about the message formats between
integer DH and ECDH in GSS KEX, except that the mpints sent back and
forth as part of integer DH are replaced by the opaque strings used in
ECDH. So I've invented a new KEXTYPE and made it control a bunch of
small conditionals in the middle of the GSS KEX code, leaving the rest
unchanged.
2022-08-30 18:09:39 +01:00
Simon Tatham
031d86ed5b Add RFC8268 / RFC3126 Diffie-Hellman group{15,16,17,18}.
These are a new set of larger integer Diffie-Hellman fixed groups,
using SHA-512 as the hash.
2022-08-30 18:09:39 +01:00
Jacob Nevins
d2e982efa7 openssh-certs: Avoid C99 strftime() specifiers.
These were introduced in 34d01e1b65 to pretty-print certificate validity
ranges. But Microsoft's C runtime took a while to catch up with C99 --
stackoverflow claims that VS2013 and earlier don't support these
specifiers -- so it's possible to end up with PuTTY executables that
misdisplay these dates. Also, the mingw-w64 toolchain's -Wformat
complains about these specifiers, at least on Debian buster, presumably
for the same reason.

Since the specifiers in question have exact pre-C99 replacements, it
seems easiest just to use those.
2022-08-30 18:05:07 +01:00
Simon Tatham
c1a2114b28 Implement AES-GCM using the @openssh.com protocol IDs.
I only recently found out that OpenSSH defined their own protocol IDs
for AES-GCM, defined to work the same as the standard ones except that
they fixed the semantics for how you select the linked cipher+MAC pair
during key exchange.

(RFC 5647 defines protocol ids for AES-GCM in both the cipher and MAC
namespaces, and requires that you MUST select both or neither - but
this contradicts the selection policy set out in the base SSH RFCs,
and there's no discussion of how you resolve a conflict between them!
OpenSSH's answer is to do it the same way ChaCha20-Poly1305 works,
because that will ensure the two suites don't fight.)

People do occasionally ask us for this linked cipher/MAC pair, and now
I know it's actually feasible, I've implemented it, including a pair
of vector implementations for x86 and Arm using their respective
architecture extensions for multiplying polynomials over GF(2).

Unlike ChaCha20-Poly1305, I've kept the cipher and MAC implementations
in separate objects, with an arm's-length link between them that the
MAC uses when it needs to encrypt single cipher blocks to use as the
inputs to the MAC algorithm. That enables the cipher and the MAC to be
independently selected from their hardware-accelerated versions, just
in case someone runs on a system that has polynomial multiplication
instructions but not AES acceleration, or vice versa.

There's a fourth implementation of the GCM MAC, which is a pure
software implementation of the same algorithm used in the vectorised
versions. It's too slow to use live, but I've kept it in the code for
future testing needs, and because it's a convenient place to dump my
design comments.

The vectorised implementations are fairly crude as far as optimisation
goes. I'm sure serious x86 _or_ Arm optimisation engineers would look
at them and laugh. But GCM is a fast MAC compared to HMAC-SHA-256
(indeed compared to HMAC-anything-at-all), so it should at least be
good enough to use. And we've got a working version with some tests
now, so if someone else wants to improve them, they can.
2022-08-16 20:33:58 +01:00
Simon Tatham
840043f06e Add 'next_message' methods to cipher and MAC vtables.
This provides a convenient hook to be called between SSH messages, for
the crypto components to do any per-message processing like
incrementing a sequence number.
2022-08-16 18:27:06 +01:00
Simon Tatham
dbc77dbd7a Change the rules for how we free a linked cipher and MAC.
In the situation where a MAC and cipher implementation are tied
together by being facets of the same underlying object (used by the
inseparable ChaCha20 + Poly1305 pair), previously we freed them by
having the cipher_free function actually do the freeing, having the
mac_free function do nothing, and taking great care to call those in
the right order. (Otherwise, the mac_free function dereferences a
no-longer-valid vtable pointer and doesn't get as far as _finding out_
that it doesn't have to do anything.)

That's a time bomb in general, and especially awkward in situations
like testcrypt where we don't get precise control over freeing order
in any case. So I've replaced that system with one in which there are
two flags in the ChaCha20-Poly1305 structure, saying whether each of
the cipher and MAC facets is currently considered to be allocated.
When the last of those flags is cleared, the object is actually freed.
So now they can be freed in either order.
2022-08-16 18:22:29 +01:00
Simon Tatham
423ce20ffb Pageant core: separate public and private key storage.
Previously, we had a single data structure 'keytree' containing
records each involving a public and private key (the latter maybe in
clear, or as an encrypted key file, or both). Now, we have separate
'pubkeytree' and 'privkeytree', the former storing public keys indexed
by their full public blob (including certificate, if any), and the
latter storing private keys, indexed by the _base_ public blob
only (i.e. with no certificate included).

The effect of this is that deferred decryption interacts more sensibly
with certificates. Now, if you load certified and uncertified versions
of the same key into Pageant, or two or more differently certified
versions, then the separate public key records will all share the same
private key record, and hence, a single state of decryption. So the
first time you enter a passphrase that unlocks that private key, it
will unlock it for all public keys that share the same private half.
Conversely, re-encrypting any one of them will cause all of them to
become re-encrypted, eliminating the risk that you deliberately
re-encrypt a key you really care about and forget that another equally
valuble copy of it is still in clear.

The most subtle part of this turned out to be the question of what key
comment you present in a deferred decryption prompt. It's very
tempting to imagine that it should be the comment that goes with
whichever _public_ key was involved in the signing request that
triggered the prompt. But in fact, it _must_ be the comment that goes
with whichever version of the encrypted key file is stored in Pageant
- because what if the user chose different passphrases for their
uncertified and certified PPKs? Then the decryption prompt will have
to indicate which passphrase they should be typing, so it's vital to
present the comment that goes with the _file we're decrypting_.

(Of course, if the user has selected different passphrases for those
two PPKs but the _same_ comment, they're still going to end up
confused. But at least once they realise they've done that, they have
a workaround.)
2022-08-06 11:34:36 +01:00
Simon Tatham
cd7f6c4407 Certificate-aware handling of key fingerprints.
OpenSSH, when called on to give the fingerprint of a certified public
key, will in many circumstances generate the hash of the public blob
of the _underlying_ key, rather than the hash of the full certificate.

I think the hash of the certificate is also potentially useful (if
nothing else, it provides a way to tell apart multiple certificates on
the same key). But I can also see that it's useful to be able to
recognise a key as the same one 'really' (since all certificates on
the same key share a private key, so they're unavoidably related).

So I've dealt with this by introducing an extra pair of fingerprint
types, giving the cross product of {MD5, SHA-256} x {base key only,
full certificate}. You can manually select which one you want to see
in some circumstances (notably PuTTYgen), and in others (such as
diagnostics) both fingerprints will be emitted side by side via the
new functions ssh2_double_fingerprint[_blob].

The default, following OpenSSH, is to just fingerprint the base key.
2022-08-05 18:08:59 +01:00
Simon Tatham
4b8dc56284 Formatting: remove spurious spaces in 'type * var'.
I think a lot of these were inserted by a prior run through GNU indent
many years ago. I noticed in a more recent experiment that that tool
doesn't always correctly distinguish which instances of 'id * id' are
pointer variable declarations and which are multiplications, so it
spaces some of the former as if they were the latter.
2022-08-03 20:48:46 +01:00
Simon Tatham
4fa3480444 Formatting: realign run-on parenthesised stuff.
My bulk indentation check also turned up a lot of cases where a run-on
function call or if statement didn't have its later lines aligned
correctly relative to the open paren.

I think this is quite easy to do by getting things out of
sync (editing the first line of the function call and forgetting to
update the rest, perhaps even because you never _saw_ the rest during
a search-replace). But a few didn't quite fit into that pattern, in
particular an outright misleading case in unix/askpass.c where the
second line of a call was aligned neatly below the _wrong_ one of the
open parens on the opening line.

Restored as many alignments as I could easily find.
2022-08-03 20:48:46 +01:00
Simon Tatham
3a42a09dad Formatting: normalise back to 4-space indentation.
In several pieces of development recently I've run across the
occasional code block in the middle of a function which suddenly
switched to 2-space indent from this code base's usual 4. I decided I
was tired of it, so I ran the whole code base through a re-indenter,
which made a huge mess, and then manually sifted out the changes that
actually made sense from that pass.

Indeed, this caught quite a few large sections with 2-space indent
level, a couple with 8, and a handful of even weirder things like 3
spaces or 12. This commit fixes them all.
2022-08-03 20:48:46 +01:00
Simon Tatham
ff2ffa539c Windows Pageant: display RSA/DSA cert bit counts.
The test in the Pageant list box code for whether we should display
the bit count of a key was done by checking specifically for ssh_rsa
or ssh_dsa, which of course meant that it didn't catch the certified
versions of those keys.

Now there's yet another footling ssh_keyalg method that asks the
question 'is it worth displaying the bit count?', to which RSA and DSA
answer yes, and the opensshcert family delegates to its base key type,
so that RSA and DSA certified keys also answer yes.

(This isn't the same as ssh_key_public_bits(alg, blob) >= 0. All
supported public key algorithms _can_ display a bit count if called
on. But only in RSA and DSA is it configurable, and therefore worth
bothering to print in the list box.)

Also in this commit, I've fixed a bug in the certificate
implementation of public_bits, which was passing a wrongly formatted
public blob to the underlying key. (Done by factoring out the code
from opensshcert_new_shared which constructed the _correct_ public
blob, and reusing it in public_bits to do the same job.)
2022-08-02 18:39:31 +01:00
Simon Tatham
fea08bb244 Windows Pageant: use nicer key-type strings.
If you load a certified key into Windows Pageant, the official SSH id
for the key type is so long that it overflows its space in the list
box and overlaps the key fingerprint hash.

This commit introduces yet another footling little ssh_keyalg method
which returns a shorter human-readable description of the key type,
and uses that in the Windows Pageant list box only.

(Not in the Unix Pageant list, though, because being output to stdout,
that seems like something people are more likely to want to
machine-read, which firstly means we shouldn't change it lightly, and
secondly, if we did change it we'd want to avoid having a variable
number of spaces in the replacement key type text.)
2022-08-02 18:03:45 +01:00
Simon Tatham
6737a19072 cmdgen: human-readable certificate info dump.
The recently added SeatDialogText type was just what I needed to add a
method to the ssh_key vtable for dumping certificate information in a
human-readable format. It will be good for displaying in a Windows
dialog box as well as in cmdgen's text format.

This commit introduces and implements the new method, and adds a
--cert-info mode to command-line Unix PuTTYgen that uses it. The
Windows side will follow shortly.
2022-07-30 17:16:55 +01:00
Simon Tatham
42740a5455 Allow manually confirming and caching certified keys.
In the case where a server presents a host key signed by a different
certificate from the one you've configured, it need not _always_ be
evidence of wrongdoing. I can imagine situations in which two CAs
cover overlapping sets of things, and you don't want to blanket-trust
one of them, but you do want to connect to a specific host signed by
that one.

Accordingly, PuTTY's previous policy of unconditionally aborting the
connection if certificate validation fails (which was always intended
as a stopgap until I thought through what I wanted to replace it with)
is now replaced by fallback handling: we present the host key
fingerprint to the user and give them the option to accept and/or
cache it based on the public key itself.

This means that the certified key types have to have a representation
in the host key cache. So I've assigned each one a type id, and
generate the cache string itself by simply falling back to the base
key.

(Rationale for the latter: re-signing a public key with a different
certificate doesn't change the _private_ key, or the set of valid
signatures generated with it. So if you've been convinced for reasons
other than the certificate that a particular private key is in the
possession of $host, then proof of ownership of that private key
should be enough to convince you you're talking to $host no matter
what CA has signed the public half this week.)

We now offer to receive a given certified host key type if _either_ we
have at least one CA configured to trust that host, _or_ we have a
certified key of that type cached. (So once you've decided manually
that you trust a particular key, we can still receive that key and
authenticate the host with it, even if you later delete the CA record
that it didn't match anyway.)

One change from normal (uncertified) host key handling is that for
certified key types _all_ the host key prompts use the stronger
language, with "WARNING - POTENTIAL SECURITY BREACH!" rather than the
mild 'hmm, we haven't seen this host before'. Rationale: if you
expected this CA key and got that one, it _could_ be a bold-as-brass
MITM attempt in which someone hoped you'd accept their entire CA key.
The mild wording is only for the case where we had no previous
expectations _at all_ for the host to violate: not a CA _or_ a cached
key.
2022-07-17 14:11:38 +01:00
Simon Tatham
bc61acc53d NTRU: fix copy-paste error in comment.
The polynomial Stein's algorithm in that code was adapted from the
binary Stein in mpint.c. One of the comments which originally said
'dividing by 2' should have been updated to say 'dividing by x' in the
polynomial case, and didn't.
2022-06-11 13:12:33 +01:00
Simon Tatham
b753cf6e3b Reject multilayer certificates in check_cert.
Rejecting them in the CA config box reminded me that the main checking
code also ought to do the same thing.
2022-05-07 12:26:55 +01:00
Simon Tatham
ab70bda4c7 ntru_gen_short: remove quadratic-time shuffle.
This function has to make an array containing a specific number of
random values that are +1 or -1, and all the rest zero. The simplest
way I could think of to do it at first was to make the array with all
the zeroes at the end and then shuffle the array.

But I couldn't think of a time-safe algorithm to shuffle an array in
such a way that all orders come out equiprobable, that was better than
quadratic time. In fact I still can't think of one. (Making a random
Benes network is the best idea I've come up with: it arranges that
every output order is _possible_, and runs in O(N log N) time, but it
skews the probabilities, which makes it unacceptable.)

However, there's no need to shuffle an array in this application
anyway: we're not actually trying to generate a random _permutation_,
only a random element of (n choose w). So we can just walk linearly
along the array remembering how many nonzero elements we have yet to
output, and using an appropriately chosen random number at each step
to decide whether this will be one of them.

This isn't a significant improvement in the performance of NTRU
overall, but it satisfies my sense of rightness a little, and at least
means I don't have to have a comment in the code apologising for the
terrible algorithm any more.
2022-05-07 12:02:23 +01:00
Simon Tatham
dc7ba12253 Permit configuring RSA signature types in certificates.
As distinct from the type of signature generated by the SSH server
itself from the host key, this lets you exclude (and by default does
exclude) the old "ssh-rsa" SHA-1 signature type from the signature of
the CA on the certificate.
2022-05-02 11:17:58 +01:00
Simon Tatham
de5f295b99 Fix handling of RSA + SHA-2 certified host keys.
Initial live testing pointed out that the ssh_keyalg corresponding to
the certified version of rsa-sha2-512 was expecting to see the SSH id
string "rsa-sha2-512-cert-v01@openssh.com" at the start of the public
key blob, whereas in fact, the _key_ type identifier is still
"ssh-rsa-...", just as the key type for base rsa-sha2-512 is base
ssh-rsa.

Fixed inside openssh-certs.c, by adding a couple more strings to the
'extra' structure.
2022-04-27 08:22:42 +01:00
Simon Tatham
9f583c4fa8 Certificate-specific ssh_key method suite.
Certificate keys don't work the same as normal keys, so the rest of
the code is going to have to pay attention to whether a key is a
certificate, and if so, treat it differently and do cert-specific
stuff to it. So here's a collection of methods for that purpose.

With one exception, these methods of ssh_key are not expected to be
implemented at all in non-certificate key types: they should only ever
be called once you already know you're dealing with a certificate. So
most of the new method pointers can be left out of the ssh_keyalg
initialisers.

The exception is the base_key method, which retrieves the base key of
a certificate - the underlying one with the certificate stripped off.
It's convenient for non-certificate keys to implement this too, and
just return a pointer to themselves. So I've added an implementation
in nullkey.c doing that. (The returned pointer doesn't transfer
ownership; you have to use the new ssh_key_clone() if you want to keep
the base key after freeing the certificate key.)

The methods _only_ implemented in certificates:

Query methods to return the public key of the CA (for looking up in a
list of trusted ones), and to return the key id string (which exists
to be written into log files).

Obviously, we need a check_cert() method which will verify the CA's
actual signature, not to mention checking all the other details like
the principal and the validity period.

And there's another fiddly method for dealing with the RSA upgrade
system, called 'related_alg'. This is quite like alternate_ssh_id, in
that its job is to upgrade one key algorithm to a related one with
more modern RSA signing flags (or any other similar thing that might
later reuse the same mechanism). But where alternate_ssh_id took the
actual signing flags as an argument, this takes a pointer to the
upgraded base algorithm. So it answers the question "What is to this
key algorithm as you are to its base?" - if you call it on
opensshcert_ssh_rsa and give it ssh_rsa_sha512, it'll give you back
opensshcert_ssh_rsa_sha512.

(It's awkward to have to have another of these fiddly methods, and in
the longer term I'd like to try to clean up their proliferation a bit.
But I even more dislike the alternative of just going through
all_keyalgs looking for a cert algorithm with, say, ssh_rsa_sha512 as
the base: that approach would work fine now but it would be a lurking
time bomb for when all the -cert-v02@ methods appear one day. This
way, each certificate type can upgrade itself to the appropriately
related version. And at least related_alg is only needed if you _are_
a certificate key type - it's not adding yet another piece of
null-method boilerplate to the rest.)
2022-04-25 15:09:31 +01:00
Simon Tatham
34d01e1b65 Family of key types for OpenSSH certificates.
This commit is groundwork for full certificate support, but doesn't
complete the job by itself. It introduces the new key types, and adds
a test in cryptsuite ensuring they work as expected, but nothing else.

If you manually construct a PPK file for one of the new key types, so
that it has a certificate in the public key field, then this commit
enables PuTTY to present that key to a server for user authentication,
either directly or via Pageant storing and using it. But I haven't yet
provided any mechanism for making such a PPK, so by itself, this isn't
much use.

Also, these new key types are not yet included in the KEXINIT host
keys list, because if they were, they'd just be treated as normal host
keys, in that you'd be asked to manually confirm the SSH fingerprint
of the certificate. I'll enable them for host keys once I add the
missing pieces.
2022-04-25 15:09:31 +01:00
Simon Tatham
c2f1a563a5 Utility function ssh_key_clone().
This makes a second independent copy of an existing ssh_key, for
situations where one piece of code is going to want to keep it after
its current owner frees it.

In order to have it work on an arbitrary ssh_key, whether public-only
or a full public+private key pair, I've had to add an ssh_key query
method to ask whether a private key is known. I'm surprised I haven't
found a need for that before! But I suppose in most situations in an
SSH client you statically know which kind of key you're dealing with.
2022-04-24 08:39:04 +01:00
Simon Tatham
cf36b9215f ssh_keyalg: new method 'alternate_ssh_id'.
Previously, the fact that "ssh-rsa" sometimes comes with two subtypes
"rsa-sha2-256" and "rsa-sha2-512" was known to three different parts
of the code - two in userauth and one in transport. Now the knowledge
of what those ids are, which one goes with which signing flags, and
which key types have subtypes at all, is centralised into a method of
the key algorithm, and all those locations just query it.

This will enable the introduction of further key algorithms that have
a parallel upgrade system.
2022-04-24 08:39:04 +01:00
Simon Tatham
f9775a7b67 Make ssh_keyalg's supported_flags a method.
It's a class method rather than an object method, so it doesn't allow
keys with the same algorithm to make different choices about what
flags they support. But that's not what I wanted it for: the real
purpose is to allow one key algorithm to delegate supported_flags to
another, by having its method implementation call the one from the
delegate class.

(If only C's compile/link model permitted me to initialise a field of
one global const struct variable to be a copy of that of another, I
wouldn't need the runtime overhead of this method! But object file
formats don't let you even specify that.)

Most key algorithms support no flags at all, so they all want to use
the same implementation of this method. So I've started a file of
stubs utils/nullkey.c to contain the common stub version.
2022-04-24 08:39:04 +01:00
Simon Tatham
52f296b7e2 ntru.c: fix benign paste error.
smemclr(array, ... * sizeof(*different_array)) was not what I meant to
do, even though the two arrays have the same element size.
2022-04-22 22:20:36 +01:00
Simon Tatham
9aae695c62 NTRU: speed up the polynomial inversion.
I wasn't really satisfied with the previous version, but it was
easiest to get Stein's algorithm working on polynomials by doing it
exactly how I already knew to do it for integers. But now I've
improved it in two ways.

The first improvement I got from another implementation: instead of
transforming A into A - kB for some k that makes the constant term
zero, you can scale _both_ inputs, replacing A with mA - kB for some
k,m. The advantage is that you can calculate m and k very easily, by
making each one the constant term of the other polynomial, which means
you don't need to invert something mod q in every step. (Rather like
the projective-coordinates optimisations in elliptic curves, where
instead of inverting in every step you accumulate the product of all
the factors that need to be inverted, and invert the whole product
once at the very end.)

The second improvement is to abandon my cumbersome unwinding loop that
builds up the output coefficients by reversing the steps in the
original gcd-finding loop. Instead, I do the thing you do in normal
Euclid's algorithm: keep track of the coefficients as you go through
the original loop. I had wanted to do this before, but hadn't figured
out how you could deal with dividing a coefficient by x when (unlike
the associated real value) the coefficient isn't a multiple of x. But
the answer is very simple: x is invertible in the ring we're working
in (its inverse mod x^p-x-1 is just x^{p-1}-1), so you _can_ just
divide your coefficient by x, and moreover, very easily!

Together, these changes speed up the NTRU key generation by about a
factor of 1.5. And they remove lots of complicated code as well, so
everybody wins.
2022-04-21 08:13:15 +01:00
Simon Tatham
faf1601a55 Implement OpenSSH 9.x's NTRU Prime / Curve25519 kex.
This consists of DJB's 'Streamlined NTRU Prime' quantum-resistant
cryptosystem, currently in round 3 of the NIST post-quantum key
exchange competition; it's run in parallel with ordinary Curve25519,
and generates a shared secret combining the output of both systems.

(Hence, even if you don't trust this newfangled NTRU Prime thing at
all, it's at least no _less_ secure than the kex you were using
already.)

As the OpenSSH developers point out, key exchange is the most urgent
thing to make quantum-resistant, even before working quantum computers
big enough to break crypto become available, because a break of the
kex algorithm can be applied retroactively to recordings of your past
sessions. By contrast, authentication is a real-time protocol, and can
only be broken by a quantum computer if there's one available to
attack you _already_.

I've implemented both sides of the mechanism, so that PuTTY and Uppity
both support it. In my initial testing, the two sides can both
interoperate with the appropriate half of OpenSSH, and also (of
course, but it would be embarrassing to mess it up) with each other.
2022-04-15 17:46:06 +01:00
Simon Tatham
e59ee96554 Refactor ecdh_kex into an organised vtable.
This is already slightly nice because it lets me separate the
Weierstrass and Montgomery code more completely, without having to
have a vtable tucked into dh->extra. But more to the point, it will
allow completely different kex methods to fit into the same framework
later.

To that end, I've moved more of the descriptive message generation
into the vtable, and also provided the constructor with a flag that
will let it do different things in client and server.

Also, following on from a previous commit, I've arranged that the new
API returns arbitrary binary data for the exchange hash, rather than
an mp_int. An upcoming implementation of this interface will want to
return an encoded string instead of an encoded mp_int.
2022-04-15 17:46:06 +01:00
Simon Tatham
422a89e208 Use C99 named initialisers in all ssh_kex instances.
No functional change, but this will allow me to add more fields to
that structure without breaking the existing initialisers.
2022-04-15 17:46:06 +01:00
Simon Tatham
d5af33da53 Utility function mp_resize.
This reallocs an existing mp_int to have a different physical size,
e.g. to make sure there's enough space at the top of it.

Trivial, but I'm a little surprised I haven't needed it until now!
2022-04-15 17:46:06 +01:00
Simon Tatham
5935c68288 Update source file names in comments and docs.
Correcting a source file name in the docs just now reminded me that
I've seen a lot of outdated source file names elsewhere in the code,
due to all the reorganisation since we moved to cmake. Here's a giant
pass of trying to make them all accurate again.
2022-01-22 15:51:31 +00:00
Simon Tatham
4ecb40a60d Fix a batch of typos in comments and docs. 2022-01-03 06:40:51 +00:00
Simon Tatham
831accb2a9 Expose openssh_bcrypt() to testcrypt, and test it.
I happened to notice in passing that this function doesn't have any
tests (although it will have been at least somewhat tested by the
cmdgen interop test system).

This involved writing a wrapper that passes the passphrase and salt as
ptrlens, and I decided it made more sense to make the same change to
the original function too and adjust the call sites appropriately.

I derived a test case by getting OpenSSH itself to make an encrypted
key file, and then using the inputs and output from the password hash
operation that decrypted it again.
2021-12-24 10:13:28 +00:00
Simon Tatham
cd60a602f5 Stop using short exponents for Diffie-Hellman.
I recently encountered a paper [1] which catalogues all kinds of
things that can go wrong when one party in a discrete-log system
invents a prime and the other party chooses an exponent. In
particular, some choices of prime make it reasonable to use a short
exponent to save time, but others make that strategy very bad.

That paper is about the ElGamal encryption scheme used in OpenPGP,
which is basically integer Diffie-Hellman with one side's key being
persistent: a shared-secret integer is derived exactly as in DH, and
then it's used to communicate a message integer by simply multiplying
the shared secret by the message, mod p.

I don't _know_ that any problem of this kind arises in the SSH usage
of Diffie-Hellman: the standard integer DH groups in SSH are safe
primes, and as far as I know, the usual generation of prime moduli for
DH group exchange also picks safe primes. So the short exponents PuTTY
has been using _should_ be OK.

However, the range of imaginative other possibilities shown in that
paper make me nervous, even so! So I think I'm going to retire the
short exponent strategy, on general principles of overcaution.

This slows down 4096-bit integer DH by about a factor of 3-4 (which
would be worse if it weren't for the modpow speedup in the previous
commit). I think that's OK, because, firstly, computers are a lot
faster these days than when I originally chose to use short exponents,
and secondly, more and more implementations are now switching to
elliptic-curve DH, which is unaffected by this change (and with which
we've always been using maximum-length exponents).

[1] On the (in)security of ElGamal in OpenPGP. Luca De Feo, Bertram
Poettering, Alessandro Sorniotti. https://eprint.iacr.org/2021/923
2021-11-28 12:19:34 +00:00
Simon Tatham
46fbe375bf Switch to a fixed-window strategy for monty_pow.
Instead of the basic square-and-multiply strategy which requires a
square and a multiply per exponent bit (i.e. two modular
multiplications per bit in total), we instead reduce to a square per
exponent bit and an extra multiply only every 5 bits, because the
value we're multiplying in is derived from 5 of the exponent bits at
once via a table lookup.

To avoid the obvious side-channel leakage of a literal table lookup,
we read the whole table every time, mp_selecting the right value into
the multiplication input. This isn't as slow as it sounds when the
alternative is four entire modular multiplications! In my testing,
this commit speeds up large modpows by a factor of just over 1.5, and
it still gets a clean pass from 'testsc'.
2021-11-28 12:19:34 +00:00
Simon Tatham
a434b13050 Pass diffiehellman ssh_kex objects to testcrypt.
This slightly simplifies the lookup function get_dh_group(), but
mostly, the point is to make it more similar to the other lookup
functions, because I'm planning to have those autogenerated.
2021-11-22 18:32:17 +00:00
Simon Tatham
42120dd1c5 testcrypt: adjust some function parameter names.
Now those names appear in help files, I thought it was worth giving
them a read-through and spotting any really obviously confusing or
wrong ones. Quite a few make more sense in the original context of C
than in the derived Python (e.g. 'BinarySink *bs' as a place to write
output to makes sense, but the output 'val_string bs' is less
helpful).

A couple were so confusing that I also corrected them in the original
C, notably the misuse of 'wc' for the elliptic curve point input to
ecc_weierstrass_point_copy. ('wc' in that section of the code is
normally a parameter describing a whole curve.)
2021-11-21 22:19:01 +00:00
Simon Tatham
be8d3974ff Generalise strbuf_catf() into put_fmt().
marshal.h now provides a macro put_fmt() which allows you to write
arbitrary printf-formatted data to an arbitrary BinarySink.

We already had this facility for strbufs in particular, in the form of
strbuf_catf(). That was able to take advantage of knowing the inner
structure of a strbuf to minimise memory allocation (it would snprintf
directly into the strbuf's existing buffer if possible). For a general
black-box BinarySink we can't do that, so instead we dupvprintf into a
temporary buffer.

For consistency, I've removed strbuf_catf, and converted all uses of
it into the new put_fmt - and I've also added an extra vtable method
in the BinarySink API, so that put_fmt can still use strbuf_catf's
more efficient memory management when talking to a strbuf, and fall
back to the simpler strategy when that's not available.
2021-11-19 11:32:47 +00:00