[Cryptography] Population Count (POPC) instruction

[Jerry Leichter]

> I'm in the middle of a discussion about computer architecture.  The POPC (bit population count) instruction came up.
> 
> Pardon my ignorance, why is this instruction so important in cryptographic (or cryptoanalytic) circles?
Frankly - it’s not clear it is.

As far as I know, the story dates back to the CDC 6600, one of the first supercomputers, back in the late 1960’s. Among the early customers for the machines was the NSA - though in those days NSA stood for No Such Agency, as even its very existence wasn’t officially confirmed. As a story in those days went, a truck driver was instructed to pick up a 6600, drive to some place in the desert where he’d find a car with the keys in it, drive to a restaurant a couple of miles down the road, come back an hour later and pick up his now-empty truck, and never say much about what transpired. 

Anyway, the 6600 had a Popcount instruction. It was alleged that the NSA asked for it to be added. The story seems possible because of claims that the instruction wasn’t useful for normal work.

The truth of all these stories is impossible to verify. Thornton’s book on the design of the machine - it’s available on line these days - doesn’t, as I recall, mention it. In fact, I think it comments that Popcount was easy to implement in the divide unit using hardware that was already there. 

And the “uselessness” of the instruction... well, maybe you can believe that if you don’t know some tricks for effective use of the machine. The 6600 was a word-addressed machine with 60 bit words. There were no byte-level operations. Efficient algorithms existed to operate on 10 (6-bit) characters in a word in parallel, and to do other similar things. Many of those use Popcount.

Of course, cryptanalysis is likely to do many character-wise operations.  So if efficient versions are helped by Popcount - perhaps the NSA did ask for it.

So ... urban legend or historical fact?  It’s a cool story either way....

                                         -- Jerry