Even if you trust the OS and the baseband, you have to trust that the federated server for Signal (OpenWhisper, Cyanogen, etc) isn't storing contact discovery requests.