SHA-1 implementation

mandruk1331

Hello, at the moment I am writting a SHA -1 algorithm implementation myself which will be used in a Qt application in the future, but the problem is that it does not calculate correctly the SHA-1 hash, I have moved the program to console one, so it can be just copy pasted. Can someone check out the code and help me out, because I'm stuck can't find the problem for more then 4 hours. Thank you in advnce. Here is the code:

#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <cstdint>
#include <sstream>
#define BIT_OF_BYTES 8
#define FOT 512 // Five one two
#define FFE 448 // Four four eight
#define QUANT_OF_WORD_CHUNKS 16
void reverse_string(std::string &temp_string){
	int string_length = temp_string.length();
	for (int i = 0; i < string_length/2; i++){
		temp_string[i] = temp_string[string_length-(i+1)] ^ temp_string[i];
		temp_string[string_length - (i + 1)] = temp_string[i] ^ temp_string[string_length - (i + 1)];
		temp_string[i] = temp_string[string_length - (i + 1)] ^ temp_string[i];
	}
}
void char_to_bin( char letter_,std::string &buff_){
	short num = (int)letter_;
	bool res = NULL;
	std::string temp_;
	while (num){
		res = num % 2;
		//if (res != false || res != true) return;
		(res == true) ? temp_.append("1") : temp_.append("0");
		num /= 2;
	}
	while (1){
		if (temp_.length() == 8){ break; }
		(temp_.length() < 8) ? temp_.append("0") : NULL;
	}
	reverse_string(temp_);
	buff_.append(temp_);
 	
}
void sf_length_rep(int msg_length, std::string &bin_string){
	bool num = NULL;
	std::string temp_;
	while (msg_length){
		num = msg_length % 2;
		msg_length = msg_length / 2;
		//if (num != true || num != false) return;
		(num == true) ? temp_.append("1") : temp_.append("0");
	}
	short add_length = 8 - temp_.length();
	for (int i = 0; i < add_length; i++){
		temp_.push_back('0');
	}
	reverse_string(temp_);
	short add_zero = 64 - temp_.length();
	std::string zero_;
	for (int i = 0; i < add_zero; i++){
		zero_.append("0");
	}
	zero_.append(temp_);
	bin_string.append(zero_);

}
void LCS(std::string &string_temp){ Left Cycle Shift for string
	string_temp.push_back(string_temp[0]);
	string_temp.erase(0, 1);
}
std::string xor_LCS_func(std::string xor_0, std::string xor_1, std::string xor_2, std::string xor_3){
	std::string temp_xor;
	std::string temp_xor1;
	for (int i = 0; i < xor_0.length(); i++){
		temp_xor.append(std::to_string(xor_0.at(i) ^ xor_1.at(i)));
	}
	for (int i = 0; i < temp_xor.length(); i++){
		temp_xor1.append(std::to_string(temp_xor.at(i) ^ xor_2.at(i)));
	}
	temp_xor.clear();
	for (int i = 0; i < temp_xor1.length(); i++){
		temp_xor.append(std::to_string(temp_xor1.at(i) ^ xor_3.at(i)));
	}
	LCS(temp_xor);
	return temp_xor;

}
struct Chunk_struct
{
	std::string string_chunk_;
	std::vector <std::string*> Chunk_words;
};
unsigned __int64 func1(unsigned __int64 b, unsigned __int64 c, unsigned __int64 d){
	//(b and c) or ((not b) and d)
	unsigned __int64 t = (b & c) | ((~b) & d);
	return t;
}
unsigned __int64 func2(unsigned __int64 b, unsigned __int64 c, unsigned __int64 d){
	//b xor c xor d
	unsigned __int64 t=  b^c^d;
	return t;
}
unsigned __int64 func3(unsigned __int64 b, unsigned __int64 c, unsigned __int64 d){
	//(b and c) or (b and d) or (c and d)
	return (b & c) | (b & d) | (c & d);
	
	
}
std::uint32_t rotl(unsigned __int64 v, unsigned __int64 shift) {
	std::int32_t s = shift >= 0 ? shift % 32 : -((-shift) % 32);
	return (v << s) | (v >> (32 - s));
}
std::string to_hex(unsigned __int64 to_convert){
	std::string result;
	std::stringstream ss;
	ss << std::hex << to_convert;
	ss >> result;
	return result;
}
void main(){
    unsigned __int64 h0 = 0x67452301;
	unsigned __int64 h1 = 0xEFCDAB89;
	unsigned __int64 h2 = 0x98BADCFE;
	unsigned __int64 h3 = 0x10325476;
	unsigned __int64 h4 = 0xC3D2E1F0;
	unsigned __int64 A = h0;
	unsigned __int64 B = h1;
	unsigned __int64 C = h2;
	unsigned __int64 D = h3;
	unsigned __int64 E = h4;
	std::vector <Chunk_struct*> Chunks;
	std::string word_;
	std::cout << "Enter word:" << std::endl;
	//std::cin >> word_;
	word_ = "A Test";
	std::string bin_word_;
	for (int i = 0; i < word_.length(); i++){
		char_to_bin(word_.at(i), bin_word_);
	}
	bin_word_.append("1");
	while (bin_word_.length() % FOT != FFE){
		int gd = bin_word_.length() % FOT;
		bin_word_.append("0");
	}	
	sf_length_rep(word_.length() * BIT_OF_BYTES,bin_word_);
	// ok until here
	Chunk_struct *chunk_obj_ = nullptr;
	if (bin_word_.length() > FOT){
		//finish for more than 512
		while (1){
			chunk_obj_ = new Chunk_struct;
			for (int i = 0; i < FOT; i++){
				chunk_obj_->string_chunk_.push_back(bin_word_.at(i));
				bin_word_.erase(0, 0);
			}
			Chunks.push_back(chunk_obj_);
			if (bin_word_.length() <= 0){
				break;
			}
		}
	}
	else if (bin_word_.length() == FOT){
		chunk_obj_ = new Chunk_struct;
		chunk_obj_->string_chunk_ = bin_word_;
		Chunks.push_back(chunk_obj_);
		bin_word_.clear();
	}
	for (int i = 0; i < Chunks.size(); i++){
		for (int k = 0; k < FOT;){
			std::string *temp_ = new std::string;
			for (int j = 0; j < 32; j++,k++){
				temp_->push_back(Chunks.at(i)->string_chunk_.at(k));
				//Chunks.at(i)->string_chunk_.erase(0, 1);
			}
			Chunks.at(i)->Chunk_words.push_back(temp_);
		}
	}
	for (int i = 0; i < Chunks.size(); i++){
		int Chunk_init_size = Chunks.at(i)->Chunk_words.size();
		std::string *temp_ = NULL;
		for (int k = Chunk_init_size; k < 80; k++){
			temp_ = new std::string;
			*temp_ = xor_LCS_func(Chunks.at(i)->Chunk_words.at(k - 3)->c_str(), Chunks.at(i)->Chunk_words.at(k - 8)->c_str(),
				Chunks.at(i)->Chunk_words.at(k - 14)->c_str(), Chunks.at(i)->Chunk_words.at(k - 16)->c_str());
			Chunks.at(i)->Chunk_words.push_back(temp_);
			
		}
	}
// till this moment i checked everything works ok
	unsigned __int64 f = 0;
	unsigned __int64 k = 0;
	unsigned __int64 temp__ = 0;
	char *pEnd;
	for (int i = 0; i < Chunks.size(); i++){
		for (int j = 0; j < Chunks.at(i)->Chunk_words.size(); j++){
			if (j>=0 && j <= 19){
				f = (B & C) | ((~B) & D);//func1(B,C,D);
				k = 0x5A827999;
			}
			else if (j>=20 && j <= 39){
				f = B^C^D;//func2(B, C, D);
				k = 0x6ED9EBA1;
			}
			else if (j>=40 && j <= 59){
				f = (B & C) | (B & D) | (C & D);//func3(B, C, D);
				k = 0x8F1BBCDC;
			}
			else if (j>=60 && j <= 79){
				f = B^C^D;
				k = 0xCA62C1D6;
			}
			temp__ = rotl(A, 5)+ f + E + k + strtol(Chunks.at(i)->Chunk_words.at(j)->c_str(), &pEnd, 2);
			E = D;
			D = C;
			C = rotl(B, 30);
			B = A;
			A = temp__;
		}
	}
	h0 = h0 + A;
	h1 = h1 + B;
	h2 = h2 + C;
	h3 = h3 + D;
	h4 = h4 + E;
	std::string hash_result;
	hash_result.append(to_hex(h0));
	hash_result.append(to_hex(h1));
	hash_result.append(to_hex(h2));
	hash_result.append(to_hex(h3));
	hash_result.append(to_hex(h4));
	std::cout <<"SHA-1: "<< hash_result.size() << std::endl;

}

