Webhacking.kr old-04

Challenge

Recover the preimage hidden behind repeated SHA-1 hashing.

恢复重复 SHA-1 哈希之前的原始值。

https://webhacking.kr/challenge/web-04/

Analysis

源码每次请求生成一个 8 位随机数并拼接固定 salt：

$hash = rand(10000000, 99999999)."salt_for_you";
$_SESSION['chall4'] = $hash;
for($i=0; $i<500; $i++) $hash = sha1($hash);

页面显示的是 500 轮 SHA-1 后的 40 位 hexadecimal digest，提交校验的是 session 中保存的原始字符串。候选空间是 10000000 到 99999999，共 90,000,000 个数字。每次刷新页面都会重新生成 session 值，因此 hash 的计算和提交必须使用同一次 session、同一次页面请求。

Solution

对每个 8 位候选值执行以下计算：

import hashlib


def repeated_sha1(number: int) -> str:
    value = f"{number}salt_for_you".encode()
    for _ in range(500):
        value = hashlib.sha1(value).hexdigest().encode()
    return value.decode()


for number in range(10_000_000, 100_000_000):
    if repeated_sha1(number) == target_hash:
        print(f"{number}salt_for_you")
        break

纯 Python 逐一计算可以验证算法，但完整搜索成本较高。CUDA solver 将候选空间分配给 GPU threads，并在 device 端完成 500 轮 SHA-1。GPU 内部每轮的输入是上一轮 digest 的 40 个 lowercase hexadecimal ASCII 字符，最终比较的也是 40 个 ASCII 字符；比较 digest bytes 与页面文本会得到错误结果。

#include <cuda_runtime.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

__device__ __constant__ uint32_t K[4]={0x5a827999,0x6ed9eba1,0x8f1bbcdc,0xca62c1d6};
__device__ __forceinline__ uint32_t R(uint32_t x,int n){return (x<<n)|(x>>(32-n));}
__device__ void sha1(const uint8_t *msg,int len,uint8_t out[20]){
 uint8_t b[64]={0}; for(int i=0;i<len;i++)b[i]=msg[i]; b[len]=0x80; uint64_t bits=(uint64_t)len*8; for(int i=0;i<8;i++)b[63-i]=(bits>>(8*i))&255;
 uint32_t w[80]; for(int i=0;i<16;i++)w[i]=((uint32_t)b[4*i]<<24)|((uint32_t)b[4*i+1]<<16)|((uint32_t)b[4*i+2]<<8)|b[4*i+3];
 for(int i=16;i<80;i++)w[i]=R(w[i-3]^w[i-8]^w[i-14]^w[i-16],1);
 uint32_t a=0x67452301,h=0xefcdab89,c=0x98badcfe,d=0x10325476,e=0xc3d2e1f0;
 for(int i=0;i<80;i++){uint32_t f,q;if(i<20){f=(h&c)|((~h)&d);q=K[0];}else if(i<40){f=h^c^d;q=K[1];}else if(i<60){f=(h&c)|(h&d)|(c&d);q=K[2];}else{f=h^c^d;q=K[3];}uint32_t t=R(a,5)+f+e+q+w[i];e=d;d=c;c=R(h,30);h=a;a=t;}
 uint32_t z[5]={a+0x67452301,h+0xefcdab89,c+0x98badcfe,d+0x10325476,e+0xc3d2e1f0}; for(int i=0;i<5;i++)for(int j=0;j<4;j++)out[4*i+j]=(z[i]>>(24-8*j))&255;
}
__device__ int hexval(uint8_t x){return x<10?'0'+x:'a'+x-10;}
__global__ void search(uint32_t start,uint32_t count,const uint8_t *target,uint32_t *found){
 uint32_t id=blockIdx.x*blockDim.x+threadIdx.x;if(id>=count)return;uint32_t n=start+id;uint8_t m[64],d[20];int p=0;uint32_t div=10000000;for(int i=0;i<8;i++){m[p++]=(n/div)%10+'0';div/=10;}const char*s="salt_for_you";for(int i=0;s[i];i++)m[p++]=s[i];int len=p;
 for(int r=0;r<500;r++){sha1(m,len,d);for(int i=0;i<20;i++){m[2*i]=hexval(d[i]>>4);m[2*i+1]=hexval(d[i]&15);}len=40;}
 bool ok=true;for(int i=0;i<20;i++){if(m[2*i]!=hexval(target[i]>>4)||m[2*i+1]!=hexval(target[i]&15))ok=false;}if(ok)atomicExch(found,n);
}
int main(int argc,char**argv){if(argc<4){fprintf(stderr,"usage: %s START COUNT TARGET_HEX\n",argv[0]);return 2;}uint32_t start=strtoul(argv[1],0,10),count=strtoul(argv[2],0,10);uint8_t target[20];for(int i=0;i<20;i++)sscanf(argv[3]+2*i,"%2hhx",&target[i]);uint8_t *dt;uint32_t *df;cudaMalloc(&dt,20);cudaMalloc(&df,4);cudaMemcpy(dt,target,20,cudaMemcpyHostToDevice);uint32_t zero=0xffffffff;cudaMemcpy(df,&zero,4,cudaMemcpyHostToDevice);int threads=256;int blocks=(count+threads-1)/threads;cudaEvent_t a,b;cudaEventCreate(&a);cudaEventCreate(&b);cudaEventRecord(a);search<<<blocks,threads>>>(start,count,dt,df);cudaEventRecord(b);cudaEventSynchronize(b);float ms;cudaEventElapsedTime(&ms,a,b);uint32_t found;cudaMemcpy(&found,df,4,cudaMemcpyDeviceToHost);printf("start=%u count=%u ms=%.3f candidates_per_second=%.0f found=%s\n",start,count,ms,count/(ms/1000.0),found==0xffffffff?"none":({static char x[16];snprintf(x,16,"%u",found);x;}));cudaFree(dt);cudaFree(df);}

$ nvcc -O3 -arch=sm_89 old04.cu -o old04_cuda
$ ./old04_cuda 10000000 90000000 <target-hash>
start=10000000 count=90000000 ms=15264.127 candidates_per_second=5896177 found=<number>