[Cryptography] Population Count (POPC) instruction

[William Allen Simpson]

On 5/12/21 9:54 AM, Patrick Chkoreff wrote:
> Jerry Leichter wrote on 5/11/21 11:30 PM:
> 
>> 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.
> 
> Ah, that takes me back.  I used a CDC 6600 at GA Tech back in '79.  At first it was all punch cards and line printer output delivered in bins, but then we got CRTs and it was a whole new world.
> 
> 

I learned to program on CDC 6500 in 1975 at Michigan State University.

The CDC 6000 series was mid-to-late 1960s.  A 6500 was 2 6400 CPU cores, so we
learned SMP programming from the ground up.

The SCOPE/Hustler operating system used the population count instruction to
generate a smooth diffusion curve for 1-way hashing functions.  (We didn't yet
have the term 1-way hashing function.)  Obviously not the original intent of the
instruction, but definitely useful for security protocols.

To give credit where it is/was due, fairly certain it was Larry Kingsbury who
came up with the novel function design for the "Program Number Card".  This
punched card was used as a deck separator to prevent users from stealing each
other's computing time.  The PNC used a 1-way hash with a secret.

Many other architectures had/have the popcount instruction.  Intel was very late.

My publication of the technique can/could be found in Cipher Block CheckSums
(CBCS) drafts circa 1996-1998.  The main criticism at the time was Intel chips
didn't have it, so a naive C implementation took about the same time as MD4.  I'd
written an x86 assembly version for speed.

Still a heck of a lot faster than Galois....