Opinion for the Court filed by Circuit Judge WALD.

WALD, Circuit Judge:

This case marks yet another stage in Carl Oglesby’s decade-long effort to retrieve World War II vintage documents about a Nazi general from six government agencies under the Freedom of Information Act, 5 U.S.C. § 552 (“FOIA” or “Act”). Oglesby, a professional writer and lecturer with a special interest in the politics of clandestine services, submitted his original FOIA requests in 1985 to the Department of the Army (“Army”), the Central Intelligence Agency (“CIA”), the Federal Bureau of Investigation (“FBI”), the National Archives and Records Administration (“NARA”), the National Security Agency (“NSA”), and the Department of State (“State”). Dissatisfied with the responses he received from the agencies, he filed suit in federal court. The district court granted summary judgment for the defendants, but this court vacated that decision in 1990, with instructions for Ogles-by to exhaust his administrative remedies. Oglesby v. Dep’t of Army, 920 F.2d 57 (D.C.Cir.1990). Several years later, having exhausted those remedies without receiving what he considered a satisfactory response, Oglesby returned to the district court, where the judge again ruled in favor of the agencies. Oglesby v. U.S. Dep’t of Army, Memorandum Opinion, No. 87-cv-3349 (D.D.C. Nov. 2, 1994) (“Mem. Op.”). Once again, Oglesby has appealed to this court, this time challenging one agency’s refusal to grant him a fee waiver for his search, and several agencies’ allegedly inadequate searches, incomplete Vaughn indices, and impermissible exemption justifications. Oglesby raises three specific claims: (1) that the statute specifically authorizing NARA to set fees for document production is not exempt from FOIA’s mandatory fee-waiver provision, and therefore NARA was obligated to waive or reduce the fees for Oglesby’s search; (2) that Army, CIA, and NSA failed to submit adequate Vaughn indices and that Army and CIA also failed adequately to justify the exemptions on which they based their decisions to withhold certain responsive documents; and (3) that Army, CIA, FBI, NSA and State failed to demonstrate that they had conducted adequate searches in response to Oglesby’s request. Because we find that Army, CIA, and NSA have failed adequately to justify their withholdings, and Army and CIA have failed to justify the adequacy of their searches, we remand once again for further explanation on these points. With respect to all claims against the other three defendants, we affirm the district court.

I. Background

Since the early 1970s, Oglesby has relentlessly pursued the story of General Reinhard Gehlen, who served as chief of . a Nazi spy ring during World War II and who allegedly later negotiated an agreement with the United States which allowed his spy network to continue in existence despite post-war de-nazification programs. After World War II, his group, then known as the Gehlen Organization, was reportedly reconstituted as a functioning espionage network under U.S. command. According to Oglesby, control of the Gehlen Organization shifted back to the newly-sovereign West German Federal Republic as the BND (for Bundesnachrichten-dienst, or “the Federal Intelligence Service”) after ten years of U.S. control.

More than ten years ago, Oglesby submitted FOIA requests to six government agencies, seeking records pertaining to Gehlen and certain post-WWII Nazi organizations. Oglesby sent identical requests to Army, CIA, NSA State, and NARA. The five requests sought the following information:

officials during the period 1944 through 1956.

Joint Appendix (“J.A.”) 39. The sixth request, submitted to the FBI, sought only requests (a) and (b) above. J.A. 64.

Two years later, dissatisfied with the responses he had received from the agencies, Oglesby initiated legal proceedings, first in the district court, and then in the Court of Appeals. With respect to five of the six defendants, this court held that Oglesby had not exhausted his administrative remedies. Oglesby, 920 F.2d at 65. However, finding that the precise exhaustion procedure required under FOIA had not previously been laid out with sufficient clarity, we permitted Oglesby an opportunity to appeal within each agency and thereafter refile his suit. With respect to the sixth defendant, State, the court reversed the district court’s decision that the agency had successfully demonstrated the adequacy of its FOIA search. Id. at 59-60.

On remand, Oglesby exhausted his administrative remedies and, still dissatisfied, refiled in the district court. At some point during the proceedings, each of the agencies submitted at least one affidavit regarding the method and results of the search it conducted pursuant to Oglesby’s request. These affidavits also describe — with varying degree of detail — the documents the agencies found but refused to disclose, and the FOIA exemptions on which the agencies based their refusals to release information. Once again, the district court determined that the searches were adequate and the exemptions were justified, and granted summary judgment in favor of the defendants. Oglesby now appeals that decision.

II. Discussion

