Chance of spotting an incorrect value by random checks in a string To check that you are communicating securely with your friend, many chat applications allow you to verify the encryption key. If you meet in person and see on their screen that they use encryption key "dbdcc", and your device also reports using that encryption key, then you know that the two devices are not being intercepted.
A typical key size is 256 bits and is often displayed in hexadecimal encoding, i.e. 64 characters to compare. Since people am lazy, I would like to find the minimum number of random characters to compare for security (such as two blocks of 6 characters). An attacker would not be able to brute force 256 bits, but they could do 64 bits. But let's keep the example small, and use the "dbdcc" string from above. Imagine an attacker can brute force only three characters of that five-character string, and only the values a through d can be used in each position.
The attacker could choose to brute force the key until the 1st, 3rd, and 5th characters match, for example yielding "dadac" as key. Depending on which characters we compare, we find that the keys do not match:
1 2*
1 3
1 4*
1 5
2 3*
2 4*
2 5*
3 4*
3 5
4 5*

* In these cases, the attack would be detected, since it includes either 2 or 4, which the attacker did not attack.
So in the example, we have a $\frac{7}{10}$ chance of detecting the attack, assuming all characters that the attacker did not attack are indeed incorrect. In reality, the odds are 1 in 4 for each overlapping character, so even if we check both positions 2 and 4, there is a 1 in 16 chance of a successful attack.
The number 10 (combinations, "5 choose 2") is a formula I was able to find:
$\frac{n!}{(n-c)!×c!} = \frac{5!}{(5-2)!×2!} = 10$
But I can't figure out how to compute the 7. How do I calculate the odds that the attacker chooses an identical set, or the converse: that the defender chooses an overlapping set? The only way I can think of solving this is by doing it manually as done for the example above, which I could easily script in Python to be able to do it for arbitrary parameters, but surely there is a better way.
One way to get to 7 would be the number of possible sets checked by the attacker (10) minus the number of characters the attacker attacks (3), but that does not hold up in the case where the attacker attacks only 2 (then there is only one case where you do not detect the attack: if the attacker attacks the exact two characters you check), since that would give $10-2=8$ but in reality we have a $\frac{9}{10}$ chance and not an $\frac{8}{10}$ chance.
How could one calculate these odds without simulating all possible choices and checking for how many choices the two chosen sets overlap? Note that we'll need to account for the chance that one or more positions are correct, even if they were not part of the attacker's chosen set, so it needs to be broken down by number of items in the sets' overlap.
 A: In your specific example, you get the number $3$ as $3$-choose-$2$ a.k.a. ${3\choose 2} = {3! \over 2! 1!} = 3$ because that's how many size-$2$ subsets (pairs) of positions which fit entirely within the size-$3$ subset of hacked positions (positions $\{1,3,5\}$).  Such pairs are guaranteed to match.
More generally...
If I understand you correctly, you have a string of $n$ characters, each character being from an alphabet $\Sigma$ of size $s.$  The attacker has a string of $n$ characters of which $m < n$ are guaranteed exact matches and the remaining $n-m$ characters has a $1/s$ chance each of matching.  Then you're comparing some $c < n$ of the characters, and you want the probability of find all $c$ matching, a.k.a. a successful attack.  (In your example, $n=5, \Sigma = \{a,b,c,d\}, s =4, m=3, c=2$.)
First, is my interpretation correct?
Among the $c$ characters being compared, some $d \le c$ of them are among the $m$ guaranteed matches, and the remaining $c-d$ of them would match with probability $1/s^{c-d}$.  The number of ways to pick such a combo is ${m \choose d} {n-m \choose c-d}$ where the ${a \choose b} = {a! \over b! (a-b)!}$ is the $a$-choose-$b$ formula you found.  So you sum over all $d$ and get:
$$\mathit{Prob}(\text{successful attack}) = {1 \over {n \choose c}} \sum_d {m \choose d} {n-m \choose c-d} {1 \over s^{c-d}}$$
You need to be careful of the range of $d$ in the summation: AFAICT, you need $0 \le d \le m, 0 \le d \le c,$ and $0 \le c-d \le n-m$.
