Home manger attackについて
Post
Cancel

manger attackについて

初めに

DownUnderCTF で rsa-interval-oracle が出題された。

主な解法は以下に纏められるし、公式解説でも同じようなことが書いてある。

  • rsa-interval-oracle-i → bitごとの復号 or LSB oracle attack
  • rsa-interval-oracle-ii → Manger attack or LSB oracle attack
  • rsa-interval-oracle-iii → EHNP(HNP) or LSB oracle attack
  • rsa-interval-oracle-iv → EHNP(HNP)

ソースコード(参考)

rsa-interval-oracle-iv のソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#!/usr/bin/env python3

import signal, time
from os import urandom, path
from Crypto.Util.number import getPrime, bytes_to_long


FLAG = open(path.join(path.dirname(__file__), 'flag.txt'), 'r').read().strip()

N_BITS = 384
TIMEOUT = 3 * 60
MAX_INTERVALS = 4
MAX_QUERIES = 4700


def main():
    p, q = getPrime(N_BITS//2), getPrime(N_BITS//2)
    N = p * q
    e = 0x10001
    d = pow(e, -1, (p - 1) * (q - 1))

    secret = bytes_to_long(urandom(N_BITS//9))
    c = pow(secret, e, N)

    print(N)
    print(c)

    intervals = [(0, 2**(N_BITS - 11)), (0, 2**(N_BITS - 10)), (0, 2**(N_BITS - 9)), (0, 2**(N_BITS - 8))]
    queries_used = 0

    while True:
        print('1. Add interval\n2. Request oracle\n3. Get flag')
        choice = int(input('> '))

        if choice == 1:
            if len(intervals) >= MAX_INTERVALS:
                print('No more intervals allowed!')
                continue

            lower = int(input(f'Lower bound: '))
            upper = int(input(f'Upper bound: '))
            intervals.insert(0, (lower, upper))

        elif choice == 2:
            if queries_used > 0:
                print('No more queries allowed!')
                continue

            queries = input('queries: ')
            queries = [int(c.strip()) for c in queries.split(',')]
            queries_used += len(queries)
            if queries_used > MAX_QUERIES:
                print('No more queries allowed!')
                continue

            results = []
            for c in queries:
                m = pow(c, d, N)
                for i, (lower, upper) in enumerate(intervals):
                    in_interval = lower < m < upper
                    if in_interval:
                        results.append(i)
                        break
                else:
                    results.append(-1)

            print(','.join(map(str, results)), flush=True)

        elif choice == 3:
            secret_guess = int(input('Enter secret: '))
            if secret == secret_guess:
                print(FLAG)
            else:
                print('Incorrect secret :(')
            exit()

        else:
            print('Invalid choice')


if __name__ == '__main__':
    signal.alarm(TIMEOUT)
    main()

問題点

問題となるのは choice == 1 の指定数と choice == 2 の応答時間である。

問題 難点
i なし
ii クエリが1つ
iii 応答時間が長い・ クエリが4つ
iv クエリが4つ指定 ,1回で全て送信

公式解説でiii,ivは詳しく解説されているのでここでは、ii の manger attack について軽く解説したいと思います。

現時点での私が理解したものを書き綴っているため、一部誤解している可能性もあります。その場合、指摘してくださるとありがたいです。

manger attack とは

ii の攻撃にある Manger’s attack とは Manger さんが2001年に出した論文に起因して Manger attack と呼ばれます。 これは、OAEPというパディングに対する攻撃に用いられるそうですが、ここでは内容をメインでするため省略します。

攻撃手法の要約

STEP1

解の範囲を大まかに絞る。(2分探索) STEP1-1 2枚目

STEP1-2

STEP2

mの存在範囲を $[iN,iN+2B)$ に移動・拡大or縮小する。 STEP2

STEP3

oracleで判定し二分探索する。 二分探索後は範囲の場所である $[iN,iN+2B)$ を満たさない。よって3.3で求める$f_{tmp}$で最小値と最大値の差を$2B$にするように範囲の縮尺を拡大する。次に、$f_3$において平行移動を行い最小値を $iN$ のところまでにする。 結果として、oracleの$B$以上か以下かの判定をうまく用いることができる。 これを繰り返し、min と max の値が同じになれば終了し min が答えの$m$となる STEP3

ここで、rsa-interval-oracle の値設定は $N = 2^{348}$ よりmanger attack を使用する際の $B$ の値は$B = 2^{( \lceil \log_{256} N \rceil-1)}=376$となる。よってiiのバージョンにおいて、クエリに376を投げてやれば manger attack が成立でき flag を得ることができる。

誤字・脱字・訂正等ありましたら、twitterでお知らせください…

This post is licensed under CC BY 4.0 by the author.