By Juanita Kelley,2014-10-15 15:07
16 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?=?=|{,??,?=?}|/#| ? |. 000000

    ?? Then ??=?:?{???????,?;???,???}. ???0000

    ?????? Define ???????,?;?,?=Pr[?,? is a valid pair;when ?,?is a valid pair] 0000

     Then ??=:?~:,;:?~(??????(?,?;?,?)). ?????(?,?)0000

Strongly universal hashing functions

    ; A review in hash function

     A cryptographic hash function is a hash function, that is, an algorithm that takes an arbitrary block of data and returns a fixed-size bit string, the (cryptographic) hash value, such that an (accidental or intentional) change to the data will (with very high probability) change the hash value. The data to be encoded is often called the "message," and the hash value is sometimes called the message digest or simply digest.

     The ideal cryptographic hash function has four main or significant properties:

    1. it is easy to compute the hash value for any given message

    2. it is infeasible to generate a message that has a given hash

    3. it is infeasible to modify a message without changing the hash

    4. it is infeasible to find two different messages with the same hash

; Universal hash families

     Definition: A (D;N,M) hash family is a set ? of D functions such that ?:,?? for each

    ???, where =? and ?=?.

     A (D;N,M) hash family, ?, is strongly universal provided that, for any two distinct elements

    ?,??, , and for any two elements ?,???,it holds that 1212

    ???????#???:??=?,??=?= 11222?

; Hash functions in MAC

     In a MAC scheme, a MAC function shares some same requirements with the universal hash families. Such as a MAC function must resist existential forgery under chosen-plaintext attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages without performing infeasible amounts of computation. This requirement can be satisfied by the property of the definition of the strongly universal hash families.

; A construction of a strongly universal hash function

    2 Suppose a (D;M,M) hash family F, which ℤ? D=M! ( M!/ ??ℤ). the hash function ???? ??

    follows that

    M12?????1,? ,? ???????????????????1?2??

     Which ? is a M level symmetric group. Then F is a Strongly universal hash function. ?

     As followed is an Example for this hash family F which F is (6!;6,6)

     ? ? ? ? ? ? 123456

    1 2 3 4 5 6 ? 1

    2 4 6 1 3 5 ? 2

    ...... ...... ...... ...... ...... ......

    5 3 1 6 4 2 ? 6!

    ??Proof: ? ??1,? and fixed ?,then #|{????=?;??ℤ}|=M!/M. ????

??#?????:????=?,??=???=#|{????=?;??ℤ}|×Pr[?=?;?=?]= M!/M*1/M ????????????

?!= 2?

According to the definition, apparently F is a strongly universal.

Report this document

For any questions or suggestions please email