From Wikipedia, the free encyclopedia
Jump to: navigation, search

Note: this is work in progress, feel free to make amendments. I have not yet checked spelling etc. Please feel free to correct anything but remember it is not finished work so please do not judge it as such.


In the context of cryptography authentication denotes three related but subtly different processes: first entity authentication where a user or computer provides credentials (often a password) to another computer to provide evidence of its identity; second message or data origin authentication where information is generally appended to a message to provide evidence that the message originated from a particular person or entity; and finally transaction authentication where transactions as a whole are authenticated.

The word authentication is often used in a narrower sense to refer to entity authentication only[1] but the wider sense has general currency.[2]

Entity authentication[edit]

The most familiar examples of entity authentication are perhaps the use of a password to authenticate a user to a computer or the use of a PIN to authenticate a user to a Mobile Phone SIM or to a chip based credit/debit card.

Cryptogtaphic techniques are at the core of almost all authentication systems as while it is possible to store PINs or passwords in plaintext this introduces an unnecessary vulnerability. Even where a system using plaintext storage of passwords has no real requirement for security users tend to reuse passwords across multiple systems[3]. The effect of this is that where an attacker can obtain a file of plaintext usernames/passwords this can be used to attack other systems where the users have accounts. Most systems using basic PIN/password authentication use some form of cryptography to store a value related to the PIN/password rather than plaintext.

Earlier Unix systems encrypted passwords with a slight variant of DES[4] to store a salted and encrypted password to file. More recent versions of Linux and Unix derivitives provide for Pluggable Authentication Modules[5] which allow for system administratior selection of authentication mechanisms.

More advanced systems that use one-time passwords of one form or another are also commonly used and typically depend on either synchronised tokens such as RSA's SecurID token or rely on a challenge response mechanism where the server provides a challenge (usually a number) which the user keys into a calculator like device.

Time synchronised tokens are provided with a seed number which is also stored on the authentication server. Both token and server encrypt this initially and use the output of each encryption as the input to the next encryption. The token displays a number which is calculated from the current encrypted value and is updated at regular intervals. Clearly the initial seed data constitutes plaintext key material and requires a high level of protection. While it is not clear exactly what data was obtained it appears that hackers gained access to servers containing information related to RSA's SecurID tokens in March 2011[6].

The essential problem with more advanced authentication mechanisms is that they have been more cumbersome to use than simple password based mechanisms and accordingly have found limited acceptance outside of a corporate environment where their use can be mandated by the organisation.[7] Software tokens for mobile phones are now available which appear to have the potential to mitigate the ease of use issues.[8] [9]

Message authentication[edit]

Simple message authentication with encryption of the message and hash.

Message authentication provides evidence as to the origin of a message or a piece of data. Encryption alone provides very little by way of authentication of the origin of a message. Any relay may modify an encrypted message and this may, or may not be noticed. The classic paper in relation to message authentication was only written in 1974[10], this paper set out the definition of absolutely secure authentication schemes based on symmetric ciphers in much the same way that Shannon's earlier work had done in respect of encryption schemes. However authentication schemes in general use, in line with the approach taken to encryption schemes, are based on it being computationally infeasible to forge an authenticated message.[11] Data integrity and message authentication are intimately connected as if a message has been altered from its purported origin the modified message originated elsewhere.[12] Accordingly, the simplest approach to message authentication using symmetric cryptography is to add some form of hash of the message (such as a cyclic redundancy check and then encrypt the entire message including the digest. Once decrypted almost all alterations to the message become apparent as on recomputing the hash it will fail to compare. With this type of scheme the cryptographic qualities of the hash function is not especially important.

This approach is vlunerable to known a known plaintext attack when used with additive stream ciphers i.e. those where the ciphertext output is computed as an exclusive or function of the plaintext with a keystream.[13] This occurs in a number of standard modes of operation of block ciphers. Accordingly this simple approach is not widely used in practice.

Simple MAC based message authentication.

When the message itself it not to be encrypted it is essential that the hash function is collision resistant (i.e. that it is computationally infeasible for an attacker to produce an alternative message which generates the same hash value). A number of cryptographic hash functions have been developed which exhibit the appropriate properties including SHA-1and SHA-2. One previously widely used cryptographic function MD5 is now considered compromised.

Authenticating with digital signatures[edit]

Overview of message authentication with RSA based digital signature (slightly simplified).

Where users do not have a shared secret key message authentication can be implemented using digital signatures which rely on public key cryptography.

It should be noted that public key based schemes rely on a (possibly public) piece of shared data: the public key, as opposed to the schemes discussed above which rely on a shared secret that should only be known to the parties.

