2022-12-07 -> by:DebugST

密码碰撞可以有多非主流?

在日常的渗透过程中难为会遇到要破解密码的时候,比如MD5,通常我们可能会在一些网站上先检索一番,如果没有结果的话可能我们就会拿出神器Hashcat碰撞。

一提到Hashcat大家的第一反应就是。。。快。。。那么它为什么会这么快呢???🤔🤔🤔🤔🤔

所以说到这里你会不会以为作者今天是想要去分析Hashcat的原理或代码?。。不不不。。今天作者要玩一次非主流。

警告:此文会很长。且此文将以MD5的碰撞作为案例。仅提供思路Demo。并没有现成的工具,作者也并不打算编写成工具,难道Hashcat它不香吗?

项目(OpenGLForHash)地址: GitHub Gitee

起因

因为一些机缘巧合,作者接触到了OpenGL,并且心血来潮的作者做了一个烂尾工程STGL

一个作者自己移植的.Net版本的OpenGL封装。之所以说是烂尾工程是因为作者从移植完毕后就没再动过这个项目了,教程也只写了一个章节:教程

作者在学习OpenGL的过程中,当编写第一个Shader(着色器)的时候就开始有点想入非非了。。为什么?。。Shader程序是运行在GPU上的代码片段。那时候作者就在想,既然可以编写运行在GPU上的代码,那么是不是可以干点别的?不过当时只是埋下了一个种子,并没有多想。

随着后来学习的深入,不仅对OpenGL了解越来越多。对显卡的工作原理也开始渐渐清晰,直到有一天作者挺好奇的跨越了一些学习步骤。直接从Blender导出了一个3D模型的obj文件。然后自己解析,并将数据送给OpenGL的接口的时候。作者震惊了,虽说不是多大的模型,几万个顶点,以线框模式绘制,并且不停的旋转。几十帧的帧率。。电脑风扇都不带转的。这是作者以前在使用GDI想都不敢想的事情。那个时候作者就慢慢开始思考关于并行运算的问题。

作为网络安全的打工仔,很自然的就联想到利用GPU碰撞密码这种事情,也很自然的就想到了Hashcat,并且思考Hashcat是如何实现的。不过作者并没有第一时间去看Hashcat的源码。而是在思考以当前的思考角度出发,自己能不能做一个Hashcat。然后脑洞打开的时候就到了。

OpenGL简介

在还没有接触到OpenGL之前,作者一直以为OpenGL是一个SDK需要安装各种东西,然后才可以进行相关的开发。事实上并非如此。基本上现在大多数的电脑都可以直接运行OpenGL程序。

OpenGL并不是一个SDK而是一个API规范,由khronos组织所维护的一套编程接口标准。它们规定了一些3D实时渲染所需要的基本函数的名称以及需要的参数和输出值。至于功能怎么实现。。。这个是硬件的事情了是吧?也就是显卡而不关khronos什么事情。就好比定义HTTP协议规范的人,他们不可能要自己去做一个浏览器吧?

如果一个显卡生产厂商愿意去支持OpenGL的规范,那么他们就会去实现那些API接口,然后将这些实现好的接口伴随着驱动程序一起安装在系统中。而基本显卡厂商都愿意去实现这些API,不然都不好意思说自己的显卡有多牛逼,所以基本上每个系统中都天然拥有OpenGL的运行环境。不会吧?不会你的电脑上连显卡驱动都没装吧?

至于如何调用OpenGL这是属于另一个问题了。这里不做过多的描述,有兴趣的同学可以看看这里:传送门

如果你是windows系统的话,我猜在你的系统目录下肯定有一个opengl32.dll🤫🤫🤫🤫🤫并且从Win98时代开始他就一直存在,且没有更新过😂😂😂。

微软:我巴不得弄死它。。当我的DirectX不存在?。。要不是弄不死它并且为了实现规范。。你以为我会放个opengl32.dll在那里???

图形渲染管线

也不知道有没有写代码的小伙伴接触过图形相关的函数,比如windows上的GDI。这类图形库基本都有提供类似于DrawXXX之类的函数。比如绘制一个矩形可能会有这样一个函数:

void DrawRectangle(/*other params,*/ float x,float y,float width,float height);

当然可能还有DrawLineDrawBezier之类的函数,但是这些函数或许可以满足一些规则几何图形的绘制,对于不规则的几何图像可能会提供一个类似于这样的函数:

void DrawPath(/*other params,*/ Point[] pts)

对于规则的我们可能直接就把坐标传入给函数,对于不规则的则是直接传入一组坐标,因为任何图形都可以被拆解成很多条线段组成。这是在平面绘图的情况下,但是OpenGL是一个三维的接口。当然三维的世界中也有很多规则物体,但是更多的是不规则物体,所以在OpenGL的接口中并没有设计类似于DrawCube之类的函数,而是直接采用通用方案,接收顶点。那么一个三维图形是如何本渲染出来到显示器上的画面的?

上面就是一个OpenGL的渲染流程,一个显卡的工程流程也差不多就是如此。其中vertex data就是要送入显卡的数据,比如三维模型的坐标顶点。比如我们希望在三维空间中绘制一个三角形可能就会送入如下数据。

