ElBlo
[crypto] SRLabs CTF: It's crypto, bros
url: https://hackingchallenge.srlabs.de/challenges
Description
In this challenge, you connect to a server that gives you a random number and asks you to provide a signature for it, using a private key that you do not possess.
The attachment is a .tgz file that contains the following:
challenge.c: The source code for the program running on the server.input/valid.txt: A binary file containing some bytes.input/valid.sig: A valid signature forvalid.text.input/invalid.sig: A 1-byte modified version ofvalid.sig.
challenge.c has two modes: if you invoke it without any arguments, it will work like in the server: it will generate a random byte array (64 bytes), and ask you to provide a signature for it. If you invoke it with 2 parameters, it will take them as files, and will validate the contents of the first file using the second file as a signature.
The file also comes with the RSA public key (4096 bits, e=65537) used for signature validation, and the signature scheme is similar to PKCS#1 v1.15, however, it has a few flaws. This is in the function decode_rsa_padding.
To verify that the signature matches, the code does the following:
- Decrypt the signature with the public key.
- Verify that the padding is correct.
- Look for the cryptographic hash in the decrypted signature (using a tag, length, value encoding)
- This sets a pointer to the beginning of the hash inside the decrypted signature buffer.
- Check that the hash matches the hash of the blob to verify.
If you try to bruteforce a solution, mutating the valid signature one bit a time, the decryption will give you garbage. This will make passing the padding check a bit difficult, and also most probably, your decrypted message will not have a valid hash tag.
PKCS#1v1.5 padding has the following format for digital signatures:
00 | 01 | PS | 00 | D
Where PS is a sequence of at least 0xFF bytes, and D is an ASN.1 encoding of the cryptographic hash. In this case, instead of the ASN.1 encoded hash, we have a list of tag, length, value fields, where one of them has to be tag_hash. If a tag is not a match, it is skipped (you still know the length).
enum signature_tag {
tag_version = 'v',
tag_author = 'a',
tag_time = 't',
tag_description = 'd',
tag_hash = 'h' // 0x68
};
Padding Check Issues
Now, there are at least 3 issues with the padding check function:
Not checking for 0xFF
// Validate PS
size_t size_ps = 0;
while (*curr & 0xFF) {
size_ps++;
curr++;
}
// Length of PS must be at least 8 according to PKCS #1 v2.1
if (size_ps < 8) {
return CRYPTO_FAILURE;
}
if (*curr++ != 0x00) {
return CRYPTO_FAILURE;
}
The check for the valid padding, instead of verifying that there are at least 8 0xFF bytes, checks that there are at least 8 non-zero bytes. This means that almost any random garbage will pass that check, as long as there is a long enough sequence of non-zero bytes.
TLV decoding issues.
Then, the code needs to decode each of the tag-length-value fields:
// Search for target tag (e.g. version information or hash) in D.
while (((curr + 1) - decoded_sig) < sig_len) {
const uint8_t tag = *curr++;
const uint8_t len = *curr++;
const uint8_t *value = curr;
if (tag == target) {
*out = value;
found_target = true;
break;
}
// Skip over other tags (even unknown ones to safeguard future
// compatibility)
curr += len;
}
if (!found_target) {
return CRYPTO_FAILURE;
}
return CRYPTO_SUCCESS;
One of the issues is that unknown fields are skipped. So basically, random data will be skipped. The sad part is that we have to be a bit lucky with the tags and lengths that we get.
However, the biggest issue is that if the target tag is found (tag_hash), this will set the pointer to 2 bytes after the tag, even if it falls outside the decrypted signature buffer.
Let’s say that we have the following:
| T 4 V V V V T 3 V V V H 0 | memory outside the buffer
-----------------------------^
Where T is a random tag, V is random data, and H is tag_hash. In that case, the “hash pointer” will be set to two bytes after the tag, which is one byte outside the decrypted signature buffer. And what is after the decrypted signature buffer?
typedef struct {
uint8_t decoded_sig[RSA_SIZE_BYTES];
uint8_t expected_hash[SHA256_DIGEST_LENGTH];
} verification_ctx_t;
The decrypted signature is stored in a struct, and right after it, is where we store the expected hash (the hash that we will check against).
If we can get our program to reach the end of the padding verification, and in the second to last byte there’s a tag_hash byte, the hash pointer will point to expected_hash, which will trivially succeed when the hashes are compared.
This feels like it is an bruteforceable problem. To pass the verification we need:
- 3 fixed bytes: 00 01 at the beginning and the
tag_hash(0x68) on the second to last byte.p = (1/256)^3 - A bit of luck to pass the padding verification:
- 8 non-zero bytes at pos 2 - 10.
p = (255/256)^8. - At least one zero byte at pos 10 .. 509.
p ~= 1 - (255/256)^499
- 8 non-zero bytes at pos 2 - 10.
- Some luck on getting a chain of tags, and lengths:
- We don’t see any
tag_hashin the process. - We end exactly on the second to last character.
- We don’t see any
The probabilities of the last part are a bit hard to calculate, a simulation showed that it’s ~0.007, and together with the previous one (padding validation), it’s around 0.006.
Overall, it is like our chances are a bit better than bruteforcing 4 bytes, which is like 1 in 4294967296 (256^4). The good thing is that the process is very paralelizable, and can be done locally. We just need to decrypt random byte arrays until we get one that matches our requirements.
I rewrote the challenge.c code to make it easier to bruteforce:
char error_buf[8192] = {0};
int bruteforce(uint8_t *blob, size_t blob_len, size_t pos) {
typedef struct {
uint8_t decoded_sig[RSA_SIZE_BYTES];
uint8_t expected_hash[SHA256_DIGEST_LENGTH];
} verification_ctx_t;
verification_ctx_t ctx = {0};
uint8_t sig_buf[RSA_SIZE_BYTES] = {0};
size_t sig_len = RSA_SIZE_BYTES;
uint32_t *data = (uint32_t *)&sig_buf[0];
sig_len = read(0, sig_buf, RSA_SIZE_BYTES);
// Load RSA public key from memory
BIO *bio =
BIO_new_mem_buf(RSA_SIGNATURE_PUBLIC_KEY, RSA_SIGNATURE_PUBLIC_KEY_LEN);
if (!bio) {
return CRYPTO_FAILURE;
}
RSA *pubkey = PEM_read_bio_RSA_PUBKEY(bio, NULL, NULL, NULL);
if (!pubkey) {
BIO_free(bio);
return CRYPTO_FAILURE;
}
const size_t expected_len = RSA_size(pubkey);
if (expected_len != sig_len) {
RSA_free(pubkey);
BIO_free(bio);
return CRYPTO_FAILURE;
}
// Compute SHA-256 of `blob` for comparison.
if (hash_sha256((char*)blob, blob_len, &ctx.expected_hash[0])) {
fprintf(stderr, "Could not hash file\n");
return CRYPTO_FAILURE;
}
size_t decryptions_count = 0;
size_t first_two_bytes_count = 0;
size_t has_tag_count = 0;
size_t padding_success_count = 0;
size_t i = 0;
while (true) {
if (i++ % 10000 == 0) {
fprintf(stderr, "[#] decrypts: %zu | first_two: %zu | has_tag: %zu | padding: %zu\n",
decryptions_count, first_two_bytes_count, has_tag_count, padding_success_count);
}
// Mutate our signature in the allocated area.
data[pos]++;
if (-1 == RSA_public_decrypt(sig_len, sig_buf, &ctx.decoded_sig[0], pubkey,
RSA_NO_PADDING)) {
unsigned long error = ERR_get_error();
ERR_error_string(error, error_buf);
fprintf(stderr, "[!] decryption failed: %s\n", error_buf);
return 0;
}
decryptions_count++;
uint8_t* decoded = (uint8_t*)(&ctx.decoded_sig[0]);
if (decoded[0] != 0 || decoded[1] != 1) {
continue;
}
first_two_bytes_count++;
if (decoded[sig_len-2] != tag_hash) {
continue;
}
has_tag_count++;
// Verify blog signature format. Find embedded SHA-256 hash for further
// verification.
const uint8_t *signature_dgst = NULL;
if (decode_rsa_padding(&ctx.decoded_sig[0], RSA_SIZE_BYTES, tag_hash,
&signature_dgst)) {
continue;
}
padding_success_count++;
if (CRYPTO_memcmp(signature_dgst, &ctx.expected_hash[0],
SHA256_DIGEST_LENGTH)) {
continue;
}
fprintf(stderr, "[#] SUCCESS\n");
hexdump(sig_buf, sig_len);
hexdump(decoded, sig_len);
// Save file to disk
char file_name[1024] = {0};
snprintf(file_name, sizeof(file_name) - 1, "%zu.%zu", pos, i);
FILE* f = fopen(file_name, "wb");
fwrite(sig_buf, sig_len, 1, f);
fclose(f);
fprintf(stderr, "[#] Saved input to %s\n", file_name);
return CRYPTO_SUCCESS;
}
return CRYPTO_SUCCESS;
}
int main(int argc, char** argv) {
if (argc != 2) {
fprintf(stderr, "usage %s num\n", argv[0]);
exit(EXIT_FAILURE);
}
size_t area = (size_t) atoi(argv[1]);
fprintf(stderr, "[#] Starting... Area: %zu\n", area);
uint8_t data[128] = {0};
bruteforce(&data[0], sizeof(data), area);
return 0;
}
The main differences with the original code are:
- It only loads the public key and calculates the hash once, then everything else is using that same key and hashes.
- It bails out early if the second to last byte is not the
tag_hash. This avoid having to process the entire buffer. - It “splits” the signature buffer into 32bit chunks, and each process can work modifying a different chunk, just call the program N times with N different numbers.
Leave it running and come back in a couple of hours :)
After a few hours, the program found a key that looks like this when decrypted:
00 01 cb 51 11 37 72 1b 46 f9 95 c8 c8 29 55 5c
3a 9e 9e a9 2b b4 bf df 4f 35 da d7 42 16 1a a8
64 27 30 06 80 5f 98 c1 98 6a f8 d6 be 18 d5 63
8a 06 f8 e9 41 ed c5 a3 1b b8 f0 cd 61 65 2e 82
a0 e6 b6 42 e3 68 98 44 99 18 8c 9f 4c 69 fe 6f
7e 54 83 6b b1 b0 39 70 b3 c5 c9 62 32 40 8e 36
fa 23 dd df 56 3f 79 5f c1 7c 5d 72 5e e0 3e 10
cf 08 5f 89 b1 e7 5c fb cd 2c 4f 86 79 92 45 4c
7d e7 15 92 3c 74 d0 38 53 19 c6 8c cd 0c 39 75
2e 5a 8c d8 6b 2d f3 1a f7 14 8a dd 1e f4 84 47
67 24 f3 48 7e fe a5 bd c9 b6 1d 0e 84 9a 61 d6
d7 09 b1 c3 b5 ce 88 18 47 d3 3e a9 5e dd ee 28
06 58 58 17 b5 fd 50 b7 0f 9e 4a d1 c1 00 29 16
ac af 4b 3b cb 4d 45 09 44 de 25 ad 7c 5f fa e9
5e 3f 2f b3 9c 31 39 32 f4 34 e6 15 74 f4 c6 51
c9 ce 2c 4e b0 18 6b 08 28 82 d9 8a f7 97 e3 e6
2d a5 48 3e ae 71 ea e2 45 2e 8c d1 ab b9 a9 c0
14 00 bb 0a 8b 81 de f2 97 57 28 e2 bf f8 c2 3c
80 f1 2f 4b e2 f4 9c 23 a4 a7 c0 e4 c4 1f 30 41
f2 ad 50 e6 56 4b 50 41 90 03 aa db 4e 9d 1a 7e
b3 e3 fa bc 57 56 be 12 71 3e c4 d1 d2 74 c4 12
41 e7 47 af 90 c1 66 2a 2f 50 de dd 1f 39 20 5c
18 25 87 96 60 60 55 e5 65 b9 b7 53 5f e5 cd 9b
ce 87 c7 e5 97 06 58 2f fd e3 4a c1 aa b7 b9 55
d5 42 6d b6 01 d7 81 bf 3b fa b2 7d 7f ab 91 84
8f c5 3b bd f9 67 82 07 78 d2 c3 7c 55 3b 1f 97
69 91 ca 32 65 78 83 8f 95 24 1e 04 1e 42 be 28
90 1a 06 21 93 93 c2 88 bd b2 44 60 c4 f3 db 12
ab 54 15 37 de 25 31 d2 af 21 e2 6b 3d 73 4e 9d
c3 7d e3 27 f8 84 d1 2d b9 03 4c 74 6c 71 02 d7
b5 ab 25 e2 e3 02 65 f0 20 89 b2 3d eb e7 eb 5a
55 8f d2 4a b8 9e 3e 2f d3 3d 2a 5f 78 c5 68 c1
Which when parsed gives us:
Tag: 29, Len: 16, pos: 208
Tag: 39, Len: 32, pos: 232
Tag: 28, Len: e2, pos: 284
Tag: 68, Len: c1, pos: 512
And as you can see, the last tag is tag_hash and the position where it’s value is stored is 512 bytes from the start of the array (which is 512 bytes length).
Appendix: A rust implementation.
Just for fun, I reimplemented the check in rust. It’s considerably slower. Instead of modifying the original signature, the code generates a random 4096 bit number, and on each iteration, it will increment it and decrypt it.
use num_bigint::{BigUint, RandomBits, ToBigUint};
use rand::Rng;
use std::fs::File;
use std::io::prelude::*;
const MODULUS_HEX: &str = "00eaa7c6c0a5bcb06e97b57a5b32b5a67aa9684d6f9509f7b38f67ccc9806da7e9b43c8d5f68a4eb1e31e2a7f048ed181eca06b50a2eba3cf97da02e9fbe09017baa54af3145eff7b9b87f6c19a3fb653771cf93faf7e6267a0965c45f7dea7a4759b9efabd5b88889030abc406f4323199440d9de43f8a2e9c1d1d95ccab589ccd4c166f90fdd982721659dd73c05898876a3f54383d6953dda525fbf32c2b9f7605debe89faf6bc2d20b30d28daf74dfe45d1809f3d67e6e219c595f9fde0904e03cf8e4178fac261bc3c20d18500495f6889c9262b81e5109e2a834647586ecaad16610975adae299365d9729a4ca06627d476052e8644a09160e342c3428f7f35ea824f63ec135e23d9a255b3db9f44b8d20fb3163e1a76e58b05321fc0f54b57240a9ac55fc70ac4da5cb1ccf1e058a8bd765e3fcfa87f769d49553c0605b7a6d0b21cf569b2a2f8ed5f81e0eddafc7aec32f75baa37d7125cbdd97133f42c8e22f028e7b2aa31135f7830ca12d791c0afa5ff15c965e294902aefc7cb7c5aadc93fe24ec7e59bf71234177fc7e89fccdf230023a84a5f4a5f5902020973301ec1254d9e885dbde2adfe45a1eb505cba3d3dfd9137ff36ff390e57ff2c826e1859ca4f81bba5f106e863204e90f26576b6264152cc3025892cb131d9c0af748cdd4186b8f2397116bd1781790027a759516be72c2a1187dafc4afba02118d";
fn main() {
let mut rng = rand::thread_rng();
let candidate: BigUint = rng.sample(RandomBits::new(4096));
let modulus = BigUint::parse_bytes(MODULUS_HEX.as_bytes(), 16).unwrap();
let mut candidate = candidate % &modulus;
println!("candidate is: {candidate:x}");
let exp = ToBigUint::to_biguint(&65537).unwrap();
let mut iterations = 0;
let mut first_two_bytes_count = 0;
let mut tag_hash_count = 0;
let mut padding_check_count = 0;
'outer: loop {
if iterations % 100000 == 0 {
println!("iters: {iterations} | first_two: {first_two_bytes_count} | tag_hash: {tag_hash_count} | padding: {padding_check_count}");
}
iterations += 1;
candidate += 1u32;
let decrypted = candidate.modpow(&exp, &modulus);
let bytes = decrypted.to_bytes_be();
// We want the number to star with exactly one zero.
// This means that the number must be 0x1FF bytes.
if bytes.len() != 0x1FF {
continue;
}
if bytes[0] != 0x01 {
continue;
}
first_two_bytes_count += 1;
// The second to last byte has to be tag_hash
if bytes[bytes.len() - 2] != 0x68 {
continue;
}
tag_hash_count += 1;
// Next check: There has to be at least one zero byte, at a position greater than 9.
let pos = bytes.iter().position(|&val| val == 0x00);
let mut pos = match pos {
// There are no NUL-bytes in the entire string. Pretty rare.
None => continue,
Some(pos) => {
// It has to start with at least 8 non NUL bytes.
if pos < 9 {
continue;
} else {
pos + 1
}
}
};
padding_check_count += 1;
let original_pos = pos;
// Finally, iterate over the TLV fields.
while pos < bytes.len() - 2 {
let tag = bytes[pos];
let len = bytes[pos + 1] as usize;
if tag == 0x68 {
continue 'outer;
}
pos += len + 2;
}
// If we ended up in the second to last position.
// We already know it's the tag_hash, so we won.
if pos != bytes.len() - 2 {
continue;
}
{
// We found a solution, print it and save it to disk.
println!("success!");
println!("candidate: {candidate:x}");
println!("decrypted: {decrypted:x}");
pos = original_pos;
// Finally, iterate over the TLV fields.
while pos < bytes.len() - 2 {
let tag = bytes[pos];
let len = bytes[pos + 1];
println!("pos: {pos}, tag: {tag:x}, len: {len:x}");
pos += (len + 2) as usize;
}
let filename = format!("{iterations}.sig");
let bs = candidate.to_bytes_be();
let mut buffer = File::create(filename).unwrap();
buffer.write_all(&bs).unwrap();
}
}
}