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

[Read-only notification of GnuTLS library development activities]

Daiki Ueno started a new discussion on lib/x509/verify-high.c: https://gitlab.com/gnutls/gnutls/-/merge_requests/1653#note_1136970650

> -		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) {

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.

-- 
Reply to this email directly or view it on GitLab: https://gitlab.com/gnutls/gnutls/-/merge_requests/1653#note_1136970650
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/2a6fd857/attachment-0001.html>