To relieve users of the burden to memorize and manage their credentials while allowing for seamless roaming between various end devices, the idea of so-called credential repositories that store credentials for users came to attention. Both the risk of the credential repository being unavailable and the risk of the credentials becoming compromised are managed by the party that hosts the credential repository and that has to be trusted by the user. Removing the need for a trust relationship to a single party implies that users have to manage the risks themselves, for instance, by splitting the credentials across multiple systems/parties. However, if the systems differ in terms of availability and vulnerability, determining a suitable splitting strategy to manage the tradeoff between credential availability and vulnerability constitutes a complex problem. In this paper we present CREDIS, an approach that supports the user in building a credential repository based on heterogeneous systems that differ in terms of vulnerability and availability. CREDIS enables users to specify requirements on the availability and the vulnerability of the distributed credential repository and determines an optimal strategy on how to split secrets across the heterogeneous systems. ... mehrWe prove the NP-hardness of finding an optimal strategy, introduce an approach based on Integer Linear Programming to find optimal strategies for medium sized scenarios and propose heuristics for larger ones. We show that the CREDIS approach yields a reasonably secure and available credential repository even when the distributed repository is built based on low-grade devices or systems.