0
$\begingroup$

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) << \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.

$\endgroup$
  • $\begingroup$ I suppose approaches from typo-correcting key exchanges / hashing / whatever could work. $\endgroup$ – SEJPM Jul 14 '18 at 16:54
  • $\begingroup$ Googling typo-correcting key exchanges produced nothing remotely relevant. $\endgroup$ – Meir Maor Jul 14 '18 at 16:58
  • 1
    $\begingroup$ Pick any error-correcting code? Pick a secret Goppa code for which Alice knows a generator matrix and Bob knows the secret structure of the Goppa code, and you can even get a public-key encryption scheme called McEliece! $\endgroup$ – Squeamish Ossifrage Jul 14 '18 at 20:41
  • $\begingroup$ Repeat the key exchange over and over until the keys match. It is not necessary for the keys to be error-free - the error patterns just need to match. $\endgroup$ – conchild Jul 15 '18 at 0:21
1
$\begingroup$

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>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.

$\endgroup$
  • $\begingroup$ What is to stop eve from doing the same $2^r$ attempts to complete C. I fail to see how knowing k2 helps him. $\endgroup$ – Meir Maor Jul 14 '18 at 18:08
  • $\begingroup$ If Alice sends a truncated C missing r bits, Eve can guess the missing r bits and verify with the hash. Where does k2 come into play? $\endgroup$ – Meir Maor Jul 14 '18 at 18:15
  • $\begingroup$ I now realize your FEC is only the additional information without the original. So we need an error correction codr which includes original and handled individual bit flips. reed Solomon which you suggest builds words so any bit flip ruins a full word. $\endgroup$ – Meir Maor Jul 15 '18 at 3:04
  • $\begingroup$ turbocode would work $\endgroup$ – Meir Maor Jul 15 '18 at 3:08
  • $\begingroup$ @Meir Maor: Yes I mean a FEC that is a mall addition to the original data, and the FEC I had in mind when I said Reed-Solomon might not be RS after all, so I removed that. $\endgroup$ – fgrieu Jul 15 '18 at 5:55

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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