The fall and rise of cryptanalysis at CSE

A slightly rewritten and updated version of an article on CSE's cryptanalysis effort that I wrote about 17 years ago:


Canada has been in the cryptanalysis business since the NRC Examination Unit was established in 1941. The CBNRC, now known as CSE, took over this cryptanalytic role on its inception in 1946.[1]

Cryptanalysis continued to play a prominent role in the CBNRC's activities for more than a decade. However, during the late 1950s (probably November 1957), the organization for the most part abandoned its cryptanalytic effort against machine cipher systems: "The Communications Branch gradually got out of serious cryptanalysis. Worldwide improvements in cipher security made it too expensive."[2]

By the late 1970s, very little cryptanalysis was still being done by CSE.[3] The organization's cryptanalysis unit, the O1 section of O Group, "had a poor reputation as a dead end, being unproductive". O1's computer resources were limited and much of its work was still being done by hand. Only one O1 staffer, O1A member Ed Cheramy, was doing full-fledged codebreaking, and he worked only on manual cryptosystems. The other members of O1A had "moved away from cryptanalysis" and were engaged instead in "linguistic analysis," the recovery of garbled plain text, and "depth reading," a more limited form of cryptanalysis in which sections of encrypted text are recovered by painstakingly comparing two or more messages encrypted with the same key or closely-related keys. O1B, the other subunit of O1, recovered high-frequency radio call signs through traffic analysis.[4]

At the beginning of the 1980s, however, CSE decided to revitalize Canadian codebreaking capabilities. In the spring of 1980, Tom Briscoe, the new head of O1, sent O1A staffer Thomas Johnston to NSA "to assess and study the cryptoanalysis [sic] performed there and recommend to CSE how it could re-enter the area of cryptanalysis." Johnston's report led CSE's management to conclude that the only way for CSE to re-enter the cryptanalysis business was to hire a new cryptanalysis staff with advanced mathematical training and purchase a powerful supercomputer to support their work.[5]

At the time, however, CSE didn't have the money for a supercomputer. CSE's largest computers were its IBM 370 mainframes; O1 was accessing the SIGINT databases kept on the mainframes, but using PDP-8 and PDP-11 computers to run its linguistic analysis and call sign recovery software. The section's equipment budget was only $8,000, and it would take time to get approval for a multi- million dollar computer purchase.[6] In the interim, therefore, Johnston recommended that O1 try to use one of the IBMs for cryptanalysis. NSA reportedly doubted that any useful results could be achieved with this system, but it nonetheless assisted Johnston's efforts, supplying daily key information on the system he was trying to break. Meanwhile, O1A went ahead with hiring new mathematicians to replace the people retiring or transferring out of the unit. The first two new staff members, John Mulholland (who was already a CSE employee) and Luc Laplante, joined O1A later that year, and immediately set to work helping Johnston (who had since become head of O1A) on the "machine cryptanalysis" project.[7]

