5 ms·

> 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

by wtbob 11y ago

mrb 11y ago
This is not a valid comparison. An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security. But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime. 2^80 is much larger than 2^48, therefore it is not a problem.
- wtbob 11y ago
  It's not about bruteforcing. If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it). I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.
  - mrb 11y ago
    Yes, security margins are all about what can and cannot be brute forced! You can't compare these 2 scenarios directly, because in practice: - attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but - attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.
cperciva 11y ago
Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.
- marshray 11y ago
  Most protocols do allow the attacker to choose how many times the defender must win at some game of probability. If the defender is somehow put in a situation to generate 2^80 primes, then he's in trouble.
  - cperciva 11y ago
    Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.
- wtbob 11y ago
  > When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken. But it also implies that e.g. the attacker has a 2^-128 chance of randomly guessing a key.

> 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

by wtbob 11y ago

> 2^-80 is an incomprehensibly tiny number. When one wants a 128-bit security margin, 2^-80 is 2^48 times too big.

mrb 11y ago

This is not a valid comparison. An attacker who can bruteforce, say, 2^80 128-bit keys (approximate limit of the computational power of the largest adversaries) has 1 chance out of 2^48 to break the security. But an attacker has only 1 chance out of 2^80 that this parameter is a non-prime. 2^80 is much larger than 2^48, therefore it is not a problem.

wtbob 11y ago
It's not about bruteforcing. If I want a 128-bit security level, I'm willing for a random guess of my key to have a 2^-128 chance of being correct. I'm likewise willing for a prime I generate to have a 2^-128/uses chance of not being prime (where uses is equal to the number of times I'll actually be using it). I can't be 100% certain that a large number is actually prime. But I can be certain enough. Having a 2^-80 chance of being wrong isn't good enough when I want a 2^-128 security level.
- mrb 11y ago
  Yes, security margins are all about what can and cannot be brute forced! You can't compare these 2 scenarios directly, because in practice: - attackers can take as many guesses as they want against a piece of data protected by a 128-bit key, but - attackers get only 1 chance that a particular piece of data protected by a supposed prime is not a prime.

cperciva 11y ago

Apples and oranges. When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken.

marshray 11y ago
Most protocols do allow the attacker to choose how many times the defender must win at some game of probability. If the defender is somehow put in a situation to generate 2^80 primes, then he's in trouble.
- cperciva 11y ago
  Sure, I'd aim for a higher security level in a "attacker can keep asking for new primes until we screw up" scenario.
wtbob 11y ago
> When we talk about 128-bit security, we mean that it takes ~2^128 work to break it; not that there's a 2^-128 chance that it is broken. But it also implies that e.g. the attacker has a 2^-128 chance of randomly guessing a key.