How do I have an S3 bucket return 404 (instead of 403) for a key that does not exist in the bucket/

S3 returns a 403 instead of a 404 when the user doesn't have permission to list the bucket contents.

If you query for an object and receive a 404, then you know that object doesn't exist. This is information you shouldn't know if you don't have permission to list the bucket contents so instead of telling you it doesn't exist, S3 just tells you that you're trying to do something you're not allowed to do. When you get a 403 instead of a 404 you have no way of knowing that the object you requested doesn't exist. It might not exist or it might exist and you just don't have permission to access it. There's no way for you to know for sure and so no security is bypassed.

I believe anyone with access to list the bucket contents will get a 404 instead of a 403.

The exact requirement seems to be that your user has ListBucket permission for your particular bucket AND the ARN is exactly of the form arn:aws:s3:::your_bucket_name.

I also needed to add a completely new statement to my policy because other permissions like GetObject still require that the ARN ends with /* or some other suitable wildcard.

{
  "Action": [
    "s3:ListBucket"
  ],
  "Sid": "StmtNNNNNNNNNNNNNNNwholebucket",
  "Resource": [
    "arn:aws:s3:::your_bucket_name"
  ],
  "Effect": "Allow"
},

To summarize, the important bit for me was that if the ARN is NOT of the form arn:aws:s3:::your_bucket_name/* for ListBucket or you will still get 403 instead of 404.

I needed to extend the policy like this:

 "Action": [
   "s3:Get*",
   "s3:List*"
 ],
 "Resource": [
   "arn:aws:s3:::bucket_name",
   "arn:aws:s3::: bucket_name/*"
 ],

bucket_name is needed, because without it you don't get 404 for missing objects, but 403 always, bucket_name/* is needed to actually access stuff in the bucket.