[Cryptography] Population Count (POPC) instruction

[John Denker]

On 5/10/21 5:11 PM, Dan McDonald wrote:
> The POPC (bit population count) instruction came up.
> 
> Pardon my ignorance, why is this instruction so important in
> cryptographic (or cryptoanalytic) circles?

The POPC instruction calculates Hamming weight, which is
closely related to Hamming distance.

1) This has direct, obvious relevance to non-cryptological
 coding, i.e. error-correcting codes. I wouldn't call it
 "important" because the typical case is a weight of zero,
 which can easily (!) be detected by other instructions
 ... and conversely if the weight is nonzero then counting
 the bits is the least of your worries, because a tremendous
 amount of other work (error correction) is about to ensue.

 To say the same thing another way, the value of a hardware
 instruction is limited because the job can be done fairly
 cheaply in software, especially if the input is a_priori
 known to have a small Hamming weight.

2a) There are lots of operations for which the time and/or
 energy required depend on the Hamming weight of some
 operand. This can be used as the starting point for various
 side-channel attacks on a cryptosystem.

2b) A low Hamming weight in a particular instance might
 indicate that the operations are easy to perform, making
 that instance a tempting target for attack. This may
 fall into the category of "weak keys" or something like
 that.

3) You can find more by googling for hamming-weight+"crypto"

Again, just because the instruction exists doesn't mean it
is "important".