【検証小ネタ】プログラムとヒープの間の心の溝

TLにこんなツイートが流れてきた。

SekaiCTFのDiscordでPIE Disabledだとheapのランダマイズが弱くなるって出てきたけど、もし本当なら根拠というか仕組み知りたいな
— てんぷ (@t3mpwn) October 2, 2022

そんなわけないやろどこの都市伝説だよと思いながら、PIE無効のときのヒープはアドレスが小さいので何か愉快なことが起きているのではという疑念も捨てられなかった。というのも、昔SECCONでmallocにNULLを返させて範囲外参照でGOTを破壊するという問題を出した。このときあるチームが大量の接続を貼っていたため怒りに行ったのだが、そのチームはmallocが返すヒープのアドレスからGOTまでのオフセットを決め打ちして、総当りで解くコードを書いていた。ゴリ押しが効くと知ってから今に至るまで、この意地汚い手法は1回使った記憶があるかどうかレベルだが、今こそちゃんと検証するべきだと思った。

実験による検証

説を検証するため、次のプログラムをPIE有効・無効で回しまくる。

char a;

int main() {
  char *b = malloc(1);
  printf("0x%lx\n", b - &a);
  return 0;
}

いずれもASLR無効の場合（プログラムとヒープが隣接している場合）のオフセットは0x128fになった。

matplotlib、殺れ。

import subprocess
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.ticker as ticker

min_diff = 1<<64
max_diff = 0
result = []
for i in range(0x1000):
    diff = int(subprocess.check_output(["./a.out"]), 16)
    if diff < min_diff: min_diff = diff
    if diff > max_diff: max_diff = diff
    result.append(diff)

print("Min diff:", hex(min_diff))
print("Max diff:", hex(max_diff))

plt.rcParams['figure.subplot.bottom'] = 0.25
plt.ticklabel_format(style = 'plain')
plt.hist(result)
plt.xticks(rotation=90)
axes = plt.gca()
axes.get_xaxis().set_major_formatter(
    ticker.FuncFormatter(lambda x, pos: "0x{:08x}".format(int(x)))
)
plt.savefig("test.png")

まずはPIE無効の場合：

Min diff: 0x128f
Max diff: 0x200028f

OK。

次にPIE有効の場合：

Min diff: 0x228f
Max diff: 0x200028f

OK。何度か実験を回すとminが0x128fになることもあったので、PIE有効でも無効でもプログラムとヒープが隣接することはある。 maxは0x2000028fより大きくなることはなかった。

ソースコードによる検証

ヒープのASLRに関する実装はmm/unit.cにある。

#ifdef CONFIG_ARCH_WANT_DEFAULT_TOPDOWN_MMAP_LAYOUT
unsigned long __weak arch_randomize_brk(struct mm_struct *mm)
{
    
    if (!IS_ENABLED(CONFIG_64BIT) || is_compat_task())
        return randomize_page(mm->brk, SZ_32M);

    return randomize_page(mm->brk, SZ_1G);
}

まずSZ_32MとSZ_1Gのどちらが採用されるかだが、さきほどの実験結果から0x02000000にあたるSZ_32Mのパスを通っていると考えられる。 64-bitなので条件文の1つ目は通るが、is_compat_task()がfalseらしい。

is_compat_taskはアーキテクチャごとに定義されているが、x86ではcompat.hのものが使われるようである。

#define is_compat_task() (0)

randomize_pageの実装も同じファイルにある。

unsigned long randomize_page(unsigned long start, unsigned long range)
{
    if (!PAGE_ALIGNED(start)) {
        range -= PAGE_ALIGN(start) - start;
        start = PAGE_ALIGN(start);
    }

    if (start > ULONG_MAX - range)
        range = ULONG_MAX - start;

    range >>= PAGE_SHIFT;

    if (range == 0)
        return start;

    return start + (get_random_long() % range << PAGE_SHIFT);
}

x86ではPAGE_SHIFTが12なので、結果として

get_random_long() % 0x2000

がランダム範囲となる。

とくにPIEが有効であるかをチェックしている様子は伺えない。

まとめ

0x200028f - 0x128f = 0x1fff000というのがオフセットが取り得る区間である。下位12ビットは固定なので、実際にランダムになる範囲は0x1fffである。（ソースコードで検証した結果とも合っている。）

したがって、0x2000回程度の試行で、プロラムとヒープのオフセットを決め打ちして良いと期待できる。 pwnで総当りに時間が経って腹が立つ例といえば、fork serverでcanaryを当てるときである。これがだいたい0x100 x 7 = 0x700接続以内くらいなので、canary当てゲームを4,5回やれば当たるのではないでしょうか。

つまり、リモートでも忍耐強ければ、例えばヒープのアドレスだけ知っている状態でプログラムのアドレスを当てにいける。 ASLR有効でもプログラムとヒープが隣接することはあるので、ASLR無効で手元で試したコードを投げ続ければ、原理的にはいつか刺さる。

反対に、ヒープスプレーができる状態で、プログラムのアドレスからスプレーしたヒープ上のオブジェクトを当てにいくのは、かなり高い確率で刺さることが期待できる。

いかがだったでしょうか？ PIEを無効にするとエントロピーが小さくなるのでは？という都市伝説ですが、どうやら変わらないようです！運営に怒られない自信があるなら、試してみると良いと思います。