By Juanita Kelley,2014-10-15 15:07
15 views 0

    Final Report in ATIC

    A Brief Introduction to Message Authentication


Message Authentication Code

    ; Motivation for using the message authentication code

     With the development of the information technology and computer science , nowadays , there is much more necessity for persons to keep their private or public information save from other's malice attacks and corresponding information abuses.

     In general , there exists about 5 classic ways for an ideal attacker to break a information exchange channel ,they are

    1. Interruption

    2. Interception

    3. Modification(substitution)

    4. Fabrication(impersonation)

    5. Replay

     In most cases , the situations 1 and 2 cannot be prevented through a mathematical way ,it is more likely solved in the physical level . So the motivation for someone to use an message authentication code focuses on the situation 3 and 4 , that is , by the conception of it we can easily check whether the message which we received from a transmitter has not been modified or it was just a fake one, briefly we called it as "keep the integrity of the messages".

; Definition of the message authentication code

     In cryptography, a message authentication code (MAC) is a short piece of information used

    to authenticate a message.

     A MAC algorithm, sometimes called a keyed (cryptographic) hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC (tag). The

    MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content.

Information-theoretic security

     Security is an essential criteria for a cryptographic scheme which contains two big abstract fields : information-theoretically secure and Computational security.

     A cryptosystem is information-theoretically secure if its security derives purely from the

    information theory, that is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the security. An algorithm or encryption protocol that has information-theoretic security does not depend for its effectiveness on unproven assumptions about computational hardness and such an algorithm is not vulnerable

    to future developments in quantum computing. An example of an information-theoretically secure cryptosystem is the one-time pad which invented in 1917 by Gilbert Verham.

     Generally, information-theoretically secure mainly concerns about information that leaked by secret data and by its definition we can infer that there is no bound allowed to an attacker on the amount of computations. Comparatively, computational security concerns the computational effort required for breaking a cryptographic scheme. It always relies on some hard unproven computational assumptions(e.g. Decisional Composite Residuosity Assumption, Quadratic Residuosity Assumption).

     Security model for the message authentication code ; Participants

    1. Message transmitter(Alice)

    2. Message receiver(Bob)

    3. Opponent(Eve)

     In this model, the transmitter wants to communicate some information to the receiver using a public communications channel, and the target of a opponent is to fabricate or modify the message which was sent by transmitter and he has to try every possible method to make receiver believe that the fake message is exactly sent by the transmitter.

     The relation among these three participants is as follows:



    Message m=e(s) Alice Bob public channel

    secure channel



    Key Resource

; Basic notation

     We will use the following notation.

     S :set of source state(or plaintext)which contains k states.

     M : set of v messages.(i.e. #|M|=v)

     ε :set of encoding rules

     the relation between these three sets is ????,e??,then ?? ?=(?) .

; Matrix representation

     We can represent a code by an |?|×? matrix, where the rows are indexed by encoding rules,

    the column are indexed by source states like the table as follows.

    ?? Suppose ?=,, ,?={?,?,?,} then the matrix is 123123

     ? ? ? 123

    ?? (?) ? (?) 1111213

     (?) (?) (?) 2212223

     (?) (?) (?) 3313233

    ?? Similarly, we can define the set ?={?;,??} . ?

    ???? In the example above, ?={?,?, (?)} . ?1121311

    ; Impersonation attack and substitution attack

     As we have referred in the first paragraph, to an ideal attacker(or opponent), there are two

    mainly methods from which we have to prevent and against. That is, the Modification and the

    Fabrication(here we call them Impersonation attack and substitution attack).

     To make these two methods distinctly, I'd like to show a picture beneath.

     Alice Alice Bob Bob

    m0 m1 m

    Eve Eve

    Fabrication(Impersonation attack) Modification(Substitution attack)

     Now we define the probability of the impersonation attack and substitution attack:

     Impersonation attack: let a ??? chosen by an opponent(Eve or a forger), suppose that ? a 0

    forger which on input ? outputs a valid pair (?,m)??×? with probability (. Define the 000

    deception probability ?? to be the maximum value ( s.t. the above opponent exists. ???

     Substitution attack: let s?? chosen by an opponent, suppose that ? a forger which on input a valid pair (?,?) outputs a valid pair (?,m)??×? with probability ). Define the 00

    deception probability ?? to be the maximum value ) s.t. the above opponent exists. ???

     (Notice that we will consider the "worst possible case")

     In fact, ?? and ?? can generalized by the definition of payoff function. ??????

    ???? For ???,???, we define ???????,?=Pr[?,? is a valid pair;? fixed]. 0000000

    ???????? We can also write ???????,?=Pr?=