[Cryptography] Finding undocumented opcodes

[William Allen Simpson]

On 8/7/17 12:02 AM, Ray Dillinger wrote:
> 
> 
> On 08/05/2017 08:54 PM, Dave Horsfall wrote:
>> But speaking of weird opcodes, there is the "population count"
>> instruction on the CDC series; it counted the number of "1" bits in a
>> (60-bit) word, and was known as the "NSA Instruction" (at first glance,
>> it appeared to have no use at all, but Seymour Cray wouldn't have
>> included it for no reason).
> 
> This opcode calculates Hamming Weight.  It is useful in providing
> an additional dimension for rapid location of data in large multiply-
> indexed data structures.  I have synthesized it myself using binary
> comparisons for that purpose.
> 
It is also useful for cryptography, for providing a nearly uniform
shift count (instead of the more common shift-by-constant used by such
as SHA-1) to unpredictably mix a one-way hashing/"whitening" function.

For example, in the CDC SCOPE/Hustler authentication back in the '70s.
Therefore I used it in CBCS in '94 (as it couldn't be patented),
arguably the first public "authenticated encryption" algorithm.

Unfortunately, on architectures that don't have a population count,
counting is somewhat more expensive than a table lookup.  Happily,
almost all of them have population count now.