While visiting 30c3, I attended the You-broke-the-Internet workshop on NaCl.
One thing mentioned in the talk was that auditing crypto code is a lot of work, and that this is one of the reasons why Ed25519 isn't included in NaCl yet (they promised a version including it for 2014). The speakers mentioned a bug in the amd64 assembly implementation of Ed25519 as an example of a bug that can only be found by auditing, not by randomized tests. This bug is caused by a carry being added in the wrong place, but since that carry is usually zero, the bug is hard to fint (occurs with probability 2^{-60} or so).
The TweetNaCl paper briefly mentions this bug as well:
Partial audits have revealed a bug in this software (
r1 += 0 + carry
should ber2 += 0 + carry
inamd64-64-24k
) that would not be caught by random tests; this illustrates the importance of audits.