[gnutls-devel] GnuTLS | Fix removal of duplicate certs during verification (!1653)

[Read-only notification of GnuTLS library development activities]

Andreas Metzler commented on a discussion on lib/x509/verify-high.c: https://gitlab.com/gnutls/gnutls/-/merge_requests/1653#note_1136984774

> -		if (!(flags & GNUTLS_VERIFY_DO_NOT_ALLOW_UNSORTED_CHAIN)) {
> -			sorted_size = _gnutls_sort_clist(&cert_list[i],
> -							 cert_list_size - i);
> -		}
> -
> -		/* Remove duplicates. Start with index 1, as the first element
> -		 * may be re-checked after issuer retrieval. */
> -		for (j = 1; j < sorted_size; j++) {
> -			if (cert_set_contains(&cert_set, cert_list[i + j])) {
> -				if (i + j < cert_list_size - 1) {
> -					memmove(&cert_list[i + j],
> -						&cert_list[i + j + 1],
> -						sizeof(cert_list[i]));
> +	/* Remove duplicates */
> +	for (i = 0; i < cert_list_size - 1 && cert_list_size <= DEFAULT_MAX_VERIFY_DEPTH; ++i) {
> +		for (j = i + 1; j < cert_list_size && cert_list_size <= DEFAULT_MAX_VERIFY_DEPTH; ++j) {

On 2022-10-16 Daiki Ueno wrote:
> Can we fix the issue without removing the logic using `cert_set`? The point of introducing `cert_set` was to keep the algorithm being $`O(n)`$, while this patch seems to make it $`O(n^2)`$ at the worst case, also assuming the original certificate chain is sorted.

This hinges on [verify-high.c line 1494](lib/x509/verify-high.c#L1494)
~~~c
/* [...] Start with index 1, as the first element may be re-checked after issuer retrieval. */
~~~
The current code explicitly avoids taking the first item (in the context of the bug report this is the server certificate, but can it be something else, too?) into account but I do not understand the rationale **at all**. Does the first item change "after issuer retrieval"? And if not why should not we not remove copies further down in the chain? (The algorithm keeps the first instance and removes later ones.)
cu Andreas

-- 
Reply to this email directly or view it on GitLab: https://gitlab.com/gnutls/gnutls/-/merge_requests/1653#note_1136984774
You're receiving this email because of your account on gitlab.com.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gnutls-devel/attachments/20221016/4c9b1dee/attachment-0001.html>