float[] vertices = {
    -0.5f, -0.5f, 0.0f, // 第一个顶点
     0.5f, -0.5f, 0.0f, // 第二个顶点
     0.0f,  0.5f, 0.0f  // 第三个顶点
};
/* 这里采用的是归一化空间中标(右手坐标系)
 * OpenGL的归一化空间是一个2*2*2的立方体中心是原点坐标。立方体正面和UI界面形成映射关系。
 * 关于归一化空间,这里不做过多介绍。理解为UI窗口左上角是(-1,1,1)右下角是(1,-1,1)就行了。
 */

然后将他送入到显存中,然后紧接着顶点着色器会率先处理这些顶点坐标,直到最终画面在显示器上呈现。可以看到上图大概有6个步骤,其中蓝色部分是需要编写着色器代码的。而对于OpenGL而言顶点着色器片段着色器是必须的,没有默认处理方式。(当然在老版本的OpenGL接口中是没有渲染管线的,在3.2版本的接口以前是立即渲染模式这里不做过多介绍)

着色器

顶点着色器(Vertex Shader)是对传入的verte data做预处理,比如传入了一个三维模型的数据进去(以上面的vertices为例),想将模型向上移动一个单位你认为应该怎么做?

你会不会认为修改vertices的数据后然后重新传入显存?。。比如:

for(int i = 0;i < vertices.Length;i+=3){
    vertices[i + 1] += 1; // y坐标
}

是的,其实这样做也没毛病,但是如果vertices不止3个顶点而是3W个顶点呢?并且不是只向上移动一个单位,而是以每秒一个单位的速度往上移动并且每秒24帧呢?那么上面的代码需要每秒执行24次并且每次Y坐标增加1/24,我猜按照上面的代码去处理的话,估计CPU距离100%已经不远了。

但是你有没有想过其实上面的每个顶点都是独立的,将第一个顶点的Y坐标加上n并不影响第二个顶点的Y加上n后的结果,也就是说它们的计算过程都是独立的并不依赖先前的计算。也就是说,即便3W个顶点同时计算Y加上n也没有任何问题。而这正是顶点着色器的作用。所以在一些游戏开发中,传入显存的数据都是模型的基本数据,至于游戏中物体的移动全在顶点着色器中完成。顶点着色器是并行运算的且由GPU执行,每个顶点都会被分配到一个顶点着色器代码片段中,而上面的代码则是在CPU中执行。至于CPUGPU的区别这里就不介绍了。

顶点着色器处理完一个顶点就会继续往下传递,接下来的图元装配几何着色器这里就不做介绍了。接下来就是栅格化的过程,也就是说生成二维的像素点。毕竟显示器上显示的画面终究还是二维的,可以看到渲染管线图中传入的是一个三角形的顶点,到了栅格化后,显卡补差生成了很多像素点。最后这些像素点会传递给片段着色器

片段着色器(Fragment Shader)是一个很重要的过程,如果说栅格化是生成了像素点,那么片段着色器就是为像素点上色的过程,而这直接决定了最后显示效果的质量,这就是为么有些游戏画面看起来很真实,而有些画面惨不忍睹。如何上色这个过程是需要通过自己写算法去完成的,比如光影追踪什么的。当然片段着色器也是运行在GPU之上的。

到了最后就是测试与混合,比如三维场景中会有很多元素,哪些元素在前哪些在后,或者说哪些是带有Alpha通道的。处理完这些,一帧二维图像就渲染完成了。

你好三角形

可能读到这里你会不会认为已经跑题了?不是说跑碰撞密码的吗?怎么扯上三维图像的渲染了?没错。。。作者就是想利用上面这一套机制去碰撞密码。所以必须对OpenGL做一些基本的介绍,并且接下来还有用一个完整案例做一个三角形的渲染,就像刚开始写代码一样我们会写一个Hello World,我们会先写一个Hello Triangle来做一个完整流程,再继续替换里面的代码,最终完成MD5的碰撞。

接下来的代码将采用STGL为基础进行编写,当然首先我们需要创建一个窗口,因为我们需要绑定OpenGLContext。就好比在Windows中使用GDI需要一个HDC一样,至于如何绑定Context这里并不做介绍,只介绍关键代码。最终的Demo可以参考GitHub仓库,代码已经添加详细注释。

首先我们需要准备一组数据,就以上面的vertices为例,然后我们需要将它送入显存。在那之前我们需要现在显存中创建一个对象,一个VAO对象(Vertex Array Object)。

uint vao = GL.GenVertexArrays();    // 创建VAO,可理解为创建了一个模型对象
GL.BindVertexArray(vao);            // 将此对象绑定到当前操作的上下文

一个VAO可以理解为一个模型,就好比在三维建模软件中,我们需要先创建一个物体然后再进行编辑一样。再比如我们写代码前要先创建一个工程再打开编辑。

目前的VAO还是一个空白对象,什么都没有,就类似于一个空白工程。所以我们要给他绑定数据,而绑定数据需要用到VBO(Vertex Buffer Object)。

uint vbo = GL.GenBuffers();             // STGL对此函数进行了多个重载
GL.BindBuffer(GL.GL_ARRAY_BUFFER, vbo); // 将对象绑定到Context中 此buffer用于保存顶点数据

一个VBO可以理解为模型对象的真实数据,类似工程中的代码文件,保存在显存中,所以现在我们要做的就是将数据送入显存。

GL.BufferData(GL.GL_ARRAY_BUFFER, vertices, GL.GL_STATIC_DRAW);

