Embodiments are directed towards providing protection to DNS servers against DNS flood attacks by causing a requesting device to perform multiple DNS lookup requests for resolving a resource record. A request from a network device for a resolution of a domain name may be received by a device interposed between the requesting network device and a DNS server. Upon receiving the request to resolve the domain name, the interposed device may respond with a CNAME that includes a cookie. The requesting device may then send another request that includes the cookie preceded CNAME. The interposed device may then validate the returned cookie returned in the CNAME and if valid, forward the domain name resolution request on to a DNS server. The response may then be forwarded to the requesting device.