One embodiment of the present invention provides a system that facilitates accessing a credential. During operation, the system receives a request at a credentials-storage framework (CSF) to retrieve the credential. If a target credential store containing the credential is not already connected to the CSF, the system looks up a bootstrap credential for the target credential store in a bootstrap credential store, which contains bootstrap credentials for other credential stores. Next, the system uses this bootstrap credential to connect the CSF to the target credential store. Finally, the system retrieves the credential from the target credential store, and returns the credential to the requestor.