I am trying to solve this CTF challenge: #!/usr/bin/env python3 from hashlib import md5,…
- User
I am trying to solve this CTF challenge: #!/usr/bin/env python3
from hashlib import md5, sha1, sha256 from datetime import datetime
print("Try to login on my super safe computer! Be fast, you have at most 30 minutes.")
now = str(datetime.now()) print(now)
try: m = bytes.fromhex(input()) except: print("Access denied!") exit(1)
t = sha256(now.encode()).hexdigest() if t.encode() not in m: print("Access denied!") exit(1)
if not md5(m).hexdigest().endswith("fc5c25"): print("Access denied!") exit(1)
if not sha1(m).hexdigest().endswith("fc5c25"): print("Access denied!") exit(1)
print("Welcome! Here is your flag:") print(open("flag.txt").read())
Here is my latest attempt: import hashlib import time from datetime import datetime import sys
Target full suffix for both MD5 and SHA1
TARGET_SUFFIX = "fc5c25" SHORT_SUFFIX = "25" # Faster filtering before full check
Get timestamp string (from challenge or current time)
try: now_string = input("[] Enter timestamp from challenge: ").strip() if not now_string: now_string = str(datetime.now()) print(f"[] Using current time for testing: {now_string}") except EOFError: print("No input provided. Exiting.") sys.exit(1)
Compute required SHA256-based prefix
prefix_sha256_hex = hashlib.sha256(now_string.encode()).hexdigest() prefix_bytes = prefix_sha256_hex.encode('ascii')
print(f"[] Timestamp: {now_string}") print(f"[] Required prefix (SHA256 hex encoded): {prefix_bytes.decode()}") print(f"[] Target suffix: {TARGET_SUFFIX}") print(f"[] Using short prefilter suffix: {SHORT_SUFFIX}") print("[*] Starting optimised search...")
counter = 0 start_time = time.time()
BYTES_FOR_COUNTER = 8 last_print_time = start_time
while True: counter_bytes = counter.to_bytes(BYTES_FOR_COUNTER, 'big') candidate_bytes = prefix_bytes + counter_bytes
md5_hash = hashlib.md5(candidate_bytes).hexdigest() # First cheap check: only proceed if MD5 ends with SHORT_SUFFIX if md5_hash.endswith(SHORT_SUFFIX): sha1_hash = hashlib.sha1(candidate_bytes).hexdigest() # Second cheap check: only proceed if SHA1 ends with SHORT_SUFFIX if sha1_hash.endswith(SHORT_SUFFIX): # Now do the full check if md5_hash.endswith(TARGET_SUFFIX) and sha1_hash.endswith(TARGET_SUFFIX): end_time = time.time() print("\n[+] Success! Found matching input.") print(f"[*] Time taken: {end_time - start_time:.2f} seconds") print(f"[*] Input bytes (hex): {candidate_bytes.hex()}") print(f"[*] MD5 hash: {md5_hash}") print(f"[*] SHA1 hash: {sha1_hash}") print("\nSubmit this hex value to the challenge:") print(candidate_bytes.hex()) break # Print progress every ~2 seconds if counter % 1000000 == 0 and counter > 0: current_time = time.time() if current_time - last_print_time >= 2.0: elapsed = current_time - start_time rate = counter / elapsed if elapsed > 0 else 0 print(f"[*] Checked {counter:,} candidates ({rate:,.0f} hashes/sec). Elapsed: {elapsed:.1f}s", end='\r') last_print_time = current_time counter += 1Does it work in theory? (In practice, if it works at all, it seems far too slow...)
Assistant
Analysis of Your CTF Challenge Solution
Your approach is theoretically correct, but you're right about the performance concerns. Let's analyze the challenge and your solution:
The Challenge Requirements
- The input must be valid hex that can be converted to bytes
- The SHA256 hash of the current timestamp (as a string) must be contained within your input
- Both MD5 and SHA1 hashes of your input must end with "fc5c25"
Your Solution Analysis
Your solution correctly:
- Takes the timestamp and computes its SHA256 hash
- Uses this hash as a prefix for your candidate solution
- Appends counter bytes to create different candidates
- Checks if both MD5 and SHA1 hashes end with the target suffix
Performance Issues
The main performance bottleneck is the collision search. Finding a value that produces specific endings for both MD5 and SHA1 is computationally intensive.
For a 6-character hex suffix (24 bits), you'd expect to check around 2^24 = 16,777,216 candidates on average before finding a match. Your code is doing this correctly, but it might take hours depending on your hardware.
Optimization Suggestions
- Parallelization: Split the search space across multiple CPU cores
- GPU Acceleration: Use a GPU for hash calculations (libraries like hashcat)
- Smarter Search: Instead of sequential counting, you could use a more sophisticated approach
Theoretical Correctness
Yes, your solution is theoretically correct. The challenge is a classic hash collision problem, and your brute-force approach will eventually find a solution if one exists.
The time constraint in the challenge ("you have at most 30 minutes") refers to the timestamp validity, not your solving time. The timestamp's SHA256 hash must be part of your solution, and this hash changes every time you run the challenge.
If you're concerned about performance, consider implementing a multi-threaded version or using specialized hash cracking tools that can leverage GPU acceleration.
- User
ok, so can you give me an optimized Rust code then?
Assistant
Optimized Rust Solution for the CTF Challenge
Here's an optimized Rust implementation that uses multithreading to search for the hash collision much faster:
use std::io::{self, BufRead}; use std::sync::atomic::{AtomicBool, Ordering}; use std::sync::Arc; use std::thread; use std::time::{Duration, Instant}; use hex; use md5::{Md5, Digest}; use sha1::Sha1; use sha2::{Sha256, Digest as Sha2Digest}; const TARGET_SUFFIX: &str = "fc5c25"; const NUM_THREADS: usize = 8; // Adjust based on your CPU cores fn main() { println!("Enter timestamp from challenge:"); let stdin = io::stdin(); let now_string = stdin.lock().lines().next().unwrap().unwrap(); // Compute SHA256 of timestamp let mut hasher = Sha256::new(); hasher.update(now_string.as_bytes()); let prefix_sha256_hex = format!("{:x}", hasher.finalize()); let prefix_bytes = prefix_sha256_hex.as_bytes(); println!("Timestamp: {}", now_string); println!("Required prefix (SHA256): {}", prefix_sha256_hex); println!("Target suffix: {}", TARGET_SUFFIX); println!("Starting search with {} threads...", NUM_THREADS); let found = Arc::new(AtomicBool::new(false)); let start_time = Instant::now(); // Spawn worker threads let mut handles = vec![]; for thread_id in 0..NUM_THREADS { let prefix_bytes = prefix_bytes.to_vec(); let found = Arc::clone(&found); let handle = thread::spawn(move || { let mut counter: u64 = thread_id as u64; let mut last_report = Instant::now(); let mut attempts = 0; while !found.load(Ordering::Relaxed) { // Create candidate by appending counter bytes to prefix let mut candidate_bytes = prefix_bytes.clone(); let counter_bytes = counter.to_be_bytes(); candidate_bytes.extend_from_slice(&counter_bytes); // Check MD5 hash let mut md5_hasher = Md5::new(); md5_hasher.update(&candidate_bytes); let md5_result = format!("{:x}", md5_hasher.finalize()); if md5_result.ends_with(TARGET_SUFFIX) { // If MD5 matches, check SHA1 let mut sha1_hasher = Sha1::new(); sha1_hasher.update(&candidate_bytes); let sha1_result = format!("{:x}", sha1_hasher.finalize()); if sha1_result.ends_with(TARGET_SUFFIX) { // Found a match! found.store(true, Ordering::Relaxed); println!("\nSuccess! Found matching input in thread {}.", thread_id); println!("Time taken: {:.2?}", start_time.elapsed()); println!("Input bytes (hex): {}", hex::encode(&candidate_bytes)); println!("MD5 hash: {}", md5_result); println!("SHA1 hash: {}", sha1_result); println!("\nSubmit this hex value to the challenge:"); println!("{}", hex::encode(&candidate_bytes)); return; } } counter += NUM_THREADS as u64; // Skip by number of threads attempts += 1; // Report progress every ~3 seconds if attempts % 100000 == 0 { let now = Instant::now(); if now.duration_since(last_report) >= Duration::from_secs(3) { let elapsed = now.duration_since(start_time); let rate = attempts as f64 / elapsed.as_secs_f64(); println!("[Thread {}] Checked {:,} candidates ({:.0} hashes/sec)", thread_id, attempts, rate); last_report = now; } } } }); handles.push(handle); } // Wait for all threads to complete for handle in handles { let _ = handle.join(); } }How to Use This Code
-
Create a new Rust project:
cargo new ctf_solver cd ctf_solver -
Add these dependencies to your
Cargo.toml:[dependencies] md5 = "0.7.0" sha1 = "0.10.5" sha2 = "0.10.6" hex = "0.4.3" -
Replace the contents of
src/main.rswith the code above -
Build and run in release mode for maximum performance:
cargo run --release -
When prompted, paste the timestamp from the challenge
Key Optimizations
- Multithreading: Uses multiple CPU cores to search in parallel
- Efficient Search Space Division: Each thread takes a different starting point and increments by the number of threads
- Early Termination: All threads stop once a solution is found
- Release Mode: Make sure to compile with
--releasefor significant performance improvements - Progress Reporting: Shows hash rate to monitor performance
This implementation should be significantly faster than the Python version. On a modern multi-core CPU, it could be 10-50x faster depending on your hardware.
-
- User
maybe it's easier with C++ so I can run it in an online compiler?
Assistant
Optimized C++ Solution for the CTF Challenge
Here's an optimized C++ implementation that you can run in an online compiler. This version uses OpenMP for parallelization, which is supported by many online C++ compilers:
#include <iostream> #include <string> #include <vector> #include <iomanip> #include <sstream> #include <chrono> #include <cstring> #include <omp.h> // OpenSSL headers for cryptographic functions #include <openssl/md5.h> #include <openssl/sha.h> const std::string TARGET_SUFFIX = "fc5c25"; const int NUM_THREADS = 8; // Adjust based on available cores // Helper function to convert bytes to hex string std::string bytes_to_hex(const unsigned char* data, size_t len) { std::stringstream ss; ss << std::hex << std::setfill('0'); for (size_t i = 0; i < len; i++) { ss << std::setw(2) << static_cast<int>(data[i]); } return ss.str(); } // Helper function to convert hex string to bytes std::vector<unsigned char> hex_to_bytes(const std::string& hex) { std::vector<unsigned char> bytes; for (size_t i = 0; i < hex.length(); i += 2) { std::string byteString = hex.substr(i, 2); unsigned char byte = static_cast<unsigned char>(std::stoi(byteString, nullptr, 16)); bytes.push_back(byte); } return bytes; } int main() { std::string now_string; std::cout << "Enter timestamp from challenge: "; std::getline(std::cin, now_string); // Compute SHA256 of timestamp unsigned char sha256_hash[SHA256_DIGEST_LENGTH]; SHA256_CTX sha256_ctx; SHA256_Init(&sha256_ctx); SHA256_Update(&sha256_ctx, now_string.c_str(), now_string.length()); SHA256_Final(sha256_hash, &sha256_ctx); std::string prefix_sha256_hex = bytes_to_hex(sha256_hash, SHA256_DIGEST_LENGTH); std::vector<unsigned char> prefix_bytes = hex_to_bytes(prefix_sha256_hex); std::cout << "Timestamp: " << now_string << std::endl; std::cout << "Required prefix (SHA256): " << prefix_sha256_hex << std::endl; std::cout << "Target suffix: " << TARGET_SUFFIX << std::endl; std::cout << "Starting search with OpenMP parallelization..." << std::endl; auto start_time = std::chrono::high_resolution_clock::now(); bool found = false; std::vector<unsigned char> solution; std::string md5_result, sha1_result; #pragma omp parallel num_threads(NUM_THREADS) { int thread_id = omp_get_thread_num(); uint64_t counter = thread_id; unsigned char md5_digest[MD5_DIGEST_LENGTH]; unsigned char sha1_digest[SHA_DIGEST_LENGTH]; std::vector<unsigned char> candidate_bytes; MD5_CTX md5_ctx; SHA_CTX sha1_ctx; auto last_report = std::chrono::high_resolution_clock::now(); uint64_t attempts = 0; while (!found) { // Create candidate by appending counter bytes to prefix candidate_bytes = prefix_bytes; for (int i = 7; i >= 0; i--) { candidate_bytes.push_back((counter >> (i * 8)) & 0xFF); } // Check MD5 hash MD5_Init(&md5_ctx); MD5_Update(&md5_ctx, candidate_bytes.data(), candidate_bytes.size()); MD5_Final(md5_digest, &md5_ctx); std::string md5_hex = bytes_to_hex(md5_digest, MD5_DIGEST_LENGTH); if (md5_hex.substr(md5_hex.length() - 6) == TARGET_SUFFIX) { // If MD5 matches, check SHA1 SHA1_Init(&sha1_ctx); SHA1_Update(&sha1_ctx, candidate_bytes.data(), candidate_bytes.size()); SHA1_Final(sha1_digest, &sha1_ctx); std::string sha1_hex = bytes_to_hex(sha1_digest, SHA_DIGEST_LENGTH); if (sha1_hex.substr(sha1_hex.length() - 6) == TARGET_SUFFIX) { // Found a match! #pragma omp critical { found = true; solution = candidate_bytes; md5_result = md5_hex; sha1_result = sha1_hex; } break; } } counter += NUM_THREADS; // Skip by number of threads attempts++; // Report progress every ~3 seconds if (attempts % 100000 == 0) { auto now = std::chrono::high_resolution_clock::now(); auto report_elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - last_report).count(); if (report_elapsed >= 3) { auto elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - start_time).count(); double rate = attempts / (elapsed > 0 ? elapsed : 1); #pragma omp critical { std::cout << "[Thread " << thread_id << "] Checked " << attempts << " candidates (" << static_cast<int>(rate) << " hashes/sec)" << std::endl; } last_report = now; } } } } auto end_time = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::seconds>(end_time - start_time).count(); if (found) { std::cout << "\nSuccess! Found matching input." << std::endl; std::cout << "Time taken: " << duration << " seconds" << std::endl; std::cout << "Input bytes (hex): " << bytes_to_hex(solution.data(), solution.size()) << std::endl; std::cout << "MD5 hash: " << md5_result << std::endl; std::cout << "SHA1 hash: " << sha1_result << std::endl; std::cout << "\nSubmit this hex value to the challenge:" << std::endl; std::cout << bytes_to_hex(solution.data(), solution.size()) << std::endl; } else { std::cout << "No solution found in the given time." << std::endl; } return 0; }How to Use in an Online Compiler
-
Go to an online C++ compiler that supports OpenSSL and OpenMP, such as:
- OnlineGDB: https://www.onlinegdb.com/
- Wandbox: https://wandbox.org/
- Compiler Explorer: https://godbolt.org/
-
Make sure to select C++11 or higher
-
For some online compilers, you might need to add compiler flags:
-fopenmpfor OpenMP support-lcryptofor OpenSSL
-
If the online compiler doesn't support OpenSSL, here's a simplified version using only standard libraries (but it will be slower):
#include <iostream> #include <string> #include <vector> #include <iomanip> #include <sstream> #include <chrono> #include <thread> #include <atomic> #include <functional> // Simple MD5 implementation std::string md5(const std::vector<unsigned char>& data) { // This is a placeholder - you'd need to implement MD5 here // or use a header-only library return "md5_hash"; } // Simple SHA1 implementation std::string sha1(const std::vector<unsigned char>& data) { // This is a placeholder - you'd need to implement SHA1 here // or use a header-only library return "sha1_hash"; } // Simple SHA256 implementation std::string sha256(const std::string& input) { // This is a placeholder - you'd need to implement SHA256 here // or use a header-only library return "sha256_hash"; } // Rest of the code would be similar but using these functionsAlternative: Single-Threaded Version for Simple Online Compilers
If you're using a very basic online compiler that doesn't support threading or OpenMP, here's a single-threaded version that should work almost anywhere:
#include <iostream> #include <string> #include <vector> #include <iomanip> #include <sstream> #include <chrono> #include <cstring> // OpenSSL headers for cryptographic functions #include <openssl/md5.h> #include <openssl/sha.h> const std::string TARGET_SUFFIX = "fc5c25"; // Helper function to convert bytes to hex string std::string bytes_to_hex(const unsigned char* data, size_t len) { std::stringstream ss; ss << std::hex << std::setfill('0'); for (size_t i = 0; i < len; i++) { ss << std::setw(2) << static_cast<int>(data[i]); } return ss.str(); } // Helper function to convert hex string to bytes std::vector<unsigned char> hex_to_bytes(const std::string& hex) { std::vector<unsigned char> bytes; for (size_t i = 0; i < hex.length(); i += 2) { std::string byteString = hex.substr(i, 2); unsigned char byte = static_cast<unsigned char>(std::stoi(byteString, nullptr, 16)); bytes.push_back(byte); } return bytes; } int main() { std::string now_string; std::cout << "Enter timestamp from challenge: "; std::getline(std::cin, now_string); // Compute SHA256 of timestamp unsigned char sha256_hash[SHA256_DIGEST_LENGTH]; SHA256_CTX sha256_ctx; SHA256_Init(&sha256_ctx); SHA256_Update(&sha256_ctx, now_string.c_str(), now_string.length()); SHA256_Final(sha256_hash, &sha256_ctx); std::string prefix_sha256_hex = bytes_to_hex(sha256_hash, SHA256_DIGEST_LENGTH); std::vector<unsigned char> prefix_bytes = hex_to_bytes(prefix_sha256_hex); std::cout << "Timestamp: " << now_string << std::endl; std::cout << "Required prefix (SHA256): " << prefix_sha256_hex << std::endl; std::cout << "Target suffix: " << TARGET_SUFFIX << std::endl; std::cout << "Starting search (single-threaded)..." << std::endl; auto start_time = std::chrono::high_resolution_clock::now(); uint64_t counter = 0; auto last_report = std::chrono::high_resolution_clock::now(); while (true) { // Create candidate by appending counter bytes to prefix std::vector<unsigned char> candidate_bytes = prefix_bytes; for (int i = 7; i >= 0; i--) { candidate_bytes.push_back((counter >> (i * 8)) & 0xFF); } // Check MD5 hash unsigned char md5_digest[MD5_DIGEST_LENGTH]; MD5_CTX md5_ctx; MD5_Init(&md5_ctx); MD5_Update(&md5_ctx, candidate_bytes.data(), candidate_bytes.size()); MD5_Final(md5_digest, &md5_ctx); std::string md5_hex = bytes_to_hex(md5_digest, MD5_DIGEST_LENGTH); if (md5_hex.substr(md5_hex.length() - 6) == TARGET_SUFFIX) { // If MD5 matches, check SHA1 unsigned char sha1_digest[SHA_DIGEST_LENGTH]; SHA_CTX sha1_ctx; SHA1_Init(&sha1_ctx); SHA1_Update(&sha1_ctx, candidate_bytes.data(), candidate_bytes.size()); SHA1_Final(sha1_digest, &sha1_ctx); std::string sha1_hex = bytes_to_hex(sha1_digest, SHA_DIGEST_LENGTH); if (sha1_hex.substr(sha1_hex.length() - 6) == TARGET_SUFFIX) { // Found a match! auto end_time = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::seconds>(end_time - start_time).count(); std::cout << "\nSuccess! Found matching input." << std::endl; std::cout << "Time taken: " << duration << " seconds" << std::endl; std::cout << "Input bytes (hex): " << bytes_to_hex(candidate_bytes.data(), candidate_bytes.size()) << std::endl; std::cout << "MD5 hash: " << md5_hex << std::endl; std::cout << "SHA1 hash: " << sha1_hex << std::endl; std::cout << "\nSubmit this hex value to the challenge:" << std::endl; std::cout << bytes_to_hex(candidate_bytes.data(), candidate_bytes.size()) << std::endl; return 0; } } counter++; // Report progress every ~3 seconds if (counter % 100000 == 0) { auto now = std::chrono::high_resolution_clock::now(); auto report_elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - last_report).count(); if (report_elapsed >= 3) { auto elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - start_time).count(); double rate = counter / (elapsed > 0 ? elapsed : 1); std::cout << "Checked " << counter << " candidates (" << static_cast<int>(rate) << " hashes/sec)" << std::endl; last_report = now; } } } return 0; }This should work in most online C++ compilers that support OpenSSL.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.