vertices送入到当前的VBO,并且设置GL_STATIC_DRAW标志,表示此数据为静态数据,不会发生变化,OpenGL会根据此值决定以何种形式分配显存。可能细心的小伙伴会有疑问为什么这个函数不是下面这个样子的:

GL.BufferData(vbo, GL.GL_ARRAY_BUFFER, vertices, GL.GL_STATIC_DRAW);

这个需要去了解OpenGL的工作机制,OpenGL内部是一个超大的状态机,更多的说明可以参考作者的教程,可以理解为内存和显存之间是有数据传送的管道的,而管道上面有插槽,而上面一句BindBuffer的代码就是将vbo插到插槽上面去。而BufferData是直接在往插槽上面送数据。所以在OpenGL的原始函数中会看到很多glBindXXX之类的函数。

将数据送入显卡之后就完事了吗?不不不。并没有,我们只是送入了一堆数据到显存中去,OpenGL并不知道要如何读取这些数据,也就是说,如何结构化这些数据。虽然我们很清楚vertices是一个三角形的三个顶点,但是OpenGL并不知道。所以我们还要告诉OpenGL如何结构化我们刚才送入显存的数据。

GL.VertexAttribPointer(         // 指定一个数据处理的规则(针对当前绑定的vbo对象)
    0,                          // 设定一个通道编号 用于在Shader中进行关联
    3,                          // 每一次从vbo中获取3个数据
    GL.GL_FLOAT,                // 数据类型是float
    false,                      // 这个参数目前可以不用管 false就行了
    3 * sizeof(float),          // 下一次获取数据的时候偏移多少数据,也就是每一次取多少字节的数据。
    IntPtr.Zero                 // 第一次获取数据时候偏移多少 很奇怪这个为什么是IntPtr类型?作者也不知道。
    );
GL.EnableVertexAttribArray(0);  // 启用0号通道 下面会做说明

至此,CPU这边的工作基本已经准备完毕了。接下来就是GPU层面的准备了,上面说了对于OpenGL来说,顶点着色器片段着色器是必须的。需要自己编写代码,那么怎么编写代码?

OpenGL的着色器采用GLSL(GL Shader Language),它是一种类C风格的语言。那么我们要如何编写?是不是需要其他IDE???不不不。。OpenGL提供了类似编译器之类的东西。

下面就是顶点着色器片段着色器的代码。

//每一个顶点都会执行一次这个代码 且并行
private static string m_str_vertex_shader = @"
#version 330 core                       // 3.3 版本 使用核心模式

layout (location = 0) in vec3 dotPos;   // 还记得上面的0号通道吗?就是和这里做关联的。
                                        // dotPos就是从0号通道中获取出来的一个3维向量。
void main(){
    gl_Position = vec4(dotPos, 1.0);    // 我们先将3维坐标变成4维。
    // gl_Position是一个内置变量,作为顶点着色器的输出值。也就是预处理后的新顶点。
    // 除了将三维补成四维之外不做任何处理继续传递 这种用n+1维来表示n维的坐标叫做 齐次坐标
}";

//每一个像素点都会执行一次这个代码 且并行
private static string m_str_fragment_shader = @"
#version 330 core

out vec4 fragColor; // 最终需要输出的像素颜色

void main(){
    fragColor = vec4(1.0, 0.5, 0.2, 1.0); //(RGBA)写死 每个像素点的颜色都将是橙色
}";

var gp = GLProgram.Create(str_vertex_shader, str_fragment_shader);
gp.Use();           // 使用当前编译好的着色器 万一有多个可以切换使用

如果代码没有报错,那么gp就是编译好的着色器程序。当这一切准备好的时候就可以开始渲染了。

GL.ClearColor(.5f, .5f, .5f, 1f);           // 设置背景颜色
while (/*some code*/) {
    GL.Clear(GL.GL_COLOR_BUFFER_BIT);       // 每次渲染的时候擦除缓存
    // GL.BindVertexArray(vao);             // 绘制前绑定需要绘制的vao
    GL.DrawArrays(GL.GL_TRIANGLES, 0, 3);   // 以三角形方式绘制,一共3个顶点
    // swapbuffer                           // 交换缓冲器 双缓冲
    // other code
}

然后就可以看到窗口上的三角形了

或许你会问假如你想绘制一个四边形是不是传四个顶点进去,然后在结构化VBO的时候让他每次取四个数据就好了?然后GL.DrawArrays里面的标志换成四边形的?。。不不不。。上面我们仅仅是刚好想绘制一个三角形,而刚好确实也有GL_TRIANGLES这个常量值。巧合巧合。。要知道在OpenGL中可是一个三维的世界,所以不能用平面绘图的思维去思考问题。如果你想要绘制一个四边形那么你需要两个三角形。什么意思???众所周知构成平面的最低要求就是3个顶点,也就是三角形。只要三角形足够多,那么那就可以组合成任意三维模型,比如下面的图:

所以上面我们绘制的三角形可能仅仅是某个三维模型的一小块皮,所以vertices里面的三角形顶点足够多,那么就可以绘制出任何你想要的形状。比如一个四边形得用下面的数据:

