Subject: [Cfrg] expectations for security claims and guidance

From: David Wagner <[email-masked]>
Date: Wed, 5 Oct 2005 14:39:24 -0700 (PDT)

David McGrew writes:
>I'd like to ask for your input on an important issue that has come up  
>recently: our expectations for the security claims and guidance in  
>crypto specifications.  By specifications, I mean documents generated  
>by the IRTF, IETF, or other organizations whose main purpose is to  
>provide a stable, normative definition for implementers and other users.
>
>Ideally, we'd like to have security claims that are precise and  
>explicit.  If an algorithm is provably secure, we'd like to know all  
>of the assumptions in the proof, the properties claimed, and actual  
>values of the deltas and epsilons.  Certainly the crypto community  
>should require this sort of rigor.  But does it belong in a  
>specification?   It is applying a standard that is much higher than  
>the one that was applied when the specs for the crypto algorithms  
>currently in use were created.

Here are a few principles I would propose for consideration.

1) Informal guidance should be provided to implementors about roughly
what level of security they can expect.  This guidance should be accurate,
to the best of our knowledge at the time the spec is standardized (i.e.,
it is consistent with the best attacks currently known).  The guidance
need not be precise or formal or rigorous or proven.

2) If any security claims are made, they should be accurate to the best
of our knowledge at the time the spec is standardized.

3) If the scheme is claimed to be provably secure, then:
  3a) There should be a precise quantitative security claim that
  applies to the scheme as proposed.
  3b) The security claim should be provided either in the specification
  or in some other technical paper that is cited in the spec and freely
  available to all interested parties (either should be considered
  acceptable).
  3c) There should be a proof of security for the security claim
  provided in some other technical paper that is cited in the spec and
  freely available to all interested parties (but proofs generally
  do not belong in a spec).
If the scheme is not claimed to be provably secure, there is no need
to provide any of these.

4) The spec should try to provide guidance to implementors on how to
implement the scheme securely, if there are any pitfalls or issues specific
to the scheme being standardized.

I realize this goes a little bit beyond interoperability, but I think
it might be appropriate for cryptographic standards.  Basically, my
suggestion is to provide implementors need, to make sure it is accurate
according to the best of our knowledge at the time it is elevated to a
standard, and to provide a level of proof that is consistent with the
strength of the claims being made.

I think these principles are more or less consistent with previous
practice.  Many prior standards (e.g., you mentioned standardization of
various modes of operation) did not make any claims of provable security,
and so there is no need for precise security theorems or proofs in
that case.

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

---

From: Jack Lloyd <[email-masked]>
Date: Wed, 5 Oct 2005 18:51:58 -0400

> to the scheme being standardized.

There is a specific example in the UMAC draft that I think should be
clarified further in this respect. It is nearly universal that
constructions making use of a nonce require that the nonce never be
repeated, and UMAC makes this requirement as well. However, the draft
does not explain what happens when a nonce repeats or who should be
worried about the nonce repeating.

For example, with DSA, if the nonce repeats, the key is compromised.
Thus, the user generating the nonce must be the one who ensures it
never repeats, and they should probably be careful about it. On the
other hand, consider the case of a hypothetical MAC function that was
secure normally, but if a nonce was used twice an attacker could
easily generate tags for arbitrary messages with that nonce. As long
as recepient rejected all duplicate nonces, the flaw is not an issue
(though avoiding generating the same nonce twice would obviously still
be very advisable).

In general I feel some level of analysis of UMAC in this situation is
appropriate, if nothing else to give implementers a good understanding
of just how seriously (or not) a repeated nonce impacts UMAC's
security.

Jack

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 5 Oct 2005 16:23:47 -0700

>to the scheme being standardized.

This is a very good list, but I might go even a bit further and 
discourage (3) altogether *in the document*. The number of people who 
can understand security proofs is quite small. There would be a 
tendency in people who are reading the RFCs for two "competing" 
schemes to pick the one with the proof in it, even if they could not 
understand the proof.

Instead, I think if the author wants to say that the scheme is 
provably secure, they must point to a published paper with the proof. 
The CFRG and/or Security ADs can look at that paper and decide 
whether or not it proves what is said in the document. If it doesn't 
the statement of provably secure can be removed before publication.

>worried about the nonce repeating.

This is an excellent point, and it might be extended to schemes from 
RFCs that are already published. In fact, if someone has a grad 
student or ambitious undergrad who wants to go through 
widely-implemented crypto RFCs and detail this kind of advice, I 
think the developer community would welcome it.

--Paul Hoffman, Director
--VPN Consortium

---

From: canetti <[email-masked]>
Date: Fri, 7 Oct 2005 16:06:50 -0400 (EDT)

