Lambda cannot access KMS Key

Question

When I run my lambda code, I get the following error:

The ciphertext refers to a customer master key that does not exist, does not exist in this region, or you are not allowed to access.

I have mostly followed this to create the stack using aws-sam-cli, and the relevant sections of the template are below the code.

The relevant code is:

const ssm = new AWS.SSM();
const param = {
    Name: "param1",
    WithDecryption: true
};
const secret = await ssm.getParameter(param).promise();

The relevant part of the template.yaml file is:

KeyAlias:
    Type: AWS::KMS::Alias
    Properties:
      AliasName: 'param1Key'
      TargetKeyId: !Ref Key
Key:
    Type: AWS::KMS::Key
    Properties:
      KeyPolicy:
        Id: default
        Statement:
        - Effect: Allow
          Principal:
            AWS: !Sub arn:aws:iam::${AWS::AccountId}:root
          Action:
          - 'kms:Create*'
          - 'kms:Encrypt'
          - 'kms:Describe*'
          - 'kms:Enable*'
          - 'kms:List*'
          - 'kms:Put*'
          - 'kms:Update*'
          - 'kms:Revoke*'
          - 'kms:Disable*'
          - 'kms:Get*'
          - 'kms:Delete*'
          - 'kms:ScheduleKeyDeletion'
          - 'kms:CancelKeyDeletion'
          Resource: '*'
          Sid: Allow root account all permissions except to decrypt the key
        Version: 2012-10-17

LambdaFunction:
    Type: AWS::Serverless::Function
    Properties:
      CodeUri: ../
      Handler: app.lambda
      Runtime: nodejs8.10
      Policies:
      - DynamoDBReadPolicy:
          TableName: !Ref Table
      - KMSDecryptPolicy:
          KeyId: !Ref Key
      - Statement:
         - Action:
           - "ssm:GetParameter"
           Effect: Allow
           Resource: !Sub "arn:aws:ssm:${AWS::Region}:${AWS::AccountId}:parameter/param1"

Does the KMSDecryptPolicy not allow the use of the key? What am I missing? Thanks!

EDIT: Changing the template to below works, but I'd really like to use the KMSDecryptPolicy in the lambda definition if possible.

LambdaFunction:
    Type: AWS::Serverless::Function
    Properties:
      CodeUri: ../
      Handler: app.lambda
      Runtime: nodejs8.10
      Policies:
      - DynamoDBReadPolicy:
          TableName: !Ref Table
      - KMSDecryptPolicy:
          KeyId: !Ref Key
      - Statement:
         - Action:
           - "ssm:GetParameter"
           Effect: Allow
           Resource: !Sub "arn:aws:ssm:${AWS::Region}:${AWS::AccountId}:parameter/param1"

Key:
    Type: AWS::KMS::Key
    Properties:
      KeyPolicy:
        Id: default
        Statement:
        - Effect: Allow
          Principal:
            AWS: !Sub arn:aws:iam::${AWS::AccountId}:root
          Action:
          - 'kms:Create*'
          - 'kms:Encrypt'
          - 'kms:Describe*'
          - 'kms:Enable*'
          - 'kms:List*'
          - 'kms:Put*'
          - 'kms:Update*'
          - 'kms:Revoke*'
          - 'kms:Disable*'
          - 'kms:Get*'
          - 'kms:Delete*'
          - 'kms:ScheduleKeyDeletion'
          - 'kms:CancelKeyDeletion'
          Resource: '*'
          Sid: Allow root account all permissions except to decrypt the key
        - Sid: 'Allow use of the key for decryption by the LambdaFunction'
          Effect: Allow
          Principal:
            AWS: !GetAtt LambdaFunctionRole.Arn
          Action:
          - 'kms:Decrypt'
          Resource: '*'        
        Version: 2012-10-17

Answer 1

The answer from your question, is containing a circular dependency.

Here is a functioning version without the need to define specific names for each ressources.

The best part is that you can also pass the KmsKey Arn to your lambda environment variables for easy access and support of dynamic naming.

LambdaFunction:
    Type: AWS::Serverless::Function
    Properties:
      CodeUri: ../
      Handler: app.lambda
      Runtime: nodejs8.10
      Policies:
      - DynamoDBReadPolicy:
          TableName: !Ref Table
      - KMSDecryptPolicy:
          KeyId: !Ref Key
      - Statement:
         - Action:
           - "ssm:GetParameter"
           Effect: Allow
           Resource: !Sub "arn:aws:ssm:${AWS::Region}:${AWS::AccountId}:parameter/param1"
      Environment:
        Variables:
          KMS_ARN: !GetAtt Key.Arn

Key:
    Type: AWS::KMS::Key
    Properties:
      KeyPolicy:
        Id: default
        Statement:
        - Effect: Allow
          Principal:
            AWS: !Sub arn:aws:iam::${AWS::AccountId}:root
          Action:
          - 'kms:Create*'
          - 'kms:Encrypt'
          - 'kms:Describe*'
          - 'kms:Enable*'
          - 'kms:List*'
          - 'kms:Put*'
          - 'kms:Update*'
          - 'kms:Revoke*'
          - 'kms:Disable*'
          - 'kms:Get*'
          - 'kms:Delete*'
          - 'kms:ScheduleKeyDeletion'
          - 'kms:CancelKeyDeletion'
          Resource: '*'
          Sid: Allow root account all permissions except to decrypt the key
        - Sid: 'Allow use of the key for decryption by the LambdaFunction'
          Effect: Allow
          Principal:
            AWS: "*"
          Condition:
            ArnLike:
              "aws:PrincipalArn": !Sub
                - arn:aws:sts::${accountId}:assumed-role/${stackName}-LambdaFunction-*
                - region: !Ref AWS::Region
                  accountId: !Ref AWS::AccountId
                  stackName: !Ref AWS::StackName
          Action:
          - 'kms:Decrypt'
          Resource: '*'        
        Version: 2012-10-17

Answer 2

The question itself contains the answer. The change is that instead of giving KMS permissions in the lambda role only (identity based way), it has also given permissions to the lambda role in the key policy (resource based way).

Here is the AWS official resource on why this is happening - https://docs.aws.amazon.com/kms/latest/developerguide/iam-policies.html

According to this

All KMS CMKs have a key policy, and you must use it to control access to a CMK. IAM policies by themselves are not sufficient to allow access to a CMK, though you can use them in combination with a CMK's key policy.