1
$\begingroup$

I understand that all zeros or all ones would be weak for any cipher. And certain ciphers, e.g. DES, have a list of weak keys. But I assume that there would many 'patterns' that would be detected (if that is the correct term) as weak. For example, 0x0505 ...05, 0x1010...01 and 0x0A0A...0A. Or other patterns such as half the key being 0s and the other half being 1s or half the keys being 3s and the other half being Cs (i.e. the compliment of 3.

A key must have a large number of patterns, so is there a way to calculate this number?

Are the patterns I mentioned above (and similar) weak keys?

Improve this question
$\endgroup$
2
  • $\begingroup$ Actually, this can be rephrased as an information theory question which asks: given an n-bit string, each bit have 0.5 probabilities being 0 or 1, howmany strings would have entropy less than n-<the threshood you want to set>. $\endgroup$
    – DannyNiu
    Aug 23, 2017 at 9:10
  • 4
    $\begingroup$ @DannyNiu: and your definition for entropy of a string would be? We usually define entropy of a distribution of strings, or perhaps of a process generating strings with said distribution. $\endgroup$
    – fgrieu ♦
    Aug 23, 2017 at 11:48

1 Answer 1

Reset to default
14
$\begingroup$

I understand that all zeros or all ones would be weak for any cipher.

This isn't actually true. For good cipher there are no weak keys.

And certain ciphers, e.g. DES, have a list of weak keys. But I assume that there would many 'patterns' that would be detected (if that is the correct term) as weak. For example, 0x0505 ...05, 0x1010...01 and 0x0A0A...0A. Or other patterns such as half the key being 0s and the other half being 1s or half the keys being 3s and the other half being Cs (i.e. the compliment of 3.

This isn't true for most algorithms.

More specifically you fall into thinking that number can either be random or not. Is 3 random? On a 1-10 scale? We humans easily assume that "1234" or "1111" isn't random. But what if it's just what came our of good RNG? Is RNG broken?

No, instead we are broken. We easily consider some things "too simple", while computers can just draw random number in range that is always random (if proper algorithm is used). It doesn't really matter if the number is 1, 5 or 283921. Algorithm design decides if numbers generated are good, not the number itself. Algorithm doesn't have to check for only 0bit keys, because chance that it generates this key is just as high as all other keys.

Now, why DES has "weak keys" then? Because those are keys that make algorithm perform poorly (encrypting again can undo effect for example). This shouldn't be case with good ciphers. We hope that Enc(K1,text) can only be undone with Dec(K1,text), not Dec(K2,text), nor Enc(K3,text) and especially not with Enc(K1,text) again!

A key must have a large number of patterns, so is there a way to calculate this number?

Yes, random key in 128-256bit range is good. Any attempt at excluding keys like only zeros just limit how random your algorithm is.

Are the patterns I mentioned above (and similar) weak keys?

No, DES weak keys come from how DES performs with those keys, not from how they look. If we found AES weak key of 0x28357129912581823923, this would be weak key because of how it works in algorithm, not because it looks non-random.

If we speak of "weak key" as in keys that aren't random enough, then it only comes down to how you generate those keys, not what those keys are! (Any key you get is not random then).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I accept that 1111 and 1234 are just as likely as any other four 'randomly' chosen numbers. But I heard that symmetric keys should not have large strings of all 1s or 0s. Other features were also, apparently, undesirable. Is this not true then? $\endgroup$
    – Red Book 1
    Aug 24, 2017 at 9:29
  • 1
    $\begingroup$ @RedBook1 Symmetric key should be random. This is enough to give you maximum security. I'm not sure what "other features" you mean. It's surely not true that you should check key for bunch of 1s or 0s. Just use proper CSPRNG with good seed and you are done. $\endgroup$
    – axapaxa
    Aug 24, 2017 at 10:55
  • $\begingroup$ My concern comes from a NIST Test Suite for RNG for cryptographic applications. The first few are: 1) Frequency (Mono-bit) Test: No. of 1’s and 0’s should be approximately the same, i.e., with p(½). 2) Frequency Test within a Block: Whether frequency of 1’s in an M-bit block is approximately M/2. 3) Runs Test: Number of runs of 1’s and 0’s of various lengths is as expected for a random sequence. And so on. This is what got me thinking about strings of 1s and 0s, and other patterns. $\endgroup$
    – Red Book 1
    Aug 25, 2017 at 2:09
  • $\begingroup$ @RedBook1 Those are tests for RNG that are absolutely unrelated to weak keys in DES sense (keys that are poor because of cipher). Keys we use in ciphers have to be random, but we don't care about tests like that because they will fail with very small chance, they don't really test much (blackbox testing gives us almost nothing) and reduce performance. Number of zeros and ones will be close with very high probability, but we don't exclude keys where it isn't because all those keys are just as strong, and if our keys are terribly broken they can look random anyway. Nothing we can fix! $\endgroup$
    – axapaxa
    Aug 25, 2017 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.