Can't create a new key-pair using CloudFormation AWS

I am trying to create a new key pair using the CloudFormation service AWS.

I wrote the yaml below and sent it to CF. But it caused a strange result.

AWSTemplateFormatVersion: "2010-09-09"
Description: A sample template
Resources:
  MyEC2KeyPair:
    Type: "AWS::EC2::KeyPair"
    Properties:
      KeyName : myKey
      KeyType : ed25519

First MyEC2KeyPair resource got CREATE_FAILED status with the error message saying

"Resource handler returned message: "null" (RequestToken: ××××-××××-××××-××××-××××, HandlerErrorCode: InternalFailure)"

Then, the stack started to rollback and MyECC2KeyPair resource got DELETE_IN_PROGRESS status. (To my surprise, the resource had been created). And finally got DELETE_FAILED status with the message saying:

"Resource handler returned message: "null" (RequestToken: ××××-××××-××××-××××, HandlerErrorCode: InternalFailure)"

What would be the reason for the error, and how can you fix this?

The error message from AWS is kind of vague here; it could have been a more informative message.

When you create a new key pair using AWS CloudFormation, the private key is saved to the AWS Systems Manager Parameter Store. The parameter name has the following format:

/ec2/keypair/key_pair_id

So the role that CloudFormation is using to make the stack resources needs to also have permission (ssm:PutParameter) to create a parameter in the Systems Manager Parameter Store.

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "Statement1",
            "Effect": "Allow",
            "Action": [
                "ec2:CreateKeyPair",
                "ssm:PutParameter"
            ],
            "Resource": "*"
        }
    ]
}

Hope it helps.