Merge branch 'ordered-hashtable'

This changes the hashtable implementation to that it maintains insertion
order.  This is then used in the vici plugin to store connections in a
hash table instead of a linked list, which makes managing them quite a
bit faster if there are lots of connections.

The old implementation is extracted into a new class (hashlist_t), which
optionally supports sorting keys and provides the previous get_match()
function.

hashtable: Use quadratic probing

This reduces the clustering problem (primary clustering) but is not
completely free of it (secondary clustering) it still reduces the maximum
and average probing lengths.

vici: Store configs in a hashtable

This makes updates more efficient if many configs are loaded. Configs
still have to be enumerated to select them.

hashtable: Maintain insertion order when enumerating

With the previous approach we'd require at least an additional pointer
per item to store them in a list (15-18% increase in the overhead per
item).  Instead we switch from handling collisions with overflow lists to
an open addressing scheme and store the actual table as variable-sized
indices pointing into an array of all inserted items in their original
order.

This can reduce the memory overhead even compared to the previous
implementation (especially for smaller tables), but because the array for
items is preallocated whenever the table is resized, it can be worse for
certain numbers of items.  However, avoiding all the allocations required
by the previous design is actually a big advantage.

Depending on the usage pattern, the performance can improve quite a bit (in
particular when inserting many items).  The raw lookup performance is a bit
slower as probing lengths increase with open addressing, but there are some
caching benefits due to the compact storage.  So for general usage the
performance should be better.  For instance, one test I did was counting the
occurrences of words in a list of 1'000'000 randomly selected words from a
dictionary of ~58'000 words (i.e. using a counter stored under each word as
key).  The new implementation was ~8% faster on average while requiring
10% less memory.

Since we can't remove items from the array (would change the indices of all
items that follow it) we just mark them as removed and remove them once the
hash table is resized/rehashed (the cells in the hash table for these may
be reused).  Due to this the latter may also happen if the number of stored
items does not increase e.g. after a series of remove/put operations (each
insertion requires storage in the array, no matter if items were removed).
So if the capacity is exhausted, the table is resized/rehashed (after lots
of removals the size may even be reduced) and all items marked as removed
are simply skipped.

Compared to the previous implementation the load factor/capacity is
lowered to reduce chances of collisions and to avoid primary clustering to
some degree.  However, the latter in particular, but the open addressing
scheme in general, make this implementation completely unsuited for the
get_match() functionality (purposefully hashing to the same value and,
therefore, increasing the probing length and clustering).  And keeping the
keys optionally sorted would complicate the code significantly.  So we just
keep the existing hashlist_t implementation without adding code to maintain
the overall insertion order (we could add that feature optionally later, but
with the mentioned overhead for one or two pointers).

