The CCM authenticated encryption mode has gained widespread usage and standardization. Notably, in conjunction with GCM and ChaCha20-Poly1305, CCM is recommended to be used in TLS 1.3 that underlies in https. Since TLS 1.3 is currently utilized by a large number of users, it is imperative to assess the security of these schemes in the multi-user model. Concrete multi-user security analysis for GCM and ChaCha20-Poly1305 have been scrutinized in literature. However, the formal multi-user security analysis for CCM falls behind that for GCM and ChaCha20-Poly1305. Furthermore, in the associated IETF document, the multi-user security bound for CCM is derived by naive generic reduction and falls considerably short of our expectations. In this paper, we bridge the gap by establishing a concrete multi-user security bound for CCM. Our new bound surpasses that derived from generic reduction and it indicates that CCM maintains birthday-bound security in the multi-user model as in the single-user model.

We analyze the multi-user security of the streaming encryption in Google's Tink library via an extended version of the framework of nonce-based online authenticated encryption of Hoang et al. (CRYPTO'15) to support random-access decryption. We show that Tink's design choice of using random nonces and a nonce-based key-derivation function indeed improves the concrete security bound. We then give two better alternatives that are more robust against randomness failure. In addition, we show how to efficiently instantiate the key-derivation function via AES, instead of relying on HMAC-SHA256 like the current design in Tink. To accomplish this we give a multi-user analysis of the XOR-of-permutation construction of Bellare, Krovetz, and Rogaway (EUROCRYPT'98).