To better protect passwords used for authentication or for generating cryptographic keys, methods and apparatuses may store password data on multiple storage devices. For each password, each subset of multiple distinct subsets of a data set may be sufficient to authenticate a trial password or generate a cryptographic key. A first subset enables a quick method for authenticating the trial password or generating the cryptographic key. The first subset may be stored in a distributed manner to make it more difficult to steal. If the first subset is unavailable, then a second subset, which is stored centrally, may be used to authenticate the trial password or generate the cryptographic key, but with a method that is an order of magnitude slower than the quick method. Brute force and dictionary attacks based on the second subset may take much longer than such attacks based on the quick method.