[zijbqywd] Relationship among key bits

What weaknesses are introduced to a block cipher if, even though the key is not explicitly known, the attacker knows the key bits satisfy some predicate?  We are interested in weaknesses beyond simply decreasing the search space for a brute force attack.

For example, bits X and Y are equal, or that the later bits of the key are a known function of the earlier bits (inspired by perl Crypt::CBC and its md5 key derivation loop).

Thread the predicate structurally through the cipher's operation.  Does it cause the cipher to behave poorly?  What relationships does it introduce among the ciphertext and plaintext?  Was the cipher designed under the assumption that key bits are independent?