If two devices do not trust each other yet, you can't simply send the correct fingerprint across: you have to manually verify it. I am looking into the security of comparing only random parts of a fingerprint (e.g. pgp / ssh / certificate / e2ee-chat fingerprints). Because a human looks at it, the attacker basically gets one shot at forging the key before a human sees this invalid key and (optimistically) raises the alarm bells, so we can achieve good security while comparing a relatively small part. Ultimately I am looking to find how to bother the user the least while achieving high confidence that an exchanged key is correct.
To answer this, I'm building a simulation of the verification process and an attack thereon. The verification process, as I currently designed it, picks short sequences from two random positions in the fingerprint (non-overlapping and not wrapping around). It says something like "starting at position 8, the fingerprint should read aa8833cc"1. Simulating the attack, the 'real' fingerprint is set to a static string of the correct length and character set, and now I want to figure out how much and what parts of the fingerprint an attacker can forge to see if the randomly chosen parts match up.
A configurable parameter for the simulation is how much computational power we estimate the attacker to be able to (or care to) muster (under simplified circumstances2). Let's say the attacker wants to generate at most $2^{72}$ key pairs with the goal of using one to fool the verification process and perform a MITM attack.
What properties does that allow them to choose for the fingerprint?
Sub-question 1: The attacker cannot choose which parts of the fingerprint will be correct for any given guess at the key. Am I correct in estimating that this would yield the attacker, on average, a fingerprint with on average no more than 72 random bits set correctly? I.e. can I just equate the number of keys generated to how many bits will be correct in the resulting fingerprint? It feels right but short of just simulating it for small cases, I don't know how to verify that.
Sub-question 2: Correct sequences seem beneficial to the attacker, rather than using the fingerprint with the most, but randomly placed, correct characters. How can it be calculated what length sequences the attacker is able to generate?
Sub-question 3: Since the two (or more) sequences the user is told to verify can be adjacent (equally likely as the sequences being in any other position), am I correct in assuming that it doesn't matter whether the attacker tries to find one long correct sequence or multiple correct shorter ones of the same total length, i.e. should they expect the same chance of success regardless of which they find / are trying to find?
Finally, I am not great with math (lack of education on that topic), it would be really great if answers could explain formulas maybe a little bit more than you would otherwise! (I know how to use the things that are usually essential for combinatorics like exponentiation, factorials, the basics of log scales, and of course anything more basic than that).
Footnote 1: It is assumed that the attacker knows exactly how we will be verifying the exchanged key and the positions that the user is instructed to check are generated with a CSPRNG. No lookalike glyph attacks are assumed. Perhaps I should account for one comparison error, but there should be some security margin anyway. The user is not expected to count out the 52nd character in a fingerprint; rather, it's a general region to look at. (Large errors in position estimation will be part of the attack simulation. Or perhaps I'll make it say "in the first third/middle third/last third" to make it more predictable what the user will or won't find suspiciously far off.)
Footnote 2: For practicality, the time between key creation and fingerprint verification (which may be mere seconds, but can also be years) is ignored, so the attacker is assumed to have as much time to perform the brute force as they wish. Another imperfection is that generating an asymmetric key pair is not as fast as, say, doing a single round of a fast hash. So while an attacker might be able to do $2^{72}$ hashing operations, they might not be able to generate that many key pairs. Since that is more of an implementation detail of a particular cryptosystem, unless I'm way off by several powers of two here, this seems acceptable to ignore for the general case.
