首页
社区
课程
招聘
[原创]对api 名字 hash的一点理解
发表于: 2008-12-24 11:26 10412

[原创]对api 名字 hash的一点理解

2008-12-24 11:26
10412

Hash windows api method
为了控制shellcode 大小,总将api的名字用一个算法求得对应的一个Dword数(32位)
2的 32次方 可以表达4 294 967 296种可能。
网络常用的一个hash算法的c语言实现如下
#include <windows.h>
#include <stdio.h>
DWORD GetHash(char *fun_name)
{
DWORD digest=0;
while(*fun_name)
{
   digest=((digest<<25)|(digest>>7));
   digest+=*fun_name;
   fun_name++;
}
return digest;
}
void main()
{
DWORD hash;
hash=GetHash("MessageBoxA");
printf("result of hash is %.8x\n",hash);
}
基本算法就是 h=h<<25 | h>>7 +*fun_name

用汇编语言实现                                                       
xor edx,edx                                ;ebx equals zero
mov esi,offset funcname                        ;get the start of api name string
1oop:
Movsz eax,byte prt[esi]                        ;get one byte from name string to eax
cmp al,ah                                               ;if we get zero then Exit
jz Exit
ror   edx ,07h                                ;this statement equals digest=((digest<<25)|(digest>>7));
add edx,eax                                ; this statement equals digest+=*fun_name;
add esi,1                                ; ask esi to point to the next byte
jmp 1oop
Exit:

一时间没有想明白ror   edx ,07h 为什么等于digest=((digest<<25)|(digest>>7))
好笨,昨天画了画明白了~
假如有这样一来一个32位二进制数
执行完digest<<25后把右边的7位移动到左边,然后右边七位补25个0
执行完digest>>7后把左边25位移动到右边,然后左边7位补0
把两个数或运算后 正好跟循环右移7位是相等的.


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 7
支持
分享
最新回复 (20)
雪    币: 2056
活跃值: (13)
能力值: ( LV13,RANK:250 )
在线值:
发帖
回帖
粉丝
2
把这个数重新异或后 正好跟循环右移7位是相等的.

应该是

digest<<25:把最低7位变成高位。
digest>>7:右移7位是为了保留原来的最高7位。
2008-12-24 12:07
0
雪    币: 104
活跃值: (72)
能力值: ( LV2,RANK:15 )
在线值:
发帖
回帖
粉丝
3
改过来了~  谢谢大牛~
2008-12-24 14:31
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
谢谢,我也在这儿有点儿困惑!
2009-4-14 20:08
0
雪    币: 1708
活跃值: (586)
能力值: ( LV15,RANK:670 )
在线值:
发帖
回帖
粉丝
5
tag : api hash
2009-4-14 20:13
0
雪    币: 517
活跃值: (35)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
6
如果真用汇编,何必要这么做?
2009-4-14 20:56
0
雪    币: 315
活跃值: (23)
能力值: ( LV9,RANK:220 )
在线值:
发帖
回帖
粉丝
7
to 楼上:
因为高级语言没有提供rol ror这样的循环移位操作符。

所以如需
rol dest, n , 需[shl dest, n] or [shr dest, 32 - n]
2009-4-14 21:51
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
8
LS怎么总是这么执着高级语言不行??
我觉得应该是你对c语言不够了解吧

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

ULONG GetHash(char *fun_name)
{
	ULONG digest = 0;
	while (*fun_name)
	{
	   digest = _lrotl (digest, 7);
	   digest += *fun_name;
	   fun_name ++;
	}
	return digest;
}

void main()
{
	ULONG hash;
	hash = GetHash("MessageBoxA");
	printf ("result of hash is %.8x\n", hash);
	getchar ();
	return ;
}


上面代码在VC6里面release /MT编译后的结果:

