1. A storage device configured to join a network-accessible storage service comprised of a plurality of unaffiliated and un-trusted storage nodes, the storage device comprising: a storage medium configured to store data electronically; a network communication component configured to detect a connection with a wide area network (WAN) and further configured to send and receive data via the WAN; a registration component coupled to the network communication component and configured to transmit a registration request across the WAN to a storage service management node, the registration request offering to make at least a portion of the storage medium accessible to the network-accessible storage service comprised of a plurality of unaffiliated and un-trusted storage nodes under terms that do not require any level of guaranteed service from the storage device to maintain the accessibility of at least the portion of the storage medium to the network-accessible storage service, the registration component being configured to receive a confirmation from the storage service management node in response to the offer to make at least a portion of the storage medium accessible being accepted by the storage service management node; and an access manager coupled to the network communication component and configured to, after the registration component receives the confirmation from the storage service management node, receive data across the WAN from a client device that utilizes the network-accessible storage service, the access manager being configured to store the received data in the storage medium, wherein the received data is encrypted prior to receipt so that the received data is not readily accessible to the host of the storage device and wherein the network-accessible storage service increases the number of unaffiliated and un-trusted storage nodes at which a data object is stored to account for increases in the number of unreliable storage nodes associated with the network-accessible storage service and decrease the probability that all of the storage nodes storing the data object are compromised.