zer0pts CTF 2021 | signme - crypto-writeup-public

#zer0ptsCTF2021

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "signme.h"

void authenticated(void) {
  puts("Thank you for signing my message!");
  system("/bin/sh");
}

void fatal(const char *msg) {
  fputs(msg, stderr);
  exit(1);
}

/**
 * Pad message with PKCS1 v1.5
 */
char* pad_pkcs1_v15(char *msg, int s, int n) {
  mpz_t r;
  char *padded;
  int i, rlen = n - s - 3;

  /* Initialize */
  mpz_init(r);
  padded = (char*)malloc(n);
  memcpy(&padded[3 + rlen], msg, s);

  /* Generate PS */
  msg = (char*)realloc(msg, rlen);
  for(i = 0; i < rlen; i++) {
    do {
      mpz_urandomb(r, rstate, 8);
    } while(mpz_cmp_ui(r, 0) == 0);
    msg[i] = mpz_get_ui(r);
  }

  /* PKCS thing */
  padded[rlen + 2] = '\x00';
  padded[0] = '\x00';
  padded[1] = '\x02';
  memcpy(&padded[2], msg, rlen);

  mpz_clear(r);
  return padded;
}

/**
 * Read message
 */
void get_message(mpz_t m) {
  char *padded, *msg;
  size_t s;

  /* Read message */
  msg = (char*)malloc(SECURITY_PARAMETER / 8);
  
  printf("Message: ");
  if ((s = read(0, msg, SECURITY_PARAMETER / 8)) <= 0)
    fatal("I/O Error\n");
  if (msg[s-1] == '\n') msg[--s] = '\0';

  /* Pad message */
  padded = pad_pkcs1_v15(msg, s, SECURITY_PARAMETER / 8);

  /* Bytes to integer */
  mpz_import(m, 1, 1, SECURITY_PARAMETER / 8, 1, 0, padded);
  free(padded);
  free(msg);
}

/**
 * Entry Point
 */
int main(void) {
  mpz_t m, s;
  PrivateKey priv;
  PublicKey pub;

  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(60);

  /* Step 0. Key generation */
  generate_keypair(&pub, &priv);
  mpz_inits(s, m, NULL);

  /* Step 1. I'll sign your message */
  get_message(m);
  gmp_printf("m = %Zx\n", m);
  generate_signature(s, m, &priv);
  gmp_printf("pubkey = (%Zx, %Zx)\n", pub.n, pub.e);
  gmp_printf("signature = %Zx\n", s);

  /* Step 2. You'll sign my message */
  mpz_urandomb(m, rstate, SECURITY_PARAMETER);
  gmp_printf("Sign this message: %Zx\n", m);
  printf("Signature: ");
  if (gmp_scanf("%Zx", s) != 1) fatal("I/O Error\n");

  /* Step 3. I'll validate your signature */
  if (validate_signature(s, m, &pub) == 0) {
    authenticated();
  } else {
    puts("Nope.");
  }

  return 0;
}

gmpを用いてRSA-CRTによる署名と検証が実装されている

* $m$ を送る

* $pad(m)^d \mod n$ が送られてくる

* $m'$ が送られてくる

* $x$ を送る

* $x^e \equiv m' \mod n$ 、すなわち $x \equiv m'^d \mod n$ ならシェルがもらえる

通常、秘密鍵がなければメッセージへの署名は行えず、また変な $m$ を送ろうにもPKCS1 v1.5できちんとパディングが行われている。

そこでpwnというタグを頼りになにかおかしいところが無いかを探す。すると $m$ にパディングを付与する部分に気になる処理がある

/**
 * Pad message with PKCS1 v1.5
 */
