Solved

Hash Collision (easy)

Posted on 2011-02-20
13
1,470 Views
Last Modified: 2012-05-11
Hi

I have seen MD5 hash collisions and I already created 2 exe files with same MD5, that's all I know.

I want to learn it in deep, for startup, I want to start with COMP128 v1 which is 10 years old and seems to have really easy collision. I see/read papers about it, but I can't really understand so I can't launch attack.

I'm writing my own code for this attack, but as I don't understand paper, I can't do it properly. I have everything needed, actual SIM cards, known KIs, COMP128 algorithm everything.

For example see this paper:
http://www.stuartwray.net/comp128-a-birthday-surprise-rev.pdf

OR

http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html

It says:

The attack exploits a lack of diffusion: there's a narrow ``pipe'' inside COMP128. In particular, bytes i,i+8,i+16,i+24 at the output of the second round depend only on bytes i,i+8,i+16,i+24 of the input to COMP128. (By ``round'', I refer to one layer of ``butterflies'' and S-boxes; there are a total of 5*8 rounds in COMP128.) Bytes i,i+8 of the COMP128 input are bytes i,i+8 of the key, and bytes i+16,i+24 of the COMP128 input are bytes i,i+8 of the challenge input.

I can't understand:
round
butterflies
layers
S-Boxes
etc.

Could someone give me some easy documents/references for learning this type of knowledge?

Thanks from now
0
Comment
Question by:CSecurity
  • 6
  • 5
  • 2
13 Comments
 
LVL 39

Accepted Solution

by:
noci earned 500 total points
Comment Utility
I am not sure what you are exactly looking for:
(general overview)
How about: (illustrated)
http://unixwiz.net/techtips/iguide-crypto-hashes.html

(Detailed:)
Cryptography handbook:
http://www.cacr.math.uwaterloo.ca/hac/

(A lot of references)
Or Bruce Schneiers site (a lot of valuable information):
http://www.schneier.com/cryptography.html

0
 
LVL 17

Author Comment

by:CSecurity
Comment Utility
I want to learn Hash collisions, none of the links are related. Specially I want to learn COMP128 collision in depth.

Regards
0
 
LVL 39

Assisted Solution

by:noci
noci earned 500 total points
Comment Utility
You asked about:

round
butterflies
layers
S-Boxes

Those are cryptography concepts, if you don't know what those concepts are how do you expect to get "cracking"
The excerpt you have show explains the crux of the problem with COMP128, in terms of cryptography "macro's"
like rounds, s-boxes etc.so if you understand the concepts behind them you can expect to interpret that short piece.
rounds, butterflies are not "cracking" of "collision" concepts. Hence the references to fairly basic cryptography stuff.
Explaining each concept here is more or less copy-typing what is stated in the references.

Collisions are nothing else then multiple inputs generating the same hash outcome.
They best work with concepts like passwords and might help when hashes are used as signatures. (datacom).
0
 
LVL 61

Expert Comment

by:btan
Comment Utility
For a start if you are interested in MD5 hash which I thought we should look at it and spend the effort since it is widely used especially in certificate generated using it instead of SHA1. The couple of link below may be of interest

MD5 Collision Demo @ http://www.mscs.dal.ca/~selinger/md5collision/
MD5 collision finder @ http://www2.mat.dtu.dk/people/S.Thomsen/wangmd5/

Apparently, you may have interest in it since COMP128 is widely used in h/w implementation like the GSM A3/A8 schemes. Strictly speaking, hash is used for integrity checks unlike COMP128 which is implemented for the A3 (authentication) and A8 (key derivation) algorithms using a central core algorithm doing hash function and based on a butterfly structure. The output of the algorithm contains the response used for authentication and session key for the A5 stream cipher used for encryption. COMP128 is considered unsafe because of the small changes in the hash input is not sufficiently dispersed resulting in higher chances of collision at the output.

I suggest looking at the slides, the diagram may help visualisation
@ http://www.tcs.hut.fi/Studies/T-79.514/slides/S5.Brumley-comp128.pdf

I will attempt to explain (pardon me as I am no cryptographer).

For 5*8 rounds, it meant there are total of 8 cycles (or rounds) where the use of 128 bits (16 bytes) Ki is placed as the first 0-15th bytes appended by 128 bits RAND forming the 16-31th bytes. This total of 32 bytes is then run through a set of operation which comprises of 5 round of compression in each of the cycle. The compression is using sort of "butterfly structure".  It is graphically like butterfly. Maybe it is best to check out the slides, I will not say I understand all of it (best effort)

For S-box, it is referencing to substitution box or basically a look up table based on your inputs
@ http://en.wikipedia.org/wiki/S-box

For Butterfly, it is a fundamental mathematical operation in many fast transforms, and shows the processing of two elements in one stage of the transform. The transform is referring to mathematics such as Fourier transform. The name comes from a common graphic depiction of FFT operation which has the shape of a standing "hourglass," or butterfly wings on edge.

For crypto terms, can do a quick search for it and go into that link, good for quick explanation and each statement has links to assist further @ http://www.ciphersbyritter.com/GLOSSARY.HTM

