In [2], Bellare, Pietrzak and Rogaway proved an O ⁢ ( ℓ ⁢ q 2 / 2 n ) ${O(\ell q^{2}/2^{n})}$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an n -bit random permutation Π, provided ℓ < 2 n / 3 ${\ell<2^{n/3}}$ . Here an adversary can make at most q prefix-free queries each having at most ℓ ${\ell}$ many “blocks” (elements of { 0 , 1 } n ${\{0,1\}^{n}}$ ). In the same paper an O ⁢ ( ℓ o ⁢ ( 1 ) ⁢ q 2 / 2 n ) ${O(\ell^{o(1)}q^{2}/2^{n})}$ bound for EMAC (or encrypted CBC-MAC) was proved, provided ℓ < 2 n / 4 ${\ell<2^{n/4}}$ . Both proofs are based on structure graphs representing all collisions among “intermediate inputs” to Π during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. In the present paper, we show that [2, Lemma 10], stating an important result on structure graphs, is incorrect. This is due to the fact that the authors overlooked certain structure graphs. This invalidates the proofs of the PRF bounds. In [31], Pietrzak improved the bound for EMAC by showing a tight bound O ⁢ ( q 2 / 2 n ) ${O(q^{2}/2^{n})}$ under the restriction that ℓ < 2 n / 8 ${\ell<2^{n/8}}$ . As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about σ ⁢ q / 2 n ${\sigma q/2^{n}}$ provided ℓ < 2 n / 3 ${\ell<2^{n/3}}$ where σ is the total number of blocks in all queries. We also recover tight bound for PRF security of EMAC with a much relaxed constraint ( ℓ < 2 n / 4 ${\ell<2^{n/4}}$ ) than the original ( ℓ < 2 n / 8 ${\ell<2^{n/8}}$ ).

Telegram is a popular secure messaging service with third biggest user base as of 2021. In this paper, we analyze the security of Telegram’s end-to-end encryption (E2EE) protocol in presence of mass-surveillance. Specifically, we show >that Telegram’s E2EE protocol is susceptible to fairly efficient algorithm substitution attacks. While official Telegram clients should be protected against this type of attack due their open-source nature and reproducible builds, this could potentially lead to a very efficient state sponsored surveillance of private communications over Telegram, either on individuals through a targeted attack or massively through some compromised third-party clients. We provide an efficient algorithm substitution attack against MTProto2.0 — the underlying authenticated encryption scheme — that recovers significant amount of encryption key material with a very high probability with few queries and fairly low latency. This could potentially lead to a very efficient state sponsored surveillance of private communications over Telegram, either through a targeted attack or a compromised third-party app. Our attack exploits MTProto2.0’s degree of freedom in choosing the random padding length and padding value. Accordingly, we strongly recommend that Telegram should revise MTProto2.0’s padding methodology. In particular, we show that a minor change in the padding description of MTProto2.0 makes it subversion-resistant in most of the practical scenarios. As a side-effect, we generalize the underlying mode of operation in MTProto2.0, as MTProto-G, and show that this generalization is a multi-user secure deterministic authenticated encryption scheme.