Binary Exploitation [pwnable.kr] - (Level 2) Collision

#Challenge Description

Name	BOF
Points	7
Solves	12586 times
Category	Exploitation
Description	Daddy told me about cool MD5 hash collision today. I wanna do something like that too!

Below is the source code of the challange which you will see on the server.

unsigned long hashcode = 0x21DD09EC;
unsigned long check_password(const char* p){
	int* ip = (int*)p;
	int i;
	int res=0;
	for(i=0; i<5; i++){
		res += ip[i];
	}
	return res;
}

int main(int argc, char* argv[]){
	if(argc<2){
		printf("usage : %s [passcode]\n", argv[0]);
		return 0;
	}
	if(strlen(argv[1]) != 20){
		printf("passcode length should be 20 bytes\n");
		return 0;
	}

	if(hashcode == check_password( argv[1] )){
		system("/bin/cat flag");
		return 0;
	}
	else
		printf("wrong passcode.\n");
	return 0;
}

#What are Hashes?

and why is there a collision between them, you might ask!

Hash are core elements of the modern digital signature. Input to a hash function is data for
which you want to create a signature for, and output is a unique fixed-sized signature.
This conversion of input data to signature is done by a special algorithm like MD5, SHA1,
SHA256, etc. output of these algorithms is called hash value or message digest.

Hash algorithm can be applied to any data/document or any size and its hash value can be
considered as the unique identification of that document, and in future, if anyone changes
the content of data/document the resulting hash value also change. Hashes are used in
block-chains, digital certificates, etc, to validate the integrity of the document issued.

Ideally, no two different sets of data/document should have the same hash value, that will result in the hash collision which is bad because then we can generate duplicate data/document of the same hash value, which make the hash value useless for integrity check.

#Hint

This challenge uses one such over-simplified such hash algorithm and our task is to
provide an input that will result in hash value 0x21DD09EC, we have to generate
a hash collision.

#Hash Algorithm

The program takes one input parameter which is the data which will be hash and it
should be of fixed size 20 bytes. The hash algorithm converts the char pointer
to integer pointer which will transform 20 bytes into 5 integer data and then it
does the addition of those values. The result of this hashing should be 0x21DD09EC
to get the flag.

#Solution

Plan one byte at a time. One way to visualize the input would that input is 5 groups of 4 bytes.
The first byte of each group will affect the first byte of the resultant hash second byte of
each group will affect the second byte, so on and so forth.

Offset	0	1	2	3
0x0	0x01	0x01	0x01	0x01
0x4	0x01	0x01	0x01	0x01
0x8	0x01	0x01	0x01	0x01
0xC	0x01	0x01	0x01	0x01
0x10	0xE8	0x05	0xD9	0x1D
========	======	======	======	======
Result	0x21	0xDD	0x09	0xEC

To give a hex input you need to do command-line fu, the following command will be the solution
to the challenge.

echo -e "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\xe8\x05\xd9\x1d"

#Conclusion

This challenge is to give you a peek of how hashes are created and how to manipulate them
to create a collision.