Having said all these, as for the collision for COMP128, if the idea is to know in depth how it works then to appreciate how it can collide. Agree the need to understand the crypto aspects but do note it take another whole lots of fundamental (esp math working) again to overcome another "hill" - not straightforward. But if looking at application, maybe the simple pseudo codes may help
@ http://de.wikipedia.org/wiki/COMP128 (can use google to translate)

Hope it helps
0
 
LVL 17

Author Comment

by:CSecurity
Comment Utility
I know MD5 collision, I don't want to learn about it.

My question is in COMP128 where is says, Round 2 bits has collision, I don't know where is Round 2 and in Output of COMP128 (which is available only) where is Round 2? I don't see any collision in output with some changes in COMP128

I know a little about AES S-Box etc. and I know about COMP128 S-Box, but I want to know more about butterflies, I know that because of butterfly style substition they call it butterflies, but I'm sure after that butterflies major algorithm applies so in output you can't see result of butterflies, so how we can analysis and check collision?
0
 
LVL 17

Author Comment

by:CSecurity
Comment Utility
Let me tell 1 question specifically instead of generic question:

"By ``round'', I refer to one layer of ``butterflies'' and S-boxes; there are a total of 5*8 rounds in COMP128."

When we give A to COMP128 and receive B output, we can't know result of Round 1 or round 2 or round 3 in hashing of COMP128, we see only LAST result (output) of COMP128, how you want to know result of Round 1 output or Round 2 output?

0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 17

Author Comment

by:CSecurity
Comment Utility
0
 
LVL 39

Expert Comment

by:noci
Comment Utility
now you assume correct use of the hash function. What if random isn't exactly random,
it changes all the BYTES, but are some bits unaffected? Can you infer more bits from u changed ones? if some bits are not carried over, then you might have an angle to create collisions.

And creating collisions is never supposed to be easy..., it's exactly why why hash functions exist, to validate that a change did or didn't occur in some data. The earliest form of that is checksumming, but that is easily subverted so more sophisticated function got built...

0
 
LVL 17

Author Comment

by:CSecurity
Comment Utility
I want to understand sentence in COMP128 attack and texts related to ROUNDS, how to apply it? What should I do to see a simple collision in Round X? How to know result of Round X?
0
 
LVL 39

Expert Comment

by:noci
Comment Utility
Well peek in the data while rounds are calculated for a simple sample.
So dump the data at the end of the rounds 1-7 loop and compare it.
Then you can learn each step and see how bits get moved around...

      /* Round 1-7 */
      for (i=0; i<7; i++) {
            /* x[0-15] = Ki */
            memcpy(x, ki, 16);

            /* Compression */
            _comp128_compression(x);

            /* FormBitFromBytes */
            _comp128_bitsfrombytes(x, bits);

            /* Permutation */
            _comp128_permutation(x, bits);
-- Print here for end of round result --

      }

And maybe you need to print intermediates. from in between function calls.
This is fairly basic computer program debugging , may be you need some more basic educaton w.r.t. programming and mathematics if you want to pursue this task.
0
 
LVL 17

Author Comment

by:CSecurity
Comment Utility
I have programming skills, no worries.

Ok, let's work practical, not in technical or imaginations or assumptions.

for example I want to use COMP128 algorithm to find Ki of an unknown card.

I send a RAND to real card and receive X output.

I run same RAND with a Ki which I create, assume:
Ki: 1D000000000000009900000000000000

After 7 round or even after round 2 to run 2-R attack, what should I understand from it? How I should compare something/some result with real card's ALL ROUNDS output?

This is my problem. I know hash algorithm, I know debugging, I know programming
0
 
LVL 39

Expert Comment

by:noci
Comment Utility
to find a weakness you probably start with an All zero RAND number and see if you can predict a bit set in the Ki/Data part after the hash.
if you can find a pattern to  influence the end result then you have a faster way than brute forcing a whole list of values against the keyspace and.
0
 
LVL 61

Expert Comment

by:btan
Comment Utility
understand that the attack is due to narrow pipe, extracted some para for consideration though.

http://www.tcs.hut.fi/Studies/T-79.514/slides/S5.Brumley-comp128.pdf

Specifically, the output bytes of the second round of compression i, i+8, i+16, i+24 are dependent ONLY upon their corresponding input bytes. Thus, the ’pipe’ has a width of 4 bytes.

Involves sending lots of challenges to the card, and collecting the responses. Only bytes i and i+8 are varied; the rest are held constant.

How can we detect a collision in the second round? Since each byte depends only upon 2 bytes of the previous rounds output, a collision in the second round will propagate throughout the rest of the algorithm, causing a collision in the response as well.

Since the pipe is 4 bytes wide (7-bit values), the birthday paradox says we can expect a collision to occur after 2^(4*7/2) = 214 challenges.
One challenge equals one query to the card.
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Since pre-biblical times, humans have sought ways to keep secrets, and share the secrets selectively.  This article explores the ways PHP can be used to hide and encrypt information.
Never store passwords in plain text or just their hash: it seems a no-brainier, but there are still plenty of people doing that. I present the why and how on this subject, offering my own real life solution that you can implement right away, bringin…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now