Crypto-ThreadCracker

PUZZLE
, ,

题目背景

线程调度大师,我还记得你…

题干

人们总说,线程调度带来的熵很低.
但,,真的如此吗?

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<thread>
#include<iostream>
#include<string>
#include<vector>
#include<mutex>
#include<sstream>
#include<iomanip>
#include<random>
#include<openssl/sha.h>
#include<openssl/aes.h>
#include<openssl/evp.h>
#include"secret.h"

std::mutex rng_mutex;
std::mt19937 rng(12345);
const int max_hex_len=8;

std::string pad_hex(uint32_t val){
    std::stringstream ss;
    ss<<std::hex<<std::setfill('0')<<std::setw(max_hex_len)<<val;
    return ss.str();
}

std::string sha256_hash(const std::string& input){
    unsigned char hash[SHA256_DIGEST_LENGTH];
    SHA256_CTX sha256;
    SHA256_Init(&sha256);
    SHA256_Update(&sha256,input.c_str(),input.size());
    SHA256_Final(hash,&sha256);
    std::stringstream ss;
    for(int i=0;i<SHA256_DIGEST_LENGTH;i++){
        ss<<std::hex<<std::setfill('0')<<std::setw(2)<<(int)hash[i];
    }
    return ss.str();
}

std::string aes256_ecb_encrypt(const std::string& plaintext,const std::string& key){
    std::string aes_key=key.substr(0,32);
    EVP_CIPHER_CTX* ctx=EVP_CIPHER_CTX_new();
    EVP_EncryptInit_ex(ctx,EVP_aes_256_ecb(),NULL,
                       (const unsigned char*)aes_key.data(),NULL);
    EVP_CIPHER_CTX_set_padding(ctx,1);
    
    int len=0;
    int ciphertext_len=0;
    std::vector<unsigned char> ciphertext(plaintext.size()+AES_BLOCK_SIZE);
    
    EVP_EncryptUpdate(ctx,ciphertext.data(),&len,
                      (const unsigned char*)plaintext.data(),plaintext.size());
    ciphertext_len=len;
    
    EVP_EncryptFinal_ex(ctx,ciphertext.data()+len,&len);
    ciphertext_len+=len;
    
    EVP_CIPHER_CTX_free(ctx);
    
    std::stringstream ss;
    for(int i=0;i<ciphertext_len;i++){
        ss<<std::hex<<std::setfill('0')<<std::setw(2)<<(int)ciphertext[i];
    }
    return ss.str();
}

void worker(std::string& result){
    std::string res="";
    for(int i=0;i<1000;i++){
        uint32_t rnd_val;
        {
            std::lock_guard<std::mutex> lock(rng_mutex);
            rnd_val=rng();
        }
        std::string rnd_hex=pad_hex(rnd_val);
        res=sha256_hash(res+rnd_hex);
    }
    result=res;
}

int main(){
    std::cout<<"Hey this is a cryptography problem.\n";
    const int num_threads=10;
    std::vector<std::thread> threads;
    std::vector<std::string> results(num_threads);
    
    for(int i=0;i<num_threads;i++){
        threads.emplace_back(worker,std::ref(results[i]));
    }
    for(auto& t:threads){
        t.join();
    }
    
    std::string combined="";
    for(int i=0;i<num_threads;i++){
        combined+=results[i];
    }
    
    std::string private_key=sha256_hash(combined);
    std::string flag=FLAG;
    
    std::string encrypted_flag=aes256_ecb_encrypt(flag,private_key);
    std::cout<<"Encrypted flag: "<<encrypted_flag<<"\n";
    
    return 0;
}

Output:

1
2
Hey this is a cryptography problem.
Encrypted flag: f7d88db849c173307e732fecef861d2fb662aa96da73322181aa5b02f35c58ef4334c64b81d080a12d4c3128cb456147f5fbb37230ba97a6eefaaeacbb6e32527710735df37b46122b46269bdb8a908f

hint 0

多线程争抢资源造成的熵很不稳定,有分布不均的情况.
举一个例子: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int tmp=0;
void ad(){
    for(int i=1;i<=100000;++i){
        tmp+=1;
    }
}
int main(){
    vector<thread>vc;
    for(int i=1;i<=10;++i){
        vc.emplace_back(thread(ad));
    }
    for(int i=0;i<10;++i){
        vc[i].join();
    }
    cout<<tmp;
    return 0;
}

Fluu为了解决上面代码中 + 有交换律所以区分不清的情况,对每一步引入了伪随机数生成器和sha256来消掉线性,于是就有了这个题.

hint1

本题编译命令:

1
g++ ./problem.cpp -o problem -lcrypto

Fluu出题使用的环境:Windows11 22H2 22621.3155
WSL(程序在wsl上运行): 

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
fluorine@NaraFluorine:/mnt/c/Users/lenovo$ cat /etc/os-release
PRETTY_NAME="Ubuntu 22.04.5 LTS"
NAME="Ubuntu"
VERSION_ID="22.04"
VERSION="22.04.5 LTS (Jammy Jellyfish)"
VERSION_CODENAME=jammy
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=jammy
fluorine@NaraFluorine:/mnt/c/Users/lenovo$ uname -r
uname -a
6.6.87.2-microsoft-standard-WSL2
Linux NaraFluorine 6.6.87.2-microsoft-standard-WSL2 #1 SMP PREEMPT_DYNAMIC Thu Jun  5 18:30:46 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
fluorine@NaraFluorine:/mnt/c/Users/lenovo$ g++ --version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
fluorine@NaraFluorine:/mnt/c/Users/lenovo$ ls -l
...
-rwxrwxrwx 1 fluorine fluorine    88480 Sep 23 16:20 problem
...

提交