float[] vertices = {
    -0.5f, -0.5f, 0.0f, // 第一个顶点
     0.5f, -0.5f, 0.0f, // 第二个顶点
    -0.5f,  0.5f, 0.0f, // 第三个顶点

    -0.5f,  0.5f, 0.0f, // 第一个顶点
     0.5f, -0.5f, 0.0f, // 第二个顶点
     0.5f,  0.5f, 0.0f  // 第三个顶点
};
//======================
GL.DrawArrays(
    GL.GL_TRIANGLES,
    0,
    6                       // 一共有6个顶点
    );

当然可以看到有两个重复的顶点,这种情况下还会引入EBO。不过这里不做介绍。而且真的是一个复杂的模型我们也不可能通过手动构造顶点,而是通过建模软件帮我们生成导出,并通过文件加载的形式解析出顶点数据,然后再送入显存。

思路分析

通过两个着色器代码我们可以知道,着色器是并行计算的,至于并发数,我们无需关心,由OpenGL或者说显卡自动去分配,着色器代码可以理解为一个函数,每一份数据都会调用它一次。我们的三角形传入的三个顶点会被分成3份数据然后同时调用顶点着色器处理,然后结果继续往下传递,然后被栅格化成了一堆的像素,然后这些像素也会同时去调用片段着色器。而GLSL是一个类C风格的语言,里面也可以编写函数什么的,那么,我们是否可以在着色器中编写计算hash的代码呢?毫无疑问是可以的。只是GLSL所支持的数据类型有限不过计算哈希已经足够了。

仔细想一想,刚才的vertices中我们传入了3个三角形的顶点,每一份顶点着色器会获取到一个顶点。在刚才的vertices我们传入的是float类型,如果我们使用的是uint类型,或者直接就是byte类型呢?因为我们在编程的时候所使用的数据类型是什么都无所谓,因为它仅仅是一堆数据被传入到显存中去。刚才上面所看到的GL.BufferData其实是STGL自己封装出来的一堆重载函数,他所对应的OpenGL原生C函数签名如下:

void glBufferData(GLenum target, GLsizeiptr size, const void * data, GLenum usage);

C/C++的角度去思考,其实glBufferData就相当于一个内存拷贝的函数,void*就可以知道它是无关数据类型的万能指针。真正决定这堆数据如何使用的是顶点着色器中的layout (location = n) in [TYPE] [NAME]GL.VertexAttribPointer所设定的数据宽度。

所以我们完全可以传入任何我们想传入的数据,通常情况下,一个密码都是8-16位,且我们以这个为例,假设密码字符都是ASCII字符的情况下。那么16字节足够了。那么我们在使用GL.VertexAttribPointer的时候设定成16字节就好了。而且16字节刚好是4个uint。那么我们可以这样写代码。

GL.VertexAttribPointer(
    0,                  // 依然使用0号通道
    4,                  // 每次获取4个数据
    GL.GL_FLOAT,        // 没错这里继续使用FLOAT类型,作者尝试过GL_UNSIGNED_INT了,得不到正确结果。
                        // 调试发现使用GL_UNSIGNED_INT时候,绑定到uvec4向量的时候采用了FLOAT的内存布局 导致uvec4.xyzw会得到错误值
                        // 也有可能是我虚拟机中的OpenGL版本问题导致的 可能我的OpenGL不支持uint然后使用缺省(FLOAT)的布局方式
                        // 这个值并不是告诉OpenGL我们传入的是什么数据类型,而是希望把我们传入的数据当做什么数据类型使用。
                        // 其实作者也不理解为何顶点着色器中已经指定了通道的数据类型,这里为何还要指定一次。也不太像是历史遗留问题。
    false,
    4 * sizeof(uint),   // 每一份数据的字节宽度,也可以直接写死16 (uint float都是4字节)
    IntPtr.Zero
    );

然后顶点着色器中我们从0号通道接收数据的时候使用uvec4数据类型:

layout (location = 0) in uvec4 loc_uv4_text; // 4个uint的四维向量
// GLSL的数据类型没有那么自由,使用uvecN是最适合的,而且如果是MD5的话 uint也会方便很多
// uvec4 是一个四维向量分别可以通过 loc_uv4_text.x 获取对应值 一共四个分量(xyzw)每个值是一个uint

这时候可能你会问,如果密码的字节数超过16位怎么办?没有什么事情是一顿烧烤解决不了的如果有就两顿:

GL.VertexAttribPointer(
    0,                  // 依然使用0号通道
    4,
    GL.GL_FLOAT,
    false,
    8 * sizeof(uint),   // 现在每次获取数据是偏移8个uint了
    IntPtr.Zero
    );
GL.VertexAttribPointer(
    1,                  // 1号通道也用起来
    4,
    GL.GL_FLOAT,
    false,
    8 * sizeof(uint),   // 现在每次获取数据是偏移8个uint了
    (IntPtr)(4 * sizeof(uint)) // 第一次获取数据的时候偏移4个uint
    );

然后顶点着色器中:

layout (location = 0) in uvec4 loc_uv4_text_1;
layout (location = 1) in uvec4 loc_uv4_text_2;

用两个uvec4作为拼接。当然代价就是浪费显存,因为一个明文需要32字节数据,如果说送入100W个密码到显存中去需要30MB内存和显存,如果只用一个uvec4那么30MB可以送入200W个明文进去计算。因为数据需要结构化,所以哪怕明文只有两个字符,我们也需要字节对齐。我们的案例将采用16字节的明文作为讲解。