The authentication problem then reduces to obtaining an authentic copy of the public key of the signing entity. This is generally addressed recursively an entity wishing to use digital signatures usually generates a public/private key pair and then gets a certificate authority to digitally sign a certificate as to the authenticity of its public key. While multiple layers of certificate authorities can be accommodated in this way ultimately a root certificate must be authenticated by some out-of-band mechanism.

Authentication with digital signatures, where the public key is obtained from a certificate signed by an appropriate certificate authority provides authentication, message integrity and non-repudiation.

The example shown to the right is a slight simplification of an implementation using RSA based digital signatures. The fundamental operation used in RSA based algorithms is modular exponentiation. While message padding defined by PKCS#1 varies between encryption and signing, in essence signing is equivalent to encryption using the user's private key.[14] This enables verification to be performed by carrying out the equivalent operation using the user's public key.

It should be noted that it is generally considered bad practice, largely for key management reasons, to use the same public/private keypair for encryption and signing.[15]

Transaction authentication[edit]

Transaction authentication builds on message authentication to add guarantees of timeliness and uniqueness. This addresses the issue of message replay.

To take a simple example of why transaction authentication is important if a cryptographic protocol allowed the recipient of a digitally signed message instructing a credit card provider to make a payment from the signer's account could simply forward the message twice to the credit card company and receive two payments that protocol would be unlikely to be widely used.

Simple sequence numbers can prevent replay attacks but do not provide real time timeliness.[16] Other techniques such as the use of cryptographic nonces provide an enhanced level of protection against such attacks.

Domain Name System Security Extensions[edit]

Domain Name System Security Extensions[17] ("DNSSEC") in an extension to the Domain Name System that provides data origin authentication for all responses from name servers.

It is implemented using digital signatures to sign all responses from DNS name servers. DNSSEC implements some features such as timestamps that perhaps more properly belong to transaction authentication than data origin identification.

The DNS root zone is now signed with DNSSEC.[18]


  1. ^ Smith, Richard E. (2002), Authentication: From Passwords to Public Keys, Addison - Wesley, ISBN 0-201-61599-1 
  2. ^ Menzes, Alfred; et al. (1997). Handbook of Applied Cryptography. CRC Press. Section 1.7. ISBN 0-8493-8523-7. 
  3. ^ Samson, Ted (10 February 2011), Study finds high rate of password reuse among users  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  4. ^ Garfinkel, Simson (April 1996), Practical UNIX and Internet Security, ISBN 1-56592-148-8  Text " publisher - O'Reilly " ignored (help); Unknown parameter |retrieved= ignored (|access-date= suggested) (help); Unknown parameter |second2= ignored (help); |first2= missing |last2= in Authors list (help)
  5. ^ >"Linux-PAM".  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  6. ^ Coviello, Arthur, Open Letter to RSA Customers  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  7. ^ Dodson, Ben; Sengupta, Debangsu; Boneh, Dan; Lam, Monica S. "Snap2Pass: Consumer-Friendly Challenge-Response Authentication with a Phone" (PDF).  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  8. ^ "OATHTOKEN".  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  9. ^ Dodson, Ben; Sengupta, Debangsu; Boneh, Dan; Lam, Monica S. "Snap2Pass: Consumer-Friendly Challenge-Response Authentication with a Phone" (PDF).  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  10. ^ Gilbert, E.N.; MacWilliams, F.J.; Slone, N.J.A. (1974). "Codes which detect deception". Bell Sys. Tech. J (53): 405 – 424.  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  11. ^ Pfitzmann, Birgit (1996). Digital Sitnature Schemes: General Framework and Fail-Stop Signatures. Springer Verlag. Chapter 2. ISBN 3-540-61517-2. 
  12. ^ Menzes, Alfred; et al. (1997). Handbook of Applied Cryptography. CRC Press. Section 9.6. ISBN 0-8493-8523-7. 
  13. ^ Menzes, Alfred; et al. (1997). Handbook of Applied Cryptography. CRC Press. Section 9.86. ISBN 0-8493-8523-7. 
  14. ^ "What is a digital signature and what is authentication?". RSA Laboratories.  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  15. ^ Curry, Ian. "Key Update and the Complete Story on the Need for Two Key Pairs" (PDF). Entrust.  Unknown parameter |retrieved= ignored (|access-date= suggested) (help)
  16. ^ Menzes, Alfred; et al. (1997). Handbook of Applied Cryptography. CRC Press. Section 9.79. ISBN 0-8493-8523-7. 
  17. ^ "DNSSEC: DNS Security Extensions: Securing the Domain Name System url=".  Unknown parameter |retrieved= ignored (|access-date= suggested) (help); line feed character in |title= at position 65 (help);
  18. ^ "The DNS Root Zone is now signed with DNSSEC". IANA. 15 July 2007. Retrieved 7 May 2011.