It was none too soon. Late in 1980, while the O1A team was still labouring over its software, CSE unexpectedly found itself out of the codebreaking business. A sudden illness had forced Ed Cheramy to leave work (he died early in 1981). During the period between Cheramy's departure from CSE and January 1981, when Michel Jetté was transferred from M Group and took over Cheramy's work, nobody at CSE was actually "breaking codes." (In 1982, Jetté was reassigned to machine cryptanalysis and CSE's manual work was effectively dropped. Former cryptanalyst Celia McInnis has stated that she saw only one "manually generated code" during the entire period - August 1985 to March 1988 - that she worked in O1.) Depth reading, however, continued.[8]

In the spring of 1981, O1A finally achieved a minimal cryptanalysis capability on the IBM. Nevertheless, estimating that the IBM "would cease to be effective [for cryptanalysis] within one to two years," Johnston (by then head of O1) recommended again in 1981 that CSE purchase a "suitable scientific computer" for cryptanalysis.[9]

Late in 1983 or early in 1984, the purchase of O1's cryptanalysis computer was finally approved.[10] At the same time, 14 new positions were authorized in O1A: 8 cryptanalyst-mathematicians, 3 computer operators, 2 engineers, and 1 assistant. By 1985, most of these positions had been filled.[11]

Cray supercomputer

The computer initially approved may have been either a Cyber 740 or a Cray supercomputer; the evidence is unclear on this point. After consultations with NSA in April 1984, however, CSE settled on the Cray X-MP supercomputer. The X-MP was Cray's second generation of supercomputer; developed in 1982, it superseded the original Cray-1 model developed in 1976. The purchase was formally approved in June 1984, under the name Project PM-40 (or Project Elevator), and a purchase contract was signed with Cray Research Inc. the following December.[12]

CSE's Cray X-MP/11 (modified) supercomputer was delivered to the Sir Leonard Tilley building in March 1985. Purchased for a mere $8,536,210, CSE's Cray was the budget version of the X-MP, containing just 1 central processing unit and 1 megaword of central memory (hence the designation X-MP/11).[13] Nonetheless, it was an impressive machine. At the time of its purchase, it was the most powerful computer in Canada. (The machine is reportedly now on display inside one of CSE's buildings. Comparable X-MPs are also on display in the lobby of the Defence Signals Directorate's headquarters and at the NSA museum at Fort Meade, Maryland.)

[Update 12 November 2020: According to the Canada Museum of Science and Technology, the computer was retired on 24 August 1995. "Known as ANT-1, it was principally used to solve complex mathematical alogarithms related to codes and code breaking. The shell of the computer is still at the CSE (2005). When decommissioned, staff at the CSE were each given a few of the boards but had to sign a Cray form agreeing not to provide information about the boards to foreign nationals as required by the US Export Administration Regulations."]

[Update 2 April 2024: You can see a photo of the computer here.]

The system underwent continuous upgrades following its arrival in 1985. The first element to be upgraded was the disk subsystem, which was traded in for the DD-49 system, with twice the capacity, in April 1986. The trade cost CSE an extra $849,848. In 1987-1988, a much more ambitious upgrade was undertaken. Three megawords of central memory were added to the X-MP/11, making it an X-MP/14. This additional central memory enabled more complex problems to be tackled without slowing the system down by resorting to external storage systems. At the same time, a special 64-megaword Solid-state Storage Device (SSD) was added to the system. This upgrade—apparently planned from the beginning—cost CSE a total of $4,340,880, more than half the cost of the original X-MP/11, for a total expenditure of about $13,726,938 (not including maintenance fees paid to Cray Canada Inc.).[14]

An even more ambitious upgrade took place at the end of 1989, when the entire system was augmented at a cost of $4,695,240. Elements of the initial part of this upgrade entered service in December 1989, with the rest entering service in February 1990. In September 1990, the upgrade itself was expanded, with its purchase price being amended to $5,664,240. Subsequent additions to the system took place in February 1991 ($876,766) and March 1992 ($680,260), the latter consisting of updated disk drives and controllers.[15]

At the beginning of the 1990s, CSE also acquired a Floating Point Systems FPS 522-EA supercomputer, apparently paying $1,620,371. This computer was upgraded to a Cray S-MP superserver following Cray's acquisition of Floating Point Systems in December 1991.[16] According to Cray, S-MP "superservers are intended to work as a bridge between SPARC-based workstations and larger Cray Research supercomputers on the same network."

The above purchases, plus a number of other, minor purchases that have been revealed, add up to a total of $9,142,534, making a grand total of $22,869,472 spent on CSE's Cray systems between 1984 and March 1992.[17] Counting contracted maintenance between 1 May 1985 and 30 June 1994, CSE spent more than $34 million on its Cray systems up to 1994.[18]

NSA contribution

The NSA contribution to CSE's Crays was indispensable. NSA not only supplied the basic Cray software, the Folklore operating system, it also trained at least three of O1's cryptanalysts in the use of the machine: "Operations required that O1 have in residence the expertise to continuously modify the operating system. Thus, Dr. Johnston arranged for the American counterparts to train the computer operators and the O1 staff for CSE."[19]

The first O1 staff member sent for training at NSA was Christina Sattler, a CO-3 (trainee) cryptanalyst, who had joined O1B in 1982 to run the call sign software on the PDP-11. Early in March 1984, Sattler started a 14-month stint at NSA's Fort Meade headquarters, returning to Ottawa late in April 1985, just in time to help get the Cray up and running. John Mulholland, then head of O1A, also went to NSA for training in 1984, starting a 12-month stint at Fort Meade in April and returning, like Sattler, just in time to help get the Cray running. Finally, upon the return of Mulholland and Sattler, Luc Laplante was sent to NSA for 3 years of training, returning to CSE in the summer of 1988.[20] Mulholland and Laplante were still working with Cray systems at CSE as recently as 2002 and 2003, respectively.

In addition to NSA's training assistance, CSE also conducted its own training to prepare for the Cray's arrival. One such course, run in February 1985 "as a result of direct operational requirements," was shift-register cryptology, which required 3 weeks of full-time study. Among the 16 students who took the course were 5 members of O1, nearly half of O1's working cryptanalysts. (Most of the other students were from S Group in CSE's INFOSEC arm.)[21]

