Subject: [Cfrg] Estimating the adversary's computational power (was Re: [CFRG] Actual security levels)

From: David Leon Gil <[email-masked]>
Date: Tue, 28 Oct 2014 11:26:49 -0400

Some numbers.

On Tue, Oct 28, 2014 at 3:02 AM, Yoav Nir <[email-masked]> wrote:
> The weaker curve already has quite a bit of margin. We’ve had a 64-bit
> work factor collision attack on SHA-1 for several years now, and yet
> nobody has produced a pair of colliding buffers.[1]

> I’m sure we have computers that can do 256 as much work. Point is,
> it’s not so easy.

The main difficulty is that there isn't funding for this work.

E.g.: Marc Stevens's attack's claimed complexity is ~ 2^61 SHA-1 evals.

One GK110 can do ~ 2^31 SHA-1 evals per second. DOE's Titan
supercomputer has ~ 18800 GK110s. Stevens's attack would take
about *1 day* of its time.

18800 * 3600 * 24
~= 2^31 GK110-seconds per day
~= 2^61 hash evals per day

How many GK110s does djb's Saber have? 48. The same attack would take
about a year.

(I'm not accounting for Saber's 192 Opteron cores, or Titan's 300,000.)

--

[reordered slightly]
> [1] I’m sure there are quite a few actors who can perform a 64-bit attack.
> It’s been 19 years since a university brute-forced a 56-bit DES key.

It was actually the EFF; Cryptography Research built the machine. It cost
about $361k, adjusted for inflation.

Saber: http://blog.cr.yp.to/20140602-saber.html
Titan: https://www.olcf.ornl.gov/titan/

But anyways, how much do these supercomputers cost?

DES:   $0.361m
Saber: $0.065m
Titan:   $97m

The adversary has: > $3,100m / year

(Sum of data processing and data analysis categories from NSA budget
at http://www.washingtonpost.com/wp-srv/special/national/black-budget/)

I am rather sick of the nonsense that large computations are infeasible.

-dlg

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Oct 2014 18:45:03 +0200

I think your message proves my point rather than disprove it. There's a
61-bit work factor task that is infeasible for a 20 year old machine,
infeasible for DJB's Saber, and the DOE's $97,000,000 machine can do it
once a day.

A 96-bit work factor is over 30 billion times more difficult, making it
infeasible for even a million NSAs. 126-bit work factor is a billion times
again more difficult

I'm not saying that we should aim for 96-bit security. We need some margin.
What I am objecting to is looking at Curve25519 that to the best of our
knowledge is billions of billions of times harder to crack than anything
that's ever been done, and saying "well, this is the option for those who
can't afford super-good security because of performance issues. Those who
really need security need quadrillions of quadrillions or times more.
Merely getting quadrillions more is not enough."

(sorry for the poor paraphrase, Phil)

Yoav