Problem 

You use OIDC as authentication method and Azure AD as IdP, and we cannot find the kid during login, and it does not change on next try, you might need to change the key URL.

The authentication tracker shows the following message:

"message" : "Could not retrieve public key from key store because Failed to get key with kid <your-kid>"

This error means that the app tries to find the public key with <your-kid> from the key store, but there’s no such a key there. The plugin will only continue if it can find the key in the key store.

Solution

In order to fix this problem, you need to change your JWKS URL. Go to → SAML Single Sign On Configuration → Identity Providers → Security Settings.

Change the current JWKS URL and add the following: https://login.microsoftonline.com/<tentant-id>/discovery/v2.0/keys?appid=<your-app-id>

Save the configuration and try again.

Background 

What is the JWKS URL?

The JSON Web Key Set (JWKS) is a set of keys containing the public keys, and it will be used to verify any JSON Web Token (JWT). The JWKS URL (endpoint) is a read-only endpoint.

What is a Key ID (kid)?

The "kid" (key ID) Header Parameter is a hint indicating which key was used to secure the JWS. This parameter allows originators to explicitly signal a change of key to recipients. Use of this Header Parameter is OPTIONAL. When used with a JWK, the "kid" value is used to match a JWK "kid" parameter value.