1. A computer-implemented method for obfuscating resource identifiers, comprising: under the control of one or more computer systems configured with executable instructions, determining an identifier from a pre-defined set of valid identifier values; associating the identifier with a computing resource hosted in a distributed system of a service provider on behalf of a customer of the service provider, the computing resource being from a plurality of computing resources hosted by the service provider for different customers; generating an obfuscated identifier by at least encrypting the identifier using a symmetric key, wherein the encrypting includes constructing a block cipher using a Feistel network, the obfuscated identifier generated to: have a value within the pre-defined set of valid identifier values; and contain a human-readable tag denoting a resource type; and making available to the customer the obfuscated identifier for identification of the resource in the distributed system.