Newer records regarding NSA, NIST, and post-quantum cryptography

1. Summary

This is a FOIA request for the records described below. This request is organized into six sections: (1) summary; (2) preamble part 1 (copied from the preamble of my 16 March 2022 FOIA request, and included here to keep this request self-contained), (3) preamble part 2; (4) request for records; (5) request for fee categorization (same as the request for fee categorization in my 16 March 2022 FOIA request); (6) request for fee waiver (same as the request for fee waiver in my 16 March 2022 FOIA request).

2. Preamble part 1

NSA's policy decision to sabotage public cryptographic standards is described in an internal NSA history book released in 2013:

https://nsarchive2.gwu.edu/NSAEBB/NSAEBB441/
https://archive.org/details/cold_war_iii-nsa/cold_war_iii-ISCAP/page/n239/mode/2up

The critical quote from NSA's history book is as follows: "Narrowing the encryption problem to a single, influential algorithm might drive out competitors, and that would reduce the field that NSA had to be concerned about. Could a public encryption standard be made secure enough to protect against everything but a massive brute force attack, but weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques?"

The first cryptographic mechanism standardized by NBS/NIST was DES in the 1970s. DES had a key size that was too small for security. The same history book reports that NSA had managed to "convince" the DES designers to reduce the key size.

In the 1990s, NIST proposed DSA, another cryptographic mechanism with a key size that was too small for security. A lawsuit by CPSR revealed that DSA had been secretly designed by NSA:

https://web.archive.org/web/20200229145033/https://catless.ncl.ac.uk/Risks/14/59

In 2005, 2006, and 2007, ISO, NIST and ANSI respectively issued standards for Dual EC, a cryptographic mechanism with an NSA back door:

https://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html

The same 2013 report describes NSA's budget to "covertly influence and/or overtly leverage" cryptography to make it "exploitable", in NSA's words. The budget had grown to a quarter of a billion dollars per year. Presumably NSA's budget for cryptographic sabotage is even larger today.

NIST's Dual EC post-mortem concluded that "It is of paramount importance that NIST's process for developing cryptographic standards is open and transparent and has the trust and support of the cryptographic community":

https://web.archive.org/web/20220219211917/https://www.nist.gov/system/files/documents/2017/05/09/VCAT-Report-on-NIST-Cryptographic-Standards-and-Guidelines-Process.pdf

The same post-mortem shows NIST's invited reviewers recommending clear transparency rules, such as "full documentation of all decisions, and clear processes for the disposition of each and every comment received", along with being open about "what authorities were consulted".

In 2016, NIST's call for proposals for its Post-Quantum Cryptography Standardization Project stated that "NIST will perform a thorough analysis of the submitted algorithms in a manner that is open and transparent to the public":

https://web.archive.org/web/20220119113311/https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

81 FR 92787 says that this call for proposals establishes the criteria "that will be used to appraise the candidate algorithms":

https://www.federalregister.gov/documents/2016/12/20/2016-30615/announcing-request-for-nominations-for-public-key-post-quantum-cryptographic-algorithms

Regarding the Post-Quantum Cryptography Standardization Project, NIST stated in October 2021 that "We operate transparently. We've shown all our work":

https://web.archive.org/web/20211115191840/https://www.nist.gov/blogs/taking-measure/post-quantum-encryption-qa-nists-matt-scholl

However, my current understanding is that, for five years, NIST was intentionally concealing NSA's involvement in this project. On 22 July 2020, NSA and NIST issued coordinated announcements that made reasonably clear NSA was involved but that did not reveal the details. On 2 August 2020, I asked "What exactly has NSA told NIST regarding NISTPQC, regarding security levels or otherwise?" NIST did not answer. NIST later tried to suggest that NSA has had only a minor influence, but NIST has provided no records showing what NSA's input actually was.

More broadly, most of the information that I've found on NIST's web site for this project is simply copies of submissions. NIST has posted some extra information, but the total volume of information in NIST's reports, web pages, and mailing-list messages obviously falls far short of "all our work". Anyone trying to obtain more than a superficial understanding of what has happened in this project rapidly discovers that critical information is missing. See Section 5 of the following paper for various examples of mysteries regarding the NIST process:

https://cr.yp.to/papers/categories-20200918.pdf

