Cryptography is all about keys, and it is usually assumed that a large random number would make a good key. Your cryptographic security depends on how hard it is for an enemy to guess this key. If you consider a password as a cryptographic key, we all know that large and random is best - the National Cyber Security Centre (NCSC) recommends using 3 random words.
Clearly an obvious class of weak keys would be keys that are simply too short. For this reason the commonly used AES (Advanced Encryption Standard) uses at a minimum 128-bit keys, far too big to be guessed. And the AES has no weak keys, each possible key is as good as any other.
However its’ predecessor DES - which used 56-bit keys - did have a small number of keys that while 56-bits long were particularly “weak”, in the sense that they resonated with the cipher’s structure to render it completely ineffective and unable to encrypt securely. An example of a weak DES key would be FFFFFFF0000000 in hex. Clearly a randomly generated key would be very unlikely to be a weak key, but nonetheless it was often recommended during key generation that a check be made to exclude the remote possibility of a weak key being generated.
Sometimes the possibility of weak keys cannot be avoided. The famous RSA encryption method uses a public key N which is the product of two secret and randomly chosen prime numbers p and q, so N=pq. The strength of the system depends on the difficulty of factoring N into p and q. Now normally if p and q were random 1024-bit primes this would indeed be a hard problem to solve. But if some idiot were to choose p=q, then factoring N becomes a simple matter of finding the square root of N – an easy problem. Also if p or q is re-used between multiple public keys, then they all become weak. And this does happen, as p and q are typically generated using random number generators, and if they are not truly random they may well produce the same p or q more than once.
Indeed some studies have shown that from random samples of RSA public keys plucked from the internet some 0.5% may be weak.
Elliptic curve cryptography is becoming more popular, driven in part by its use to protect Bitcoin wallets. Here a generator point G on an elliptic curve is denoted by its integer coordinates (x,y). When multiplied by a large secret key s this produces another point Q=sG on the curve. There are q points on the curve, whereqis a large prime. The strength of the system depends on the difficulty of determining the key s given G and Q. Since a NIST standard curve is used, the standard specifies and fixes the values of G and q.
Consider the choice of:
s=6482687712184010168252362946267496770293767958036933 4126295633893540044112329
Which results in:
Q=(100760202697161893004335214126591116800117319792545 458764085267675326325395621, 75193444318165031146359304 621062797862272142296678797285916994295833810377664)
The key s surely looks big and random enough. And there is nothing obviously suspicious about Q. But given just Q it’s trivially easy to calculate s, because in fact s is a weak key. We omit the details, except to point out why s is weak. It is weak because s4 mod q = 1 (that is the remainder you get when you divide s to the power of 4 by q, equals 1).But you wouldn’t know that unless you explicitly tested for it. This weak key is just one of many highlighted in a recent research paper - https://eprint.iacr.org/2020/1436.pdf
Now the chances of a randomly generated s being weak in this way are vanishingly small. However a clever insider attack would be to modify the random number generator to only generate weak keys. These weak keys are hard to spot! The Bitcoin curve is particularly poor in this regard.
The good news is that it’s not hard to test for these weak keys, and it’s not hard to modify the key generation process to avoid them. It’s also quite easy to determine if a public key Q is generated from a weak key.
Intriguingly, shortly after the original article was published, a Bitcoin wallet was found with the exact same weak key as specified above. The account had seen multiple transactions. So clearly bad actors are already considering the possibilities for exploiting these weak keys!
So generate your cryptographic keys with care. Either assure yourself that they are truly randomly generated (remember weak keys, unless deliberately introduced, are vanishingly rare), or put in extra tests to detect and eliminate them.
Find out more about MIRACL’s zero knowledge proof authentication, using military grade cryptography, by visiting MIRACL or follow us on social media: Twitter @MIRACL | LinkedIn MIRACL
