Well, curve25519 uses 256-bit keys (actually, a few bits less than 256). The parallel brute force search should take time similar to that of a 256-bit symmetric

Well, curve25519 uses 256-bit keys (actually, a few bits less than 256). The parallel brute force search should take time similar to that of a 256-bit symmetric cipher. The reason curve25519 has a security level of only 128 bits is that ECDLP takes time proportional to the square root, so half the number of bits (https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Ke...). As for poly1305, it actually uses not one, but two separate 128-bit keys. The authentication tag computed using the first key is encrypted with the second key. For a brute force search, it should be as hard as breaking something with a single key of around 256 bits.