Google Apps email DKIM won't authenticate

Question

We're trying to set up DKIM authentication on our Google Apps/G Suite for Business domain to reduce the number of our emails which are ending up in people's spam folders. We have generated the DKIM key and set it up in Google Cloud DNS and have confirmed that it's set up using 3 different DKIM tools:

1. Mail-checker
2. MX Toolbox
3. DKIM Core

All of them say it is valid, and yet when we try to Start Authenticating, it says "Email authentication was not verified. ..." We waited the suggested 48h (despite the DNS records being visible and correct 24h ago) and it still won't authenticate.

Any idea what else could be going wrong?

The domain is safedoorpm.com if you want to check the DNS yourself.

Edited to add email header 2016/10/21

Here is the header of a mail sent from our domain to gmail. Note that it is still using the default gappssmtp domain for DKIM, not ours:

Delivered-To: [email protected]
Received: by 10.79.95.130 with SMTP id t124csp1047440ivb;
        Thu, 20 Oct 2016 14:30:12 -0700 (PDT)
X-Received: by 10.37.231.193 with SMTP id e184mr4430151ybh.13.1476999012850;
        Thu, 20 Oct 2016 14:30:12 -0700 (PDT)
Return-Path: <[email protected]>
Received: from mail-yw0-f176.google.com (mail-yw0-f176.google.com. [209.85.161.176])
        by mx.google.com with ESMTPS id v62si10092566ybg.141.2016.10.20.14.30.12
        for <[email protected]>
        (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
        Thu, 20 Oct 2016 14:30:12 -0700 (PDT)
Received-SPF: pass (google.com: domain of [email protected] designates 209.85.161.176 as permitted sender) client-ip=209.85.161.176;
Authentication-Results: mx.google.com;
       dkim=pass [email protected];
       spf=pass (google.com: domain of [email protected] designates 209.85.161.176 as permitted sender) [email protected]
Received: by mail-yw0-f176.google.com with SMTP id u124so527ywg.3
        for <[email protected]>; Thu, 20 Oct 2016 14:30:12 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=safedoorpm-com.20150623.gappssmtp.com; s=20150623;
        h=mime-version:from:date:message-id:subject:to;
        bh=rxgZTPk8FeVq2/dWzyjPIHnShPXlQzmPnvfbrUzW/Ss=;
        b=CJ6/IB1YNKvIsO0sUW8BvWyZZdjTQqBofzgOIbuW3Auo0sWtQB4cgWtzjzltr1SyZO
         b+eKJGSrdvRaaaLj7240nZwrVtrmTTlXcx2Qvm2yIp20ilDZWd4pJAAlvSC8wCxDQhYY
         1zwn9UcXxuwD2c05El/DSrdJy+mwVlNv4w3D2v+hPSO0CKS7rKYsjFLEJcQrlAjjANnJ
         itn3oz6DxasplOSmSX8tIOXSHFNnYaJM5lbUtm9cLOWvffclmeShcTbhu/BWWdg1pFHn
         6dXvj6tX7KvbPr9GzH6LnVd71IHe/R65/2VQdqdT0uvJn5KWkc0ziHRlm3HV8JiWXGZf
         oyRQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20130820;
        h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
        bh=rxgZTPk8FeVq2/dWzyjPIHnShPXlQzmPnvfbrUzW/Ss=;
        b=IcWYvLXbpDB2CCV40fWymGcvbICsjuJipBhW5d1d9WFAM4jVDsZd+2K5ENwvVM4L20
         DDbYoqPIoNBwFIaqIB3Sx30xVgFb7d4k7SVSfRZJctrY6QQyO/k6KaxL6++AAxHPbcNw
         jls+G5kzs+62OGQzq6w2Z9VNp6CSEyKqqORsAAjEdwa89v8VLLwyRdUoDxZvpiLAFZ8K
         riyjP7ebj5iyKJsuviX24kQ6QEJZh6RAAhILudAw8+vtNM3Ml+UUHOlAqbPPgseUB4qx
         9hSv+9uQA8w2v7sDiNVVCOoJa20bXZTsLmqlJB6yC4Bt2kzIeSpg5GcALx8EfuaGBiCu
         qo+w==
X-Gm-Message-State: AA6/9RmpTg+BzD0kFfXdFBfUIsAcwb0VxlByb8FBWzHYz/gJotrTZ42AzZtIqsANt5a7rf/hu9In1wdErNHioA==
X-Received: by 10.202.53.68 with SMTP id c65mr8679383oia.57.1476999012386; Thu, 20 Oct 2016 14:30:12 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.202.207.5 with HTTP; Thu, 20 Oct 2016 14:29:31 -0700 (PDT)
From: Mike Totman <[email protected]>
Date: Thu, 20 Oct 2016 15:29:31 -0600
Message-ID: <[e-mail]>
Subject: DKIM test 10
To: Mike Totman <[email protected]>
Content-Type: multipart/alternative; boundary=001a113d4f2877afad053f52a17e

---

Edited to add output from DKIMValidator.com 2016/10/21

I also tried sending an email to the DKIMValidator.com tool, and this is the result. Note that it is still using the default gappssmtp domain for DKIM, not ours:

DKIM Information:

DKIM Signature


Message contains this DKIM Signature:
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=safedoorpm-com.20150623.gappssmtp.com; s=20150623;
        h=mime-version:from:date:message-id:subject:to;
        bh=5wQSTkgMlB+S2PAmekAxIh7O+zBt2H5aC2Ft8cNRJWQ=;
        b=ItJ0UFj97i19qHEFF9ACB5sQY50iZv9ZJ2J9l4JIgSKkSbd/QOi0OGsRWtMe9p5yU4
         vp6z1mgah8DBa+fgCEtTqrOyd+LjaXm0f6FJXyJiV+E7FcdpJ1bSEHyzRlulR0TLqJ/E
         LK0JDXSFNCSUTrWVsrGxIKo7HscI+jY5CR/nTf9cRvTj9Z22lFeukAvVpuhSz88XQeBX
         2TXk2I+p21+L0xAbv0x4OCDgWM5W4WRJUqGi0+gu/IhQBomi/e7wEYZ2f+lvNKRpRggU
         QD2dv15fCibJ3jufVBglpCx9En94UlPuiZqaCi0qqriLnhV/76iBMajI+WyelCG2SimU
         Ht6g==


Signature Information:
v= Version:         1
a= Algorithm:       rsa-sha256
c= Method:          relaxed/relaxed
d= Domain:          safedoorpm-com.20150623.gappssmtp.com
s= Selector:        20150623
q= Protocol:        
bh=                 5wQSTkgMlB+S2PAmekAxIh7O+zBt2H5aC2Ft8cNRJWQ=
h= Signed Headers:  mime-version:from:date:message-id:subject:to
b= Data:            ItJ0UFj97i19qHEFF9ACB5sQY50iZv9ZJ2J9l4JIgSKkSbd/QOi0OGsRWtMe9p5yU4
         vp6z1mgah8DBa+fgCEtTqrOyd+LjaXm0f6FJXyJiV+E7FcdpJ1bSEHyzRlulR0TLqJ/E
         LK0JDXSFNCSUTrWVsrGxIKo7HscI+jY5CR/nTf9cRvTj9Z22lFeukAvVpuhSz88XQeBX
         2TXk2I+p21+L0xAbv0x4OCDgWM5W4WRJUqGi0+gu/IhQBomi/e7wEYZ2f+lvNKRpRggU
         QD2dv15fCibJ3jufVBglpCx9En94UlPuiZqaCi0qqriLnhV/76iBMajI+WyelCG2SimU
         Ht6g==
Public Key DNS Lookup


Building DNS Query for 20150623._domainkey.safedoorpm-com.20150623.gappssmtp.com
Retrieved this publickey from DNS: v=DKIM1; k=rsa; p=MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA2UMfREvlgajdSp3jv1tJ9nLpi/mRYnGyKC3inEQ9a7zqUjLq/yXukgpXs9AEHlvBvioxlgAVCPQQsuc1xp9+KXQGgJ8jTsn5OtKm8u+YBCt6OfvpeCpvt0l9JXMMHBNYV4c0XiPE5RHX2ltI0Av20CfEy+vMecpFtVDg4rMngjLws/ro6qT63S20A4zyVs/V19WW5F2Lulgv+l+EJzz9XummIJHOlU5n5ChcWU3Rw5RVGTtNjTZnFUaNXly3fW0ahKcG5Qc3e0Rhztp57JJQTl3OmHiMR5cHsCnrl1VnBi3kaOoQBYsSuBm+KRhMIw/X9wkLY67VLdkrwlX3xxsp6wIDAQAB
Validating Signature


result = pass
Details: 

---

Solution

After finally talking to Google support I ended up trying a 1024 bit DKIM key instead of a 2048 bit key. That worked.

One thing I noticed is that the DNS record for the 1024 bit key was all one string, whereas I had to break up the 2048 bit key into several strings in the same record. My theory is that Google Admin console doesn't recognize that properly, since the other tools I used (links in the question) validated it OK.

Comments

[Paul]

Can you post the relevant header authentication results from an email sent to another domain, such as some Gmail account?

[Paul]

The DKIM header is passing Google's DKIM checks, so there doesn't seem to be a problem. What service are you using that tells you the DKIM checks are failing?

[Bdoserror]

We are unable to turn on the email authentication, so the email checks are actually using Google's default DKIM for 'gappssmtp', not our configured DKIM key. I forgot about that when I added the mail headers.

[Paul]

Which step in the Google DKIM support article are you stuck on?

[Bdoserror]

We're stuck on the final step "Turn on Authentication". When we click the "Start Authenticating" button it says "Email authentication was not verified. ..."

[Bdoserror]

I've added a screenshot of the error

[Paul]

The DNS record is fine, so as near as I can tell, the problem must be on Google's end of things. I successfully set up a new DKIM record through Google Apps not even a week ago, and had no problems, though I did feel the amount of time for Google to see my DNS record was unacceptable. The record was immediately available from my DNS server, but I couldn't authenticate until the next day.

[George]

Did you try splittin the key into multiple quoted text strings and enter them together in the TXT record value field, as mentioned in this Help Center article: support.google.com/a/answer/173535

[Bdoserror]

Yes, it is split into 2 strings

[George]

@Bdoserror 2 Strings in one TXT record, right?

[George]

Are you sure the quoted strings are in order? Try to make it 3 strings instead of 2, and make sure that they are placed between quotes and in order.

[Bdoserror]

Since the key validates on the 3 test sites (they are able to decode and validate the key), I'm pretty sure they're in the right order. I'll try breaking it into 3.

[Paul]

@George There is nothing wrong with the record. You can inspect it yourself at google._domainkey.safedoorpm.com

[Paul]

If you resolve this issue, please post an answer or inform someone who helped you resolve the issue that they should post the resolution as an answer, then mark the answer as accepted in order to help out future peoples with the same issue.

[Bdoserror]

Yeah, I will. Not yet though, still trying. Just about time to pay Google support. It would help if it gave a better message, with more detail on what failed.

[George]

@Bdoserror did you have the chance to do any changes?

[Bdoserror]

No, not yet. Busy with other issues unrelated to email for now.