Re: Question about authentication protocols

From: Anne & Lynn Wheeler (lynn_at_garlic.com)
Date: 07/08/05


Date: 08 Jul 2005 12:25:30 -0600

Peter Seibel <peter@gigamonkeys.com> writes:

> One page 54 of Schnier's _Applied Cryptography_ he presents a naive
> authentication protocol based on public key crpto. It goes like this:
>
> (1) Host sends Alice a random string.
>
> (2) Alice encrypts the string with her private key and sends it back
> to the host, along with her name.
>
> (3) Host looks up Alice's public key in its database and decrypts
> the message using that public key.
>
> (4) If the decrypted string matches what the host sent Alice in the
> first place, the host allows Alice access to the system.
>
> He then points out that this protocol is problematic because Alice
> shouldn't be encrypting arbitrary strings with her private key lest
> she open herself up to various attacks which he describes in Section
> 19.3. He then gives an outline of more sophisticated protocols for
> proving identity that involve Alice performing various computations
> based on random numbers that she generates and her private
> key. (The actual protocols are described in Section 21.1.)
>
> However in 19.3 when he discusses the attacks that are possible if
> Alice encrypts arbitrary strings with her private key he closes with
> this Moral: "Never use RSA to sign and random document presented to
> you by a stranger. Always use a one-way hash function first."
>
> So why can't the naive protocol be fixed by simply following that
> advice and having Alice hash the random string and encrypt the
> hash. In other words the patched protocol (with changes in ALL CAPS)
> goes like this:
>
> (1) Host sends Alice a random string.
>
> (2) Alice HASHES THE STRING and encrypts the HASH with her private
> key and sends it back to the host, along with her name.
>
> (3) Host looks up Alice's public key in its database and decrypts
> the message using that public key.
>
> (4) If the decrypted string matches THE HASH OF what the host sent
> Alice in the first place, the host allows Alice access to the
> system.

i think the examples were to take the student through the various thot
processes.

so standard digital signature definition is using private key to
encode hash of message. the recipient then calculates the hash of the
string, decodes the digital signature with the public key and compares
the two hashs. if they are equal, the recipient assumes

1) message hasn't been changed in transit
2) "something you have" authentication (aka originator has access
   and use of the corresponding "private" key).

discussion of the digital signature standard:
http://csrc.nist.gov/cryptval/dss.htm

lots of posts on the 3-factor authentication model
http://www.garlic.com/~lynn/subpubkey.html#3factor

and other posts on certificateless public key operations
http://www.garlic.com/~lynn/subpubkey.html#certless

there can be an issue of the dual-use attack ... there has sometimes
been some possibly semantic confusion with the term *digital
signature* and *human signature* because they both contain the word
*signature*.

*human signature* usually includes the connotation of read,
undertstands, agrees, approves, and/or authorizes.

as in your description, the party, being authenticated, assumes that
they are getting a random string and rarely, if ever, examines what is
being digitally signed.

in various scenarios, there have been efforts to promote *digital*
signatures to the status of *human* signatures. a dual-use attack on a
private key used for both authentication infrastructures as well as
such *human* signature operations ... is for the attacker to
substitute a valid document in lieu of random bit string.

this was exaserbated in the pki/certificate standards world by the
introduction of the "non-repudiation" bit as part of the certification
standard. if a relying party could find any certificate, anyplace in
the world (for the signer's public key) containing the non-repudiation
bit ... then they could claim that the existance of that digital
ceritificate (for the originator's public key containing the
non-repudiation bit) was proof that the originator had read,
understood, agrees, approves, and/or authorizes what had been
digitally signed. in some of the PKI-related payment protocols from
the 90s, this implied that if a relying-party could produce a digital
certificate containing the signer's public key & the non-repudiation
bit ... then in any dispute, it would shift the burden of proof from
the relying party to the digitally signing party.

some recent posts on the subject
http://www.garlic.com/~lynn/2005l.html#18 The Worth of Verisign's Brand
http://www.garlic.com/~lynn/2005l.html#29 Importing CA certificate to smartcard
http://www.garlic.com/~lynn/2005l.html#35 More Phishing scams, still no SSL being used
http://www.garlic.com/~lynn/2005l.html#36 More Phishing scams, still no SSL being used
http://www.garlic.com/~lynn/2005m.html#1 Creating certs for others (without their private keys)
http://www.garlic.com/~lynn/2005m.html#5 Globus/GSI versus Kerberos
http://www.garlic.com/~lynn/2005m.html#6 Creating certs for others (without their private keys)

-- 
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/


Relevant Pages

  • Re: Question about authentication protocols
    ... >> Host sends Alice a random string. ...
    (sci.crypt)
  • Question about authentication protocols
    ... Host sends Alice a random string. ... He then points out that this protocol is problematic because Alice ...
    (sci.crypt)
  • Re: Multi-layered PKI implementation
    ... Bob is an online retailer and Eve is a nasty ... Alice -> Bob: I want to by a shiny wotsit from you for 500 monkeys. ... my public key is 12345. ... Sure, my public key is 12345, and here is my certificate ...
    (Debian-User)
  • Re: Multi-layered PKI implementation
    ... Bob is an online retailer and Eve is a nasty ... Alice -> Bob: I want to by a shiny wotsit from you for 500 monkeys. ... my public key is 12345. ... Sure, my public key is 12345, and here is my certificate ...
    (Debian-User)
  • Re: Searchindexer -- for whose benefit?
    ... If the OTP is a 32 Gb MicroSD card, they can exchange a pair of email ... How does the recipient know he has your correct public key? ... Lets call you Alice, and the other guy Bob. ...
    (rec.arts.sf.fandom)