On Wed, 5 Oct 2005, Paul Hoffman wrote:

...

> the statement of provably secure can be removed before publication.

I agree. I-Ds and RFCs are not a good place to post proofs or even state
full-fledged mathematical theorems. Still, the relvant facts and
considerations should be clearly stated.

The question is, ofcourse, how to implement/enforce this nice spec.
Here Dave's rules of thumb might be helpful.

Ran

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 10 Oct 2005 09:05:10 -0700

At 8:55 AM -0700 10/10/05, David McGrew wrote:
>I agree completely, though I think that we need to be very careful 
>about what we mean by "published" here.  We don't want to require 
>that the proof be published in a peer reviewed journal or 
>conference.  There are many crypto mechanisms worth using in 
>practice for which it would be nearly impossible to publish a proof 
>of security, because the proof would be so mundane and/or derivative 
>of other work.  The CFRG can review the proof regardless of where it 
>is published.  One idea would be to have the proof published as a 
>separate CFRG document, which is a good way to make sure that the 
>proof is accessible.

Alternatively, something on the eprint.iacr.org site should be sufficient.

--Paul Hoffman, Director
--VPN Consortium

---

From: David McGrew <[email-masked]>
Date: Mon, 10 Oct 2005 08:55:09 -0700

Hi Paul,

On Oct 5, 2005, at 4:23 PM, Paul Hoffman wrote:

> discourage (3) altogether *in the document*. The number of people  
> who can understand security proofs is quite small. There would be a  
> schemes to pick the one with the proof in it, even if they could  
> not understand the proof.

Also, I would require that any specification that did include a proof  
must be sensible to the user who chooses to not read it, and that the  
section containing the proof not contain any normative text,  
including usage limitations.

> provably secure, they must point to a published paper with the  
> proof. The CFRG and/or Security ADs can look at that paper and  
> decide whether or not it proves what is said in the document. If it  
> doesn't the statement of provably secure can be removed before  
> publication.
>

I agree completely, though I think that we need to be very careful  
about what we mean by "published" here.  We don't want to require  
that the proof be published in a peer reviewed journal or  
conference.  There are many crypto mechanisms worth using in practice  
for which it would be nearly impossible to publish a proof of  
security, because the proof would be so mundane and/or derivative of  
other work.  The CFRG can review the proof regardless of where it is  
published.  One idea would be to have the proof published as a  
separate CFRG document, which is a good way to make sure that the  
proof is accessible.

> This is an excellent point, and it might be extended to schemes  
> from RFCs that are already published. In fact, if someone has a  
> grad student or ambitious undergrad who wants to go through widely- 
> implemented crypto RFCs and detail this kind of advice, I think the  
> developer community would welcome it.

Agreed.

David

---

From: David McGrew <[email-masked]>
Date: Mon, 10 Oct 2005 08:55:02 -0700

Hi David,

this is a great set of points.  We should flesh it out and codify  
it.  More inline,

> need not be precise or formal or rigorous or proven.

I would add:

If there are parameter choices that affect security, then guidance  
must be provided on each of these parameter choices.

It would also be good to have assumptions include an expiration date  
or a specific computational limit.  RFC1321, the MD5 specification,  
tells us that "the level of security discussed in this memo is  
considered to be sufficient", which was true enough in '92, but which  
does not tell the modern reader the right message.

> If the scheme is not claimed to be provably secure, there is no need

I'd add these clarifications:

The proof may appear in a copyrighted publication, and it does not  
need to be freely available over the Internet.  In this case, the  
CFRG relies on the fact that at least some of the reviewers of the  
specification are also able to review the proof.

The ideal place for a proof of security to be published is in a peer- 
reviewed journal or conference proceedings.  However, proofs may be  
published other ways, in which case the CFRG must provide the peer  
review, and drafts MUST NOT advance to RFCs without it.  In order to  
ensure the availability of the proof for the lifetime of the  
specification, authors are encouraged to publish these proofs as CFRG  
documents.

(I fear that the RFC format is not conducive to proofs, but I don't  
have a better idea about where to publish them :-)

David

---

From: Jack Lloyd <[email-masked]>
Date: Mon, 10 Oct 2005 12:22:09 -0400

> have a better idea about where to publish them :-)

Would the IACR ePrint service suffice as a reference point? The documents are
generally static, though it is possible for authors to update or withdraw their
documents, so it is not entirely fixed. But it is a fairly common place to
submit papers, it's a central service that probably won't go away, and it makes
it possible to use a real markup language for your math.

