The present solution provides systems and methods for generating DNS queries that are more resistant to being compromised by attackers. To generate the transaction identifier, the DNS resolver uses a cryptographic hash function. The inputs to the hash function may include a predetermined random number, the destination IP address of the name server to be queried, and the domain name to be queried. Because of the inclusion of the name server's IP address in the formula, queries for the same domain name to different name servers may have different transaction identifiers, preventing an attacker from observing a query and predicting the identifiers for other queries. Additional entropy may be provided for generating transaction identifiers by including the port number of the name server and/or a portion of the domain name as inputs to the hash function. If it is determined that the responding server may preserve capitalization in its responses, the upper and lower case characters may be salted within the domain name to provide additional entropy in generating transaction identifiers.