Scribd Logo
Upload

Welcome to Scribd!

  • 16 views

    Seminar Report On Authentication Codes Theme: Cryptography Course Instructor: Prof. C Pandu Rangan 93124 CS

    Uploaded by

    Aman Machra
    This document summarizes key concepts from a seminar report on authentication codes: 1. Authentication codes provide message integrity by allowing a receiver to verify authenticity using a tag computed from the message and secret key. 2. Deception probabilities quantify the likelihood an adversary can impersonate or substitute a message. Combinatorial bounds show deception probabilities are minimized by orthogonal arrays. 3. Orthogonal arrays model optimal authentication codes, where each pair of symbols occurs equally in each pair of columns. The size of orthogonal arrays relates to properties of authentication codes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Seminar Report On Authentication Codes Theme: Cryptography Course Instructor: Prof. C Pandu Rangan 93124 CS

    Uploaded by

    Aman Machra
    16 views10 pages
    This document summarizes key concepts from a seminar report on authentication codes: 1. Authentication codes provide message integrity by allowing a receiver to verify authenticity using a tag computed from the message and secret key. 2. Deception probabilities quantify the likelihood an adversary can impersonate or substitute a message. Combinatorial bounds show deception probabilities are minimized by orthogonal arrays. 3. Orthogonal arrays model optimal authentication codes, where each pair of symbols occurs equally in each pair of columns. The size of orthogonal arrays relates to properties of authentication codes.

    Original Description:

    rep

    Original Title

    Report 6

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document summarizes key concepts from a seminar report on authentication codes: 1. Authentication codes provide message integrity by allowing a receiver to verify authenticity using a tag computed from the message and secret key. 2. Deception probabilities quantify the likelihood an adversary can impersonate or substitute a message. Combinatorial bounds show deception probabilities are minimized by orthogonal arrays. 3. Orthogonal arrays model optimal authentication codes, where each pair of symbols occurs equally in each pair of columns. The size of orthogonal arrays relates to properties of authentication codes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    16 views10 pages

    Seminar Report On Authentication Codes Theme: Cryptography Course Instructor: Prof. C Pandu Rangan 93124 CS

    Uploaded by

    Aman Machra
    This document summarizes key concepts from a seminar report on authentication codes: 1. Authentication codes provide message integrity by allowing a receiver to verify authenticity using a tag computed from the message and secret key. 2. Deception probabilities quantify the likelihood an adversary can impersonate or substitute a message. Combinatorial bounds show deception probabilities are minimized by orthogonal arrays. 3. Orthogonal arrays model optimal authentication codes, where each pair of symbols occurs equally in each pair of columns. The size of orthogonal arrays relates to properties of authentication codes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    Seminar Report on

    AUTHENTICATION CODES
    Theme : Cryptography
    Course Instructor : Prof. C Pandu Rangan
    R Parthasarathy
    93124 CS

    1 Introduction
    Secrecy has been a major concern in the study of cryptography. That is, Alice
    wants to send a message to Bob and doesn't want anyone else, in particular,
    our famous adversary Oscar to see the contents of the message. But when
    we talk about authentication, we no longer care about secrecy. The objective
    here is, Bob must be sure that the message he receives actually came from
    Alice and no one else. This leads us to the focal point in the seminar, the
    authentication code:
    An authentication code provides a method of ensuring the integrity of a
    message. In such a code, a key is used to compute an authentication tag that
    enables Bob to check the authenticity of the message he receives.
    For the purpose of analysis, it is useful to consider a formal mathematical
    de nition of an authentication code.

    De nition 1 An authentication code is a four tuple (S ; A; K; E ) where the


    following conditions are satis ed:

    1. S is a nite set of possible source states.

    2. A is a nite set of possible authentication tags.


    3. K, the keyspace, is a nite set of possible keys.

    4. For each K 2 K, there is an authentication rule


    eK : S ! A.

    The message set is de ned to be M = S  A.

    Let us see how our adversary Oscar can attack the system. This will give us
    an insight into what authentication codes are trying to guard against.

     Impersonation : Oscar introduces a message (s; a) into the channel,


    hoping that Bob will accept it as authentic.
     Substitution : Oscar observes a message (s; a) in the channel, and
    then changes it to (s0; a0), s 6= s0, again hoping that Bob will accept it
    as authentic.
    2

    Having seen the formal de nition of authentication codes, let us look at an


    auxiliary entity that will be used during our analysis. This is the authentication matrix
    The authentication matrix tabulates all the values of eK (s). For each
    K 2 K and for each s 2 S , the authentication tag eK (s) is placed in row K
    and column s of a jK j  jS j matrix M .

    Example :
    Key
    1
    2
    3

    1
    1
    2
    1

    2
    1
    2
    2

    3
    1
    1
    2

    4
    2
    2
    1

    2 Deception Probabilities

    2.1 What are deception probabilities ?

    Deception probability is the probability that Oscar will successfully deceive


    Bob, assuming he follows an optimal strategy. These probabilities are denoted
    by:
     Pd : Impersonation probability
     Pd : Substitution probability
    Additionally, we have the probability distributions of S and K denoted by PS
    and PK respectively.
    0

    Deception probabilities essentially give a lower bound on the chances that the
    system will be vulnerable to attack. An example would prove instructive to
    understand how deception probabilities are computed.

    Example : Suppose S = A = Z3 and K = Z3  Z3


    and for each (i; j ) 2 K and each s 2 S de ne :
    eij (s) = is + j mod 3
    The authentication matrix is given below:
    Key 0
    (0,0) 0
    (0,1) 1
    (0,2) 2
    (1,0) 0
    (1,1) 1
    (1,2) 2
    (2,0) 0
    (2,1) 1
    (2,2) 2
    It can be shown that Pd = 1=3 and Pd
    0

    1 2
    0 0
    1 1
    2 2
    1 2
    2 0
    0 1
    2 1
    0 2
    1 0
    = 1=3.

    Having seen an example, let us see how deception probabilities can be computed in general.

    2.2 Computation of deception probabilities in general

    Pd : Let K be the key chosen by Alice and Bob. For s 2 S and a 2 A


    de ne payoff (s; a) as the probability that Bob will accept the message (s; a)
    as being authentic.
    Clearly,
    X
    payoff (s; a) = prob(a = eK0 (s)) =
    PK(K )
    0

    K 2K:eK (s)=a

    Hence,

    Pd = maxfpayoff (s; a) : s 2 S ; a 2 Ag
    Pd : First de ne
    0

    payoff (s0 ; a0; s; a) = prob(a0 = eK0 (s0)ja = eK0 (s))


    4

    K 2K:eK (s)=a:eK (s )=a


    0

    PK(K )

    payoff (s; a)
    Since Oscar wants to maximize his chances of deceiving Bob, he will compute

    Ps;a = maxfpayoff (s0; a0; s; a) : s0 2 S ; s 6= s0; a0 2 Ag


    Now,

    Pd =
    1

    where

    s;a)2M

    PM(s; a)Ps;a

    PM(s; a) = PS (s)  payoff (s; a)

    3 Combinatorial Bounds on Deception Probabilities

    3.1 Objectives

    Before going any further, let us understand why we are studying authentication codes and trying to nd combinatorial bounds on the deception probabilities.
    1. The deception probabilities Pd and Pd should be small enough to
    obtain the desired level of security.
    2. The number of source states much be large enough so that we can
    communicate the desired level of information by appending an authentication tag to one source state.
    3. The size of the key space should be minimized, since the value of the
    key should be communicated over a secure channel.
    0

    3.2 Combinatorial Bounds

    Theorem 1 Suppose (S ; A; K; E ) is an authentication code. Then Pd 


    1=l, where l = jAj. Further, Pd = 1=l if and only if
    0

    PK(K ) = 1l

    K 2K:eK (s)=a

    for every s 2 S , a 2 A.

    Proof Suppose we x a source state s 2 S . Then we can compute


    X
    X X
    payoff (s; a) =
    PK ( K )
    a2A

    X
    K 2K

    a2A K 2K:eK (s)=a

    PK(K ) = 1

    Hence, for every s 2 S , there exists an authentication tag a(s) such that
    payoff (s; a(s))  1l
    Theorem 2 Suppose (S ; A; K; E ) is an authentication code. Then Pd 
    1=l, where l = jAj. Further, Pd = 1=l if and only if
    P
    K 2K eK s a eK s a PK (K ) 1
    =l
    P
    K 2K eK s a PK (K )
    1

    ( )= :
    :

    )=

    ( )=

    for every s; s0 2 S ; s 6= s0 ; a; a0 2 A

    Proof This proof follows a similar line. Suppose we x s; a and s0, where
    s0 =
    6 s. Then we can prove:
    X

    a 2A
    0

    payoff (s0; a0; s; a) = 1

    So there exists an authentication tag a0(s0; s; a) such that

    payoff (s0; a0(s0; s; a); s; a) f rac1l


    6

    Now, we have:

    Pd =
    1

    s;a)2M

    PM(s; a)ps;a

    X PM(s; a) 1
    l =l
    s;a 2M
    Further, equality occurs if and only if ps;a = 1=l for every (s; a). But this
    is in turn equivalent to the condition that payoff (s0 ; a0; s; a) = 1=l for every
    (s; a).

    Theorem 3 Suppose (S ; A; K; E ) is an authentication code, where l = jAj.

    Then Pd0 = Pd1 = 1=l if and only if

    K 2K:eK (s)=a:eK (s )=a


    0

    PK(K ) = l1

    for every s; s0 2 S ; s 6= s0 ; a; a0 2 A

    Proof This proof directly follows from combining the LHS and RHS of the
    previous two theorems.

    Corollary 4 Suppose (S ; A; K; E ) is an authentication code, where l = jAj,

    and keys are chosen equiprobably. Then Pd0 = Pd1 = 1=l if and only if

    jK 2 K : eK (s) = a; eK (s0) = a0j = jKl j


    2

    4 Orthogonal Arrays
    Let us take a slight detour here and introduce the concept of Orthogonal
    Arrays (OA's)
    De nition 2 An orthogonal array OA(n; k; ) is a n  k array of n symbols, such that in any two columns of the array every one of the possible n
    pairs of symbols occurs in exactly  rows.
    2

    Why OA's ?
    OA's are well studied structures in combinatorial design theory. OA's and
    authentication codes have a one-to-one relationship.
    Example : An OA(3; 3; 1)
    00 0 01
    BB 1 1 1 CC
    BB 2 2 2 CC
    BB
    C
    BB 0 1 2 CCC
    BB 1 2 0 CC
    BB 2 0 1 CC
    BB 0 2 1 CC
    B@ 1 0 2 CA
    2 1 0
    Note that this OA is similar in structure to the authentication matrix given
    in an earlier example.

    5 Relation of OA's to Authentication Codes

    Theorem 5 Suppose there is an orthogonal array OA(n; k; ). Then there


    is an authentication code (S ; A; K; E ), where jSj = k; jAj = n; jKj = n ,
    2

    and Pd0 = Pd1 = 1=n.

    Proof Use each row of the orthogonal array as an authentication rule with

    equal probability 1=(n ). The correspondences are as follows:


     row ! authentication rule
     column ! source state
     symbol ! authentication tag
    The proof is now evident from the previous corollary.
    2

    Theorem 6 Suppose there exists an OA(n; k; 1). Then k  n + 1.


    Proof Let A be an OA(n; k; 1) on symbol set X = 0; 1; : : : ; n 1. Suppose

     is a permutation of X , and we permute the symbols in any column of A


    according to the permutation . The result is again an OA(n; k; 1). Hence,
    by applying a series of permutations of this type, we can assume without loss
    of generality that the rst row of A is (0; 0; : : : ; 0).
    We next show that each symbol must occur exactly n times in each column
    of A. Choose two columns, say c and c0, and let x be any symbol. Then for
    each symbol x0, there is a unique row of A in which x occurs in column c and
    x0 occurs in column c0. Letting x0 vary over X , we see that x occurs exactly
    n times in column c.
    Now, since the rst row is (0; 0; : : : ; 0), we have exhausted all occurrences
    of ordered pairs (0; 0). Hence, no other row contains more than one occurrence
    of 0.
    Now, the number of rows containing atleast one 0  Total number of rows,
    hence, 1 + k(n 1)  n , i.e k  n + 1.
    2

    Theorem 7 Suppose p is prime. Then there exists an orthogonal array

    OA(p; p; 1).

    Proof The array will be a p  p array, where the rows are indexed by Zp Zp
    and the columns are indexed by Zp. The entry in row (i; j ) and column x is
    de ned to be ix + j mod p. Now it can easily be shown that if we choose two
    columns x; y; x =
    6 y, and two symbols a; b, there is a unique row (i; j ) such
    2

    that a occurs in column x and b in column y of row (i; j ).


    Suppose we choose two columns, x; y; x 6= y and two symbols a; b. We
    want to nd a (unique) row (i; j ) such that a occurs in column x and b occurs
    in column y of row (i; j ). Hence, we want to solve the two equations :

    a = ix + j
    b = iy + j
    for the unknowns i and j (where all arithmetic is done in the eld Zp). But
    this system has the unique solution
    i = (a b)(x y) mod p
    j = a ix mod p
    1

    Hence, we have an orthogonal array.

    Jensen's Inequality Suppose f is a continuous strictly concave function on

    the interval I ,

    n
    X

    and ai > 0; 1  i  n. Then


    n
    X
    i=1

    i=1

    ai = 1

    n
    X
    aif (xi)  f ( aixi)
    i=1

    where xi 2 I; i  i  n. Further, equality occurs if and only if x = x =


    : : : = xn.
    Lemma 8 Suppose b ; b ; : : :; bm are real numbers. Then
    m
    m
    X
    X
    m bi  bi
    1

    i=1

    i=1

    Apply the previous result with f (x) = x and ai = 1=m;


    1im
    Theorem 9 Suppose there exists an OA(n; k; ). Then
      k(n n1) + 1
    This can be proved by counting the number of ordered pairs (0; 0) in the OA.
    2

    6 Conclusions
    A lot of theoretical work has been done in the area of authentication codes.
    Many of the fundamental results have been proved by G.J.Simmons. There
    are a number of survey articles on the topic too.
    The connection between orthogonal arrays and authentication codes has
    been addressed by several researchers. The material presented is based on
    some papers published by D.R.Stinson. Orthogonal arrays, by themselves
    have been studied by researchers in statistics and in combinatorial design
    theory.
    10

    You might also like