A method for authenticating communication traffic includes receiving a first Domain Name System (DNS) request, sent using a connectionless protocol over a network from a source address, to provide network information regarding a domain name. Responsively to the first DNS request, a client at the source address is solicited to send a second DNS request using the connectionless protocol. An authenticity of the first DNS request is assessed based on the second DNS request.