00401000   /$  8B5424 04           mov     edx, dword ptr [esp+4]
00401004   |.  33C0                xor     eax, eax
00401006   |.  8A0A                mov     cl, byte ptr [edx]
00401008   |.  84C9                test    cl, cl
0040100A   |.  74 10               je      short TestRol.0040101C
0040100C   |>  0FBEC9              /movsx   ecx, cl
0040100F   |.  C1C0 07             |rol     eax, 7                         ;  注意这行是编译出来的,不是内联汇编
00401012   |.  03C1                |add     eax, ecx
00401014   |.  8A4A 01             |mov     cl, byte ptr [edx+1]
00401017   |.  42                  |inc     edx
00401018   |.  84C9                |test    cl, cl
0040101A   |.^ 75 F0               \jnz     short TestRol.0040100C
0040101C   \>  C3                  retn
0040101D       90                  nop
0040101E       90                  nop
0040101F       90                  nop
00401020   /$  68 48704000         push    TestRol.00407048                ;  ASCII "MessageBoxA"
00401025   |.  E8 D6FFFFFF         call    TestRol.00401000
0040102A   |.  50                  push    eax
0040102B   |.  68 30704000         push    TestRol.00407030                ;  ASCII "result of hash is %.8x",LF
00401030   |.  E8 BD010000         call    TestRol.004011F2
00401035   |.  A1 5C704000         mov     eax, dword ptr [40705C]
0040103A   |.  83C4 0C             add     esp, 0C
0040103D   |.  48                  dec     eax
0040103E   |.  A3 5C704000         mov     dword ptr [40705C], eax
00401043   |.  78 07               js      short TestRol.0040104C
00401045   |.  FF05 58704000       inc     dword ptr [407058]              ;  
0040104B   |.  C3                  retn
0040104C   |>  68 58704000         push    TestRol.00407058
00401051   |.  E8 0A000000         call    TestRol.00401060
00401056   |.  59                  pop     ecx
00401057   \.  C3                  retn
2009-4-15 00:23
0
雪    币: 4396
活跃值: (4383)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
膜拜风月
2009-4-15 00:55
0
雪    币: 325
活跃值: (97)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
10
我只是进来膜拜名字的。
2009-4-15 02:03
0
雪    币: 204
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
我认为海风那个代码的优化是VC6做了手脚的,当判断出是调用那个函数的时候,直接用汇编指令代替。原因有三个,如下:

1.看编译器安装目录中库文件代码中的rotl.c,我同样用VC6试验了,同样的函数无论如何优化总是不能只得到一条汇编指令。
/***
*unsigned _rotl(val, shift) - int rotate left
*
*Purpose:
*       Performs a rotate left on an unsigned integer.
*
*       [Note:  The _lrotl entry is based on the assumption
*       that sizeof(int) == sizeof(long).]
*Entry:
*       unsigned val:   value to rotate
*       int    shift:   number of bits to shift by
*
*Exit:
*       returns rotated value
*
*Exceptions:
*       None.
*
*******************************************************************************/

unsigned long __cdecl _lrotl (
        unsigned long val,
        int shift
        )
{
        return( (unsigned long) _rotl((unsigned) val, shift) );
}

unsigned __cdecl _rotl (
        unsigned val,
        int shift
        )
{
        register unsigned hibit;        /* non-zero means hi bit set */
        register unsigned num = val;    /* number to rotate */

        shift &= 0x1f;                  /* modulo 32 -- this will also make
                                           negative shifts work */

        while (shift--) {
                hibit = num & 0x80000000;  /* get high bit */
                num <<= 1;              /* shift left one bit */
                if (hibit)
                        num |= 1;       /* set lo bit if hi bit was set */
        }

        return num;
}

2.海风的代码在编译之后,查看obj文件的时候代码里面就出现了那条汇编指令。针对一般的库函数没有这种搞法的,都是需要再连接一下。

3.这个更有意思,就算在c文件中只想声明一个名叫_rotl的函数都不行,编译的时候提示
error C2169: '_rotl' : intrinsic function, cannot be defined