Modern cryptanalysts need an extensive background knowledge of both mathematics and computer programming. As Johnston wrote in 1986, "Although it is fair to say that one need not necessarily be a graduate Mathematician to be a good cryptanalyst, modern cryptologic developments make it extremely unlikely that one can be a good cryptanalyst without having a good basis in Mathematics. Our recruitment processes have therefore been aimed at the selection of personnel with good analytic abilities who also happen to have the requisite formal mathematical education."[22]

Even with this background, new members of O1 underwent up to 3 years of classroom and on-the-job training before they became fully-qualified cryptanalysts.[23] Required internal courses included

• CA-105 - Introduction to Cryptography and Exploitation of Manual Cryptosystems
• CA-107 - Exploitation of Manual Cryptosystems
• CA-123 - Shift-Register Cryptology
• CA-223 - Advanced Shift-Register Cryptology
• CA-247 - Vocoders for Cryptanalysts
• MA-213 - PTAH [whatever that is]
• MA-246 - Cryptomathematics for Mathematicians
• MA-256 - Signal Processing Mathematics[24]

The cryptanalysts also required extensive computer programming knowledge and specific training on using the Cray, starting with Introduction to IMP/Folklore.[25]

Organizational changes

In addition to the acquisition of the Cray, a number of organizational changes were also undertaken as O1 was transformed during the 1980s. In 1982, for example, depth reading was transferred out of O1A, and, in June 1984, O1B was disbanded entirely, with its call sign recovery work, more formally known as the "[deleted] Identification Systems Task," transferred to M Group, which previously had been the recipient of O1B's product. The 4 staff positions in O1B were transferred to M4B, leaving only the head of O1, the section clerk, a cryptanalytic engineer, and O1A in O1 section.[26]

Another major change came in the summer of 1985, by which time O1's Cray was finally running and O1A had grown to a staff of about 16, too large for one unit to administer. Effective 2 July 1985, O1A was broken into 2 parts: a smaller O1A (Cryptanalysis Research and Diagnosis) with 8 members, and a new O1B (Computer Production) also with 8 members. O1E (the Cryptanalytic Engineer) remained unchanged with its single member, leaving the new O1 with a total staff of 19.[27]

Finally, in 1986, O Group itself was reorganized. O1B's computer support personnel were transferred out of the section and combined with O2's computer support personnel (O2 was a traffic analysis section) to create a new O3 section, with 6 or 7 members, which became responsible for the "pure computer sciences support" for O Group. Production cryptanalysis runs remained with the 6 remaining members of O1B, and O1A was unchanged.[28] As a result of these changes, about 17 personnel were left in the O1 section as a whole: 15 had extensive and up-to-date cryptanalytic training and 12 were working cryptanalysts.

Update

Little information is available about cryptanalytic developments at CSE since the 1990s. CSE's original Cray computers have long since retired, but (as mentioned above) Mulholland and Laplante continued working with Cray systems at CSE well into the current century. A couple of generations of Crays (e.g., the Cray T3E) have apparently come and gone in the meantime, and the current generation of Crays is evidently still in use. CSE's recent cash influx may well include money to upgrade to the next generation. A new generation of cryptanalysts has also appeared—apparently literally in the case of Maureen Patteeuw, who is presumably the daughter of Marcel Patteeuw, one of CBNRC's originals. The elder Patteeuw headed CSE's cryptanalysis efforts for a number of years and served as CANSLO/L in the late 1970s/early 1980s. The younger was working with CSE's Crays as recently as 2008.

End Notes

[1] For more information, see John Bryden, Best-Kept Secret: Canadian Secret Intelligence in the Second World War, 1993.

[2] Best-Kept Secret, p. 326.

[3] Most of the information in the remainder of this page was originally published in "The Fall and Rise of Cryptanalysis in Canada," Bill Robinson, Cryptologia, January 1992. This article in turn was derived primarily from a single source, the account recorded in Muriel Korngold Wexler, Record of Decision, Public Service Staff Relations Board file 166-13-17850, 12 March 1990, concerning the case of Edwina Slattery, a former head of O1B, who the PSSRB concluded had been unjustly fired by CSE. Ms. Slattery has stated that, among other faults, the account in the Record of Decision overvalues the contributions of some members of O Group and undervalues the contributions of others.