? Offline

Hi! Lets start from top:

void reverse_string(std::string &temp_string)

You don't need that, use std::reverse instead.

? Offline

Another thing: if this isn't only for education and fun, maybe use something from the public domain, e.g. https://github.com/vog/sha1.

mandruk1331

@Wieland it's more for education. Want to learn some cryptography, network stuff and Qt

jsulm

@mandruk1331 Why don't you just use http://doc.qt.io/qt-5/qcryptographichash.html ?

mandruk1331

@jsulm because I want to learn how the alg. works, therefore I'm writing the alg. myself. I have tested the code but it gives me the wrong hash for the message, and I don't know where the problem is. When I enter the first if ( if (i>=0 && i<=20)) it gives me the rights result, but after the result is incorrect I checked everything and can't find the error.

jsulm

@mandruk1331 Your question isn't related to Qt, but maybe we have cryptographic experts here.

hskoglund

Hi, code looks ok, except for the 64-bit uints used in the calculations, according to Wikipedia:
...
Note 1: All variables are unsigned 32-bit quantities ...
...

Try changing the var declarations, like this:

void main(){
uint32_t h0 = 0x67452301;
    uint32_t h1 = 0xEFCDAB89;
    uint32_t h2 = 0x98BADCFE;
    uint32_t h3 = 0x10325476;
    uint32_t h4 = 0xC3D2E1F0;
    uint32_t A = h0; 
    uint32_t B = h1;
    uint32_t C = h2;
    uint32_t D = h3;
    uint32_t E = h4;

and

...
// till this moment i checked everything works ok
    uint32_t f = 0;
    uint32_t k = 0;
    uint32_t temp__ = 0;
...

hskoglund

@mandruk1331 I just tested your code (with the 64-bit to 32 bit changes I wrote about above) and it works fine on the Ubuntu GCC and MacOS Clang compilers, but fails in Visual Studio, I'm guessing because of the rotl rand rotr function still being 64-bit flavored.

mandruk1331

@hskoglund thanks for the tips. I will change the code.

hskoglund

@mandruk1331 Forgot to mention, correct hash_result is 8f0c0855915633e4a7de19468b3874c8901df043
(so you know when it's working :-)

mandruk1331

@hskoglund I have checked the result using the online SHA-1. But thanks :-). I changed the types but it didn't do the trick, I also changed the strtol to stoi, and now the program crashes, in this case it's a good thing, because I now have a place to investigate.

hskoglund

@mandruk1331 If you're using Visual Studio that could explain why you get the wrong hash_result. Try on a Mac or on Ubuntu as I did, and you'll get the correct result.

mandruk1331

@hskoglund I will try that, but It would be also great if the program gave the correct result in VS

hskoglund

@mandruk1331 Couldn't resist testing in Visual Studio and I put in trace output of temp__ after the
temp__ = rotl(A, 5)+ f + E + k + strtol(Chunks.at(i)->Chunk_words.at(j)->c_str(), &pEnd, 2); line,
and it agrees with Ubuntu on the first 16 iterations (of the 80) then it goes south in Visual Studio. Interesting...

mandruk1331

@hskoglund interesting... I checked the whole table of chunk_words and the numbers are correct. I followed the instruction on wikipedia and also found this site which describes how SHA-1 works in a good way: http://www.metamorphosite.com/one-way-hash-encryption-sha1-data-software

hskoglund

@mandruk1331 Found it! It's the strtol() function that behaves differently, in clang and g++ it returns more than 32 bits, but not in Visual Studio. The solution is to use strtoll()(it also works in Ubuntu).

So, change your call from strtol() to strtoll() and you should be good to go, like this:

temp__ = rotl(A, 5)+ f + E + k + strtoll(Chunks.at(i)->Chunk_words.at(j)->c_str(), &pEnd, 2);

mandruk1331

@hskoglund Wow! It works I am so thankful. I'd be looking for this issue probably a week.