Backdoor CTF 2013 Crypto 400

0x00 题目

现在,这里有个公开的挑战,h4x0r创造了他自己的加密算法,决定向世界上所有的黑客发起挑战。他已经在这里公布了加密代码,他向你发起挑战,如果成功破解已加密的文本,承诺会给你丰厚的奖励。不要想得太复杂,已经给了提示,加密只是字母数字方式的。
使用上述加密算法之后的加密文本是:168 232 100 162 135 179 112 100 173 206 106 123 106 195 179 157 123 173
Flag就是文本信息的MD5值。
提示:有时候最直接的方法往往接近答案。

0x01 解题

打开链接,简单分析一下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
<?php
// h4x0r的终极加密算法
// 将要加密的明文字符串
$str = 'samplestring';
// 将明文字符串转换成对应的ASCII码值
for ($i = 0; $i<strlen($str); $i++)
$dec_array[] = ord($str{$i});
$ar = $dec_array;
$max = max($ar); //取ASCII码值数组中的最大值
// 在10到max生成一个随机数作为key
// 所以每次key都不一样
$key = rand(10,$max);
// key乘以101来增加复杂度
$key = 101*$key;
// 使用以下算法和key来实现加密
for($i=0;$i<strlen($str);$i++) // 循环加密处理,一次加密一个ASCII值
{
$x = $ar[$i];
$am = ($key+$x)/2;
$gm = sqrt($key*$x);
$enc = $am + $gm;
$encrypt = floor($enc)%255; // 这是最终加密出的数字结果
echo $encrypt.' ';
}
?>

通过分析我们发现其实这个加密算法的弱点就是key的生成,虽然每次加密的key都是随机生成,但是key的生成范围较小,可以用穷举法来破译密文,为什么呢,我们来分析一下原因,我们先看ASCII表。

ASCII表.jpg

key既然是在10在由待加密的字符串转ASCII码值数组中最大值生成,且题目已经说了是字母数字方式的加密(实质就是字母随机映射数字),那么在此题中ASCII码值的范围就是65-90和97-122,也就是说key值是在10到122中生成的。那么问题就简单了,我们可以大致算一下破译密文需要穷举次数:18(密文长度)x(122-65+1(明文ACSII取值范围))x(127-10+1(key的取值范围))=123192,这个次数对现在的CPU来说就是1,2秒不到的时间,所以能很轻松破译密文。

下面是参考的破译代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php
$cipher = array(168, 232, 100 ,162, 135, 179, 112, 100, 173, 206, 106, 123, 106, 195, 179, 157, 123, 173);
for($key=10; $key<=122; $key++){ //key的取值范围
$plain = array();
$key_new = $key * 101;
for($i=0; $i<count($cipher); $i++){ //循环破译密文
for($p=65; $p<=122; $p++){ //明文字符生成的ASCII码范围
$x = $p;
$am = ($key_new+$x)/2;
$gm = sqrt($key_new*$x);
$enc = $am + $gm;
$encrypt = floor($enc)%255;
//判断每次穷举与密文ASCII值是否相等
if($encrypt == $cipher[$i])
array_push($plain,$p);
}
}
//将明文ASCII值转为字符
if(count($plain) == count($cipher)){
$text = '';
foreach($plain as $t)
$text = $text.chr($t);
echo $text."\n";
}
}
?>

最终破译的结果:

Backdoor CTF 2013 Crypto 400 result.gif

计算出MD5值

1
2
[email protected]:~# echo -n myalgocantbebroken | md5sum
e5f948edd0a2c79d3ab1d13d7948f04a -

另外提供一篇通过计算密钥key来破译密文的文章,感兴趣的小伙伴可以去研究一下:P