Just personally speaking, I would much rather read or write a mathematical
proof in TeX-produced PostScript than in RFC-format ASCII; I rather suspect
most of the real cryptographers and mathematicians on the list feel the same,
though if I'm wrong about that feel free to shout me down.

-Jack

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 10 Oct 2005 12:39:07 -0400

>Alternatively, something on the eprint.iacr.org site should be sufficient.

Not really -- it's not stable, and the submissions aren't reviewed by 
anyone.  I'd vote for some sort of peer-reviewed publication, 
conference or journal.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: David McGrew <[email-masked]>
Date: Mon, 10 Oct 2005 10:08:35 -0700

Steve,

> anyone.  I'd vote for some sort of peer-reviewed publication,

if a specification refers to an external proof, it is desirable that  
it be published in a peer-reviewed venue, but I really don't think  
that we want to require that.  For many crypto mechanisms that we  
might want to include in future standards, the proof of security is  
so mundane, or so close to a proof that's already been published,  
that it would be extremely difficult to get it accepted by a journal  
or conference.  In contrast, CFRG and IETF are interested in many  
crypto algorithms whose proofs are boring to theorists.  For us,  
being obvious or being close to some other established security  
analysis is a good thing.

Reminds me of the discussion you sometimes hear in the IACR about the  
need for a journal that is practice-oriented.

David

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 10 Oct 2005 13:48:10 -0400

In message <[email-masked]>, David McGrew write
>need for a journal that is practice-oriented.

I understand your point.  That said, the (substantive) issue on the 
table here is whether or not a proof is adequate.  I remember my 
advisor commenting on this, way back when.  He said that there was no 
formal definition, but the proof had to be convincing enough.  My goal 
here is to have "enough" people think that the proof is convincing.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 10 Oct 2005 11:01:49 -0700

>here is to have "enough" people think that the proof is convincing.

...for how long? If a proof disappears from the eprints.iacr.org site 
before the CFRG and the ADs are finished with the document, clearly 
that is a problem. But if the proof becomes unavailable after "the 
right people" have determined it is good enough, why should this 
affect the protocol? If a proof is important enough, it will exist 
within the crypto community long enough for someone to later ask "I 
can't find the eprint referred to here; where is the proof?" and get 
a reasonable answer.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 10 Oct 2005 14:15:25 -0400

>can't find the eprint referred to here; where is the proof?" and get 

People might want to refer to it later.  That aside, there's already a 
strong bias by the RFC editor for stable references, i.e., URLs are 
discouraged unless there's absolutely nothing better.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 10 Oct 2005 11:43:05 -0700

At 2:15 PM -0400 10/10/05, Steven M. Bellovin wrote:
>People might want to refer to it later.

Of course. If we believed that eprint.iacr.org was shaky, we could 
start to discourage publishing proofs there.

>That aside, there's already a

I consider a URL better than "Proceedings, WhizzyCrypt Conference, 
June 1998". It is more likely to be accessible in the future, either 
directly or in a cached form.

Again, we are talking about just the proof, not the protocol itself. 
If someone goes to the CFRG, the ietf-general mailing list, or the 
sci.crypt Usenet group and says "I want to see the proof pointed to 
in RFC 6789, but the URL is dead", they will likely get a pointer to 
a copy of it. If it was from a printed journal or proceedings, they 
might get a photocopy, but it would likely be illegal for the person 
who is giving it to them to do so.

--Paul Hoffman, Director
--VPN Consortium

---

From: Jack Lloyd <[email-masked]>
Date: Mon, 10 Oct 2005 15:24:32 -0400

> who is giving it to them to do so.

I want to second this. I've found that while many conference proceedings/papers
are easy to get ahold of (the big IACR/IEEE/Usenix conferences), some are quite
obscure and you're lucky if you can get a photocopy or an interlibrary
loan. And in the case of an uninteresting proof, it's much more likely to be
published in a small obscure conference than one of the major ones that most
academic libraries will get the proceedings of.

If the purpose of publishing the proof is for public review, publishing it
where people can easily get to it seems to be a reasonable thing to do.

-Jack

---

From: David McGrew <[email-masked]>
Date: Tue, 11 Oct 2005 09:29:03 -0700

Jack,

On Oct 10, 2005, at 9:22 AM, Jack Lloyd wrote:

> documents, so it is not entirely fixed.

This is a practical idea.  The eprint service may not be stable over  
the lifetime of the RFC, but it will almost certainly can be stable  
during the review of a draft.

> But it is a fairly common place to

Which is a significant advantage.

> though if I'm wrong about that feel free to shout me down.

I think you're right.  ASCII equations can get ugly fast.

David

---

From: Greg Rose <[email-masked]>
Date: Tue, 11 Oct 2005 10:54:53 -0700