The Freedom of Information Act requires agencies to comply with requests to make their records available to the public, unless the requested records fit within one or more of nine categories of exempt material. 5 U.S.C. § 552(a), (b). If a document contains exempt information, the agency must still release “any reasonably segregable portion” after deletion of the nondisclosable portions. Id. § 552(b). Although the Act makes public disclosure of nonexempt material mandatory, it also expressly permits agencies, in many circumstances, to charge certain reasonable fees to help defray the cost of compliance with their FOIA responsibilities. Id. § 552(a)(4)(A). However, in certain instances, where the dissemination of information will benefit the public, FOIA requires the responsive agencies to waive or reduce the fees they charge the requestor. Id. § 552(a)(4)(A)(iii).

This court has held that the Act also requires an agency in possession of material it considers exempt from FOIA to provide the requestor with a description of each document being withheld, and an explanation of the reason for the agency’s nondisclosure. See, e.g., King v. DOJ, 830 F.2d 210, 224 (D.C.Cir.1987) (“[T]he agency affidavits must ... diselos[e] as much information as possible without thwarting the exemption’s purpose.”); Vaughn v. Rosen, 484 F.2d 820 (D.C.Cir.1973). The description and explanation the agency offers should reveal as much detail as possible as to the nature of the document, without actually disclosing information that deserves protection. See, e.g., King, 830 F.2d at 223. This requirement serves the purpose of providing the request- or with a realistic opportunity to challenge the agency’s decision.

In this case, Oglesby first claims that NARA violated the mandates of FOIA when it refused to grant him a fee waiver for his

search. Second, he alleges that several of the defendant agencies provided him with inadequate descriptions of the responsive documents they had located, and that two agencies further failed to justify their reb-anee on certain FOIA exemptions. Finally, Oglesby argues that the agencies have not sufficiently demonstrated that the searches they conducted in response to his request were “reasonably calculated to uncover all relevant documents,” as required under FOIA. Truitt v. Dep’t of State, 897 F.2d 540, 542 (D.C.Cir.1990).

A. NARA’s Fee Statute and FOIA’s Fee Waiver

FOIA’s fee provision, 5 U.S.C. § 552(a)(4)(A), requires agency regulations to provide for the setting of reasonable charges for document searches, duplication and review. The Act also contains a provision waiving the agency’s fees for searches requested for certain noncommercial purposes:

5 U.S.C. § 552(a)(4)(A)(iii). However, a few paragraphs later, the Act states:

5 U.S.C. § 552(a)(4)(A)(vi) (“subsection (vi)”).

NARA claims that subsection (vi) works as an exception not only to FOIA’s fee 'provisions, but also to the Act’s mandatory fee waiver. Since NARA’s own enabling statute specifically provides for the setting of fees, the agency argues, it is therefore exempt from the FOIA waiver requirement.

The statute which NARA claims justifies its denial of Oglesby’s waiver request authorizes the Archivist

44 U.S.C. § 2116(c) (“NARA § 2116”).

In response to NARA’s claim of exemption, Oglesby argues that NARA’s fee provision does not meet the requirements for exemption under subsection (vi) of FOIA’s fee provision because NARA § 2116 “neither provides a set formula for the imposition of fees nor mandates the assessment of fees.” Appellant’s Brief at 19. Although on its face, the fee-waiver exception provision requires neither a statutorily fixed fee nor a mandatory fee, Oglesby claims that these requirements are implied by the legislative history of FOIA, which provided examples of fee-setting laws which should and should not qualify under the exception. See 132 Cong. Rec. H-29618 (daily ed. Oct. 8, 1986).

The district court rejected Oglesby’s argument, and found that NARA’s fee provision was exempt from FOIA’s fee-waiver requirement. We find as well that the plain language of the two statutes confirms the district court’s determination that the NARA statute is indeed “a statute specifically providing for setting the level of fees for particular types of records,” and thus fits comfortably within the exception carved out in FOIA subsection (vi).

The legislative history to which Oglesby directs our attention does not convince us that the district court erred. For example, the fact that Congress did not intend 31 U.S.C. § 9701, which generally permits the heads of agencies “to establish the charge for a service or thing of value provided by the agency,” to enjoy exempt status has no bearing whatsoever on NARA § 2116. Whereas “a thing of value” clearly does not describe “particular types of records,” Oglesby cannot credibly claim that NARA’s statute, which refers to “materials transferred to [the Archivist’s] custody,” succumbs to the same attack. Although the “types of records” it describes do indeed encompass the vast bulk of material the agency deals with, the material is nonetheless accurately identified. In short, pursuant to the plain language of both provisions, NARA § 2116 qualifies as the

