31 Dec 2014 @ 12:17 AM 

OTP (one time password) challenge gave us a website with username/password/otp as login scheme. A sample login of admin was provided. Since OTP is OTP :P, it won’t work for the second time. We need to understand how exactly OTPs are generated.

Once we create a login in the website, we are provided with an option to download and use OTP generator. Each user gets an option to create a config (token) file, which should be used to feed the OTP generator binary. OTP values contain counters, which will make sure that different OTP gets generated every time.

Reversing OTP binary

Provided binary is ELF x64 C++ binary. Useful symbols were there to help reverse engineer the binary. The config/token files should look like this.

tokenFirst 8 bytes is key-id/random number, second 8 bytes is counter and rest is username. After spending some time with IDA and debugging, we figured the token generating algorithm. It more or less looked like this
1. Username + 7 bytes of key-id is hashed(SHA2) and XORed byte by byte – First 8 bytes of OTP
2. Counter – Next 8 bytes of OTP
3. Counter + 8 bytes of key-id is hashed(SHA2) – last 16 bytes of OTP

Now we know the algorithm, Admin’s OTP and to create the next OTP, we need to know his key-id/token file (8bytes).

Recovering OTP key-id

To attack this scheme, we have to figure out a way to predict the 7 bytes from first part of OTP. An all out brute-force may take ages to complete (even if we precompute values). At this point I consulted dcoder, who pointed me to do meet-in-the-middle.

We are attacking a 7 byte combination. So the idea is to precompute hashes of 3 byte combination, and try to find a match when creating 4 byte hashes. Code should look like this:

uint64 MakeBaseSum()
	uint64 base = 0; 
	uint8 data[] ="\x61\x64\x6d\x69\x6e\x00";		//admin\0

	base = SingleHash(0, 0);
	for(int i=0;i<6;i++)
		base ^= SingleHash(data[i], i);
	return base;
void MiTM()
	uint64 basesum;
	uint8 target_a[] = "\x9a\xe6\x84\xca\x58\x32\x14\xd3";	//hash
	uint64 p0sum[256];
	uint64 p1sum[256];
	uint64 p2sum[256];
	uint64 p3sum[256];
	uint64 p4sum[256];
	uint64 p5sum[256];
	uint64 p6sum[256];
	uint64 target; 
	memcpy(&target, target_a, sizeof target);

	basesum = MakeBaseSum();
	size_t userLen = 6;		//with '\0'
	for(int i=0;i<256;i++)
		p0sum[i] = SingleHash(i, userLen + 0);
		p1sum[i] = SingleHash(i, userLen + 1);
		p2sum[i] = SingleHash(i, userLen + 2);
		p3sum[i] = SingleHash(i, userLen + 3);
		p4sum[i] = SingleHash(i, userLen + 4);
		p5sum[i] = SingleHash(i, userLen + 5);
		p6sum[i] = SingleHash(i, userLen + 6);
	printf("Tables created.\n");
	unordered_map<uint64, uint32> map;
	//all 3 byte combination
	for(uint32 i=0; i < (1<<24); i++)
		uint64 temp = basesum ^ p0sum[i&0xFF] ^ p1sum[(i>>8)&0xFF] ^ p2sum[(i>>16)&0xFF];
		map.insert(std::pair<uint64, uint32>(temp, i));
	printf("3 byte done.\n");
	//all 4 byte combination
	for (uint64 i= 0; i < (1LL<<32); i++)
		uint64 temp = p3sum[i&0xFF] ^ p4sum[(i>>8)&0xFF] ^ p5sum[(i>>16)&0xFF] ^ p6sum[(i>>24)&0xFF];
		if(map.count(temp ^ target))
			uint64 full = ((i << 24) + map.at(temp ^ target));
			uint8 bytes[8]; 
			memcpy(bytes, &full, sizeof bytes);
			printf("Found: \n");
			for(size_t j = 0; j < 8; ++j)
				printf("0x%02X,", bytes[j]);

After running this for couple of minutes, we got the 7 bytes of key-id. Missing byte can be brute-forced by comparing with the known OTP value.
Final source code for OTP gen should look like this:
int main( int argc, char *argv[] )
	int i;
	sha256_context ctx;
	unsigned char sha256sum[32], basesum[32];
	uint8 data[] ="\x61\x64\x6d\x69\x6e\x00\xC1\x0E\x43\x8C\x99\xBB\x49"; //name+7bytes of key-id
	uint8 base[] ="\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"; //null byte string to hash first
	sha256_starts( &ctx );
	sha256_update( &ctx, base, 0xd );
	sha256_finish( &ctx, basesum );

	//data is hashed byte by byte and xored
		uint8 cont[] ="\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00";
		cont[i] = data[i];
		sha256_starts( &ctx );
		sha256_update( &ctx, cont, 0xd );
		sha256_finish( &ctx, sha256sum );
		XOR(basesum, sha256sum);			//byte array XOR
	//first 8 bytes of OTP
		printf("%02x", basesum[i] );
	uint8 count[] = "\x3a\x05\x00\x00\x00\x00\x00\x00\x93\xC1\x0E\x43\x8C\x99\xBB\x49"; //computed key-id
	sha256_starts( &ctx );
	sha256_update( &ctx, count, 0x10 );
	sha256_finish( &ctx, sha256sum );

	//second 8bytes - the counter
		printf("%02x", count[i] );
		printf("%02x", sha256sum[i] );
	return 0;

Now we can login to the webpage and get our flag 🙂

Posted By: Dan
Last Edit: 02 Jan 2015 @ 07:02 PM

EmailPermalinkComments (0)
Tags: , , , ,
Categories: CTF

 Last 50 Posts
Change Theme...
  • Users » 1
  • Posts/Pages » 15
  • Comments » 39
Change Theme...
  • VoidVoid « Default
  • LifeLife
  • EarthEarth
  • WindWind
  • WaterWater
  • FireFire
  • LightLight


    No Child Pages.