char* pad_pkcs1_v15(char *msg, int s, int n) {
  mpz_t r;
  char *padded;
  int i, rlen = n - s - 3;

  /* Initialize */
  mpz_init(r);
  padded = (char*)malloc(n);
  memcpy(&padded[3 + rlen], msg, s);

  /* Generate PS */
  msg = (char*)realloc(msg, rlen);
  for(i = 0; i < rlen; i++) {
    ...

ここでrealloc(msg, rlen) としているが、rlenは $n - s - 3$ となっていて、 $n$ は128で固定、 $s$ は入力文字数なので、 $s = 125$ となるようにメッセージを送ることで $rlen = 0$ とすることができる。reallocのサイズ部分に0を渡したときの動作は処理系に依存するが、glibcの実装ではfree相当の動作になるから、意図しないfreeを起こすことができる。ここで意図しないfreeを起こしたmsgはget_message関数の末尾で次のようにもう一度freeされる

void get_message(mpz_t m) {
  char *padded, *msg;
  size_t s;

  /* Read message */
  msg = (char*)malloc(SECURITY_PARAMETER / 8);
  
  printf("Message: ");
  if ((s = read(0, msg, SECURITY_PARAMETER / 8)) <= 0)
    fatal("I/O Error\n");
  if (msg[s-1] == '\n') msg[--s] = '\0';

  /* Pad message */
  padded = pad_pkcs1_v15(msg, s, SECURITY_PARAMETER / 8);

  /* Bytes to integer */
  mpz_import(m, 1, 1, SECURITY_PARAMETER / 8, 1, 0, padded);
  free(padded);
  free(msg);
}

これで128バイトの領域をdouble freeすることができた。そしてその後処理を追っていくと、この領域はgenerate_signature関数のなかで確保されている。ちょうど同じサイズの領域を確保しているので、spとqiは同じ領域を共有している

void generate_signature(mpz_t sign, mpz_t m, PrivateKey *priv) {
  mpz_t sp, sq, qi;
  mpz_init2(sp, SECURITY_PARAMETER); // same
  mpz_init2(sq, SECURITY_PARAMETER);
  mpz_init2(qi, SECURITY_PARAMETER); // same
  ...

すると、RSA-CRTの署名処理が

$i_q = q \mod p$

$S_p = m^{d_p} \mod p$

$S_q = m^{d_q} \mod q$

$S = S_q + q(i_q(Sp − Sq) \mod p)$

だったものが実質↓のようになる。

$S = S_q + q(i_q(i_q − Sq) \mod p)$

このときに何が起こるかは https://www.cryptologie.net/article/371/fault-attacks-on-rsas-signatures/ にわかりやすく解説されている。

そもそも↑の式は $m^{d_p} \mod p, m^{d_q} \mod q$ を中国剰余定理（正確にはGarner's algorithm）で $m^d \mod pq$ にまとめているので、 $s^e \equiv m \mod p, s^e \equiv m \mod q$ が成り立つが、 $S_p$ が壊れたときの署名 $\tilde{s}$ については $\tilde{s}^e \equiv m \mod q$ だが $\tilde{s}^e \not\equiv m \mod p$ となる。すなわち、 $\tilde{s}^e - m$ は $q$ を因数に持つが $p$ は因数に持たない。したがって、 $GCD(\tilde{s}^e - m, N) = q$ がなりたち、素因数分解ができてしまう。これをBellcore Attackという。

というわけで実装する

from ptrlib import Socket, Process
from math import gcd

# sock = Process("./chall")
sock = Socket("localhost", 10298)
sock.sendlineafter("Message: ", "A" * 125)
m = int(sock.recvlineafter("m = "), 16)
N = int(sock.recvregex(r"\(([0-9a-f]+), 10001\)")[0], 16)
sig = int(sock.recvlineafter("signature = "), 16)
m2 = int(sock.recvlineafter("message: "), 16)

e = 65537
p = gcd(pow(sig, e, N) - m, N)
q = N // p
assert p != 1 and p != N

d = pow(e, -1, (p-1)*(q-1))
s_p = pow(m2, d, p)
s_q = pow(m2, d, q)
q_i = pow(q, -1, p)
sign2 = (s_q + q * ( q_i * (s_p - s_q) % p )) % N

sock.sendlineafter("Signature: ", hex(sign2)[2:])
sock.interactive()