genre of fee-setting provision not to be “supersede[d]” under FOIA’s subsection (vi) exemption.

We wish, however, to make it clear that we are in no way ruling on a separate argument which Oglesby failed to raise in a timely fashion. In a motion filed after oral argument, Oglesby pressed the claim that the FOIA subsection (vi) exception excuses a qualified agency only from FOIA’s fee-seiting requirements, and not from the fee-waiver provision. Oglesby attempts at this point to argue that the legislative history of the fee-waiver and exception provisions suggests that Congress intended by subsection (vi) to allow agencies the freedom to develop their own fee-setting formulae, without also intending to allow those agencies to refuse categorically to provide waivers in the public interest. However, since Oglesby did not raise this argument in a timely manner, we do not address it on the merits. See, e.g., Charter Oil Co. v. Am. Employers’ Ins. Co., 69 F.3d 1160, 1170-71 (D.C.Cir.1995) (issue waived where not raised until reply brief); McBride v. Merrell Dow & Pharmaceuticals, Inc., 800 F.2d 1208, 1211 (D.C.Cir.1986) (“Considering an argument advanced for the first time in a reply brief ... is not only unfair to an appellee but also entails the risk of an improvident or ill-advised opinion on the legal issues tendered.”) (citations omitted).1 We refer to this argument only to emphasize that our narrow ruling today on the argument Oglesby did successfully make is not intended to bar a future challenge on broader grounds. In this case, we hold only that NARA § 2116 fits within the description of fee-setting laws set out in FOIA subsection (vi).

B. Vaughn Indices and Exemptions

In Vaughn v. Rosen, 484 F.2d 820 (D.C.Cir.1973), this court outlined the requirements an agency must meet in indexing the documents it has found responsive to a FOIA request. The court explained that it would “simply no longer accept eonclusory and generalized allegations of [FOIA] exemptions,” but rather would require agencies to offer “a relatively detailed analysis in manageable segments.” Id. at 826. Because FOIA challenges necessarily involve situations in which one party (the government) has sole access to the relevant information, and that same party bears the burden of justifying its disclosure decisions, the courts must require the government to provide as detailed a description as possible — without, of course, disclosing the privileged material itself — of the material it refuses to disclose. Additionally, the agency must determine if any portion of an exempt document contains nonexempt information, and, if so, must disclose that nonexempt portion. “In a large document it is vital that the agency specify in detail which portions of the document are disclosable and which are allegedly exempt.” Id. at 827. If an affidavit submitted by an agency contains sufficient detail to forge the “logical connection between the information [withheld] and the claimed exemption,” Goldberg v. U.S. Dep’t of State, 818 F.2d 71, 78 (D.C.Cir.1987), then the court will accord that affidavit substantial weight and consider the agency’s “unique insights into what adverse effects might occur as a result of public disclosure.” Id.

In this case, Oglesby challenges the adequacy of the document descriptions offered in the affidavits submitted by Army, CIA, and NS A, which he claims are too sparse to allow an assessment of the various exemptions on which the agencies based their decisions to withhold responsive documents. In an overlapping claim, Oglesby raises specific challenges to Army’s and CIA’s reliance on FOIA exemptions 1 and 3, even with respect to individual documents described in adequate detail in the affidavits. He criticizes Army for not specifically stating that the supposedly exempt documents had been classified in accordance with the appropriate procedures, and he faults CIA for failing to address specifically the age of the documents and for depending on an allegedly unreliable affiant.

FOIA exemption 1, 5 U.S.C. § 552(b)(1), protects from disclosure matters that are: (A) specifically authorized under criteria established by an Executive Order to be kept secret in the interest of the national defense or foreign policy; and (B) are in fact properly classified pursuant to that order. Id. The Army and the CIA both withheld information under this exemption.

Exemption 3, 5 U.S.C. § 552(b)(3), protects from disclosure matters that are specifically exempted from disclosure by statute. The CIA withheld information under this exemption, claiming that two statutes specifically operated to exempt certain responsive information; 50 U.S.C. § 403(d)(3), which requires the CIA to protect intelligence sources and methods from unauthorized disclosure; and 50 U.S.C. § 403g, which provides that the CIA shall be exempt from any other law requiring the publication or disclosure of the organization, functions, names, official titles, salaries, or numbers of people employed by the CIA

Because resolution of the issues raised by Oglesby’s appeal depends on a fact-intensive analysis of each of the agencies’ searches and declarations, we outline the relevant facts regarding each agency separately.