The maximum size is currently not changed.  With the new implementation
this translates to a hard limit for the maximum number of items that can be
held in the table (=CAPACITY(MAX_SIZE)).  Since this equals 715'827'882
items with the current settings, this shouldn't be a problem in practice,
the table alone would require 20 GiB in memory for that many items.  The
hashlist_t implementation doesn't have that limitation due to the overflow
lists (it can store beyond it's capacity) but it itself would require over
29 GiB of memory to hold that many items.

hashlist: Move get_match() and sorting into a separate class

The main intention here is that we can change the hashtable_t
implementation without being impeded by the special requirements imposed
by get_match() and sorting the keys/items in buckets.

unit-tests: Pass test iteration to fixtures

hashtable: Optionally collect and report profiling data

hashtable: Optionally sort keys/items in buckets in a specific way

This can improve negative lookups, but is mostly intended to be used
with get_match() so keys/items can be matched/enumerated in a specific
order.  It's like storing sorted linked lists under a shared key but
with less memory overhead.

hashtable: Store items in buckets in insertion order

This is more predictable when using get_match() in particular because
the order does not change anymore when the table is rehashed.

unit-tests: Add tests for larger number of items in hashtables

unit-tests: Optionally report the times test cases ran

kernel-netlink: Ignore preference for temporary addresses for IPv6 VIPs

They are not marked as temporary addresses so make sure we always return
them whether temporary addresses are preferred as source addresses or not
as we need to enumerate them when searching for addresses in traffic selectors
to install routes.

Fixes: 9f12b8a61c47 ("kernel-netlink: Enumerate temporary IPv6 addresses according to config")

charon-nm: Set DPD/close action to restart and enable indefinite keying tries

We don't track CHILD_SA down events anymore and rely on NM's initial timeout
to let the user know if the connection failed initially.  So we also don't
have to explicitly differentiate between initial connection failures and
later ones like we do an Android.  Also, with the default retransmission
settings, there will only be one keying try as NM's timeout is lower than
the combined retransmission timeout of 165s.

There is no visual indicator while the connection is reestablished later.

Fixes #3300.

vici: With start_action=start, terminate IKE_SA without children on unload

This includes IKE_SAs in CONNECTING state, which not yet have any
CHILD_SAs.

Closes strongswan/strongswan#175.

eap-radius: Small spelling fix

Closes strongswan/strongswan#174.

testing: Skip tests with missing files, don't abort the test run

This allows simple test configs in testing/tests/local that are no
actual test cases.

Version bump to 5.9.0dr2

testing: Fix SQL scenarios after preferring AEAD for ESP

sql/net2net-route|start-pem seem to be the only ones that configure a
proposal via database.

testing: Fix ikev2/net2net-fragmentation scenario

The IKE_AUTH message from moon is now larger because of the AEAD proposal.

ike: Send AEAD ESP default proposal first

We generally prefer AEAD nowadays.

References #3461.

proposal: Add AES-GCM to the ESP default AEAD proposal

References #3461.

ikev2: Ensure ALERT_RETRANSMIT_SEND_CLEARED is triggered

If a MOBIKE task is deferred, the retransmission counter is reset to 0
when reinitiating.  So if there were retransmits before, this alert would
not be triggered if a response is received now without retransmits.

travis: Don't pipe negative lgtm.com result into jq

The data might not be valid JSON.

ikev1: Ensure local IP is known as identity fallback during Main Mode

We usually have a local IP already via ike_sa_t::resolve_hosts() before
build_i() is called but if that's not the case, it's more likely we have
one after we processed the first response (it might also have changed).
There is a potential chance we still don't have one if the socket API
doesn't provide us with the destination address of received messages,
but that seems not very likely nowadays.

Version bump to 5.9.0dr1

child-create: Don't reset DH group when retrying after INVALID_KE_PAYLOAD

migrate() is called before retrying.

Fixes: 0184a69b7b14 ("child-create: Properly handle DH group during
migration when reestablishing")

ikev1: Fix PSK lookup for Main Mode initiators

We need the PSK/identity already when deriving the keys in process_i().

Fixes: 1665a4e0504f ("ikev1: Use actual local identity as initiator or aggressive mode responder")

ike: Fix retransmission timeouts if base is <= 1

Fixes: 72b282cf202d ("ike: Properly support high number of retransmission tries")

android: New release after improving connectivity/scheduling

travis: Add build of the Android app

android: Suppress linting error in manifest related to cert import activity

<data> tags that only specify the mimeType attribute are perfectly fine
according to the docs.

android: Ignore some missing quantity lint errors

Once these strings are translated and the quantities are defined, this
attribute can be removed again.

android: Mock parseInetAddress() method to fix unit tests

The native parseInetAddressBytes() method called by that method is not
available when running the tests.

Not very pretty and there are some warnings because PowerMock does
reflection in some illegal way but it fixes the unit tests and does
not require any new dependencies like Apache Commons or Guava just to
parse IP addresses without DNS lookup.

Fixes: 2ef473be1532 ("android: Use helper to parse IP addresses where appropriate")
Fixes #3443.

Merge branch 'android-scheduler'

Starting with Android 6, the system will aggressively suspend apps when
the device is idle (Doze mode).  With Android 10 on a Pixel 4 this seems
to happen after about 70 minutes.  Then the scheduler thread in our
default scheduler is only woken rarely, combined with our previous use
of the monotonic clock it meant that events were executed with severe
delays and noticing that there was such a delay.  This was particularly
bad in regards to NAT keepalives as it usually meant that the device was
not reachable anymore from the outside.

Some changes here try to improve that situation, e.g. the clock is switched
to CLOCK_REALTIME (Bionic doesn't support CLOCK_BOOTTIME for condvars) so we
can measure the actual difference e.g. since the last outbound message,
other changes try to ensure that connectivity is restored after being asleep
for a while (send DPD instead of keepalive after a long delay, send DPD even
if path to peer stays the same).

However, the most significant change is the replacement of the default
scheduler with one specifically designed for Android.  It schedules
long-term events via AlarmManager, which allows waking up the app even
if the system put it to sleep.  The latter requires adding the app to the
system's battery optimization whitelist, which is requested from the
user automatically if necessary.  With this, NAT keepalives and rekeyings
are now scheduled accurately, with little changes to the battery usage.
If the app is not whitelisted (there is a setting to ignore this), events
are delayed by up to 15 minutes after about 70 minutes, so behind a NAT
the device won't be reachable from the outside afterwards (connectivity
should be restored as soon as the device is woken from deep sleep by the
user).

Fixes #3364.

android: Add a preference flag to ignore battery optimizations

This allows users to ignore whether the app is on the device's power
whitelist without a warning.  The flag is currently not set
automatically if the user denies the request.

android: Increase lifetimes a bit

This should avoid clashes of soft and hard lifetimes even if the app is
not whitelisted.

android: Ask user to add our app to the device's power whitelist

This is necessary so we can actually schedule events accurately in Doze
mode. Otherwise, we'd only get woken in intervals of several minutes (up to
15 according to the docs) after about an hour.

android: Use the default scheduler for short-term events

Using AlarmManager has quite some overhead, so we use our regular
scheduler for events that are to be executed in the near future.

android: Use Android-specific scheduler on Android 6 and later

android: Add Android-specific implementation of scheduler_t

This uses AlarmManager to schedule events in a way that ensures the app
is woken up (requires whitelisting when in Doze mode to be woken up at
the exact time, otherwise there are delays of up to 15 minutes).

scheduler: Use timercmp(3) instead of a custom function

ike: Only track actually sent retransmits as outbound packets

Retransmission jobs for old requests for which we already received a
response previously left the impression that messages were sent more
recently than was actually the case.

task_manager_t always defined INVALID_STATE as possible return value if
no retransmit was sent, this just was never actually returned.

I guess we could further differentiate between actual invalid states
(e.g. if we already received the response) and when we don't send a
retransmit for other reasons e.g. because the IKE_SA became stale.

android: Change how initial log handler is registered

Previously, if the two utility functions were called while the VPN
connection was established (i.e. charon was initialized) the logger for
libstrongswan would get reset to the initial log handler.  So certain
log messages would not get logged to the log file after the TUN device
was created (one of the helpers is used to convert IPs there).

android: Check the current path using DPD after a roaming event

A new NAT mapping might be created even if the IP stays the same.  Due to
the DPD fallback with NAT keep-alives this might only be necessary in
corner cases, if at all.

ike: Optionally use DPD to check if the current path still works

We could maybe check the duration of the last stale condition or when
the last packet was sent as filter to avoid unnecessary updates.

android: Enable switch from NAT interval to DPDs after 20 seconds

ike: Add an option to trigger a DPD instead of a NAT keepalive

This is useful on Android where the app might not be able to send
keep-alives if the device is asleep for a while.  If the NAT mapping
has been deleted in the mean time, the NAT-D payloads allow detecting
this and connectivity can be restored by doing a MOBIKE update or
recreating the SA if the peer already deleted it because the client
wasn't reachable.

android: Switch to CLOCK_REALTIME on Android

This allows measuring the delay between events more accurately if a
device is often suspended.

While CLOCK_BOOTTIME would be preferable, Android's bionic C library
does not support it for condvars.

time: Allow using different clocks

On some systems it might be preferable to use e.g. CLOCK_BOOTTIME
instead of CLOCK_MONOTONIC, which is also not affected by time
adjustments but includes times when the system was suspended.

mutex: Don't use ...timedwait_monotonic() if clock is set via attribute

This allows using clocks other than CLOCK_MONOTONIC.

ike: Track NAT-keepalives as outbound packets

android: Fix app icon on Android versions < 5.0

XML resources are apparently not supported there.  Moving the icon to
the mipmap folders should fix that.  Aliases are defined for the icons on
Android < 8.0.

android: Update Gradle plugin

android: Again change how data source is handled in TileService

Evidently, onClick() may be called either before onStartListening() or
after onStopListening() has been called, which causes a crash when
trying to load a VpnProfile via mDataSource.

This partially reverts 3716af079e21 ("android: Avoid crash related to
TileService on Huawei devices").

travis: Bump tpm2-tss to 2.4.1

Manually built dependencies are now built in a separate step after
packages have been installed as they might depend themselves on some
packages (e.g. tpm2-tss, which now requires libjson-c).

charon-nm: Allow configurable remote traffic selectors

This change allows to customize the previously hard-coded remote traffic
selectors.

This does not actually write the newly added "remote-ts" configuration option
into NetworkManager's configuration file, but will use an existing value.
Exposing the config setting in the GUI could be done later if this is a
desired change.

Use case:  remote firewall appliance wrongly accepts the `0.0.0.0/0` TS but
does not actually route external traffic, leaving the user with a partially
working internet connection.

Closes strongswan/strongswan#173.

ikev2: Return to the original host if connection fails after redirection

If we fail connecting to the host we got redirected to, we should restart
with the original host where we might get redirected to a different host.

We must not reset this when retrying due to INVALID_KE_PAYLOAD or COOKIE
notifies.  Since we keep the initiator SPI in those cases, we use that
flag as indicator.

Since we don't store the original remote_host value, we can't restore
that.  So there is a potential conflict with MIPv6.

Closes strongswan/strongswan#171.

nm: Version bump to 1.5.2

nm: Move server port to options tab and position tabs to the left

Also shortened the title of the proposal tab.  This saves some additional
screen space.

Fixes #3448.

nm: Use tabs for options/proposals to save screen space

The height of the dialog increased due to the recently added additional
fields for certificate selection and identities.  On some screens the
fields to configure custom proposals were not visible anymore.
Together with less spacing on the top level GtkBox this change reduces
the height by about 80 pixels.

Fixes #3448.

nm: Migrate appdata to metainfo

The path '/usr/share/appdata' is deprecated as is the .appdata.xml
extension, files should be in installed in '/usr/share/metainfo' with
a .metainfo.xml extension.

According to the docs, the metainfo path should be well supported even
by older distros like Ubuntu 16.04.

Reference: 2.1.2. Filesystem locations
https://www.freedesktop.org/software/appstream/docs/chap-Metadata.html

nm: Version bump to 1.5.1

charon-nm: Clear secrets when disconnecting

The need_secrets() method is called before connect() (where we clear the
previous secrets too), so e.g. a password-protected private could be
decrypted with the cached password from earlier but if the password was not
stored with the connection, it would later fail as no password was requested
from the user that could be passed to connect().

References #3428.

nm: Fix password entry for private keys and allow saving it

On newer desktops the auth dialog is called with --external-ui-mode and
it seems that the password flag has to be set, otherwise the password is
not stored temporarily in the profile and passed to charon-nm (not sure
how this works exactly as need_secrets() is called multiple times even
after the password was already entered, only before doing so the last
time is the password available in that callback, but only if the flag
was set).  This now also allows storing the password for the private key
with the profile.

Fixes #3428.

ike: Properly support high number of retransmission tries

Due to the exponential backoff a high number of retransmits only
makes sense if retransmit_limit is set.  However, even with that there
was a problem.

We first calculated the timeout for the next retransmit and only then
compared that to the configured limit.  Depending on the configured
base and timeout the calculation overflowed the range of uint32_t after
a relatively low number of retransmits (with the default values after 23)
causing the timeout to first get lower (on a high level) before constantly
resulting in 0 (with the default settings after 60 retransmits).

Since that's obviously lower than any configured limit, all remaining
retransmits were then sent without any delay, causing a lot of concurrent
messages if the number of retransmits was high.

This change determines the maximum number of retransmits until an
overflow occurs based on the configuration and defaults to UINT32_MAX
if that value is exceeded.  Note that since the timeout is in milliseconds
UINT32_MAX equals nearly 50 days.

The calculation in task_manager_total_retransmit_timeout() uses a double
variable and the result is in seconds so the maximum number would be higher
there (with the default settings 1205).  However, we want its result to
be based on the actual IKE retransmission behavior.

ike-auth: Add option to use EAP-only authentication without notify

Some peers apparently don't send the notify and still expect to
authenticate with EAP-only authentication.  This option allows forcing
the configured use of EAP-only authentication in that scenario.

child-create: Properly handle DH group during migration when reestablishing

If such a task was active while reestablishing it will get queued on the
new IKE_SA.  If the DH group is already set, the DH groups won't be
stripped from the proposals and a KE payload will be sent, which is invalid
during IKE_AUTH.  We don't want to reset the group if the task is part of a
child-rekey task.

ikev1: Use actual local identity as initiator or aggressive mode responder

If none is configured, there is a fallback to the IP address, which is
not stored on the static auth config, but is set on the IKE_SA.

Fixes #3394.

ikev1: Store fallback identity (IP address) on IKE_SA's auth-cfg

The other auth-cfg object is shared via peer-cfg, so we must not
modify it.  It's only stored to simplify memory management.

Fixes #3394.

lookip: Use line buffering for stdout

Otherwise, the output is buffered when e.g. piping the output to another
command (or file).  And it avoids having to call fflush() in the
interactive mode.

Fixes #3404.

travis: Bump wolfSSL to 4.4.0

SHA-3 is only automatically enabled on x86/x64.  The tests are disabled
because we don't need them and they currently cause a compile warning/error
when built with clang on x64 (sizeof() on a pointer to an array).  If the
examples are enabled, another test suite is built, which includes the
disabled crypto tests.

wolfssl: Add support for Ed448

wolfssl: Add support for x448 Diffie-Hellman

file-logger: Set owner/group of log file

The file is usually opened/created by root, however, if user/group IDs
are configured and the configuration is reloaded, the file will be reopened
as configured user.  Like with UNIX sockets we only attempt to change
the user if we have CAP_CHOWN allowing a start as regular user.

We don't have chown() on Windows, so check for it.

xfrmi: Only build if libcharon is built

The kernel-netlink plugin is only built if libcharon is.

Closes strongswan/strongswan#167.

pkcs11: Optionally hash data for PKCS#1 v1.5 RSA signatures in software

If cards/libraries don't support signature mechanisms with hashing, we fall
back to do it ourselves in software and pass the PKCS#1 digestInfo ASN.1
structure to sign via CKM_RSA_PKCS mechanism.

Closes strongswan/strongswan#168.

scripts: Initialize libstrongswan in id2sql to fix a crash

Since 770f4ccee12d ("identification: Optionally match RDNs in any order
and accept missing RDNs") the DN parser requires lib->settings.

vici: Allow maximum vici message size configuration via compile option

Signed-off-by: Thomas Egerer <thomas.egerer@secunet.com>

Use Botan 2.14.0 for tests

Requires at least GCC 5.0 to build with `--amalgamation`, so it's
disabled for our Ubuntu 16.04 build.

Version bump to 5.8.4

openssl: Allow squeezing multiple times from SHAKE128/256 XOFs

OpenSSL currently doesn't support squeezing bytes out of an XOF multiple
times.  Unfortunately, EVP_DigestFinalXOF() completely resets the context
and later calls not simply fail, they cause a null-pointer dereference in
libcrypto.  This fixes the crash at the cost of repeating initializing
the whole state and allocating too much data for subsequent calls.

There is an open issue and PR that might add a function that allows
squeezing more data from an XOF in a future version of OpenSSL.

charon-nm: Allow using fixed source ports

This could be useful in cases a client behind a NAT has to be made reachable
via port forwarding.

Closes strongswan/strongswan#166.

settings: Use strtoul(3) for settings to int conversion

strtol(3) accepts values in the range of [LONG_MIN;LONG_MAX].  Based
on the architecture (32 or 64 bits), these values expand to either
0x8000000000000000/0x7fffffffffffffff for 64-bit builds, or
0x80000000/0x7fffffff for 32-bit builds.

The behavior when retrieving non-default values for charon.spi_min or
charon.spi_max, for example, depends on the architecture of the target
platform.  While 0xC000001/0xCFFFFFFE work fine on a 64-bit build, on a
32-bit build, due to the use of strtol(3), an ERANGE causes get_int()
to return the default values.

By using strtoul(3) the default is only returned if the input value
exceeds 32 or 64 bits, based on the platform.  Negative values are still
parsed correctly.

Signed-off-by: Thomas Egerer <thomas.egerer@secunet.com>

quick-mode: Make sure we have a proposal before determining lifetimes

Fixes: e0dd36c9c730 ("ikev1: Get and set the lifetimes of the selected proposal/transform")

unit-tests: Update expired certificates for TLS tests

nm: Version bump to 1.5.0

Version bump to 5.8.3

charon-nm: Correctly set remote auth class for PSK authentication

Fixes: bc3eda99bac0 ("charon-nm: Add support for EAP-TLS")

Version bump to 5.8.3rc1

NEWS: Add news for 5.8.3

openssl: Add support for SHAKE128/256

openssl: Add support for SHA-3

Merge branch 'throw-type-routes'

Implements simpler routes for passthrough policies on Linux, which
basically act as fallbacks on routes in other routing tables.  This way
they require less information (e.g. no interface or source IP) and can
be installed earlier and are not affected by updates.

Closes strongswan/strongswan#165.
Fixes #3118.

kernel-netlink: Extract shared route handling code in net/ipsec

kernel-netlink: Don't require an interface name for passthrough policies

kernel-netlink: Allow blank source address in routes for passthrough policies

kernel-netlink: Implement passthrough type routes and use them on Linux

Enables us to ignore any future kernel features for routes unless
we actually need to consider them for the source IP routes.

Also enables us to actually really skip IPsec processing for those networks
(because even the routes don't touch those packets). It's more what
users expect.

Co-authored-by: Tobias Brunner <tobias@strongswan.org>

kernel-interface: Reallocate previously used reqids

This is mainly an issue on FreeBSD where the current kernel still only
allows the daemon to use reqids < IPSEC_MANUAL_REQID_MAX (0x3fff = 16383).

Fixes #2315.

ike: Optionally allow private algorithms for IKE/CHILD_SAs

Charon refuses to make use of algorithms IDs from the private space
for unknown peer implementations [1]. If you chose to ignore and violate
that section of the RFC since you *know* your peers *must* support those
private IDs, there's no way to disable that behavior.

With this commit a strongswan.conf option is introduced which allows to
deliberately ignore parts of section 3.12 from the standard.

[1] http://tools.ietf.org/html/rfc7296#section-3.12

Signed-off-by: Thomas Egerer <thomas.egerer@secunet.com>

openssl: Don't check signature if issuer doesn't match always

Doing this for the self-signed check also (i.e. if this and issuer are
the same) is particularly useful if the issuer uses a different key type.
Otherwise, we'd try to verify the signature with an incompatible key
that would result in a log message.

Fixes #3357.