I've filed six FOIA requests with NIST since mid-2020. NIST has released a few dribbles of information, but in general NIST's responses have been very slow and obviously not complete. For example, my FOIA request #20210610-NIST eight months ago, which asked for "copies of all NIST records of communication between NSA and NIST regarding the NIST Post-Quantum Cryptography Standardization Project", has, so far, produced zero records, even though NIST had already admitted in the following document that it made changes to a report based on "feedback received (from the NSA)":

https://web.archive.org/web/20210508052729/https://csrc.nist.gov/CSRC/media/Presentations/pqc-update-round-2-and-beyond/images-media/pqcrypto-sept2020-moody.pdf

Analyzing NSA's impact on this project will require not just seeing NSA's communication with NIST, but also tracing how NIST's decisions were made and analyzing the influence of the information that NIST received from NSA. If each step of this analysis requires dealing with another round of stonewalling from NIST then the analysis will obviously not be done in time to help the public make safe decisions regarding post-quantum cryptography.

NSA's documented history of sabotage, along with its evident sway over NIST, makes NSA's influence on NIST a high priority to review, but it also seems likely that other entities have also been trying to sabotage NIST's process. As far as I can tell, NIST has no procedures in place to prevent attackers from influencing the project through pseudonyms, proxies, etc. Anything short of a full review of project records could easily miss evidence of attacks.

Even without sabotage, getting cryptography right is challenging. Public review has identified security flaws in dozens of submissions and has identified many errors in the limited additional information released by NIST. Having NIST keep most of its analysis secret is a recipe for disaster. Given that NIST promised to be "open and transparent", and recently claimed to have "shown all our work", it's hard to understand why the full project records aren't already available to the public.

3. Preamble part 2

After the above preamble, my 16 March 2022 FOIA request asked for a copy of NIST's records regarding the NIST Post-Quantum Cryptography Standardization Project, and specifically for all records of NIST/NSA meetings mentioning the word "quantum", whether or not NIST views those meetings as part of this project.

NIST did not comply with the FOIA deadlines. NIST did not produce any records until half a year later, after I filed a lawsuit. The records that I have seen from NIST so far are limited, and do not include any of NIST's communications with NSA:

https://nist.pqcrypto.org/foia/

The records do show NIST intentionally violating its transparency promises. For example, NIST secretly marked various documents "not for public distribution".

Furthermore, the records show NIST applying secret evaluation criteria rather than the official evaluation criteria. For example, NIST secretly compared submissions on the basis of private-key size.

The records also show NIST making one content mistake after another. For example, NIST secretly described a 2020 attack as "a general timing attack on all Fujisaki-Okamoto schemes" when in fact the attack was much more specific.

If NIST had actually "shown all our work" then various errors would have been corrected much sooner.

I expected that, after the FOIA request and subsequent lawsuit, NIST would realize that it had promised to be "open and transparent" and would begin acting accordingly. Instead NIST appears to have become even more intent upon hiding records.

For example, NIST has recently announced a plan to standardize Kyber-512. NIST has issued a questionable claim that Kyber-512 meets the project's announced security requirements. Full details of how NIST arrived at this conclusion should have been made promptly available for public review.

NIST says that it consulted "among ourselves and with the Kyber team" to reach this conclusion. However, NIST still has not published those communications.

I have asked various questions regarding how NIST reached this conclusion. I find it clear from NIST's reaction that NIST's lack of transparency on this topic is intentional.

4. Request for records

Please send me, in electronic form, a copy of NIST's records regarding the NIST Post-Quantum Cryptography Standardization Project from 16 March 2022 up to the day that this request is processed.

My 16 March 2022 FOIA request similarly requested records up to the day that that request was processed. If NIST tells me the cutoff date that it assigned for my 16 March 2022 request then I will be happy to narrow this new request to cover only records starting from that date.

This request includes, but is not limited to, documents from NIST, documents from NSA, documents from other U.S. government agencies, and documents from foreign government agencies. This request also includes all records of NIST/NSA meetings during the specified period, whether or not NIST views those meetings as part of this project.

If there are any responsive records that are publicly available on NIST's web site as of the date that this request is processed, I request that NIST provide the specific URL for each record. Please clearly indicate any such parts of your response as "Records already available".

For all other responsive records, I request that NIST deliver the records in their original electronic format, such as PDF format, or as PDF scans for documents that were originally created on paper.

