An idea for a new standard

An interesting issue concerning standards relates to weak cryptographic keys. Not long after a new cryptographic algorithm is invented, researchers find families of weak keys for that algorithm. These are keys whose properties result in a lower level of security than you'd expect. In some cases these weak keys can totally eliminate the protection provided by encryption. In other cases it just reduces it to a lower level. Once these weak keys are identified, any relevant standards are quickly amended to ban their use.

Each cryptographic algorithm has its own set of weak keys, and researchers have devoted a significant amount of time to finding them. In the case of the RSA algorithm, for example, if we have modulus N = pq and p-1 is relatively smooth, Pollard’s p-1 algorithm can quickly factor N, which then lets an attacker defeat RSA encryption. The MOV attack against elliptic curve cryptography, which can be done against curves with a low embedding degree, lets an attacker reduce the more difficult elliptic-curve discrete logarithm problem to the easier discrete logarithm problem in the multiplicative group of a finite field.

DES also has a set of four weak keys and 12 so-called semi-weak keys. These keys don't provide the same sort of advantage to an attacker that the weak keys of RSA or ECC do. The weak DES keys just produce 16 identical subkeys that are used in the DES key schedule. The semi-weak DES keys produce only two different subkeys, each of which ends up being used eight times.

Weak keys are actually fairly rare. In most cases, the chances of randomly picking a weak key are roughly like the chances of randomly guessing a key by chance. This happens so rarely that it's usually not even worth the effort to test for weak keys. Because this is the case, there might be a better use of researchers' time than looking for weak keys, and here's an idea for what they might want to think about instead.

If researchers were to focus its efforts on discovering the strongest possible key for each algorithm instead of finding weak keys, we could then standardize on this key to ensure that all users of the technology benefit from the strongest possible security. Maybe that's an approach worth trying. I should probably write this up as a new work item for the X9F1 working group. I'll have to make sure that I submit it on April 1.