Low entropy - how does it compromise the crypto

One of the often pointed out mistake in dealing with crypto is not having enough entropy in the system. Without enough entropy the random numbers generated are not random enough.

But what I am not able to piece together is how exactly the lack of randomness can lead to less secure systems. In what does a key generation on a low entropy system make it vulnerable for attacks ?

If the adversary can guess the key, then they can do all the things that a legitimate user can do: decrypt secret messages, sign statements transferring money to their accounts, etc. The min-entropy of the process used to generate keys must be high enough that the adversary has no hope of guessing the generated keys by chance.

If the key is generated on a low-entropy system, then the corresponding crypto scheme's security cannot depend on its key size (which is usually the security parameter), but instead, should depend on the exact key entropy.

For example, it is currently believed that no attacker can distinguish AES-256 from a random permutation (on 128-bit strings) with significantly less than $$2^{256}$$ computations. However, this security relies on the assumption that its key has full 256-bit entropy, i.e., all 256-bit keys occur with equal probabilities of $$2^{-256}$$. If the key has low entropy (<256-bit), AES-256's security will be weakened correspondingly. Intuitively, considering a brute-force attacker that searches all possible AES-256 keys, low-entropy key means some 256-bit keys are more likely to happen than others, then the attacker can reduce the expected computation work consumed to find out the right key.

By example, consider these two passwords/keys:-

"secret"

"6D 9F 8F 5F 6B A6 03 21 8E C3 FB 68 1F 1C 9D 51 84 E5 6D 62 4C 0F 6F 63 42 42 8E 88 07 B1 E2 23 34 07 20 C2 93 1B C0 21 F1 8C 56 95 BC 51 55 54 4F 20 47 66 82 16 2A B7 EB 1C CA EF A4 81 5B A1 11 4D 3D CD 9A F5 09 90 26 61 0A BC 91 F5 2D 98 E2 0C 28 C3 06 CD A7 C5 4C E3 8B D1 78 36 C8 57 6F 83 51 1A 62 42 64 B4 4D 9F BC FD B6 6D 1D F6 66 5E 15 9C 03 E2 C9 63 79 9F B2 76 A6 B3 6D EB"

The former was pulled out of my head. Password entropy calculations are notoriously difficult, but you can see that it's a bit short. It's also a common word and can be found in hackers' dictionaries. The latter is 1024 bits of entropy pulled from a true random number generator (TRNG). There are $$2^{1024}$$ or $$10^{308}$$ possible values of this length. Clearly that's much harder to guess.

But the latter was also much harder to generate. It took a device, investment £s and consumes space and electricity. These are often in short supply with many internet of things devices built to a price point and running on batteries. This causes entropy starvation. The cheapest of these do not have any form of embedded entropy source. And that can lead to weak keys like "secret" simply being hard coded into the firmware.

Eg.: simply spending £K's on kit without entropy is not always adequate either. This is a technical guide to stealing Tesla Model S cars by exploiting 40/24 bit fixed keys with a Time-Memory Trade-Off attack using a kiddies Raspberry Pi. A low entropy car, and quite ironic given that the £30 Pi has a good TRNG inside it.

• Entropy starvation is largely a non-issue. All you need is to generate 128 bits of random data once and you can generate more cryptographically-strong pseudorandom data indefinitely. Feb 24 '19 at 10:25
• @PaulUszak Please remember that we have a "be nice" policy here, and that "unfriendly or unkind" is a flag reason for comments. Instead of asserting that someone is wrong, consider providing an objective explanation as to why you disagree. Apr 17 '19 at 15:33