128-EIA3 is not a collision resistant Integrity Algorithm

View previous topic View next topic Go down

128-EIA3 is not a collision resistant Integrity Algorithm

Post  zeshan on Tue Mar 15, 2011 11:03 pm

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

View user profile

Back to top Go down

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

Post  Steve Babbage on Wed Mar 23, 2011 3:11 am

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?

Steve Babbage

Posts : 30
Join date : 2010-08-02

View user profile

Back to top Go down

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

Post  zeshan on Fri Mar 25, 2011 12:29 am

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.


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

View user profile

Back to top Go down

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

Post  Steve Babbage on Thu Apr 07, 2011 9:28 am

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

Steve Babbage

Posts : 30
Join date : 2010-08-02

View user profile

Back to top Go down

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

Post  zeshan on Mon Apr 11, 2011 12:50 am

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

zeshan

Posts : 11
Join date : 2010-08-16

View user profile

Back to top Go down

Collision Attack is not practical on 128-EIA3

Post  zeshan on Tue May 31, 2011 11:48 pm

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.

zeshan

Posts : 11
Join date : 2010-08-16

View user profile

Back to top Go down

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

Post  Peng Wang on Wed Jun 08, 2011 3:34 am

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

View user profile

Back to top Go down

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

Post  zllz on Sun Jun 12, 2011 5:22 pm

Hi Peng,

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

Thank you.

zllz
Guest


Back to top Go down

32-bit MAC

Post  Peng Wang on Sun Jun 12, 2011 7:34 pm

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

View user profile

Back to top Go down

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

Post  Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum