So the attack is due to the fingerprint of the key being smaller than the actual key and therefore theoretically possible to find another key with the same fingerprint..

Doesn't textsecure and threema have the exact same problem? Both show a fingerprint to the user instead of the actual key.