Instant Messaging (IM) applications, such as Telegram and WeChat, have become indispensable tools for individuals. To protect users’ privacy, popular IM applications employ advanced encryption mechanisms. However, we demonstrate that the encrypted traffic of popular IM applications can still leak information about users’ social relationships. In this paper, we reveal that the message notification traffic in IM application is exploitable and propose a novel privacy attack called NotiCorr, which allows an adversary to infer the users in the same group based on flow correlation. Specifically, even if the IM application is not running, the client will still instantly receive group message notifications. To this end, we extract robust fingerprints from both message notification and message transmission traffic to enable attacks in more realistic usage scenarios. To the best of our knowledge, this is the first study to highlight the privacy risks posed by message notification traffic in IM applications. Through extensive experiments, we demonstrate that NotiCorr significantly outperforms related methods. Finally, we discuss the mitigation strategies.