那么问题来了我们现在只是可以做到将明文或者说一个字典文件送入显存了。。如果要碰撞MD5那么我们是不是还需要一个MD5字符串?即便我们可以在着色器编写MD5的算法,那么每计算一次总的需要一个MD5去判断吧?如果判断一毛一样了,说明碰撞成功了,那么我们还得知道是哪个明文碰撞出来的吧?。。这个要怎么搞?

MD5字符串我们也是通过vertices传入进去吗?。。。不不不。。。在着色器代码中有一个数据类型uniformuniform修饰的变量可以和CPU交互,也就是说可以在CPU端的代码对其进行设置或者读取。

layout (location = 0) in uvec4 loc_uv4_text;

//用于保存最终结果
varying float[16] m_result;
//用于保存MD5密文
uniform uint u_x;
uniform uint u_y;
uniform uint u_z;
uniform uint u_w;

如上,我们用4个uint来保存密文,4个uint刚好16字节。但是可以看到,作者用了一个varying修饰的m_result来保存结果,也就是说哪个明文计算结果与目标密文一直。或许你又不理解了,uniform可以被CPU读取和设置,为什么我们还要用一个verying修饰的float数组来保存结果?直接再用一个uniform来保存结果就好了啊。是的想法没错,但是要知道被uniform所修饰的数据类型对于着色器代码来说他是只读不可写。所以凉凉。。。而varying是可读写,但无法和CPU进行交互。且支持数据类型有限,无法使用整数型。所以我们用了16个float当做16个byte用。

不对啊。。不是说不能和CPU交互吗?那我们要怎么获取计算结果啊。。。是的。。这很烦。。毕竟这是图形渲染管线中。而不是在类似于CUDA或者OpenCL在通用计算单元中。。。图形渲染管线是用来渲染实3D图像的。只是我们在用图形渲染管线干着非主流的事情。起码以目前作者的知识还并不知道要怎么样从着色器中直接返回一个数据给CPU。但是也并不是说没有办法。那我们就按图形渲染管线的规则来。他最终会渲染一帧图像来是吧?图像是不是有像素?像素是不是RGB?好的。问题解决了。我们将结果写入渲染的图像中。然后获取像素值。这样一来整个流程就通了。

uniformvarying在同一个GLProgram中为全局变量。当然需要在不同的着色器中声明同样的变量,它们将会自动关联在一起。

所以我们直接在顶点着色器中算MD5片段着色器中写入结果。就这么愉快的决定了。

那么除了vertices我们通过BufferData送入显存,那么上面的四个uniform要怎么处理?

// 着色器代码有点多,我们直接从外部加载
var str_vertex_shader = System.IO.File.ReadAllText("./glsl_md5.vs", Encoding.UTF8);
var str_fragment_shader = System.IO.File.ReadAllText("./glsl_md5.fs", Encoding.UTF8);
var gp = GLProgram.Create(str_vertex_shader, str_fragment_shader);
gp.Use();
// strTargetMd5为目标Md5字符串
uint[] arrs_result = OpenGLMd5.Md5ToUints(strTargetMd5);
gp.SetUniform("u_x", arrs_result[0]);
gp.SetUniform("u_y", arrs_result[1]);
gp.SetUniform("u_z", arrs_result[2]);
gp.SetUniform("u_w", arrs_result[3]);
// 至于怎么将Md5字符串转换成四个uint大家可以各显神通,下面并不是最好的办法,仅仅是方便,反正只执行一次。
public static uint[] Md5ToUints(string strMd5) {
    uint[] ret = new uint[4];
    byte[] by_md5 = new byte[16];
    for (int i = 0; i < 16; i++) {
        by_md5[i] = Convert.ToByte(strMd5.Substring(i << 1, 2), 16);
    }
    unsafe {
        fixed (void* ptr_src = &amp;by_md5[0])
        fixed (void* ptr_dst = &amp;ret[0]) {
            Pointer.Copy(ptr_dst, ptr_src, by_md5.Length < 16 ? by_md5.Length : 16);
        }
    }
    return ret;
}

MD5算法

MD5: RFC-1321

网上找一找能找到一大堆的MD5算法,唯一不同的是,这个算法我们需要使用GLSL编写。MD5有两个重要步骤,一个是字节补齐,一个是计算。

MD5计算是需要的数据长度必须是512的整数倍的bit位,也就是说64字节的倍数。并且最后16字节是原始数据的长度。如果参与计算的数据总长度无法是整数倍则补齐到整数倍。也就是说差不多是下面的结构

[原始数据|填充数据|原始数据长度(16字节)].Length % 64 = 0

注意:最后部分的原始数据长度是bit位,不是字节长度。关于国内一些文档的翻译并没有提到这一点。

而填充数据的规则为[0x80,0,0,...],也就是说从二进制的角度去看在原始数据后面补一个1然后一直填充0直到满足上面的规则。

我们的密码才多少字节?16字节。。别说16字节,就算32字节。的密码也在64字节的范围内。所以关于字节补齐的这个步骤我们可以直接写死以加快算法速度,我们肯定是返回64字节的。

