correct a corrupted shared key Suppose we have an almost shared secret. For example if we have a noisy connection to a shared secret source of randomness.
So Alice has $k_1$ and Bob has $k_2$ similar but not necessarily identical to $k_1$. One formalization could be:

$\operatorname{hammingDistance}(k_1,k_2) &lt;&lt; \operatorname{length}(k_1)=\operatorname{length(k_2)}$

If the keys are similar in absolute terms we could have Alice send a message with Mac and Bob brute force small variations of his key.

Can we do better? Perhaps ending up with a shorter shared key. 
Obviously I would not want to rely on other key exchange or asymmetric primitives.
If the maximum Hamming distance $d$ between the keys is small enough (and to a lesser degree if the key size $n$ is bits is small enough), one obvious technique is that Alice computes $H(k_1)=h$ for $H$ some cryptographic hash, e.g. SHA-256; and sends $h$ to Bob. He explores $x$ of small Hamming weight until $H(k_2\oplus x)=h$, and when he finds such $x$, he knows $k_1=k_2\oplus x$. There are $\displaystyle\sum_{i=0}^d{{n}\choose i}$ values to try. That's $2^{\approx40.5}$ hashes for a $n=128$-bit key with up to $d=8$ garbled bits, which is already inconveniently slow/costly for Bob, thus that does not work at all for sizably larger $d\log_2(n)$.

If the key has enough entropy and thus can't be enumerated (e.g. it has $n\ge128$ uniformly random and independent bits) and is used to key some fast cryptographic algorithm unrelated to $H$ (e.g. AES when $H$ is SHA-256), this reveals nothing useful about the key. However, beware of interactions! As an extreme example, if the key is used as an HMAC-SHA-256 key, and $H$ is SHA-256, and $n&gt;512$, then $k_1$ is entirely compromised, because by definition of HMAC for long keys, $\forall M,\,\text{HMAC-SHA-256}(k_1,M)=\text{HMAC-SHA-256}(H,M)$.

Note: this is essentially the question's brute force method, except that by processing the key thru a hash independent of the normal use of the key, we avoid using the key in one of its possible intended later way. A more formal approach could always use $k_1$ as the key of a Key Derivation Function, with one derivation parameter reserved for repairing $k_1$.



If the key is large with aplenty entropy (e.g. 256-bit or more), and the above can't be applied because $d\log_2(n)$ is too large, or we want no guesswork for Bob, another option is to use Forward Error Correction: Alice computes and reveals $C=\text{FEC}(k_1)$ of $c$ bits, with $c$ large enough to correct the expected error knowing $k_2$, but still a small fraction of $n$.

It must be used a FEC system where the message normally sent for payload $M$ is $M\mathbin\|C$ with $C=\text{FEC}(M)$, which is common, and includes some Turbocode (as used in 3G/4G mobile communications). The FEC should have little or no extra error-detection capability after correction.

Alice computes and sends $C\gets\text{FEC}(k_1)$, and $h\gets H(k_1)$ as before.

Bob receives $C$ and $h$, applies the FEC recovery to $C$ and $k_2$ to get a tentative $\widetilde{k_1}$, and if $H(\widetilde{k_1})=h$ concludes that $k_1=\widetilde{k_1}$.

Compared to the previous scheme, at most $c$ bits of entropy have leaked about $k_1$, and for a full-entropy $k_1$, we are safe as long as $n-c$ remains large enough to make $k_1$ unguessable; and the FEC, $H$, and the algorithm used for $k_1$ do not interfere.



If we again allows some guesswork for Bob, we can reveal less about the key, as follows.

Alice


computes $C\gets\text{FEC}(k_1)$ as above
optionally applies some public pseudorandom permutation $P$ to $C$, yielding $C'$ (or just $C'=C$)
splits $C'$ into $C_1\|C_2=C'$, with $C_2$ of $r$-bit, e.g. $r=32$ (or smaller, down to possibly $1$);
computes $h\gets H(C_2\mathbin\|k_1)$
sends $C_1$ and $h$


Bob


recovers $C_1$ and $h$
for up to $2^r$ values of $\widetilde{C_2}$


deduces the corresponding $\widetilde{C}=P^{-1}(C_1\mathbin\|\widetilde{C_2})$ (or just $\widetilde{C}=C_1\mathbin\|\widetilde{C_2}$ for no optional pseudorandom permutation)
applies the FEC recovery to $\widetilde{C}$ and $k_2$ to get a tentative $\widetilde{k_1}$
if $H(\widetilde{C_2}\mathbin\|\widetilde{k_1})$ matches $h$


concludes that $k_1=\widetilde{k_1}$, and proceedq to use that with Alice.


if no match is found, stops with failure.


$C_1$ was $c-r$-bit, thus at most that much entropy has directly leaked. The pseudo-random permutation allows a simple security argument that the attacker's best strategy has cost $O(2^{n-c+r})$ operations for full-entropy $k_1$ even for pathological FEC, but is probably not necessary in practice.

If $k_1$ is not full-entropy, then $O(2^{\text{Entropy}(K_1)-c+r})$ work must remain infeasible to the adversary, and if we want a simple security argument (including if $k_1$ is used only in part), we can pass $k_1$ thru another public PRP before applying the whole scheme, and pass it thru the inverse permutation in the end.

If wanted, the PRPs can be built from a MGF as in OAEP.