Late last year, the NSA declassified and released a redacted version of Lambros D. Callimahos’s Military Cryptanalytics, Part III. We just got most of the index. It’s hard to believe that there are any real secrets left in this 44-year-old volume.
Entries Tagged "cryptanalysis"
Page 1 of 19
General Packet Radio Service (GPRS) is a mobile data standard that was widely used in the early 2000s. The first encryption algorithm for that standard was GEA-1, a stream cipher built on three linear-feedback shift registers and a non-linear combining function. Although the algorithm has a 64-bit key, the effective key length is only 40 bits, due to “an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance.”
GEA-1 was designed by the European Telecommunications Standards Institute in 1998. ETSI was — and maybe still is — under the auspices of SOGIS: the Senior Officials Group, Information Systems Security. That’s basically the intelligence agencies of the EU countries.
Details are in the paper: “Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2.” GEA-2 does not have the same flaw, although the researchers found a practical attack with enough keystream.
Hacker News thread.
EDITED TO ADD (6/18): News article.
I have been seeing this paper by cryptographer Peter Schnorr making the rounds: “Fast Factoring Integers by SVP Algorithms.” It describes a new factoring method, and its abstract ends with the provocative sentence: “This destroys the RSA cryptosystem.”
It does not. At best, it’s an improvement in factoring — and I’m not sure it’s even that. The paper is a preprint: it hasn’t been peer reviewed. Be careful taking its claims at face value.
Some discussion here.
I’ll append more analysis links to this post when I find them.
The NSA has just declassified and released a redacted version of Military Cryptanalytics, Part III, by Lambros D. Callimahos, October 1977.
Parts I and II, by Lambros D. Callimahos and William F. Friedman, were released decades ago — I believe repeatedly, in increasingly unredacted form — and published by the late Wayne Griswold Barker’s Agean Park Press. I own them in hardcover.
Like Parts I and II, Part III is primarily concerned with pre-computer ciphers. At this point, the document only has historical interest. If there is any lesson for today, it’s that modern cryptanalysis is possible primarily because people make mistakes
The monograph took a while to become public. The cover page says that the initial FOIA request was made in July 2012: eight and a half years ago.
And there’s more books to come. Page 1 starts off:
This text constitutes the third of six basic texts on the science of cryptanalytics. The first two texts together have covered most of the necessary fundamentals of cryptanalytics; this and the remaining three texts will be devoted to more specialized and more advanced aspects of the science.
Presumably, volumes IV, V, and VI are still hidden inside the classified libraries of the NSA.
And from page ii:
Chapters IV-XI are revisions of seven of my monographs in the NSA Technical Literature Series, viz: Monograph No. 19, “The Cryptanalysis of Ciphertext and Plaintext Autokey Systems”; Monograph No. 20, “The Analysis of Systems Employing Long or Continuous Keys”; Monograph No. 21, “The Analysis of Cylindrical Cipher Devices and Strip Cipher Systems”; Monograph No. 22, “The Analysis of Systems Employing Geared Disk Cryptomechanisms”; Monograph No.23, “Fundamentals of Key Analysis”; Monograph No. 15, “An Introduction to Teleprinter Key Analysis”; and Monograph No. 18, “Ars Conjectandi: The Fundamentals of Cryptodiagnosis.”
This points to a whole series of still-classified monographs whose titles we do not even know.
EDITED TO ADD: I have been informed by a reliable source that Parts 4 through 6 were never completed. There may be fragments and notes, but no finished works.
The whole story is puzzling. Cellebrite’s details will make it easier for the Signal developers to patch the vulnerability. So either Cellebrite believes it is so good that it can break whatever Signal does, or the original blog post was a mistake.
EDITED TO ADD (12/22): Signal’s Moxie Marlinspike takes serious issue with Cellebrite’s announcement. I have urged him to write it up, and will link to it when he does.
EDITED TO ADD (12/23): I need to apologize for this post. I finally got the chance to read all of this more carefully, and it seems that all Cellebrite is doing is reading the texts off of a phone they can already access. To this has nothing to do with Signal at all. So: never mind. False alarm. Apologies, again.
There’s no paper yet, but there are a bunch of details in the news articles.
Here’s an interview with one of the researchers:
Cryptologist David Oranchak, who has been trying to crack the notorious “340 cipher” (it contains 340 characters) for more than a decade, made a crucial breakthrough earlier this year when applied mathematician Sam Blake came up with about 650,000 different possible ways in which the code could be read. From there, using code-breaking software designed by Jarl Van Eycke, the team’s third member, they came up with a small number of valuable clues that helped them piece together a message in the cipher
This paper describes a SIGINT and code-breaking alliance between Denmark, Sweden, Germany, the Netherlands and France called Maximator:
Abstract: This article is first to report on the secret European five-partner sigint alliance Maximator that started in the late 1970s. It discloses the name Maximator and provides documentary evidence. The five members of this European alliance are Denmark, Sweden, Germany, the Netherlands, and France. The cooperation involves both signals analysis and crypto analysis. The Maximator alliance has remained secret for almost fifty years, in contrast to its Anglo-Saxon Five-Eyes counterpart. The existence of this European sigint alliance gives a novel perspective on western sigint collaborations in the late twentieth century. The article explains and illustrates, with relatively much attention for the cryptographic details, how the five Maximator participants strengthened their effectiveness via the information about rigged cryptographic devices that its German partner provided, via the joint U.S.-German ownership and control of the Swiss producer Crypto AG of cryptographic devices.
Sidebar photo of Bruce Schneier by Joe MacInnis.