// GLSL 顶点着色器中的代码片段
// 16个uint刚好就是64字节,所以代码直接写死。
uint[16] MD5_Append(uvec4 uv4){
    // uv4为0号通道获取到的数据
    // 所以uv4是我们的明文数据,我们需要检测明文数据长度,看看那个字节是0
    uint z = uint(0);
    if ((uv4[0] & uint(0x000000FF)) == z) { // 0字节
        return uint[16] ( uint(0x00000080), z, z, z, z, z, z, z, z, z, z, z, z, z, z, z );
    }
    if ((uv4[0] & uint(0x0000FF00)) == z) { // 1字节 后面的uint(8)表原始数据8个bit位
        return uint[16] ( uv4[0] & uint(0x000000FF) | uint(0x00008000), z, z, z, z, z, z, z, z, z, z, z, z, z, uint(8), z );
    }
    // ....
    return uint[16] ( uv4[0], uv4[1], uv4[2], uv4[3], z, z, z, z, z, z, z, z, z, z, uint(128), z ); // 16字节的明文
}

然后就是计算MD5的过程,这个过程就不贴代码了,毕竟没有太多特别的地方。同样的,计算的中循环我们也可以去掉,我们的算法只会执行一次流程没必要使用循环。

计算过程

然后就是顶点着色器main函数。也就是入口。

void main(){
    // gl_XXXX开头的都是GLSL内置变量 我不会以三角形方式渲染图像,而是直接绘制顶点
    // 不然使用三角形 鬼知道我们传入的数据会组合成什么样的三角形 而且还会执行栅格化
    gl_PointSize = 1000; //设置顶点大小,其实我们只需要6个像素就够了6 * RGB = 18字节了
    uint arr[16] = MD5_Append(loc_uv4_text);    // 字节补齐
    uint md5[4] = MD5_Trasform(arr);            // 计算md5
    // loc_uv4_text是当前着色器从0号通道获取到的数据,如果计算出来的结果和uniform变量一直
    // 那么我们就将这个明文保存到m_result中并在片段着色器中作为像素值输出
    if(md5[0] == u_x && md5[1] == u_y && md5[2] == u_z && md5[3] == u_w){
        m_result[0] = float((loc_uv4_text.x) & uint(0x000000FF));
        m_result[1] = float((loc_uv4_text.x >> 8) & uint(0x000000FF));
        m_result[2] = float((loc_uv4_text.x >> 16) & uint(0x000000FF));
        m_result[3] = float(loc_uv4_text.x >> 24);

        m_result[4] = float((loc_uv4_text.y) & uint(0x000000FF));
        // ...
        gl_Position = vec4(-1,-1,0,1); // 此坐标在OpenGL归一化空间Z方向投影的左下角
    }else{
        // 此坐标在归一化空间之外会被栅格化裁剪并丢弃 所以不会有像素参数 片段着色器不会触发
        gl_Position = vec4(-2,-2,0,1);
    }
}

OpenGL使用一个2*2*2的立方体作为归一化空间,立方体中心是原点坐标。而这个立方体的正面则与显示视窗对应,而最终视窗显示画面就是z平面的空间投影。这里不做过多介绍了。反正在这个立方体之外的坐标都会被裁剪掉。因为没有计算出正确结果前,我们没必要让片段着色器运行。一旦片段着色器被触发那就说明计算出了正确的结果了。

#version 330 core
// 片段着色器全部代码
// 此变量与顶点着色器中的同名变量关联 即:结果
varying float[16] m_result;

out vec4 fragColor; //当前像素需要输出的颜色

void main(){
    // 我们在顶点着色器中输出的坐标为(-1,-1,0,1)。即在二维平面的左下角
    // gl_FragCoord 当前着色器输出的颜色位于显示视窗中的那个像素
    // 最终屏幕中的像素是以RGB呈现 所以我们需要6个像素来写入结果
    // 6 * 3 = 18 m_result有16个值
    int x = int(gl_FragCoord.x) * 3;

    if(x < 15){     // 15 = 5 * 3, 也就是前面5个像素
        fragColor = vec4(
            m_result[x] / float(255),       // R
            m_result[x + 1] / float(255),   // G
            m_result[x + 2] / float(255),   // B
            1.0);                           // A
    }else if(x == 15){
        fragColor = vec4(m_result[15] / float(255),0,0,1);
    }else{
        fragColor = vec4(0,0,1,1);          // 其他区域随便给个颜色比如蓝色
    }
}

批量计算

接下来就是将字典分批送入显存中。

// nCountForFrame表示没渲染一帧画面 准备送入多少个密码明文到显存
uint[] u_arrs_text_buffer = new uint[nCountForFrame * 4]; //最终要送入显存的数据

int nBufferLen = sizeof(uint) * u_arrs_text_buffer.Length;

uint vbo = GL.GenBuffers();         // 创建一个buffer对象并得到id STGL对此函数进行了多个重载
GL.BindBuffer(GL.GL_ARRAY_BUFFER, vbo); // 将对象绑定到Context中 此buffer用于保存顶点数据
GL.BufferData(GL.GL_ARRAY_BUFFER, nBufferLen, IntPtr.Zero, GL.GL_STREAM_DRAW_ARB);
//GL_STREAM_DRAW_ARB 表示数据是一直在变化的 每一帧数据都会变化
//当时上面的代码并没有拷贝数据,我们将打算使用GL.BufferSubData进行数据拷贝。

加载字典

using (StreamReader reader = new StreamReader(strDic, Encoding.UTF8)) {
    int nCounter = 0;
    string strLine = string.Empty;
    while ((strLine = reader.ReadLine()) != null) { // 每读取一行写入到vbo需要的buffer中
        OpenGLMd5.TextToBuffer(u_arrs_text_buffer, nCounter << 2, strLine);
        if (++nCounter != nCountForFrame) {         // 到达设定的条数
            continue;
        }   // 然后将数据拷贝至显存
        GL.BufferSubData(GL.GL_ARRAY_BUFFER, IntPtr.Zero, u_arrs_text_buffer);
        GL.DrawArrays(GL.GL_POINTS, 0, nCounter);   // 这里我们直接渲染顶点而不是三角形
        nCounter = 0;                               // 计数清0
        strResult = OpenGLMd5.GetResult(b_arrs_result_buffer); // 每渲染一帧 获取一下像素
        if (strResult != null) return strResult;
    }
    if (nCounter != 0) { // 将剩下的数据送入显存
        GL.BufferSubData(GL.GL_ARRAY_BUFFER, IntPtr.Zero, nCounter * 4 * sizeof(uint), u_arrs_text_buffer);
        GL.DrawArrays(GL.GL_POINTS, 0, nCounter);
        strResult = OpenGLMd5.GetResult(b_arrs_result_buffer);
        if (strResult != null) return strResult;
    }
}
// 同理如何把 strText 写入 buffers 中大家可以各显神通,同样的这不是最好的方法,仅仅是方便。
public static void TextToBuffer(uint[] buffers, int nIndex, string strText) {
    buffers[nIndex] = 0;        // 每个明文数据我们给定16字节 先将数据全部清0
    buffers[nIndex + 1] = 0;    // 在顶点着色器中将通过判断0来确认数据长度
    buffers[nIndex + 2] = 0;
    buffers[nIndex + 3] = 0;
    byte[] byText = Encoding.UTF8.GetBytes(strText);
    unsafe {
        fixed (void* ptr_src = &amp;byText[0])
        fixed (void* ptr_dst = &amp;buffers[nIndex]) {
            Pointer.Copy(ptr_dst, ptr_src, byText.Length < 16 ? byText.Length : 16);
        }
    }
}
// 每渲染一帧读取一下像素。glReadPixels的原点坐标在左下角,读取6个像素就好了
private static string GetResult(byte[] byBuffer) {
    unsafe {
        fixed (byte* ptr = &amp;byBuffer[0]) {
            GL.ReadPixels(0, 0, 6, 1, GL.GL_RGB, GL.GL_UNSIGNED_BYTE, (IntPtr)ptr);
        }
    }
    if (byBuffer[0] != 0) { // 如果左下角有像素被设定,那说明触发片段着色器了。有结果了。
        return Encoding.UTF8.GetString(byBuffer).Trim('\0');
    }
    return null;
}

好了大功告成了。。。关键代码已经全部完成。。下面就是开始封装进行试验。

试验效果

为了检验效果差距,我们需要编写一个CPU方式计算的作为对比,CPU计算的方式这里就不贴代码了。然后我们生成1000W个字典,并将最后一个作为结果

using (StreamWriter writer = new StreamWriter("./md5_test.txt", false, Encoding.UTF8)) {
    for (int i = 0; i < 10000000; i++) {
        writer.WriteLine(i);
    }
}
// 最后一个是 9999999 MD5: 283f42764da6dba2522412916b031080
// other code
// ...
sw.Start();
var aa = CPUMd5.Run("./md5_test.txt", "283f42764da6dba2522412916b031080");
sw.Stop();
Console.WriteLine("CPU_TIME: " + sw.ElapsedMilliseconds);
Console.WriteLine("CPU_RESULT: " + aa);
Console.WriteLine("=====================================");
sw.Reset();
sw.Start();
// 每次送入400W个明文到显存
var bb = OpenGLMd5.Run("./md5_test.txt", "283f42764da6dba2522412916b031080", 4000000);
sw.Stop();
Console.WriteLine("GL_TIME: " + sw.ElapsedMilliseconds);
Console.WriteLine("GL_RESULT: " + bb);

效果如下:

额。。。。好像效果也不是很理想啊。。虽然确实比CPU快了很多。。。但是根本没有预期的那么好啊。。没事问题不大。。毕竟一个Demo已经先出来了。。这个时候去和Hashcat对比看看差距到底有多大。。然后将工程拷贝到Linux环境下并且用dotnet进行编译。

好家伙。。看来我的古董Server2008虚拟机是时候换掉了。。。然后再来看看Hashcat

hashcat -a 0 -m 0 283f42764da6dba2522412916b031080 ./md5_test.txt -O

听说加上-OBuff加成。。反正它的提示是这么告诉我的。。

You can use it in your cracking session by setting the -O option.
Note: Using optimized kernel code limits the maximum supported password length.

😶😶😶😶😶....如果我没有算错的话。。。是不是49S????人都看傻了 。。。。以为打开方式不对加不加-O效果差不了多少。。于是运行它的基准测试

hashcat -b -m 0

