Okay, I can reproduce the failure in a container updated from f37 to f38. And then it started working after installing crypto-policies-scripts. I'd expect the following to fix your issue: '/usr/bin/update-crypto-policies --no-check' and if that's not installed, that may be the reason it's failing for you, and running 'dnf -y install crypto-policies-scripts' should sort it out.

`crypto-policies-scripts` was installed (`crypto-policies-20230301-1.gita12f7b2.fc38.noarch`), but `/usr/bin/update-crypto-policies --no-check` didn't fixed the issue even after reboot.

Okay, please do and attach the output from the RPM_TRACE command here:

# sudo dnf download google-cloud-ci
# RPM_TRACE=1 rpmkeys -Kv google-cloud-cli*.rpm

Created attachment 1953352 [details]
RPM_TRACE=1 rpmkeys -Kv google-cloud-cli*.rpm

Created attachment 1953353 [details]
`RPM_TRACE=1 rpmkeys -Kv *google-cloud-cli*.rpm`

Okay...

----
 _pgpVerifySignature: certificate F09C394C3E1BA8D5 (Google Cloud Packages RPM Signing Key <gc-team>) uses legacy cryptography: No binding signature at time 2023-03-17T21:39:33Z
 _pgpVerifySignature: -> error: Signature is OK, but key is not trusted: verification relies on legacy crypto

    Header V4 RSA/SHA256 Signature, key ID 3e1ba8d5: NOTTRUSTED
    Header SHA256 digest: OK
    Header SHA1 digest: OK
    Payload SHA256 digest: OK
    V4 RSA/SHA256 Signature, key ID 3e1ba8d5: NOTTRUSTED
   MD5 digest: OK
---

And the reason for that is:

[root@localhost ~]# rpm -qi gpg-pubkey-3e1ba8d5|sq packet dump
Public-Key Packet, old CTB, 269 bytes
    Version: 4
    Creation time: 2015-06-24 13:54:48 UTC
    Pk algo: RSA
    Pk size: 2048 bits
    Fingerprint: 3749E1BA95A86CE054546ED2F09C394C3E1BA8D5
    KeyID: F09C394C3E1BA8D5
  
User ID Packet, old CTB, 58 bytes
    Value: Google Cloud Packages RPM Signing Key <gc-team>
  
Signature Packet, old CTB, 312 bytes
    Version: 4
    Type: PositiveCertification
    Pk algo: RSA
    Hash algo: SHA1
               ^^^^
    Hashed area:
      Signature creation time: 2015-06-24 13:54:48 UTC
      Key flags: CSEtErA
      Symmetric algo preferences: AES256, AES192, AES128, CAST5, TripleDES
      Hash preferences: SHA256, SHA1, SHA384, SHA512, SHA224
      Compression preferences: Zlib, BZip2, Zip
      Features: MDC
      Keyserver preferences: no modify
    Unhashed area:
      Issuer: F09C394C3E1BA8D5
    Digest prefix: F90C
    Level: 0 (signature over data)


But this is supposed be allowed in the current crypto-policy which is installed and should be activated too. But somehow isn't. I don't know how to debug that side further, reassigning.

I don't know what's wrong,
because everything should be fine with these versions of the packages.
Fedora 38 VM, obtained by upgrading a clean Fedora 37 VM:

[root@fedora38 ~]# rpm -q crypto-policies crypto-policies-scripts rpm rpm-sequoia
crypto-policies-20230301-1.gita12f7b2.fc38.noarch
crypto-policies-scripts-20230301-1.gita12f7b2.fc38.noarch
rpm-4.18.1-1.fc38.x86_64
rpm-sequoia-1.3.0-1.fc38.x86_64
[root@fedora38 ~]# cat > /etc/yum.repos.d/gcc.repo <<EOF
[google-cloud-cli]
name=Google Cloud CLI
baseurl=https://packages.cloud.google.com/yum/repos/cloud-sdk-el9-x86_64
enabled=1
gpgcheck=1
repo_gpgcheck=0
gpgkey=https://packages.cloud.google.com/yum/doc/rpm-package-key.gpg
EOF
[root@fedora38 ~]# dnf -y install google-cloud-cli
Google Cloud CLI                                    18 MB/s | 104 MB     00:05
Last metadata expiration check: 0:00:16 ago on Fri 24 Mar 2023 12:43:21 PM UTC.
Dependencies resolved.
===================================================================================
 Package                Architecture Version          Repository              Size
===================================================================================
Installing:
 google-cloud-cli       x86_64       423.0.0-1        google-cloud-cli       116 M

Transaction Summary
===================================================================================
Install  1 Package

Total download size: 116 M
Installed size: 643 M
Downloading Packages:
9903a0e85fcb7183015c0461cc8a494a0de38ea732b145e7ec  18 MB/s | 116 MB     00:06
-----------------------------------------------------------------------------------
Total                                               18 MB/s | 116 MB     00:06
retrieving repo key for google-cloud-cli unencrypted from http://packages.cloud.google.com/yum/doc/rpm-package-key.gpg
Google Cloud CLI                                   5.9 kB/s | 975  B     00:00
Importing GPG key 0x3E1BA8D5:
 Userid     : "Google Cloud Packages RPM Signing Key <gc-team>"
 Fingerprint: 3749 E1BA 95A8 6CE0 5454 6ED2 F09C 394C 3E1B A8D5
 From       : http://packages.cloud.google.com/yum/doc/rpm-package-key.gpg
Key imported successfully
Running transaction check
Transaction check succeeded.
Running transaction test
Transaction test succeeded.
Running transaction
  Preparing        :                                                           1/1
  Installing       : google-cloud-cli-423.0.0-1.x86_64                         1/1
  Running scriptlet: google-cloud-cli-423.0.0-1.x86_64                         1/1
  Verifying        : google-cloud-cli-423.0.0-1.x86_64                         1/1

Installed:
  google-cloud-cli-423.0.0-1.x86_64

Complete!


Panu, ojab, could you please attach the contents of
/etc/crypto-policies/back-ends/rpm-sequoia.config
for a system that exhibits the error?

Created attachment 1953372 [details]
/etc/crypto-policies/back-ends/rpm-sequoia.config

> sha1.collision_resistance = "never"
> sha1.second_preimage_resistance = "never"

That's not what's supposed to be there,
especially since the change allowing SHA-1 has happenend in the same update
as introducing rpm-sequoia.config

[root@fedora38 ~]# grep sha1 /etc/crypto-policies/back-ends/rpm-sequoia.config
sha1.collision_resistance = "always"
sha1.second_preimage_resistance = "always"
[root@fedora38]# grep sha1 /usr/share/crypto-policies/DEFAULT/rpm-sequoia.txt
sha1.collision_resistance = "always"
sha1.second_preimage_resistance = "always"

What's your configured policy `update-crypto-policies --show`?
If it's DEFAULT, how have you arrived to the situation with "never"?

```
$ update-crypto-policies --show
TEST-FEDORA39
```
:/ But I don't remember touching anything related, especially not after `dnf system-upgrade`

Works fine after `sudo update-crypto-policies --set DEFAULT`, closing as NOTABUG. I guess user error.

Oh, nice.
That means you've participated in testing of (rejected)
https://fedoraproject.org/wiki/Changes/StrongCryptoSettings3Forewarning1
(thanks for that, by the way!) and haven't switched back.

This policy is, indeed, more restrictive than the current Fedora 38 defaults,
and doesn't allow SHA-1 in conjunction with Fedora 38's rpm-sequoia.
You can revert to DEFAULT using `update-crypto-policies --set DEFAULT`.