They don't need to. You identify yourself within the app with your login.

> It says Imessage can link to your device id

While iMessage is vulnerable to (certain) MiTM attacks, and storing your message archive in iCloud is (was ?) unencrypted, iMessage is surprisingly resilient to attacks (on the protocol itself).

Every iOS/Mac device generates it's own key and uploads the public certificate to Apple's keyserver, this is why they need your device id.

When you send messages with iMessage, your device then contacts Apple's keyservers, gets ALL public certificates for the recipient, and encrypts the message once for every key, and sends an encrypted message per device.

Attachments are handled a bit different. Insted of encrypting the attachment n times, a new key is generated, which is then used to encrypt the attachement, the encrypted attachment is uploaded to Apple, and the key is sent using normal iMessage messages (encrypted)

Your private keys NEVER leave your device, so iMessage is end to end encrypted as long as you don't enable iMessage in iCloud.

I said that iMessage was vulnerable to MiTM attacks, which it is. There's nothing stopping Apple from adding a "shadow" device to your list of devices with it's own set of keys, which would then receive a copy of every message sent to you, and that's probably how iMessage in iCloud works, but they have no way of retrieving your message history from before the shadow device was added.

There's a somewhat recent (2016) paper on it here : http://www.cs.tufts.edu/comp/116/archive/fall2016/xshi.pdf