In response to Oglesby’s initial request in 1985, Army eventually informed Oglesby that it had located responsive documents concerning three of the topics contained in his request: Operation Rusty, Odessa, and Gehlen. In May, 1986, Army informed Oglesby by letter of its decision to withhold significant portions of the responsive documents. The unreleased information consisted of: eleven pages (and various redactions) in the ninety-nine pages of records pertaining to Odessa; all of the 483 pages of records it had located pertaining to Operation Rusty; and nine of 264 pages of records regarding Gehlen.

Oglesby sued for release of the undisclosed documents, which prompted Army to submit the affidavit of Robert Walsh, describing the responsive documents and attempting to justify Army’s withholdings. The Walsh declaration revealed that the Army initially released seventy pages of Odessa records in their entirety and eighteen in redacted form. Another eleven pages, the Army withheld under exemption 1 (classified information). Aff. of Robert J. Walsh 3 (Apr. 6, 1988) ("Walsh Declaration”); J.A189. Additionally, Army denied access to an entire 483-page Operation Rusty file, also on the basis of FOIA exemption 1. Id. at 7; J.A. 193.

The Walsh declaration described each of nineteen separate documents Army had identified as responsive to Oglesby’s request, and detailed the justifications for any unreleased portions of those documents. In general, the affidavit contained sufficient detail to allow a reviewing court to assess the applicability of the claimed exemptions to the undisclosed information. For example, the Army declared with respect to two documents:

Id. at 4-5; J.A. 190-91.

With respect to the 483-page document withheld in full, however, the affidavit offers significantly less detail:

entirety. The operation concerned gathering positive and counterintelligence information concerning the activities and organizations of an Intelligence Service and activities of various dissident German organizations. The operation involved close coordination and cooperation with foreign and other US intelligence organizations. Release of this information would reveal intelligence activities, sources and methods as well as classified foreign government activities.

Id. at 7; J.A. 193.

On remand, Army supplemented the Walsh declaration with a 1992 affidavit by William Grayson. Decl. of William E. Grayson (Aug. 3, 1992) (“Grayson Declaration”); J.A. 177. For each item of information that still had not been turned over to Oglesby, Grayson explained what had been withheld and why. For example, with respect to one document, he "wrote:

Grayson Decl. at 3-4; J.A. 179-80. With respect to the Operation Rusty file, however, the Grayson declaration offered no new information. Grayson provided a similar description to that which appeared in the Walsh declaration, and concluded that “release of the information would reveal intelligence activities, sources, and methods and also classified foreign government activities” and was therefore not required under exemption 1. Id. at 8; J.A. 184. Grayson also declared that, “considering the nature of the document (which is, in effect, a collection of documents), no one portion could be considered reasonably segregable.” Id. at 9; J.A. 185.

At the time of the Grayson declaration, nine of 264 pages regarding Gehlen had still not been turned over to Oglesby. Grayson explained these withholdings in paragraph 8 of the affidavit:

Id. at 9-10; J.A. 185-86.

Oglesby claims that Army’s Vaughn index is inadequate for two reasons: first, because the Operation Rusty file is not indexed in detail; and second, because the affidavit fails to declare specifically that no portion of the withheld material pertaining to Gehlen was further segregable into exempt and nonexempt portions. Oglesby also claims that Army failed adequately to justify the with-holdings it took under FOIA exemption 1, because the affidavits did not specifically assert that the “classified” information had been classified in accordance with the procedure laid out in the appropriate Executive Order.

Oglesby’s first two complaints merit some attention. The Army provided the district court with relatively little information about a 483-page document it determined was wholly exempt from FOIA disclosure. Although the Army avers that the file is not segregable, the Grayson declaration provides no details justifying that conclusion. In fact, the affidavit describes the file as “in effect, a collection of documents.” Id. at 9; J.A. 185. Since Vaughn and its progeny require that an agency itemize each document and explain the connection between the information withheld and the exemption claimed, the Army should be required on remand to provide any

disclosable information regarding each document in the Operation Rusty “compilation.” The Army has not adequately explained why it cannot provide general information (for example: length, date, author and brief description of each document) which would present Oglesby with a more realistic opportunity to challenge Army’s invocation of exemptions.

Similarly, Army has failed to offer any useful description of the nine undisclosed pages of Gehlen material. We cannot so easily accept the district court’s determination that “[t]he fact that such a tiny percentage of the [264 pages of] documents was withheld, coupled with the Army’s evident awareness of the requirement that it disclose reasonably segregable nonexempt portions, leads the Court to the conclusion that the Army did indeed make such a determination with respect to the Gehlen files.” Mem.Op. at 4; J.A. 469. Although it is quite possible that the Army, which released the vast majority of the Gehlen material, was indeed aware of its duties under FOIA to disclose all nonsegregable information, Army has not provided this court with an adequate explanation on which we can rely for that finding. We therefore remand for a description of the specific documents (or segments) withheld and an explanation of the harm that might result from release of the undisclosed information.

Oglesby’s third claim against this defendant — that Army failed to justify its reliance on exemption 1 because it did not specifically assert that the “classified” information had been labeled in accordance with the procedure laid out in the appropriate Executive Order — elicits less concern. The Walsh declaration asserts that the material withheld pursuant to exemption 1 “meets the criteria set forth in [the Executive Order] which provides that information concerning intelligence activities, sources, or methods shall be considered for classification protection.” Walsh Declaration at 9, 10; J.A. 195, 196. Walsh also stated that he had personally reviewed each of the documents and determined that they were “currently and properly classified, SECRET and CONFIDENTIAL.” Id. The district court held— and we agree — that these claims that the information was “classified” encompass both the procedural and substantive aspects of classification.

In response to Oglesby’s initial 1985 FOIA request, CIA released twenty pages of material it had previously released to someone else pursuant to a 1988 FOIA request for information on Gehlen and Operation Sunrise. Letter from John H. Wright to Carl Oglesby (Sept. 10, 1985); J.A. 57. The agency then informed Oglesby that it would not conduct a new search on Gehlen or any of the other listed topics unless and until Oglesby wrote back and agreed to pay search fees. Rather than responding to the letter, Ogles-by filed suit. In our earlier opinion, we encouraged the Army to reconsider a decision it had made to deny Oglesby a fee waiver, Oglesby, 920 F.2d at 66 n. 11, and on remand, both Army and CIA informed Oglesby that his waiver would be granted. CIA then conducted a search, during which it discovered thirty-five responsive documents. The agency disclosed twenty-nine of these documents, and withheld six of them pursuant to various FOIA exemptions.

The CIA coordinated its Vaughn declaration with the FBI’s, since the FBI had forwarded thirteen responsive documents for CIA review. The CIA submitted the declaration of Lee Carle, dated June 1, 1988, and the FBI submitted an affidavit by Angus Llewellyn, dated May 26, 1988. The Carle declaration described in impressive detail each document and portion thereof which CIA had located but refused to release. For example, Carle offered the following justification for withholding a one-page memo:

tion withheld relates to possible travels and activities of the source during a precise time period. The names of the source’s traveling companions are also included in the deleted information. Release of the information itself would immediately reveal specific details relating to activities and travel plans of these foreign intelligence sources, thereby allowing them to be easily identified.

Declaration of Lee E. Carle 19-20 (June 1, 1988) (“Carle Declaration”).

After our first remand, CIA supplemented the Carle Declaration with a 1993 affidavit by Katherine Strieker. Declaration of Katherine M. Stricker (Jan. 15, 1993) (“Stricker Declaration”); J.A. 248. In addition to the documents discussed in the Carle Declaration, Strieker addressed two new documents (documents 5 and 6 in her document description index, id. at 4; J.A. 251), which she described in significant detail. For example, Strieker referred to “document 6” as follows:

Id. at 17; J.A. 264.

Although both Carle’s and Strieker’s declarations offer sufficient details to allow a court to assess the propriety of most of the exemptions claimed by the CIA, Strieker’s declaration also contains a reference to “additional responsive documents” which the agency nowhere describes or explains. Id. at 4; J.A. 251. Apparently the agency intended to submit a classified index in camera, but for some reason failed to do so.2 With respect to these documents, which CIA has never described for Oglesby, the agency has clearly failed to meet its FOIA obligation to justify each and every exemption taken.

Despite CIA’s failure either to describe the documents or to submit the classified index in camera, the district court expressly found both that the CIA’s Vaughn index was adequate, Mem.Op. at 5; J.A. 470, and that the CIA had described its withheld information and its justifications for the withholdings, “with reasonable specificity, demonstrating a logical connection between the information and the claimed exemption.” Id. at 7; J.A. 472. At oral argument, counsel for the defendants conceded the need for a remand on this point.3

Oglesby challenges the adequacy of CIA’s Vaughn index, which we can quickly

declare insufficient with respect to the unde-scribed “additional” documents. However, Oglesby also claims that CIA has failed to justify its withholding, under FOIA exemptions 1 and 3, of material it did describe in the affidavits. First, he argues that CIA’s failure to explain expressly why the passage of time has not diminished the security concerns with respect to the undisclosed records renders the affidavits inadequate to justify the exemptions. Second, Oglesby charges that the district court should not have relied on the Strieker declaration because Ms. Strieker’s credibility had been tarnished by her involvement in a separate proceeding, in which she submitted an affidavit stating that disclosure of certain information, which it was later learned had been released thirty years before without incident, would cause damage to the national security if released. Appellant’s Brief at 36.

To back his claim that the passage of time has reduced the risk of this information leading to breaches in security, Oglesby points to the CIA’s Historical Review Program (“HRP”), pursuant to which the agency systematically reviews for declassification all records more than thirty years old. See HR 70-14 a.(1); J.A. 333. Although we would not go so far as the district court and deny that CIA’s review program “ha[s] any relevance” to Oglesby’s claim, Mem.Op. at 8 n. 4; J.A. 473, neither do we believe that the passage of time alone is enough to discredit an otherwise detailed and persuasive affidavit. Oglesby has not demonstrated that an agency’s national security concerns automatically disappear with the passage of time, and therefore has not rebutted the affidavits stating that the material had been reviewed at the time of the request, and had been determined to pose a current threat to national security if released.

Nevertheless, we hesitate to describe the existence of the review program as “irrelevant,” because if Oglesby could show that withheld information is substantially similar to information the government has declassified because of its age, he might raise a successful challenge to the government’s reliance on exemption 1. In this case, however, he has presented no such evidence; he has merely made the naked assertion that the passage of time renders the national security claims questionable. As long as an agency declares through its affidavits that the responsive material has been reviewed to assure the continuing accuracy of its original classification, and that a determination has been made that the withheld information still poses a security risk if released, the mere passage of time is not a per se bar to reliance on exemption l.4

With respect to Oglesby’s second challenge — to the credibility of CIA’s affiant — we note that the record contains no suggestion that the error Strieker allegedly made in the unrelated case involved any duplicity or intentional misrepresentation. Without any allegation of bad faith, we are unwilling to assume that an agency employee who withholds information that ultimately turns out to be substantially similar to information that has already been released — in short, an employee who makes a mistake — is forever barred from serving as a reliable affiant in the future. Accordingly, we reject Oglesby’s claim that the district court should have rejected the Strieker declaration on that basis.

NSA originally responded to Oglesby’s request by informing him that his fee waiver had been denied and that the search would likely cost him $900. After Oglesby filed suit for the first time, NSA reversed its original position and granted him a waiver. In 1990, the agency made its “final response” to the request, releasing four documents pertaining to “werewolves” and several others regarding Gehlen. In addition, the agency withheld several documents pursuant to exemptions 1 and 3.

Oglesby appealed the agency’s decision to withhold part or all of five separate reports and two letters. The NSA refused to disclose the documents in unredacted form because “release of certain portions of these documents would reveal specific information regarding communications intelligence and cryptologic activities, thereby jeopardizing intelligence sources and methods.” Declaration of Michael A. Smith 4 (May 4, 1992) (“Smith Declaration”); J.A. 167. Through the Smith declaration, NSA claimed that some of the withheld information (“such as titles of reference documents used in the preparation of one of the reports at issue, codewords and distribution caveats, and matters of foreign relations”) met the criteria for exemption 1, and the rest (“including employee names”) was also protected by exemption 3. Id. at 5; J.A. 168.

In subsequent affidavits, NSA supplemented the Smith declaration with statements by Boyd Wooton, J.A. 453 (“Wooton Declaration”), and Robert Killen, J.A. 456 (“Killen Declaration”). Wooton described the usual search procedure for NSA, and Killen provided details regarding the actual procedure the agency implemented in conducting Oglesby’s search. Killen ran a new search of the agency’s files, entering the terms: Gehlen, Strong, Dulles, Hunt, Rusty, Odessa, Kamar-adenwerk, Bruderschaft, Werewolf, Werewolves, Spinne, and Sunrise. Killen Declaration at 2; J.A. 457.

In June, 1994, Smith issued a supplemental declaration in which he explained that Kil-len’s search had produced eight new responsive documents. Supplemental Declaration of Michael A. Smith (June 28, 1994) (“Smith Supp.”); J.A. 459. Three of these documents were released in full and five were withheld in full. The supplemental affidavit offered no details regarding the five documents, but conclusively stated that they were all currently and properly classified either TOP SECRET or SECRET because “the disclosure of all or any portion of their contents could reasonably be expected to cause exceptionally grave damage and serious, damage, respectively, to the national security.” Smith Supp. at 3; J.A. 461. Smith also averred that these five documents satisfied the requirements for exemption 3 as well, since they contained classified information concerning communications intelligence activities. Id. at 4; J.A. 462. The affidavit concluded with the sweeping declaration that “it is not possible to describe further the withheld information in an unclassified declaration because any additional description would itself divulge classified information.” Id.

Oglesby claims that NSA’s Vaughn index inadequately describes the responsive material, and we are inclined to agree with him. With respect to documents located since this case’s last visit to the Court of Appeals, NSA’s affidavits contain only sweeping and eonclusory assertions that the agency withheld the documents because they contained material which could reasonably be expected to cause damage to national security. The affidavits offer no functional description of the documents; NSA has failed to disclose the types of documents, dates, authors, number of pages, or any other identifying information for the records it has withheld. Comparison of these affidavits with the Army and CIA declarations highlight the shortcomings of the NSA statements.

Thus we agree with Oglesby that NSA has clearly failed to provide an adequate Vaughn index. On remand, the district court should order NSA to submit an index describing the withheld documents to the greatest extent possible without disclosing information that must be protected.

C. Adequacy of the Searches

In addition to attacking the adequacy of the Vaughn indices and exemption justifica

tions offered by Army, CIA and NSA, Ogles-by challenges the adequacy of the searches conducted by those agencies, as well as by FBI and State.

In a letter to Oglesby dated March 31, 1986, Army explained that it had searched its automated Defense Central Index of Investigations (“DCII”) and Investigative Records Repository (“IRR”) for records responsive to his FOIA request. Letter from Thomas Conley to Carl Oglesby (Mar. 31, 1986); J.A. 41. According to the letter, DCII “is a computerized index to intelligence investigative records maintained by the Department of Defense” and the IRR “is the Army's official storage facility for all intelligence investigative records.” Id. at 1. Oglesby claims that Army has failed to aver that these two indices are the only places pertinent records might be stored. Appellant’s Brief at 44 (“The record also does not clarify whether INSCOM maintains other in-dices of its records, computerized or manual. Discovery is needed to answer these questions.”).

To back his claim on this issue, Oglesby cites to a book about Reinhard Gehlen in which the author asserts that Army Intelligence provided her with “well over a thousand documents” about Gehlen in response to her FOIA requests. Maey Ellen Reese, GeneRAl Reinhard Gehlen: The CIA Connection xiii (1990); J.A. 342. Although information in the record fails to reveal the precise nature of the FOIA request the book author submitted, and therefore her experience cannot prove that Army’s search was inadequate, her claim raises enough of a doubt to preclude summary judgment in the absence of an affidavit describing Army’s filing system and decision to search only the DCII and IRR indices. Although Oglesby argues that discovery is needed to answer his questions regarding the adequacy of Army’s search, a relatively detailed affidavit addressing the issue could suffice.

With respect to the CIA, the district court ruled that the agency had conducted an adequate search, and that CIA’s failure to describe its subsequent search which located additional records was “irrelevant.” Mem. Op. at 10; J.A. 475. We disagree that the court had sufficient information on which to base its summary judgment determination. Particularly since the record does not disclose how many additional documents were produced in the subsequent search, or offer any description of the nature of these documents, the court could not properly conclude that the original search (which failed to locate any of these possibly numerous and important documents) was “reasonably calculated to uncover all relevant documents.” Truitt v. Dep’t of State, 897 F.2d 540, 542 (D.C.Cir.1990); see also Founding Church of Scientology v. NSA, 610 F.2d 824, 837 (D.C.Cir.1979) (“[I]f, in the face of well-defined requests and positive indications of overlooked materials, an agency can so easily avoid adversary scrutiny of its search techniques, [FOIA] will inevitably become nugatory”).

The FBI submitted a detailed affidavit describing each document it found in response to Oglesby’s original request, as well as each paragraph or subparagraph deleted from each document. See Declaration of Angus Llewellyn (May 26, 1988) (“Llewellyn Declaration”). Because Oglesby does not attack the adequacy of the FBI’s index, we will not detail the documents withheld or the explanations offered to justify the exemptions.

Oglesby challenges only the adequacy of the search conducted by FBI. In response to his initial request, the FBI released a document which suggested to Ogles-by that certain Gehlen files might be found in a “section tickler” and that this tickler might contain records responsive to his request. He wrote to the FBI and asked that they search under additional terms and that they search the section tickler. See Declaration of Karlton D. Bolthouse 3 (Sept. 24, 1992); J.A. 229. On August 8, 1991, the FBI responded that it had conducted the additional requested search and had located no additional documents. The letter also informed Oglesby that the reference to a “section tickler” did

not indicate that any other responsive documents existed. Id. at 4; J.A. 230.

The FBI’s response to Oglesby described the Bureau’s search in sufficient detail to satisfy summary judgment standards. The FBI assured Oglesby that, “the reference to a ‘section tickler’ was not an indication that other responsive records existed,” id., and Oglesby has advanced no reason to doubt that allegation. Oglesby seems to believe that common sense dictates the conclusion that a “tickler” necessarily contains documents. We do not find it so clear that a “tickler” must be a repository for documents, and we will not second-guess FBI’s affidavit on this point.

As with the FBI, Oglesby challenges the district court’s ruling in favor of State only with respect to the adequacy of the department’s search.

In a 1992 declaration submitted by Frank Machak, State described its filing system and the search the department conducted in response to Oglesby’s request. Declaration of Frank Machak (Mar. 30, 1992) (“Machak Declaration”). According to the affidavit, State organizes its files under three categories: automated document system (files from 1973-present); central foreign policy files (1954-1973); and lot files (described by Ma-chak as “paper files retired by foreign service posts and by Department offices, covering the time period circa 1954-present that are maintained in sealed boxes, known as lots, and arranged according to subject matter and time periods”). Id. at 6; J.A. 155.

All State records covering the period prior to 1954 had been accessioned to NARA, and therefore State conducted a search only with respect to the first item on Oglesby’s request (records pertaining to Gehlen and his relationship with U.S. officials). A research specialist determined that any documents responsive to Oglesby’s request which had been retained by State would be contained in the central foreign policy files. State apparently did not search the lot files, because “the description of records requested ... was not specific enough to allow for [it].” Id. at 9; J.A. 158. Lot files are organized only by nine broad subject categories (administration, business affairs, consular affairs, economic affairs, military and defense, operations, political affairs, social affairs, and technology & science), and not by individuals’ names. Id.

Oglesby raises two objections to State’s conduct of its search: first, he alleges that the Department’s failure to search the lot files rendered the search inadequate; and second, he claims that the court cannot rule on the adequacy of the search based on Machak’s declaration because Machak was allegedly involved in an unlawful attempt to expedite an unrelated FOIA request in 1992. Appellant’s Brief at 47. The district court rejected these claims, and we affirm that decision.

State adequately addressed the first of Oglesby’s concerns when it explained that the lot files are organized by nine broad subject categories and not by individuals’ names. J.A 158. Since State’s search only reached the first item on Oglesby’s list (because the other items had been accessioned to NARA), the department sought only information pertaining to Gehlen and his relationship with U.S. officials. If, as the affidavit alleges, the lot files cannot be searched for an individual’s name, we find that it is reasonable that State would require more specific information in order to search these files.

Oglesby’s second challenge also lacks merit. The district court found “no reason to doubt Machak’s credibility in this ease,” and we find no reason to challenge that conclusion. Particularly in light of the fact that the judge in the case which Oglesby claims reveals Machak’s untrustworthiness ultimately determined that Machak’s declaration in that case had been “well grounded in fact,” Nation Magazine v. Dep’t of State, 92-cv-2302, slip opinion at 29 (D.D.C. Aug. 18, 1995), we find Oglesby’s unsupported allegations attacking Machak’s credibility insufficient to convince us to reverse the district court’s decision.

Oglesby claims that the Smith declaration “contains no information whatsoever

concerning the nature of the search it conducted.” Appellant’s Brief at 48. What Oglesby’s brief fails to mention is that on remand, NSA submitted additional affidavits that do detail the nature of the agency’s search. The Killen declaration explains that Killen personally ran all of the main terms in Oglesby’s request through NARA’s Archival Information Retrieval System (“AIRS”), “the only system of records ... that could reasonably be expected to contain any archival records responsive to plaintiffs FOIA request.” Killen Declaration at 1; J.A. 456. Because Oglesby has put forward no reason to doubt the sufficiency of this search, we affirm the district court’s holding that NSA had demonstrated the adequacy of its search.

III. Conclusion

In sum, we affirm the district court in part and reverse in part, holding:

Thus, we affirm the district court’s decision with respect to NARA, FBI, and State, but reverse and remand for further proceedings involving Army, CIA and NSA.