Technology for communicating by embedding messages in DNS requests/responses is disclosed. In many cases it is desirable for a device to communicate without that device having to supply network credentials. In some network environments, credentials are not required to send or receive DNS messages. The question section of a DNS request message may include a message for a destination DNS server and a query domain which, when using standard DNS routing, will result in the DNS request being directed to the intended destination DNS server. The message may be encoded in such a way that an algorithm run by the destination DNS server is able to parse the message from the DNS request.