Libnids的哈希函数

た入场券 2022-08-07 14:43 134阅读 0赞

关于hash函数基本知识，参考文章[hash函数的基本知识][hash]

# hash函数源码 #

//hash.c
    #include <sys/types.h>
    #include <sys/time.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <fcntl.h>
    #include <unistd.h>
    
    static u_char xor[12];
    static u_char perm[12];
    static void getrnd ()
    {
    	struct timeval s;
    	u_int *ptr;
    	//从如下的文件中读取随机数流
    	int fd = open ("/dev/urandom", O_RDONLY);
    	if (fd > 0)
    	{
    		read (fd, xor, 12);
    		read (fd, perm, 12);
    		close (fd);
    		return;
    	}
    
    	//如果从"/dev/urandom"中读取到了随机数函数就返回了，那么以下不会执行
    	gettimeofday (&s, 0);
    	srand (s.tv_usec);
    	ptr = (u_int *) xor;
    	*ptr = rand ();
    	*(ptr + 1) = rand ();
    	*(ptr + 2) = rand ();
    	ptr = (u_int *) perm;
    	*ptr = rand ();
    	*(ptr + 1) = rand ();
    	*(ptr + 2) = rand ();
    }
    
    //将perm数组的各个元素分别转化为0-11之间的整数，之后会在mkhash函数中使用到
    //xor数组的各个元素都是char型，元素值是0和255之间的随机数
    void init_hash ()
    {
    	int i, n, j;
    	int p[12];
    	getrnd ();
    	for (i = 0; i < 12; i++)
    		p[i] = i;
    	for (i = 0; i < 12; i++)
    	{
    		n = perm[i] % (12 - i);
    		perm[i] = p[n];
    		for (j = 0; j < 11 - n; j++)
    			p[n + j] = p[n + j + 1];
    	}
    }
    
    u_int mkhash (u_int src, u_short sport, u_int dest, u_short dport)
    {
    	u_int res = 0;
    	int i;
    	u_char data[12];
    	//将代表源/目的地址及端口的整数依次存入一个12个元素的u_char类型的数组中
    	u_int *stupid_strict_aliasing_warnings=(u_int*)data;
    	*stupid_strict_aliasing_warnings = src;
    	*(u_int *) (data + 4) = dest;
    	*(u_short *) (data + 8) = sport;
    	*(u_short *) (data + 10) = dport;
    	//perm[]在init_hash函数中其元素分别随机存储了0-11之间的数
    	//0-11之间的数分别保存在了该数组中，只是在数组中位置随机
    	//所以，data[perm[i]]是随机取出data的某个元素再与xor[i]随机数
    	//进行异或操作，res每次右移八位，所以res最终结果是res迭代的和
    	//然后将结果与大的素数16715791(0xff100f)取余，作为hash后的值
    	for (i = 0; i < 12; i++)
    		res = ( (res << 8) + (data[perm[i]] ^ xor[i])) % 0xff100f;
    	return res;
    }

# getrnd()函数 #

参考文章 [ /dev/random和/dev/urandom的一点备忘  
][_dev_random_dev_urandom_]

在getrnd函数中从文件“/dev/urandom"读取随机数流。

内核实现了一个功能强大的随机数产生器，从理论上讲它能产生真随机数，**随机数产生器从设备驱动收集环境噪音放入熵池，内核或用户空间进程都可以访问熵池，熵池中的数据不但是随机的，而且对于外部攻击者来说是非确定的，这些随机数可以用与各种程序中，尤其是加密程序**。

我们知道在C库中也有随机数产生函数，但是它产生的是 **伪随机数，因为它是由可确定的函数产生的**，虽然产生的这些数看似是随机的，但是它们并非统计意义上的随机数。而 **内核中的随机数产生函数确是非确定性的**。我们在使用计算机时，我们对键盘的操作是随机的，包括输入的字符，或者是连续两次敲击键盘的间隔时间，鼠标的位置也是随机的，鼠标的移动速度是随机的。或者是磁盘IO的请求响应时间。随机数产生函数把这些噪音放入到熵池中，访问熵池时，内核会计算熵池的SHA哈希值，SHA是一种信息摘要算法，它由一个可变长的输入，转换为一个固定长度的哈希值，输出不唯一，且不可逆向转化。

/dev/random和/dev/urandom是Linux系统中提供的随机伪设备，这两个设备的任务是**提供永不为空的随机字节数据流**。很多解密程序与安全应用程序（如SSH Keys,SSL Keys等）需要它们提供的随机数据流。  
　　这两个设备的差异在于：/dev/random的random pool依赖于系统中断，因此在系统的中断数不足时，/dev/random设备会一直封锁，尝试读取的进程就会进入等待状态，直到系统的中断数充分够用, **/dev/random设备可以保证数据的随机性**。**/dev/urandom不依赖系统的中断**，也就不会造成进程忙等待，**但是数据的随机性也不高**。

由于文件产生的是二进制的随机数流，无法直接通过cat命令查看，通过od -x命令将其转换为十六进制内容，分别查看这两个文件，可以看到random生成数据很慢、urandom生成随机数很快。

![Center][]

# init\_hash()函数 #

该函数的目的：将perm数组的各个元素转化为0-11之间的整数，之后会在mkhash函数中使用到。该函数产生0到11之间互不相同的随机数，文章 [生成k个小于n的互不相同的随机数][k_n]中有另外一种产生的方法。  
在该函数执行后输出perm数组和xor数组的元素值：

//test.c
    int main() {
      getrnd ();
      init_hash();
      
      int i;
      printf("perm[]: ");
      for (i = 0; i < 12; ++i)
         printf("%d ", perm[i]);
      printf("\n");
    
      printf("xor[]: ");
      for (i = 0; i < 12; ++i)
         printf("%d ", xor[i]);
      printf("\n\n");
    }

如下是几次输出的结果：从图中可以看出，每次perm输出的都是0-11之间的数字，但每次输出的顺序都不相同；xor数组输出的是0-255之间的随机数。

![SouthEast][]

# mkhash()函数 #

如下是hash三组源/目的IP地址和端口的结果：

//test.c
    int main() {
      getrnd ();
      init_hash();
      /*
      int i;
      printf("perm[]: ");
      for (i = 0; i < 12; ++i)
         printf("%d ", perm[i]);
      printf("\n");
    
      printf("xor[]: ");
      for (i = 0; i < 12; ++i)
         printf("%d ", xor[i]);
      printf("\n\n");
      */
      printf("%d\n",mkhash(inet_addr("0.0.0.0"),0,inet_addr("0.0.0.0"),0));
      printf("%d\n",mkhash(inet_addr("255.255.255.255"),
                       1111,inet_addr("255.255.255.255"),9999));
      printf("%d\n",mkhash(inet_addr("255.211.21.1"),
                       80,inet_addr("255.137.225.121"),23));
    
    }

![Center 1][]

[hash]: http://blog.csdn.net/u013074465/article/details/45059639
[_dev_random_dev_urandom_]: http://blog.csdn.net/ohmygirl/article/details/40385083
[Center]: /images/20220805/f5c1fd1de0d54a9a9d09b7731851ee7b.png
[k_n]: http://blog.csdn.net/u013074465/article/details/46519799
[SouthEast]: /images/20220805/65cc0dae0edd42febf1d3ffdaf7c27ba.png
[Center 1]: /images/20220805/6a189e5988434eee8a6921e3319e8180.png