The need for nodes to be able to generate their own address and verify those from others, without relying on a global trusted authority, is a well-known problem in networking. One popular technique for solving this problem is to use self-certifying addresses that are widely used and standardized; a prime example is cryptographically generated addresses (CGA). We re-investigate the attack models that can occur in practice and analyze the security of CGA-like schemes. As a result, an alternative protocol to CGA, called CGA++, is presented. This protocol eliminates several attacks applicable to CGA and increases the overall security. In many ways, CGA++ offers a nice alternative to CGA and can be used notably for future developments of the Internet Protocol version 6.