SPF Permanent Error: Too many DNS lookups

We have noticed that a lot of our emails are falsely flagged as spam. Upon reading online, it seems like a good way to solve this issue is to add an SPF record into the DNS, so we added a TXT record with this content:

v=spf1 a mx ip4:162.123.189.010 include:_spf.google.com include:bluehost.com ~all

Bluehost is our host provider, 162.123.189.010 is our VPS IP address from blue host, and _spf.google.com is needed because we send/receive email using GMail.

After running a test on Google's MX tester, we got the following error:

The SPF string can not be parsed, do you have any typos in it?
Decision    permanent error in processing
Explanation SPF Permanent Error: Too many DNS lookups
Record  v=spf1 a mx ip4:162.123.189.010 include:_spf.google.com include:bluehost.com ~all

Does anyone have any idea what the issue is?

"SPF Permanent Error: Too many DNS lookups" is a very specific problem. Your record is too big and SPF checkers will refuse to perform enough DNS queries to determine if something passed SPF.

The SPF spec allows at most 10 DNS lookups. Your SPF record has 17.

RFC 4408 § 10.1 – Processing Limits states:

SPF implementations MUST limit the number of mechanisms and modifiers that do DNS lookups to at most 10 per SPF check, including any lookups caused by the use of the "include" mechanism or the "redirect" modifier. If this number is exceeded during a check, a PermError MUST be returned. The "include", "a", "mx", "ptr", and "exists" mechanisms as well as the "redirect" modifier do count against this limit. The "all", "ip4", and "ip6" mechanisms do not require DNS lookups and therefore do not count against this limit. The "exp" modifier does not count against this limit because the DNS lookup to fetch the explanation string occurs after the SPF record has been evaluated.

Your SPF record has four lookups before traversing the inclusions, including your a and mx:

v=spf1 a mx ip4:162.123.189.010 include:_spf.google.com include:bluehost.com ~all

Google's SPF

Google has three DNS lookups for three collections of CIDRs that it blesses:

_spf.google.com (+3 lookups)

v=spf1 include:_netblocks.google.com include:_netblocks2.google.com
  include:_netblocks3.google.com ~all

_netblocks.google.com

v=spf1 ip4:35.190.247.0/24 ip4:64.233.160.0/19
  ip4:66.102.0.0/20 ip4:66.249.80.0/20 ip4:72.14.192.0/18 ip4:74.125.0.0/16
  ip4:108.177.8.0/21 ip4:173.194.0.0/16 ip4:209.85.128.0/17
  ip4:216.58.192.0/19 ip4:216.239.32.0/19 ~all

_netblocks2.google.com

v=spf1 ip6:2001:4860:4000::/36
  ip6:2404:6800:4000::/36 ip6:2607:f8b0:4000::/36 ip6:2800:3f0:4000::/36
  ip6:2a00:1450:4000::/36 ip6:2c0f:fb50:4000::/36 ~all

_netblocks3.google.com

v=spf1 ip4:172.217.0.0/19 ip4:172.217.32.0/20
  ip4:172.217.128.0/19 ip4:172.217.160.0/20 ip4:172.217.192.0/19
  ip4:108.177.96.0/19 ip4:35.191.0.0/16 ip4:130.211.0.0/22 ~all"

Bluehost's SPF

The SPF record for bluehost.com is too large (its SPF record fails Google's MX tester on its own):

bluehost.com (5 lookups before further traversal)

v=spf1 include:spf2.bluehost.com include:_spf.qualtrics.com
  include:_spf.google.com include:_spf.salesforce.com
  include:sparkpostmail.com -all

spf2.bluehost.com (+0)

v=spf1 ip4:66.147.240.0/20 ip4:69.89.16.0/20 ip4:74.220.192.0/19
  ip4:67.222.32.0/19 ip4:70.40.192.0/19 ip4:67.20.64.0/18 ip4:173.254.0.0/17
  ip4:50.87.0.0/16 ip4:69.195.64.0/18 -all

_spf.qualtrics.com (+0)

v=spf1 ip4:139.60.152.0/22 ip4:162.247.216.0/22 ip4:54.186.193.102/32
  ip4:52.222.73.120/32 ip4:52.222.73.83/32 ip4:52.222.62.51/32
  ip4:52.222.75.85/32 ?all

(see above for _spf.google.com's +3 lookups, though redundant lookups don't add to your total)

_spf.salesforce.com (+1 using an SPF macro with the IP address)

v=spf1 exists:%{i}._spf.mta.salesforce.com -all

sparkpostmail.com is a redirection and then another exists macro and a pile of pointers (+6, wow)

v=spf1 redirect=_spf.sparkpostmail.com
v=spf1 exists:%{i}._spf.sparkpostmail.com include:_netblocks.sparkpostmail.com
  ptr:sparkpostmail.com ptr:spmta.com ptr:flyingenvelope.com ~all

Danger! That sparkpost.com inclusion pulls in some ptr entries, which are trivially forged (any network operator can satisfy sparkpost.com's SPF, meaning they can satisfy bluehost.com's and therefore your own), thus defeating the anti-forgery design of SPF.

_netblocks.sparkpostmail.com was pulled in by the previous record (+0)

v=spf1 ip4:147.253.208.0/20 ip4:192.174.80.0/20 ~all

Bluehost used to use SendGrid, who actually knows what they're doing (their SPF record has no additional lookups), but apparently they have traded SendGrid for SparkPost, who (based on their six extra lookups plus the insecure ptr entries) does not.

Since that totals 12 (13 with include:bluehost.com), you cannot include Bluehhost's SPF.

Bluehost's own suggested SPF record (and its default for all customers) is similarly broken (with 16 lookups, including an easily forged ptr, not to mention its nonsensical ?all, which I address below).