[Cryptography] Population Count (POPC) instruction

[Bill Frantz]

On 5/11/21 at 11:30 PM, leichter at lrw.com (Jerry Leichter) wrote:

>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.

The Harvest computer 
<https://en.wikipedia.org/wiki/IBM_7950_Harvest>, which was a 
coprocessor for the IBM Stretch computer was made for NSA for 
cryptanalysis. (The Harvest was about twice the size of the 
Stretch.) If you really want to geek out on the machine, the 
manual is linked from the Wikipedia article.

Wikipedia quotes James Banford, "An NSA-conducted evaluation 
found that Harvest was more powerful than the best commercially 
available machine by a factor of 50 to 200, depending on the task."

Much of its power came from streaming mode — possibly taking 
two streams from memory — and writing a separate stream back 
to memory. The two byte streams could be combined, used to find 
data in tables, or counted to determine the frequency of various 
values... It handled variable length bytes with bit alignment.

I talked with someone that had used the Harvest. He said that it 
could sort words in memory without moving the instruction 
counter. POPC was a special case of facilities available in 
streaming mode.

NSA used it for 14 years after which parts for the special tape 
drives became unavailable.

I would say that POPC is an important function for certain kinds 
of cryptanalysis.

Cheers - Bill
-----------------------------------------------------------------------
Bill Frantz        | Security is like Government  | Periwinkle
(408)348-7900      | services. The market doesn't | 150 
Rivermead Rd #235
www.pwpconsult.com | want to pay for them.        | 
Peterborough, NH 03458