Как говорится, замки на дверях - это от хороших людей. В ПО это правило имеет ещё больше смысла. Есть несколько вариантов, например, использование недокументированных возможностей как системы, так и другого ПО на телефоне; скрытое использование другого приложения, имеющего доступ к контактам; ошибка пользователя, который не сразу закрыл приложению доступ и т.д.
Ещё одна возможность - это Big Data. Яндекс, как и другие IT-гиганты, имеет доступ к обширной информации, предоставляемой ему клиентами непосредственно или косвенно. Поэтому вычислить ваш круг контактов не так сложно, как вам может показаться.
Это не о Яндексе, но случай показательный: люди ставят Get contact, чтобы узнать, как их называют другие люди или чтобы сразу идентифицировать мошенников, но не понимают и не учитывают тот факт, что при этом сами сливают о себе всю информацию не очень надёжному приложению.