Subject: RE: non-repudiation, was Re: proposed key usage text

From: Peter Williams <[email-masked]>
Date: Thu, 18 Nov 1999 16:28:37 -0800

This mail discusses NR. You are warned to
pass by, if you have real work to do.

> -----Original Message-----
> From: Ed Gerck [mailto:[email-masked]]
> Sent: Thursday, November 18, 1999 2:12 PM
> To: David P. Kemp
> Cc: [email-masked]
> Subject: Re: non-repudiation, was Re: proposed key usage text
> 
> 
> 
> 
> "David P. Kemp" wrote:
> 
> > > Date: Thu, 18 Nov 1999 12:02:54 -0800
> > > From: Ed Gerck <[email-masked]>
> > >
> > > Stefan Santesson wrote:
> > >
> > > > How can you say that the X.509 definition is wrong???
> > >
> > > Because it is redundant (the same as authentication as I 
> commented)
> > > and thus superfluous.
> >
> > Some people believe that there is a difference between "provable
> > data origin authentication with integrity" and "entity 
> authentication",
> > and that nonRepudiation as used in X.509 is an appropriate 
> name for the
> > former.
> 
> David:
> 
> It is useful to list what X.509 actually says before further 
> discussing about
> "nonRepudiation as used in X.509".  These are all the 
> occurrences that I
> find when I look for the key text "repudiation" in X.509:
> 
>  "It is a matter for the security policy and responsibility 
> of the CA to keep old
>  certificates for a period of time if a non repudiation of 
> data service is provided."
> 
>  "If a non-repudiation of data service is dependent on keys 
> provided by the CA,
>  the service should ensure that all relevant keys of the CA 
> (revoked or expired)
>  and the timestamped revocation lists are archived and 
> certified by a current
>  authority."
> 
>  "nonRepudiation:  for verifying digital signatures used in 
> providing a
>  nonrepudiation service which protects against the signing 
> entity falsely
>  denying some action (excluding certificate or CRL signing, 
> as in f) or g)
>  below);"
> 
>  "The date in this extension is not, by itself, sufficient 
> for nonrepudiation
>  purposes. For example, this date may be a date advised by 
> the private key
>  holder, and it is possible for such a person to fraudulently 
> claim that a key
>  was compromised some time in the past, in order to repudiate a
>  validly-generated signature."
> 
>  "Repudiation -- The denial by a user of having participated 
> in part or all
>  of a communication."
> 
> and, the one quoted by Stefan:
> 
>  "Non-repudiation -- This service provides proof of the 
> integrity and origin
>  of data -- both in an unforgeable relationship -- which can 
> be verifed by any
>  third party at any time."
> 
> plus:
> 
>  "The data integrity mechanism supports the data integrity 
> service. It also
>  partially supports the non-repudiation service (that service 
> also needs the
>  digital signature mechanism for its requirements to be fully met)."
> 
>  "The digital signature mechanism supports the data integrity 
> service and
>  also supports the non-repudiation service."
> 
> which shows that X.509 itself  is in contradiction.  To 
> X.509, nonrepudiation
> does NOT provide proof of integrity, which needs the digital signature
> mechanism.  This is made clear in  Table B.1 "Threats and 
> protection", where
> we can read that the non-repudiation service is depicted as 
> protecting against
> the threats  of replay and repudiation -- and that "data 
> integrity" and "end
> authentication" are different services, different from 
> non-repudiation.
> 
> Thus, that is why I wrote the following in regard to the 
> definition that Stefan
> quoted from X.509:
> 
>  This definition is wrong, as well as the consequences 
> derived from it. Compare
>  with the technical definition of Menezes in  Handbook of Applied
>  Cryptography (cf.):
> 
>  Non-repudiation: a service that prevents the denial of a 
> previous act.
> 
> But, surprise! The above NR definition by Menezes can be also found in
> *another* part of X.509, if you read the X.509 definition for 
> *repudiation*
> that I quoted above:
> 
>  "Repudiation -- The denial by a user of having participated 
> in part or all
>   of a communication."
> 
> and you construct the logical complement of "non" as:
> 
> Non-Repudiation -- Preventing the denial by a user of having 
> participated in
> part or all of a communication.
> 
> Further, authentication that is neither provable nor provides 
> for integrity is
> not authentication in the sense of strong authentication as used in
> X.509 digital signatures (Section 10.1).   Thus, when you say 
> that "provable
> data origin authentication with integrity" is an appropriate name for
> non-repudiation in X.509, I must disagree and cite X.509 
> itself.  That X.509
> definition quoted by Stefan in incoherent with all other 
> definitions of X.509.
> It was a bad pick.
> 
> Actually, elsewhere as shown above, X.509 textually *agrees* with the
> definition by Menezes et. al. and with the usual sense people 
> would attach
> to something that is the complement of repudiation, the 
> complement of denial.
> 
> On the other hand, "provable data origin authentication with 
> integrity" is
> NOT an attribute of non-repudiation in X.509 but is provided by strong
> authentication as given in Section "10.1 Overview", where two-way
> authentication provides assurances for "the integrity and
> originality  of the authentication token sent in the reply".
> 
> So, should we accept that NR definition quoted by Stefan and deny
> all the other passages of X.509, including those for 
> authentication, that
> contradict with it ... or should we mark that specific 
> passage as wrong
> and accept the rest of X.509?

Yes. The latest round of fiddling with X.509 did more harm
than good. Your analysis, and subtle definitional logic
is quite accurate, for the various cases, historically.

The original 1988 model of X.509 was nicely aligned with
Davies and Price, which uses terms authentication,
strong authentication, proof of origin, as you reinforce 
here, based (interestingly) on purely textual deductions.
(this says something for the specification skills
of the early-round authors of X.500/X.509)

BUT, interestingly: the one thing D&P did not do back in 1984 
was get a full handle on non-repudiation, even though they
refer to it: "the statement of a signature procedure is not
complete until the method of arbitrating a dispute is specified".
(this text clearly distinguishes earlier between a digital
signature, and  signatures which may have additional
arbitration properties. One can note also the use of
the concepts of legal effect, and discussion of 
the policy and legal requirements thereof, years before 
Baum et al. claimed to have originated the same
as the "PEM policy idea")

Indeed, the D&P notion of certificate mentioned is distinct
from that used in X.509 1988, and has an effect on the meaning
of NR. It could be argued by linguists that D&P intended CA-issued
"certificate" to be used in the notarization sense -
not as certificate is used today - that is, the issued cert attested 
to the current accuracy of an copy of the authentic public key, in 
the  context of a proof of origin determination for an current instance
of the service. And this extra step involving certs perhaps got 
renamed "non-repudiation",  somewhere along the line.  But 
use of this term and the underlying ideas get very murky from 
D&P onwards. You an argue I am being revisionist, here.

This is all a bit academic. But the literature does clearly
show that current X.509 concepts of NR and PKCS-only dig sigs 
are not historically supported. Symmetric dig sigs were contemplated,
not just those from public-key ciphers, and the very
term NR most probably derives from the work of Smit
on notarized (symmetric) keys used for proof of
origin, that is - authenticators intended for use
in dispute resolution before judges - ie NR. Regardless
of the origin of the term, definitional cliams used today are
not in line with this available historical record.

Written in 1984, Davies and Price "Security for Computer
Networks",  Wiley, is as good intro to data security
and the background to PKI as there is. Almost nothing has 
changed in 16 years apart from key lenghts and the ease
of generating PKI material on the fly; its just now we are doing 
what they were then discussing.  

> Cheers,
> Ed Gerck