# 128-EIA3 is not a collision resistant Integrity Algorithm

3 posters

Page

**1**of**1**## 128-EIA3 is not a collision resistant Integrity Algorithm

128-EIA3 is not a collision resistant Integrity Algorithm as it collides to same MAC for different distinct messages.

**zeshan**- Posts : 11

Join date : 2010-08-16

## Re: 128-EIA3 is not a collision resistant Integrity Algorithm

Are you referring to the most recent version of the 128-EIA3 algorithm (verson 1.5, dated 4th Jan 2011, currently available at GSM Security Algorithms)?

It is already known that a forgery attack was possible against the original version. See the design and evaluation report, also available at GSM Security Algorithms, and the result published here http://eprint.iacr.org/2010/618.

If your statement does refer to the most recent version of the algorithm, can you give more detail, please?

It is already known that a forgery attack was possible against the original version. See the design and evaluation report, also available at GSM Security Algorithms, and the result published here http://eprint.iacr.org/2010/618.

If your statement does refer to the most recent version of the algorithm, can you give more detail, please?

**Steve Babbage**- Posts : 30

Join date : 2010-08-02

## Collision Found in 128-EIA3 integrity algorithm (verson 1.5)

Collisions are found in 128-EIA3 integrity algorithm (verson 1.5).

Our technique for finding collision in 128-EIA3 is different to, as mentioned in paper http://eprint.iacr.org/2010/618.As this paper deals with related messages of different length.

The purpose of our technique is to find collision in 128-EIA3 for distinct messages of the same length under following conditions:-

-Same Integrity Key(IK) and IV.

-Different Integrity Key(IK) and same IV.

-Same Integrity Key(IK) and Incremental IV.

These collided pairs can be used subsequently for message forgery.The attack complexity is less than 2^32.

Our technique for finding collision in 128-EIA3 is different to, as mentioned in paper http://eprint.iacr.org/2010/618.As this paper deals with related messages of different length.

The purpose of our technique is to find collision in 128-EIA3 for distinct messages of the same length under following conditions:-

-Same Integrity Key(IK) and IV.

-Different Integrity Key(IK) and same IV.

-Same Integrity Key(IK) and Incremental IV.

These collided pairs can be used subsequently for message forgery.The attack complexity is less than 2^32.

Last edited by zeshan on Thu Jun 09, 2011 4:22 am; edited 1 time in total

**zeshan**- Posts : 11

Join date : 2010-08-16

## Re: Collision Found in 128-EIA3 integrity algorithm (verson 1.5)

So where and when are you planning to publish your analysis?

**Steve Babbage**- Posts : 30

Join date : 2010-08-02

## Re: 128-EIA3 is not a collision resistant Integrity Algorithm

I am planning to publish these results in ZUC upcoming conference.

**zeshan**- Posts : 11

Join date : 2010-08-16

## Collision Attack is not practical on 128-EIA3

The paper titled "Collision attack and message forgery on 128-EIA3", submitted to ZUC conference 2011 doesn't present a practical attack on 128-EIA3.

Details of the paper can be found at http://eprint.iacr.org/2011/268.

Details of the paper can be found at http://eprint.iacr.org/2011/268.

**zeshan**- Posts : 11

Join date : 2010-08-16

## Re: 128-EIA3 is not a collision resistant Integrity Algorithm

zeshan wrote:The paper titled "Collision attack and message forgery on 128-EIA3", submitted to ZUC conference 2011 doesn't present a practical attack on 128-EIA3.

Details of the paper can be found at http://eprint.iacr.org/2011/268.

Some comments:

The direct goal of the attack against 128-EIA3 is to predict a new valid triple (IV, Message, MAC), but not to find collisions.

The analysis is about the 128-EIA3 version 1.4 (see page 3 of [H11]), not version 1.5 (new version).

The internal and external collisions in [H11] are general birthday collisions, and have nothing to do with the specific features of 128-EIA3.

In the real application the IK is fixed and IV is incremental. It is hard to get internal collisions under the same IK and IV and external collisions under random IK and incremental IV in [H11]. It’s not clear how to make use of external collisions under fixed IK and incremental IV to predict a new valid triple (IV, Message, MAC).

The conclusion of [H11]: “128-EIA3 is not a ε-Almost Xor Universal hash function as it is susceptible to birthday forgery attack.Both internal collisions and external collisions are found in 128-EIA3.” Actually, 128-EIA3 is a MAC making use of an AXU hash fucntion (denoted as H). The AXU property of H is provable. Maybe internal collisions have same thing to do with AXU, but it must be under the same key. So this statement is really not precise enough.

[H11] Raja Zeshan Haider. Birthday Forgery Attack on 128-EIA3 Version 1.5. http://eprint.iacr.org/2011/268

**Peng Wang**- Posts : 6

Join date : 2010-10-25

## Re: 128-EIA3 is not a collision resistant Integrity Algorithm

Hi Peng,

Could you explain the design rationale behind choosing only 32-bit MAC size?

Thank you.

Could you explain the design rationale behind choosing only 32-bit MAC size?

Thank you.

**zllz**- Guest

## 32-bit MAC

zllz wrote:

Could you explain the design rationale behind choosing only 32-bit MAC size?

It is not our deliberate choice but according to the regulation of 3GPP. The previous algorithms all have 32-bit MACs, such as UIA1 (based on KASUMI), UIA2 (based on Snow 3G) and EIA2 (based on AES). It is a big challenge to design such a small MAC and obtain a good security bound.

**Peng Wang**- Posts : 6

Join date : 2010-10-25

Similar topics

» Why do we need this new algorithm，and what is the benefit

» Algorithm Complexity of ZUC

» Test Set Mismatch for EIA3

» Why length of only 32-bits in 128-EIA3 MAC?

» How long it will take to put it into service if this algorithm passes public evaluation and becomes a standard?

» Algorithm Complexity of ZUC

» Test Set Mismatch for EIA3

» Why length of only 32-bits in 128-EIA3 MAC?

» How long it will take to put it into service if this algorithm passes public evaluation and becomes a standard?

Page

**1**of**1****Permissions in this forum:**

**cannot**reply to topics in this forum