>during the review of a draft.

The IACR's eprint server is one of the most successful things the 
association has done. There is no significant chance that it will go 
away unless the organization itself does, and there's not much chance 
of that happening either.

My team at Qualcomm has almost given up "publishing" in refereed 
journals. We don't have any "publish or perish" pressure like 
academia, we just want to get our ideas circulated, and the eprint 
server solves that problem. As others have pointed out, yet another 
security proof is probably not publishable in a reputable proceedings 
or journal.

So the stability question comes down to the fact that it's possible 
for authors to retract or update the papers. That could easily be 
handled by allowing the author to set an "immutable" bit when 
submitting, by telling the editors that this paper is expected to be 
referenced by an RFC; then the editors would refuse to honor 
retraction requests, and would keep old revisions around when updates 
are published. <plug>If elected to the IACR board in the current 
elections, I would happily champion such a process.</plug>

Greg.

---

From: David McGrew <[email-masked]>
Date: Tue, 11 Oct 2005 11:48:05 -0700

Greg,

On Oct 11, 2005, at 10:54 AM, Greg Rose wrote:

> association has done. There is no significant chance that it will  
> go away unless the organization itself does, and there's not much  
> chance of that happening either.
>
> security proof is probably not publishable in a reputable  
> proceedings or journal.
>
> submitting, by telling the editors that this paper is expected to  
> be referenced by an RFC; then the editors would refuse to honor  
> retraction requests, and would keep old revisions around when  
> updates are published. <plug>If elected to the IACR board in the  
> current elections, I would happily champion such a process.</plug>
>

Alternatively, ePrint could introduce a version-tracking system that  
would make all versions available.  This would make the old docs  
available even if they were superseded.

I very much like the idea of tailoring eprint to work with standards,  
and vice-versa.

David

---

From: canetti <[email-masked]>
Date: Tue, 11 Oct 2005 15:22:02 -0400 (EDT)

This is a very good idea even regardless of the IETF needs.
I found this "quirk" of the IACR eprint quite annoying several times, both
as a reader and as an author who likes to update his publications.
Indeed, most other scientific archives do make old versions of documents
available.

In past private discussions on this issue with the editors of the IACR
eprint archive, they said that they are aware of this issue, and that
it will be fixed as soon as they have the manpower to change the
software accordingly.  So, of someone is willing to contribute please
contact the IACR eprint editors and be blessed with a good deed...

Ran

---

From: Greg Rose <[email-masked]>
Date: Tue, 11 Oct 2005 15:21:11 -0700

>available even if they were superseded.

Well, sometimes people make egregious errors and would prefer that 
the world forgets about them (even though it never does). So I don't 
think I'd make "forever archive" the default. But it's a good option.

Greg.

Greg Rose                                    INTERNET: [email-masked]
Qualcomm Incorporated     VOICE: +1-858-651-5733   FAX: +1-858-651-5766
5775 Morehouse Drive                    http://people.qualcomm.com/ggr/
San Diego, CA 92121   232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Tue, 11 Oct 2005 19:44:40 -0400

In message <[email-masked]>, David McGrew write

>From my perspective as a former AD -- i.e., as one who's had to deal 
with the RFC editor about references -- there's one more concern: 
stability of the URLs.  Lots of sites periodically rework their 
directory tree, thus rendering old URLs useless.  It would be good if 
there could be some assurance that that won't happen.  (One major 
exception to the "we don't like URLs as references" concern is the W3C. 
For obvious reasons, it's unreasonable to expect them to publish their 
documents any other way; it's equally clear that they understand the 
value of long-term stable URLs.)

---

From: Jack Lloyd <[email-masked]>
Date: Tue, 11 Oct 2005 20:01:36 -0400

On Tue, Oct 11, 2005 at 07:44:40PM -0400, Steven M. Bellovin wrote:
> there could be some assurance that that won't happen.

It's worth noting that eprint uses about the simplest URL format imaginable
(http://eprint.iacr.org/YEAR/PAPER#/), and according to old copies of the site
found on archive.org, that same naming system has been in place since at least
2000.

That doesn't provide any assurance whatsoever that someone won't come by
tomorrow and change it, but it does suggest that it's not likely.

Jack

---

From: Mark Baugher <[email-masked]>
Date: Tue, 11 Oct 2005 17:39:55 -0700

My experience has been that the RFC editors are liberal in what they  
accept for informational references but conservative when it comes to  
normative references.  I expect that a proof would appear as in  
informative reference; even the stalest personal Internet Drafts can  
practically always be found cached on some web server and are found  
in RFC reference sections.

Mark