Subject: [Cfrg] Re: expectations for security claims and guidance

From: Shai Halevi <[email-masked]>
Date: Thu, 06 Oct 2005 10:11:26 -0400

David, maybe not quite answering your question but I list below some
rules-of-thumb that I've been using to map common terms into concrete
meaning and to help me evaluate the significance of things:

The overall theme is that a scheme is to be called secure enough if no
"reasonable" algorithmic attack can "break" it. The whole spiel is just
about assigning concrete meaning to "reasonable" attack and to
"breaking" the scheme.

The easier of the two is what should we think of as a "reasonable"
algorithmic attack. Since we are talking about algorithmic attacks
(and not, say, attacks on the O/S that hosts the crypto algorithm),
we can restrict our attention to only the computational resources that
are consumed by the attack algorithm. Typically, the relevant resources
are time, space, and interaction. (The latter refers to things such as
"how many valid signatures the attacker must obtain from the legitimate
signer before it can forge a signature on a new message".)

At the time of this writing, I call an algorithmic attack:

- "feasible" if it works in time at most 2^{60}, space at most 2^{40},
   and using at most 2^{30} interactions with the legitimate users.

- "potentially feasible" if it works in time at most 2^{80}, space at
   most 2^{60}, and using at most 2^{45} interactions with the legitimate
   users.

- "imaginable" if it works in time at most 2^{100}, space at most
   2^{80}, and using at most 2^{60} interactions with the legitimate
   users.

I then map the terms "minimally secure" to "no feasible algorithmic
attack breaks it", "commercial grade" to "no potentially feasible attack
breaks it", and "military grade" to "no imaginable attack breaks it".

What it means for an attack to "break" a scheme is a bit more murky.
For most simple tasks (such as MACs, encryption, signatures, etc.) we
can simply defer to the current commonly-accepted security definitions
in the literature. (For more complex stuff this may be a problem.)

The only thing to settle is the threshold beyond which an attack is
called successful. My rule-of-thumb here is to just pick some rather
small number such as .1% (e.g., I will say that an attack "breaks" a
MAC if it can forge a valid tag with probability>1/1000.) The rationale
for choosing .1% is that we are talking about expensive attacks, so
success probability below .1% will not justify them. (Also, the results
that I get from this rule-of-thumb sit well with my own intuitions as to
the security of things.)

With these rules-of-thumb, I can map instances of real-life schemes into
these categories of "minimally secure", "commercial grade" and "military
grade" that non-cryptographers often find easier to stomach than an
explicit bound. (Of course, these are just my own rules-of-thumb and
others can disagree, but I contend that applying them to real-life
scheme gives you very good partition of schemes according to realistic
security levels.)

Another reason not to use explicit bounds in maknig real-life decisions
on crypto schemes is that these bounds are often extremely misleading.
A simple example for that is the rule-of-thumb saying that "no real
system ever has security level above 2^40."

To see why, imagine that you have an extremely popular crypto scheme
which is used everywhere, so much so that throughout its lifetime it
is used with more than one trillion keys. Can any of you imagine that
not one of these instances using that scheme will ever accept a forged
message? (We all know that at least a few thousands of them will leak
the actual key, others will have a software bug that never calls the
tag-verification procedure, etc.) Hence "no real system ever has
security level above 2^40."

Cheers,

-- Shai

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg