AWS CLI cannot establish connection to AWS Cognito

I believe to experience the same behavior as the OP in re:Post - awscli can't access cognito. In the comments I saw they were able to resolve it by adjusting the settings for IPv6 in the routing tables but that didn't work for me (I might have as well misconfigured that but I'm unable to verify it).

I have tried uninstalling the AWS CLI (using AWS Linux Guide) and installing it following the AWS CLI install guide (for Linux). Basically

~> curl "https://awscli.amazonaws.com/awscli-exe-linux-x86_64.zip" -o "awscliv2.zip"
~> unzip awscliv2.zip
~> sudo ./aws/install

Then I run

~> aws --version
aws-cli/2.15.50 Python/3.11.8 Linux/6.8.9-200.fc39.x86_64 exe/x86_64.fedora.39 prompt/off

~> aws configure

and I setup my region and data format.
Note I'm running of Fedora Linux 39.

After that I run

~> aws configure sso

After that I successfully authenticate and try to call Cognito:

~> export AWS_PROFILE=<my-profile>
~> aws sso login
~> aws cognito-idp list-users --user-pool-id <user-pool-id> --region eu-central-1 --debug

2024-05-15 12:37:44,063 - MainThread - awscli.clidriver - DEBUG - CLI version: aws-cli/2.15.50 Python/3.11.8 Linux/6.8.9-200.fc39.x86_64 exe/x86_64.fedora.39
2024-05-15 12:37:44,063 - MainThread - awscli.clidriver - DEBUG - Arguments entered to CLI: ['cognito-idp', 'list-users', '--user-pool-id', '<user-pool-id>', '--region', 'eu-central-1', '--debug']
2024-05-15 12:37:44,071 - MainThread - botocore.hooks - DEBUG - Event building-command-table.main: calling handler <function add_s3 at 0x7f798d11b6a0>
...
...
...
2024-05-15 13:20:42,708 - MainThread - botocore.auth - DEBUG - Calculating signature using v4 auth.
2024-05-15 13:20:42,708 - MainThread - botocore.auth - DEBUG - CanonicalRequest:
POST
/

content-type:application/x-amz-json-1.1
host:cognito-idp.eu-central-1.amazonaws.com
x-amz-date:20240515T102042Z
x-amz-security-token:<token>
x-amz-target:AWSCognitoIdentityProviderService.ListUsers

content-type;host;x-amz-date;x-amz-security-token;x-amz-target
<random string>
2024-05-15 13:20:42,708 - MainThread - botocore.auth - DEBUG - StringToSign:
AWS4-HMAC-SHA256
20240515T102042Z
20240515/eu-central-1/cognito-idp/aws4_request
<random string>
2024-05-15 13:20:42,708 - MainThread - botocore.auth - DEBUG - Signature:
<random string>
2024-05-15 13:20:42,709 - MainThread - botocore.endpoint - DEBUG - Sending http request: <AWSPreparedRequest stream_output=False, method=POST, url=https://cognito-idp.eu-central-1.amazonaws.com/, headers={'X-Amz-Target': b'AWSCognitoIdentityProviderService.ListUsers', 'Content-Type': b'application/x-amz-json-1.1', 'User-Agent': b'aws-cli/2.15.50 Python/3.11.8 Linux/6.8.9-200.fc39.x86_64 exe/x86_64.fedora.39 prompt/off command/cognito-idp.list-users', 'X-Amz-Date': b'20240515T102042Z', 'X-Amz-Security-Token': b'<token>', 'Authorization': b'AWS4-HMAC-SHA256 Credential=<signature>/20240515/eu-central-1/cognito-idp/aws4_request, SignedHeaders=content-type;host;x-amz-date;x-amz-security-token;x-amz-target, Signature=5df0e3b4e97a4f79c9b6089d43164202c3211b8c81652b923c1d8a67d0c3fdb6', 'Content-Length': '40'}>
2024-05-15 13:20:42,709 - MainThread - botocore.httpsession - DEBUG - Certificate path: /usr/local/aws-cli/v2/2.15.50/dist/awscli/botocore/cacert.pem
2024-05-15 13:20:42,709 - MainThread - urllib3.connectionpool - DEBUG - Starting new HTTPS connection (1): cognito-idp.eu-central-1.amazonaws.com:443
2024-05-15 13:26:43,176 - MainThread - urllib3.connectionpool - DEBUG - https://cognito-idp.eu-central-1.amazonaws.com:443 "POST / HTTP/1.1" 400 151
2024-05-15 13:26:43,177 - MainThread - botocore.parsers - DEBUG - Response headers: {'Date': 'Wed, 15 May 2024 10:26:43 GMT', 'Content-Type': 'application/x-amz-json-1.1', 'Content-Length': '151', 'Connection': 'keep-alive', 'x-amzn-RequestId': 'defa917c-e863-46ce-8c2a-9fef5b69d806', 'x-amzn-ErrorType': 'InvalidSignatureException:', 'x-amzn-ErrorMessage': 'Signature expired: 20240515T102042Z is now earlier than 20240515T102143Z (20240515T102643Z - 5 min.)'}
2024-05-15 13:26:43,177 - MainThread - botocore.parsers - DEBUG - Response body:
b'{"__type":"InvalidSignatureException","message":"Signature expired: 20240515T102042Z is now earlier than 20240515T102143Z (20240515T102643Z - 5 min.)"}'
2024-05-15 13:26:43,180 - MainThread - botocore.hooks - DEBUG - Event needs-retry.cognito-identity-provider.ListUsers: calling handler <bound method RetryHandler.needs_retry of <botocore.retries.standard.RetryHandler object at 0x7f857171a710>>
2024-05-15 13:26:43,180 - MainThread - botocore.retries.standard - DEBUG - Not retrying request.
2024-05-15 13:26:43,180 - MainThread - botocore.hooks - DEBUG - Event after-call.cognito-identity-provider.ListUsers: calling handler <bound method RetryQuotaChecker.release_retry_quota of <botocore.retries.standard.RetryQuotaChecker object at 0x7f8571bc5e50>>
2024-05-15 13:26:43,182 - MainThread - awscli.clidriver - DEBUG - Exception caught in main()
Traceback (most recent call last):
  File "awscli/clidriver.py", line 460, in main
  File "awscli/clidriver.py", line 595, in __call__
  File "awscli/clidriver.py", line 798, in __call__
  File "awscli/clidriver.py", line 931, in invoke
  File "awscli/clidriver.py", line 953, in _display_response
  File "awscli/formatter.py", line 77, in __call__
  File "awscli/botocore/paginate.py", line 446, in build_full_result
  File "awscli/botocore/paginate.py", line 252, in __iter__
  File "awscli/botocore/paginate.py", line 329, in _make_request
  File "awscli/botocore/client.py", line 357, in _api_call
  File "awscli/botocore/client.py", line 724, in _make_api_call
botocore.exceptions.ClientError: An error occurred (InvalidSignatureException) when calling the ListUsers operation: Signature expired: 20240515T102042Z is now earlier than 20240515T102143Z (20240515T102643Z - 5 min.)

An error occurred (InvalidSignatureException) when calling the ListUsers operation: Signature expired: 20240515T102042Z is now earlier than 20240515T102143Z (20240515T102643Z - 5 min.)

You can see that after waiting for 6 minutes (hanging) on:

2024-05-15 13:20:42,709 - MainThread - urllib3.connectionpool - DEBUG - Starting new HTTPS connection (1): cognito-idp.eu-central-1.amazonaws.com:443

then I get a response the signature is expired.

Here is my nslookup:

~> nslookup cognito-idp.eu-central-1.amazonaws.com

Server:         127.0.0.53
Address:        127.0.0.53#53

Non-authoritative answer:
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 3.72.43.238
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 3.122.77.224
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 18.196.59.97
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 18.193.203.226
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 18.157.137.211
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 18.185.243.95
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:700:292d:779:4da7:7d88
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:701:8425:9e0a:4186:16d
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:702:be81:4ae1:c6c9:fd6
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:700:2a49:f249:c559:feda
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:701:5928:28fb:d7ba:1437
Name:   cognito-idp.eu-central-1.amazonaws.com
Address: 2a05:d014:32e:702:6d9e:352:6ec2:35f8

I do not have issue with other AWS CLI commands that I have tried (S3, lambda, SQS). If I execute the same command from AWS CloudShell it just works. I've asked a colleague to try the same command from his machine in a different location and it works for him.