Messaging apps have become an integral part of our everyday life. Sharing information, getting news and ubiquitous communication have never been easier, and the technological advance in this domain continues. Despite the obvious advantages, the new communication paradigm comes at a price. For example, in order to ensure seamless communication experience and transparent contact discovery, end users have to enable service providers access to personal phonebook. That raises privacy concerns and paves the way to various privacy evasion scenarios.