"Unfortunately , we were not able to find any good way to discover a new hidden service or to find where a known hidden service is hosted. For more discussion, see sections 7.2.2, Locating known hidden services and 7.3, Discovering unknown hidden services."

Yet there was an attack (on an older version of Tor) published openly not long before this paper was written. (http://www.onion-router.net/Publications/locating-hidden-ser...)

At the end of the abstract of your paper: "We recommend changes to route selection design and implementation for Tor. These changes require no operational increase in network overhead and are simple to make; but they prevent the attacks we have demonstrated. They have been implemented."

So the NSA was unable to independently discover what's in the above paper. Or they discovered it, but it was at a higher cleared level than this leaked paper.

The "Locating Hidden Servers" paper has a .mil author too.

This paper is from 2006, so there's almost certainly more developments since then.