Colossus and the Counting Attack on Lorenz Wheel Settings

Twelve wheels with co-prime periods, multiplied out, give about 1.603e19 possible starting positions for a Lorenz SZ40 or SZ42. That figure measures the key space, not the search that Colossus ran. The attack split the machine in two. The five chi wheels, with periods 41, 31, 29, 26 and 23, produce a combined period of 22,041,682; the five psi wheels, at 43, 47, 51, 53 and 59, produce 322,303,017, with motor wheels of 61 and 37 deciding when the psi wheels step. The attack decomposed the search rather than enumerating it. A first run tested two wheels together, 41 x 31 = 1,271 candidates, and later runs worked on other pairs or on single wheels. Each candidate was scored by a count taken over the entire message rather than accepted or rejected on the evidence of one character. That is what the machine was for: statistics at the speed of a paper tape, not arithmetic.

Scoring a hypothesis over the whole message

One pass of the tape corresponds to one hypothesised start position, or to five of them when the parallel processors were in use. At each character the machine forms a Boolean function of the ciphertext bits from the tape and the bits from the simulated wheels, then increments a counter if the function yields the value selected on the switch panel. Nothing is retained per character: the character is consumed, the condition is evaluated, a counter moves or not, and the next character arrives.

For a wrong hypothesis the total sits close to what chance predicts, about half the message for a balanced function. A correct hypothesis moves the total away from that value, because the plaintext is not random. German teleprinter traffic has an uneven distribution of characters, and differencing preserves enough of that unevenness for a count to detect. The operator set a threshold, called the set total, and the machine printed a line whenever a count passed it, giving a short list of candidates rather than a single answer. The operator read the totals and took the highest as the setting. Near-ties were separated by later runs over other impulse pairs or a longer stretch of text.

Differencing removes the psi component before counting

The key stream is the XOR of a chi component and a psi component. The chi wheels step once per character; the psi wheels step only when the motor wheels allow it, so consecutive characters frequently share the same psi bit. Bletchley Park’s notation for this is extended psi, and the practical consequence is that XOR-ing each impulse with the same impulse of the previous character removes most of the psi contribution from the relation. What remains ties the plaintext difference to the chi difference.

So the tape was differenced before it reached the counters, and the wheel simulator was differenced in step with it. This costs one character at the start of the message, since the first has no predecessor, and it changes the statistic from a frequency of characters to a frequency of transitions. The gain is that the psi wheels, whose start positions formed a separate and much larger search of 322,303,017 combinations, drop out of the chi-wheel problem.

The loop below is a model of the counting pass, not a simulation of Colossus and not a measurement of it. It takes the ciphertext as one bit per character, differences it, and scores each pair of start positions by a count over the whole message. The predicate is a parameter because the function and the counter were chosen by switches and plugs on the real machine. Differencing is linear over XOR, so differencing the combined chi stream is the same as combining the differenced wheels.

def delta(bits):
    """Each bit XOR-ed with its predecessor; the first bit is dropped."""
    return [b ^ p for p, b in zip(bits, bits[1:])]

def wheel_stream(cams, start, n):
    """The cam pattern read cyclically from a hypothesised start position."""
    period = len(cams)
    return [cams[(start + i) % period] for i in range(n)]

def best_start(z, cams1, cams2, holds):
    """Highest count over every pair of start positions, one pass per pair."""
    dct = delta(z)
    n = len(dct)
    best, best_score = None, -1
    for s1 in range(len(cams1)):
        a = wheel_stream(cams1, s1, n + 1)
        for s2 in range(len(cams2)):
            b = wheel_stream(cams2, s2, n + 1)
            dchi = delta([x ^ y for x, y in zip(a, b)])
            total = sum(1 for c, k in zip(dct, dchi) if holds(c, k))
            if total > best_score:
                best, best_score = (s1, s2), total
    return best, best_score

The cost is visible in that structure: 1,271 candidates for a two-wheel run, each requiring a full pass over the message. A 4,000-character message needs about five million character comparisons, and only the tape loop can supply them. Faster reading and more passes at once are the only ways to reduce wall time.

One tape instead of two

The Robinson machines, which preceded Colossus, read two paper tapes, one carrying the ciphertext and one carrying a key stream, and kept them synchronised mechanically. Two tapes at 2,000 characters per second had to stay in step for a whole run; they stretched and broke. Synchronisation, not logic, was the limit.

