I've got a scheme where I XOR a secret key value with a public (but random) value, XOR together all the bits of the result, and publish that bit (0 or 1), which is the parity of the result of the XOR. My goal is for this published bit to be hard to predict, for a given public value, before it is published.
I'm certain that this will leak information about the key: I'm doing XOR with a static key and a known plaintext, which is a classic easy-to-break cipher, and even if I'm only publishing a little information about each value that results from the reused key, eventually there's got to be a way to get the key from the published bits.
My question is:
- How fast does this leak information? If the key and the public values are, say, 128 bits, is the key "good for" producing unpredictable bits for 128 values on average before the next value can be reliably predicted? Or more? Or less?
- How do you go about exploiting the leak to recover the key from the public values and the parity bits from the XORs? You end up knowing the parity of a bunch of XORs against the same number, which is like a certain number of equations over unknowns which are the key bits, but I never learned how to do boolean linear algebra.
- Is there an easy way to fix this scheme? The key material is supposed to be (handwaving) shared between two parties; I want them to both be able to agree on this unpredictable bit. Do I just swap out the static shared key with a real stream cipher on a shared secret seed, so the key can rotate?