[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)

[Tom Ritter]

On 11 July 2014 13:46, Daniel Kahn Gillmor <dkg at fifthhorseman.net> wrote:
> On 07/11/2014 09:45 AM, Tom Ritter wrote:
>> In my mind, a 2^80 attacker is targeting a single key,
>
> Hm, i don't think this is always true.
>
> There are groups of people (and groups of machines) where the attacker
> can get value from impersonating any one of them.  For example, a
> mid-size hosting company may operate roughly 2^10 servers, each with its
> own ssh host key.  With many modern OpenSSH instances, each sshd has 3
> or even 4 host keys: dsa, rsa, ecdsa. ed25519; so that's 2^11 or 2^12
> target keys you can try to match.
>
> Maybe we don't want to capture this additional attacker advantage in our
> model, but if so, we should at least explicitly state it as out of scope.

If you're targeting different algorithms, the attacker has to do 4 *
2^80.  If you target any of the 2^10 servers, or any PGP key from a
relevant person, you stay at 2^80.  The smart attacker would gather
all relevant keys they could benefit from impersonating, and as they
go through the 2^80 keys for a single algorithm, keep the best couple
keys for each target key.

-tom