Colossus removed the second tape by generating the key stream electronically from simulated wheel patterns. One tape remained, read optically in a continuous loop at 5,000 characters per second, with the electronics clocked from the sprocket holes as they passed the reader. At that rate the tape travelled at almost 30 miles per hour. The reader had been run at up to 9,700 characters per second during development before the tape disintegrated, and 5,000 was adopted for regular use.

The trade is explicit. The machine can only test hypotheses about start positions, because the cam patterns for the wheels must be loaded into it beforehand. Wheel breaking, the recovery of the patterns themselves, had to happen by other means first, partly by hand and partly through tables that Colossus itself could produce. A wrong pattern produces no peak at all, and an operator reading the printout cannot distinguish a wrong pattern from a message too short for its deviation to clear the threshold. Short messages and mispunched characters degrade the same statistic.

Five processors reading one loop

There is no internal store for the message. The tape loop is the store, and the machine’s state is small: a six-character shift register both forms the difference and supplies the offset that lets five candidate start positions be tested at once. With five processors on the same tape, the effective rate was 25,000 characters per second.

The configuration is the program. Switches on the selection panel chose whether the ciphertext signal was the raw character or its difference, and made the same choice for the chi and psi streams; the jack field and switch panel routed the result to a chosen counter. The number of combinations available from those switches and plugs is given as about five billion. A long run, testing two chi wheels together, averaged about eight minutes, or roughly a fifth of that with the five processors in use; a short run on a single wheel took about two minutes.

Valve counts and dates that do not settle

Published counts of the machine’s valves differ, and the difference lies between sources rather than between machines. The Mark 1 is given as about 1,500 valves in some accounts and about 1,600 in others; the Mark 2 as about 2,400 or about 2,500. The National Museum of Computing gives 2,500 valves for Colossus generally. The dates drift in the same way. The museum records delivery of the Mark 1 to Bletchley Park in late December 1943 or January 1944, assembly on site, and operation by early February 1944; other accounts give first operation in December 1943, and 5 February 1944 for the first message successfully attacked. The Mark 2, which used shift registers to run five times faster, first worked on 1 June 1944. Ten Colossi were in use by the end of the war, and about 550 people using them decrypted 63 million characters of high-grade German communications.

Valve failure was the risk that made the design contentious. The proposal to use one to two thousand valves met scepticism: so many could not, it was argued, run reliably together. Flowers’s answer came from pre-war experience of telephone exchanges. Most valve failures happen at power-up, in the thermal stress of the first seconds, so a machine left powered and brought up slowly on its heaters fails far less often.

Programmable by wiring, not by stored program

Colossus holds no program in any store. Its configuration is set by plugboards, switches and jumper cables, and that configuration fixes which Boolean function of the data bits and the simulated wheel bits is evaluated and which counters receive the result. There is no branch on a counter value. The operator reads the totals, decides what to test next, and rewires.

That places it between the relay machines of the same years and the stored-program designs that followed. The Z3, completed in Berlin in 1941, was electromechanical and read its program from an external medium rather than from a stored one, with no facility to modify it during a run. The Manchester Small Scale Experimental Machine ran a stored program in 1948, and the priority dispute over that run is traced in the disputed first execution of a stored program. Colossus belongs on the earlier side of that line, with the Z3 and its relay arithmetic: electronic rather than mechanical, digital, and programmable only in the sense that its function can be rewired between runs.

The museum’s own wording is narrower than its headline. It calls Colossus the first of the electronic digital machines with programmability, “albeit limited in modern terms”, and it notes that Colossus was preceded by several computers, many of them a first in some category. It names the 1948 Manchester machine as the first fully programmable digital electronic computer capable of running a stored program, and treats the general-purpose computer as a notion that took several more years to become prominent. Claims of priority therefore turn on which adjective is doing the work: electronic, digital, programmable, general-purpose, or stored-program.

The secrecy is part of the same definitional problem. Colossus was not declassified until 1975, the machines had been dismantled, and the drawings had been burnt. In 1972 Herman Goldstine, who did not know of Colossus, wrote of the vitality with which Britain embarked on computer projects after the war; Brian Randell, who recovered the material in the 1970s, argued that the project explained much of it.