可以看到速度87918KH/s如果我没有理解错误的话是不是每一秒可以计算8791.8W次???那么为何差距会这么悬殊?即便在没有使用硬件加速的情况下。。49S的速度连.NetCPU代码都没跑过。。这说不过去啊。。到这里作者已经不想纠结是什么原因造成的了。。而是在想如果真的可以差不多每秒8791.8W此,那岂不是作者被按在地上踩????而且那么这1000W的字典岂不是可以瞬间跑完???老实说hashcat的源码也不怎么想去看,能力不足,看着头疼。不过大概猜到了原因。跑基准测试的时候,统计的是计算能力。所以也不存在什么说要不停结构化数据然后送入显存,跑跑死数据就能统计出计算能力。然后改改代码试试:

long nFrameCounter = 0, nPwdCount = by_buffer.Length / 16;
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
long l_time = sw.ElapsedMilliseconds;
while (true) {
    nFrameCounter++;
    // 虽然是重复数据 每一帧还是重新拷贝一次到显存吧
    GL.BufferSubData(GL.GL_ARRAY_BUFFER, IntPtr.Zero, by_buffer);
    GL.DrawArrays(GL.GL_POINTS, 0, (int)nPwdCount);
    strResult = OpenGLMd5_1.GetResult(b_arrs_result_buffer);
    if (strResult != null) return strResult; // 当然不会有正确结果出来
    long l_temp = sw.ElapsedMilliseconds;
    if (l_temp - l_time >= 1000) {
        l_time = l_temp;
        Console.WriteLine("AVG_SPEED: " + (long)((nFrameCounter * nPwdCount) / (sw.ElapsedMilliseconds / 1000f)));
    }
}

好家伙,平均1.2亿次计算。。。如果将拷贝数据至显存的代码注释能达到9亿。作者每一帧传入的是400W个密码。所以到这里大伙们也知道应该从哪里优化代码了吧?很多时间被加载字典和送入显存给耽误了,纯计算的速度是很逆天的。所以要优化的话应该直接从文件加载去入手。

优化方案

不管怎么说,上面的速度确实很快,但是实际上是并不符合实际应用的。实际应用中我们也不可能跑死数据的。而且对于Hashcat的基准测试作者也仅仅是猜测跑是数据,并没有实际的证据。上面的毕竟是理论,无法实战。所以我们看看依然使用我们生成的那个字典,能否再次提高一下速度?这里我们并不讨论如何加快读取文件和结构化的速度。我们假定数据已经被我们处理好了的情况。

public static void CreateDic(string strDicFile, string strOutFile) {
    byte[] by_temp = new byte[16];
    using (FileStream fs_out = new FileStream(strOutFile, FileMode.Create, FileAccess.Write)) {
        using (StreamReader reader = new StreamReader(strDicFile, Encoding.UTF8)) {
            string strLine = string.Empty;
            while ((strLine = reader.ReadLine()) != null) {
                if (strLine == string.Empty) continue;
                var bytes = Encoding.UTF8.GetBytes(strLine);
                for (int i = 0; i < bytes.Length && i < 16; i++) {
                    by_temp[i] = bytes[i];
                }
                for (int i = 0, nLen = 16 - bytes.Length; i < nLen; i++) {
                    by_temp[i + bytes.Length] = 0;
                }
                fs_out.Write(by_temp, 0, by_temp.Length);
            }
        }
    }
}
// CreateDic("md5_test.txt","dic_new");

我们直接结构化一个处理完毕的字典。。然后直接把这个字典往显存里面塞试试看。。。作者本来想直接使用下面的代码。

GL.BufferData(GL.GL_ARRAY_BUFFER, File.ReadAllBytes("dic_new"), GL.GL_STATIC_DRAW);

可惜作者的电脑是个老古董,而且又是虚拟机。直接显存溢出了。。。所以还是得分批。。。

using (FileStream fs = new FileStream(strDic, FileMode.Open, FileAccess.Read)) {
    int nLen = 0;
    while ((nLen = fs.Read(by_buffer, 0, by_buffer.Length)) != 0) {
        GL.BufferSubData(GL.GL_ARRAY_BUFFER, IntPtr.Zero, by_buffer);
        GL.DrawArrays(GL.GL_POINTS, 0, nLen / 16);
        strResult = OpenGLMd5_1.GetResult(b_arrs_result_buffer);
        if (strResult != null) return strResult;
    }
}

为何我们之前拷贝进显存的数据都是使用的uint[]类型,为什么这里用byte[]??是的没任何问题。而且上面也说了glBufferData拷贝的数据无关数据类型。glVertexAttribPointer告诉OpenGL把他当做什么什么数据用及可以了。

可以看得速度几乎翻倍了。。当然是去掉了加载字典结构化的时间。而且可以的话,应该尽可能的一次拷贝更多的数据到显存中。当然OpenGL的函数并不像一些高级语言一样如果出错会抛出Exception,而是通过状态码的方式处理,当你执行某个函数后没有达到预期效果,可以在该函数后面执行glGetError函数获取一个错误码。对于异常的封装在STGL中并没有完成。

所以说我们要如何优化加载字典的速度???醒醒老铁。。。这是一篇讲解如何用一种非主流的方式计算MD5的文章,并不是一篇探讨IO性能的文章。。。都写了这么长了。。再整下去就成连续剧了。。。如果实在要继续的话。。🤔🤔🤔。。

项目(OpenGLForHash)地址: GitHub Gitee

密码碰撞可以有多非主流? 起因 OpenGL简介 图形渲染管线 着色器 你好三角形 思路分析 MD5算法 计算过程 批量计算 试验效果 优化方案