International Association
for Cryptologic Research

One-way key chains or ratchets play a vital role in numerous important security protocols such as TLS 1.3, QUIC, Signal, MLS, EDHOC, and OSCORE. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different key chain constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions among the number of collisions occurring within chains, between chains, and between a chain and a random set. Notably, the type of key chain used in protocols such as TLS 1.3 and Signal exhibit a significant number of weak keys, an unexpectedly high rate of key collisions surpassing birthday attack expectations, and a predictable shrinking key space susceptible to novel Time-Memory Trade-Off (TMTO) attacks with complexity $\le N^{1/3}$, which is well within the capabilities of current supercomputers and distributed systems. Consequently, the security level provided by e.g., TLS 1.3 is significantly lower than anticipated based on key sizes. To address these concerns, we analyze the aforementioned protocols and provide numerous concrete recommendations for enhancing their security, as well as guidance for future security protocol design.