5. Request for fee categorization

Please confirm that you're categorizing this FOIA request, like my previous FOIA requests, under the "educational" requester category. You can find my University of Illinois at Chicago profile here:

https://cs.uic.edu/profiles/daniel-j-bernstein/

Here is an example of a paper that I coauthored analyzing previous NSA sabotage of cryptographic standards:

https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf

This paper was published as pages 256 through 281 in "The new codebreakers", edited by Peter Y. A. Ryan, David Naccache, and Jean-Jacques Quisquater, Lecture Notes in Computer Science 9100, Springer, 2015, ISBN 978-3-662-49300-7. The paper already has more than 100 citations, according to Google Scholar.

6. Request for fee waiver

I request a waiver of all fees. I am filing this request via MuckRock to ensure that the results will be made easily available to journalists and to the general public. This disclosure will contribute significantly to public understanding of NIST activities, and I have no commercial interest that would be furthered by the requested disclosure.

Regarding the six fee-waiver factors:

(1) Whether the subject of the requested records concerns "the operations or activities of the government": 81 FR 92787 is a Federal Register notice calling for submissions to a government project and saying how the submissions would be evaluated. This is a request for the records of what has happened in that project.

(2) Whether the disclosure is "likely to contribute" to an understanding of government operations or activities: Given records from the 1970s through the 2010s demonstrating NSA motivations, budgets, and activities to sabotage cryptographic standards (see links above), presumably NSA has also been trying to sabotage the NIST Post-Quantum Cryptography Standardization Project. Documents released in the past have played a major role in public analyses of NSA sabotage and other problems with NIST's cryptographic standards; see, e.g., the role of these releases in https://cr.yp.to/talks.html#2013.12.28.

(3) Whether disclosure of the requested information will contribute to "public understanding" as opposed to just "individual understanding": I have already posted a variety of in-depth analyses of the limited information that NIST has released so far regarding the Post-Quantum Cryptography Standardization Project (see, e.g., https://cr.yp.to/papers/categories-20200918.pdf), and will similarly post analyses of the further information released under this FOIA request. Cryptography is a technical subject, but there are more than 1000 members of the International Association of Cryptologic Research. There are also established mechanisms of bringing cryptographic news to broader audiences and to the general public, reflecting the public interest in the safety of Internet communication. I have been fighting NSA's cryptographic sabotage for 30 years (see, e.g., _Bernstein v. United States_, 176 F.3d 1132); together with colleagues, I have found many problems with NIST's previous NSA-influenced work on cryptography (see, e.g., https://cr.yp.to/newelliptic/nistecc-20160106.pdf), and have given talks to audiences of thousands based on NSA/NIST documents (see, e.g., https://cr.yp.to/talks.html#2013.12.28).

(4) Whether the disclosure is likely to contribute "significantly" to public understanding of government operations or activities: The limited information that NIST has released regarding the Post-Quantum Cryptography Standardization Project provides only superficial explanations of what happened in the project. It is impossible today for the public to track what inputs were provided to NIST and to analyze how the inputs influenced NIST's decisions, whereas transparency will give the public an answer to these critical questions. Transparency was also highlighted in NIST's Dual EC post-mortem (see link above), recognizing the effectiveness and importance of public disclosures of this type of information regarding cryptographic standards.

(5) Whether the requester has a commercial interest that would be furthered by the requested disclosure: No. I'm a professor. I make my work available for free with no royalties. My interest is in ensuring the safety of cryptographic mechanisms used by the general public.

(6) Whether any such commercial interest outweighs the public interest in disclosure: Not applicable. See #5.

Please let me know if you need any further information.

---Daniel J. Bernstein

I have checked the FOIA statute. The statute requires a response within 20 days after "the request is first received by the appropriate component of the agency". It does not make an exception to this deadline for agencies that set up systems to file some of the received requests as "junk".

I sent my request to NIST's designated foia@nist.gov email address. NIST received the request on 24 January 2023, and was then subject to a 20-day deadline under FOIA. I do not consent to any extension of the FOIA deadlines.

---Daniel J. Bernstein

Pursuant to 5 U.S.C. § 552(a)(7)(B)(ii), I request an estimated date of completion for DOC-NIST-2023-001133.

---Daniel J. Bernstein