TWCTF 2018で作問したやつの解説のようなもの
TWCTF 2018で作問したやつの解説のようなもの
これは CTF Advent Calendar 2018 - Adventar の22日目の記事です .21日目は,@trmr105 プロの「耐量子計算機暗号HK17-Qを解読する」でした.
はじめに
TWCTF 2018で出題した「REVersiNG」という問題について解説する.
ジャンルはReversing + Cryptoの問題だが,今回はCryptoパートに焦点をおいて解説する.
問題の概要
以下のコードと同等の動きをするプログラムがサーバーで動いており,
keyのリークを目標とした問題.
#include <stdio.h> #include <stdint.h> #include <string.h> #include <sys/stat.h> #include <stdlib.h> #include <fcntl.h> #include <unistd.h> #define KNOWN_PLAIN_SIZE 128 uint8_t write_block; uint32_t write_addr; uint8_t key[32] = {0}; uint8_t nonce[32] = {0}; uint32_t s[16]; uint8_t block[64]; uint8_t known_plain[] = "KNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXT"; uint8_t enc_known_plain[KNOWN_PLAIN_SIZE]; const uint8_t hextable[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; void dump_array(uint8_t *arr, int size) { uint8_t tmp_char; for (int i = 0; i < size; ++i) { tmp_char = hextable[arr[i] >> 4]; write(1, &tmp_char, 1); tmp_char = hextable[arr[i] & 0xf]; write(1, &tmp_char, 1); } tmp_char = '\n'; write(1, &tmp_char, 1); } #ifdef __x86_64__ static inline void u32t8(uint32_t v, uint8_t p[4]) { p[0] = v & 0xff; p[1] = (v >> 8) & 0xff; p[2] = (v >> 16) & 0xff; p[3] = (v >> 24) & 0xff; } static inline uint32_t u8t32(uint8_t p[4]) { uint32_t value = p[3]; value = (value << 8) | p[2]; value = (value << 8) | p[1]; value = (value << 8) | p[0]; return value; } #elif __mips__ static inline void u32t8(uint32_t v, uint8_t p[4]) { p[3] = v & 0xff; p[2] = (v >> 8) & 0xff; p[1] = (v >> 16) & 0xff; p[0] = (v >> 24) & 0xff; } static inline uint32_t u8t32(uint8_t p[4]) { uint32_t value = p[0]; value = (value << 8) | p[1]; value = (value << 8) | p[2]; value = (value << 8) | p[3]; return value; } #endif static inline uint32_t rotl32(uint32_t x, int n) { // http://blog.regehr.org/archives/1063 return x << n | (x >> (-n & 31)); } // https://tools.ietf.org/html/rfc7539#section-2.1 static inline void chacha20_quarterround(uint32_t *x, int a, int b, int c, int d) { x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12); x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 8); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 7); } static inline void chacha20_serialize(uint32_t in[16], uint8_t output[64]) { int i; for (i = 0; i < 16; i++) { u32t8(in[i], output + (i << 2)); } } static inline void chacha20_block(uint32_t s[16], uint8_t block[64], int num_rounds, uint8_t is_written_block) { int i; uint32_t x[16]; memcpy(x, s, sizeof(uint32_t) * 16); if (is_written_block) { *(uint8_t *)write_addr = 0x00; } for (i = num_rounds; i > 0; i -= 2) { chacha20_quarterround(x, 0, 4, 8, 12); chacha20_quarterround(x, 1, 5, 9, 13); chacha20_quarterround(x, 2, 6, 10, 14); chacha20_quarterround(x, 3, 7, 11, 15); chacha20_quarterround(x, 0, 5, 10, 15); chacha20_quarterround(x, 1, 6, 11, 12); chacha20_quarterround(x, 2, 7, 8, 13); chacha20_quarterround(x, 3, 4, 9, 14); } for (i = 0; i < 16; i++) { x[i] += s[i]; } chacha20_serialize(x, block); } // https://tools.ietf.org/html/rfc7539#section-2.3 static inline void chacha20_init_state(uint32_t s[16], uint8_t key[32], uint32_t counter, uint8_t nonce[12]) { int i; // refer: https://dxr.mozilla.org/mozilla-beta/source/security/nss/lib/freebl/chacha20.c // convert magic number to string: "expand 32-byte k" s[0] = 0x7a4e9ba3; s[1] = 0x691e8e3b; s[2] = 0x0970425b; s[3] = 0x6bd5231f; for (i = 0; i < 8; i++) { s[4 + i] = u8t32(key + i * 4); } s[12] = counter; for (i = 0; i < 3; i++) { s[13 + i] = u8t32(nonce + i * 4); } } void ChaCha20XOR(uint8_t key[32], uint32_t counter, uint8_t nonce[12], uint8_t *in, uint8_t *out, int inlen, uint8_t is_written) { int i, j; for (i = 0; i < inlen; i += 64) { chacha20_init_state(s, key, counter, nonce); chacha20_block(s, block, 20, i / 64 == write_block && is_written); for (j = i; j < i + 64; j++) { if (j >= inlen) { break; } out[j] = in[j] ^ block[j - i]; } counter++; } } int main(int argc, char **argv) { read(0, &write_block, 1); read(0, &write_addr, 4); int key_fd = open("key", O_RDONLY); int urandom_fd = open("/dev/urandom", O_RDONLY); if (key_fd < 0 || urandom_fd < 0) { close(key_fd); close(urandom_fd); return 1; } read(key_fd, key, 32); read(urandom_fd, nonce, 12); ChaCha20XOR(key, 1, nonce, known_plain, enc_known_plain, KNOWN_PLAIN_SIZE, 0); dump_array(nonce, 12); dump_array(enc_known_plain, KNOWN_PLAIN_SIZE); ChaCha20XOR(key, 1, nonce, known_plain, enc_known_plain, KNOWN_PLAIN_SIZE, 1); dump_array(enc_known_plain, KNOWN_PLAIN_SIZE); close(key_fd); close(urandom_fd); return 0; }
これは,ChaCha20の初期stateにおける定数値を変更した暗号化処理に対して平文が既知という条件のもと, 任意のラウンドのタイミングで任意のアドレスに0x00が書き込めるというプログラムである.
ChaCha20は,4バイト×16のステートに対するシャッフルを20ラウンド繰り返し,最終的なステートと平文をXORすることで暗号化するストリーム暗号. 初期ステートは定数値,鍵,nonceを元に構成される.
ChaCha20の仕様に関しては@jovi0608さんの「新しいTLSの暗号方式ChaCha20-Poly1305」が非常に参考になる.
この問題はA practical fault attack on arx-like ciphers with a case study on chacha20という2017年のFault Diagnosis and Tolerance in CryptographyというFault Injection系のワークショップで発表された論文を参考に作成した.
元の論文ではInstruction Skipによって最終ラウンドにおける最終ステートに対して初期ステートを加算する処理をスキップし,正常な暗号化結果との差を取ることでkeyをリークするという手法が取り上げられていた.
これを既知平文
と任意のアドレスに0x00が書き込める
という条件に置き換えることで,同様のFault Attackが可能というのがこの問題の本質である.
まず,平文が既知のため暗号文とのXORを取ることで最終ステートを取り出すことができる.
このとき,最終ラウンドの処理の直前で特定したいkeyの1バイトを0x00に書き換えることで最終ステートに s20 の値がリークする.
s20と正常な最終ステートの差を計算することでkeyをリークする事ができる.
Solver
import telnetlib import struct from Crypto.Util.number import * host = 'localhost' port = 16625 kp = "KNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXTKNOWN_PLAIN_TEXT" key = "" for a in range(32): while True: tn = telnetlib.Telnet(host,port) s = tn.get_socket() payload = "\x00" payload += struct.pack(">I", 0x412320 + 0x10 + a) print(repr(payload)) s.send(payload) q = [] for x in range(3): t = tn.read_until("\n") print(t.strip()) q.append(t) tn.close() kpn = bytes_to_long(kp) q1 = int(q[1],16) ^ kpn q2 = int(q[2],16) ^ kpn if q1 - q2 < 0: continue ans = q1 - q2 print "%x" % ans while ans > 0xff: ans >>= 8 print hex(ans) key += chr(ans) break print(repr(key))
まとめ
共通鍵暗号系のCrypto問は公開鍵暗号系とは違った面白さがあるので是非解いてみてください.
明日は@成瀬順 プロによる「DAppsによる賞金付きCTF」です.