[4] Record of Decision, pp. 7-9.

[5] Record of Decision, p. 9.

[6] "Computer Programmer" (careers ad), Ottawa Citizen, 10 January 1981, p. 40; Record of Decision, pp. 7, 9, 20.

[7] Record of Decision, pp. 9-12, 14.

[8] Record of Decision, pp. 13-14, 44-45; Tillian, 1981-1, p. 17.

[9] Record of Decision, pp. 10-11.

[10] Record of Decision, p. 11 states spring 1984, but pp. 15, 23 and 61 imply 1983, as does "Mathematicien en science de l'informatique" (careers ad), Ottawa Citizen, 23 July 1983, p. 20. The discrepancies may reflect the difference between a general decision to buy a cryptanalysis computer and a specific decision to proceed with a particular purchase.

[11] Record of Decision, p. 15.

[12] Record of Decision, pp. 11, 15. The model eventually purchased is revealed in contract 12213-4-9120, Supply and Services, 3 December 1984, released in severed form under Access to Information Act.

[13] Contract 12213-4-9120, purchase price determined by subtracting maintenance fees as calculated from information in amendments 001-004, also released in severed form under Access to Information Act.

[14] Contract 12213-5-0250, Supply and Services, 22 August 1985, released in severed form under Access to Information Act; contract W2213-7-4161 and amendment 001, Supply and Services, 27 November 1987 and 28 January 1988, released in severed form under Access to Information Act. Record of Decision, p. 11, reports that the cost of "the Cray" was $13.5 million and the cost of the unidentified computer authorized before April 1984 was $8.3 million, very close to the $8.5 million that CSE paid for the X-MP/11(mod) before its upgrades. It is possible, therefore, that the X-MP/11 was the originally authorized computer and that the April 1984 consultations with NSA determined that the X-MP/11 would require upgrading to be compatible with NSA's Crays.

[15] Contract W2213-9-4386, Supply and Services, 29 November 1989; contract W2213-9-4386/02, Supply and Services, 31 March 1990; contract W2213-9-4386/01, Amendment 1, Supply and Services, 7 September 1990; contract W2213-0-0721, Supply and Services, 24 December 1990; contract W2213-1-2936, Supply and Services, 4 March 1992, all contracts released in severed form under Access to Information Act.

[16] The FPS 522-EA purchase contract probably was contract W2213-9-6127, listed in Government Business Opportunities, 17 January 1990, p. 34. The system itself is identified in maintenance contract W2213-2-3509, Supply and Services, 17 July 1992, released in severed form under Access to Information Act. Cray S-MP superserver: see contract W2213-2-3509 and Government Business Opportunities, 15 April 1992, pp. 13-14.

[17] Above-listed contracts, plus contract W2213-9-4562 ($117,600), Supply and Services, released in severed form under Access to Information Act; contract W2213-9-4557 ($79,560), Supply and Services, released in severed form under Access to Information Act; and contract W2213-9-4561 ($103,737), listed in Government Business Opportunities, 1 August 1990, p. 10.

[18] See contracts 12213-9120, W2213-7-4162, W2213-9-4386/02, W2213-0-0701, W2213-2-3509, and relevant amendments, Supply and Services, all released in severed form under Access to Information Act.

[19] Record of Decision, pp. 11, 19; contract 12213-4- 9120.

[20] Record of Decision, pp. 19, 20, 39.

[21] PSSRB file 166-13-17850, exhibit 132 ("Staff training and development: course notice," CSE file U2/012-85, 7 January 1985).

[22] PSSRB file 166-13-17850, exhibit 31 ("Requirements for a Career in Cryptanalysis," CSE file O.109-86, 3 March 1986).

[23] PSSRB file 166-13-17850, exhibit 133 ("O1 training requirements," CSE file O.19-86, 9 January 1986).

[24] PSSRB file 166-13-17850, exhibit 31.

[25] PSSRB file 166-13-17850, exhibit 133.

[26] Record of Decision, pp. 14, 113; PSSRB file 166- 13-17850, exhibit 112 ("Resubordination of the [deleted] Identification Systems Task," CSE file ORG/6-4/ORG/6-2, 3 May 1984).

[27] PSSRB file 166-13-17850, exhibit 111 ("O1 Position Code Numbers," CSE file O.359-85, 17 June 1985); PSSRB file 166-13- 17850, exhibit 110-A ("Reorganization of O1," CSE file O.350-85, 17 June 1985).

[28] Record of Decision, pp. 18-19.