这里可以看出那是VC优化手段中的一种。
我凑凑热闹,不好意思,跑题了。。。
2009-4-15 10:58
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
12
楼上说得太玄乎了

把我上面的代码copy到rol.c里面,然后拖进VC6,直接编译,选release,生成一下,代码就会出现rol eax,7

至于你说的rotl.c,我在VC6里面没找到这个源码,VS2005里面才有,但是VS2005也可以编译出这个指令

用VS2005编译上面那个rol.c,命令行

cl rol.c /O2

然后看代码,你会发现同样也有rol eax,7

=====================华丽的分割线=====================================

我贴出来,只是想说VC可以编译成这个样子,这个指令并不是汇编独有的
2009-4-15 11:50
0
雪    币: 204
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
我完全没有否认你的意思,我用VC6编译了你的代码,结果和你的一样,会出现那条指令的!我只是由此说明了一下这是VC的一种优化手段。呵呵,至于那个文件嘛,VC6在安装时默认是不会安装那些文件的,便于调试,我将那些文件从安装包里面拷贝进去了。安装包里面VC98\CRT下面就是的。

我贴出来是想说,VC6之所以编译成这个样子,是由于那个函数完全可以用一条汇编编译器指令指令来实现,结果编译的时候检查_lrotl()函数是否是被调用了,如果是被调用了,编译器会破例把这个函数直接用一条汇编指令实现之。
2009-4-15 11:57
0
雪    币: 7309
活跃值: (3788)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
14
学         习
2009-4-15 12:27
0
雪    币: 1233
活跃值: (907)
能力值: ( LV12,RANK:750 )
在线值:
发帖
回帖
粉丝
15
google 杂凑函数 linux字符串hash算法
将一个大集合通过杂凑函数的索引到一个ID范围,不知道理解可对
2009-4-15 12:40
0
雪    币: 622
活跃值: (65)
能力值: ( LV13,RANK:290 )
在线值:
发帖
回帖
粉丝
16
来膜拜海风的
2009-4-15 12:41
0
雪    币: 101
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
用楼猪的代码 digest=((digest<<25)|(digest>>7));在GCC下直接就rol了。
如果C语言(编译器)这点事情都干不了的话,那嵌入式那帮哥们还怎么混。。。。。岂不是效率低下至死。。。。
是吧。
2009-4-15 12:42
0
雪    币: 204
活跃值: (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
海风太谦虚了!仅从C上讲,你就比我高出近一个数量级了。
2009-4-15 12:55
0
雪    币: 2110
活跃值: (21)
能力值: (RANK:260 )
在线值:
发帖
回帖
粉丝
19
有一种函数,叫intrisics function,它是编译器(compiler)提供的,而不是库(library)提供的。

比如此例中的_rotl,再比如memcpy。比如这里有一篇文章,对memcpy进行了分析:

http://blog.codingnow.com/2005/10/vc_memcpy.html

虽然PC平台的编译器,这种函数不常见,但也是存在的,只是不同的编译器实现方式不同。

在嵌入式编译器中,intrinsics function是相当常见的。打开iar embbedded workbench的头文件,随处可见intrisics修饰的函数,最典型的就是__disable_interrupt()。
2009-4-15 15:03
0
雪    币: 622
活跃值: (65)
能力值: ( LV13,RANK:290 )
在线值:
发帖
回帖
粉丝
20
msvcrt.dll导出了memcpy,_rotl。
2009-4-16 22:59
0
雪    币: 2110
活跃值: (21)
能力值: (RANK:260 )
在线值:
发帖
回帖
粉丝
21
它当然导出了。

intrisic fuction由编译器决定如何生成代码,如果能够优化,它就会用经过优化的代码来实现,如果编译器无法决定是否能够进行优化,它就会生成一条对库函数的CALL指令的。
2009-4-19 00:53
0
游客
登录 | 注册 方可回帖
返回
//