for some of the users
Which users? Is this in production? Maybe App Attest is doing its job correctly and not working for users who have hacked your app.
we are generating new key and challenge every time.
What exactly do you mean by that? It's important not to generate new keys too often, as that can look suspicious.
Here is one scenario to consider:
- You generate a key and register successfully. You store the key ID in the filesystem.
- The user replaces their device and restores your app on the new device.
- When your app first runs on the new device, it has the key ID that it saved in the filesystem on the old device, but the new device doesn't have that key, so App Attest fails.
(I've asked previously about best practice for where to store the key ID, but I don't have a good answer.)
If "which users?" turns out to be "users who have replaced their device", or "users who have restored their device from a backup", then something like this could be the cause.