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 解题

打开链接，简单分析一下代码：

<?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表。

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秒不到的时间，所以能很轻松破译密文。

下面是参考的破译代码：

<?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";
	}    
}
?>

最终破译的结果:

计算出MD5值

root@kali:~# echo -n myalgocantbebroken | md5sum
e5f948edd0a2c79d3ab1d13d7948f04a  -

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