satto1237’s diary

s4tt01237’s diary

ラーメンとかCTFとかセキュリティとか

線形合同法 (Linear Congruential Generators) によって生成される擬似乱数を予測する

CTF やってみた系 セキュリティ

はじめに

先日開催されたBSidesSF CTF 2020で線形合同法によって生成される擬似乱数を予測する問題 (mentalist) が出題されました．
この問題がとても勉強になったので，今回はこの問題を解く際に調べたことをまとめようと思います．

線形合同法とは

線形合同法とは，以下の漸化式で与えられる擬似乱数列の生成式です．

{ X_{n+1} = (A \times X_n + B \bmod M) }

ここでの A, B, Mは定数であり， M \gt A, M \gt B, A \gt 0, B \geq 0を満たします．

以下がPythonによる線形合同法の実装例です．

class LCG:
    # X_{n+1} = (A \times X_n + B) \bmod M
    A = 9605000926055143081 # multiplier
    B = 9749676397194673813 # increment
    M = 18446744073709551615 # modulus

    def __init__(self, seed):
        # start value
        self.state = seed

    def next(self):
        self.state = (self.A * self.state + self.B) % self.M
        return self.state

    def get_parameters(self):
        return self.A, self.B, self.M

def prediction_test(PRNGs, states, A, B, M):
    next_value = PRNGs.next()
    predicted_value = (A * states[-1] + B) % M

    for i, state in enumerate(states):
        print('X_{0}: {1}'.format(i, state))

    print('\nnext value: {}'.format(next_value))
    print('predicted value: {}'.format(predicted_value))

    if next_value == predicted_value:
        print('correct!')
    else:
        print('incorrect!')

def output_example():
    states = [114514]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    A, B, M = PRNGs.get_parameters()

    prediction_test(PRNGs, states, A, B, M)

X_0: 114514
X_1: 11263583670124855457
X_2: 4661627645215281165
X_3: 17524162438654086043
X_4: 6613605687528724796

next value: 13405047293276115594
predicted value: 13405047293276115594
correct!

擬似乱数の予測

線形合同法は，基本的に各パラメータ ( A, B, M) と現在の疑似乱数 ( X_n) が既知であれば，次の疑似乱数 ( X_{n+1}) を簡単に求めることができます．
しかし，CTFで出題される線形合同法を使った問題では，各パラメータのどれかが未知であることがほとんどです（全てのパラメータが未知であることもある）．

これから，CTFでよく出題される線形合同法を使った問題の擬似乱数を予測していきます．

B ( increment) が未知である場合

A, M, X_0, X_1は既知であるとします．

 # X_{n+1} = (A \times X_n + B) \bmod M

A = 9605000926055143081
M = 18446744073709551615

X_0 = 17460462356393494334
X_1 = 5858263937153669472

このとき，次のようにして Bを求めることができます．

{ X_1 = (A \times X_0 + B) \bmod M \\ B = (X_1 - A \times X_0) \bmod M }

以下は検証コードと出力結果です．

def solve_unknown_increment(states, A, M):
    B = (states[1] - A * states[0]) % M
    return B

def test_unknown_increment():
    print('test for unknown increment')
    # states = [getRandomNBitInteger(64)]
    states = [17460462356393494334]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())

    A, _, M = PRNGs.get_parameters()
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

test for unknown increment
X_0: 17460462356393494334
X_1: 5858263937153669472

next value: 10449136789666358545
predicted value: 10449136789666358545
correct!

A (multiplier) と B ( increment) が未知である場合

M, X_0, X_1, X_2は既知であるとします．

 # X_{n+1} = (A \times X_n + B) \bmod M

M = 18446744073709551615

X_0 = 16957592306608621537
X_1 = 8207823669407337095
X_2 = 3506114226401483223

このとき，次のようにして Aを求めることができます．

{ X_1 = (A \times X_0 + B) \bmod M \\ X_2 = (A \times X_1 + B) \bmod M }

X_2と X_1の差分をとることで Bを消します．

{ X_2 - X_1 = (A \times X_1 - A \times X_0) \bmod M = A \times (X_1 - X_0) \bmod M }

法 M上での X_1 - X_0の逆元を X_2 - X_1に乗じてあげることで Aを求めることができます．

{ A = (X_2 - X_1 ) \times (X_1 - X_0)^{-1} \bmod M }

Bについては，B ( increment) が未知である場合と同様に求めることができます．

はてなってpreタグ使わないとイコール揃えた数式使えないのか？

以下は検証コードと出力結果です．

from Crypto.Util.number import inverse

def solve_unknown_multiplier(states, M):
    A = (states[2] - states[1]) * inverse((states[1] - states[0]), M)
    return A

def test_unknown_multiplier():
    print('test for unknown increment and multiplier')
    # states = [getRandomNBitInteger(64)]
    states = [16957592306608621537]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    _, _, M = PRNGs.get_parameters()
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

test for unknown increment and multiplier
X_0: 16957592306608621537
X_1: 8207823669407337095
X_2: 3506114226401483223

next value: 3098562741469012216
predicted value: 3098562741469012216
correct!

A (multiplier) と B ( increment) と M (modulus) が未知である場合

X_0 から X_7は既知であるとします．

X_0 = 12489966254767023172
X_1 = 3269246238714648380
X_2 = 9400253767069208013
X_3 = 18133428257392075756
X_4 = 4950164846933435189
X_5 = 13061720665666400352
X_6 = 15207628738950278065
X_7 = 10125779645391706253

このとき，次のようにして Mを求めることができます．

{ X_1 = (A \times X_0 + B) \bmod M \\ X_2 = (A \times X_1 + B) \bmod M \\ X_3 = (A \times X_2 + B) \bmod M \\ }

上記の式は，以下のように表すこともできます．

{ A \times X_0 + B = k_1 M + X_1 \\ A \times X_1 + B = k_2 M + X_2 \\ A \times X_2 + B = k_3 M + X_3 }

つまり， {k_{n+1} M = A \times X_n + B - X_{n+1} }のGCDを計算することで Mを求めることができます．
しかし，今回の場合は A, Bが未知であるため，この方法で Mを求めることができません．
そこで，法 M上で Mの倍数( kM)が 0になること利用して， Mを求めていきます．

まず始めに， X_{n+1}と X_nの差分をとることにより Bを消します．

{ T_0 = X_1 -X_0 \\ T_1 = X_2 - X_1 = A \times (X_1 - X_0) \bmod M = A \times T_0 \bmod M \\ T_2 = X_3 - X_2 = A \times (X_2 - X_1) \bmod M = A \times T_1 \bmod M }

次に差分同士の積の差分をとることにより Aを消します．
ここで， T_2 \times T_0は，
{ T_2 \times T_0 = A \times T_1 \times T_0 = A \times A \times T_0 \times T_0 \bmod M }
となり， T_1 \times T_1は，
{ T_1 \times T_1 = A \times T_0 \times A \times T_0 \bmod M }
となります．
そのため， T_2 \times T_0 - T_1 \times T_1は， { T_2 \times T_0 - T_1 \times T_1 = A \times A \times T_0 \times T_0 - A \times T_0 \times A \times T_0 = 0 \bmod M }
となります．

先述した通り，法 M上での 0は kMと等価であるため， T_2 \times T_0 - T_1 \times T_1を kMとして扱うことができます．
したがって， T_{n+2} \times T_n - T_{n+1} \times T_{n+1}のGCDを計算することで Mを求めることできます．

A, BはA (multiplier) と B ( increment) が未知である場合と同様に求めることができます．

以下は検証コードと出力結果です．

from Crypto.Util.number import inverse, GCD
from functools import reduce

def solve_unknown_modulus(states):
    diffs = [X_1 - X_0 for X_0, X_1 in zip(states, states[1:])]
    multiples_of_M = [T_2 * T_0 - T_1 ** 2 for T_0, T_1, T_2, in zip(diffs, diffs[1:], diffs[2:])]

    # GCD(GCD(multiples_of_M[0],multiples_of_M[1]), multiples_of_M[2])
    M = reduce(GCD, multiples_of_M)
    return M

def test_unknown_modulus():
    print('test for unknown increment, multiplier and modulus')
    # states = [getRandomNBitInteger(64)]
    states = [12489966254767023172]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    M = solve_unknown_modulus(states)
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

test for unknown increment, multiplier and modulus
X_0: 12489966254767023172
X_1: 3269246238714648380
X_2: 9400253767069208013
X_3: 18133428257392075756
X_4: 4950164846933435189
X_5: 13061720665666400352
X_6: 15207628738950278065
X_7: 10125779645391706253

next value: 11999544724300060101
predicted value: 11999544724300060101
correct!

X_n から X_{n+4}まで知ることができれば \rm{GCD}\it{(k_1 M, k_2 M)}を計算できますが， k_1, k_2が互いに素でない場合は Mを上手く求められないので X_{n+7}程度まで利用したほうがいいと思います．

BSidesSF CTF 2020のmentalistのwrite-up

Can you read the mind of a computer?

mentalist-a05ae893.challenges.bsidessf.net:12345

> nc mentalist-a05ae893.challenges.bsidessf.net 12345

                                         ____
                                       .'* *.'
                                    __/_*_*(_
                                   / _______ \
                                  _\_)/___\(_/_
                                 / _((\- -/))_ \
                                 \ \())(-)(()/ /
                                  ' \(((()))/ '
                                 / ' \)).))/ ' \
                                / _ \ - | - /_  \
                               (   ( .;''';. .'  )
                               _\"__ / HA )\ __"/_
                                 \/  \  CK /  \/
                                  .'  '...' ' )
                                   / /  |  \ \
                                  / .   .   . \
                                 /   .     .   \
                                /   /   |   \   \
                              .'   /    .    '.  '.
                          _.-'    /     ..     '-. '-._
                      _.-'       |      ...       '-.  '-.
                     (___________\____......'________)____)
 _  _ ____ __   ___ __  _  _ ___    ___ _  _  __  ___ ___ __ _    __  __ _ ___
/ )( (  __|  ) / __)  \( \/ | __)  / __) )( \/  \/ __| __|  ( \  /  \(  ( ( __)
\ /\ /) _)/ (_( (_(  O ) \/ \)_)  ( (__) __ (  O )__ \)_)/    / (  O )    /)_)
(_/\_|____)___/\___)__/\_)(_(___)  \___)_)(_/\__/(___(___)_)__)  \__/\_)__|___)

Welcome Chosen One! I have been waiting for you...
The legend fortold of one that could read minds.
If you can read my mind I will reveal my great knowledge.

What number am I thinking of? 1
Actually I was thinking of 16056095589514, try again
What number am I thinking of? 1
No I'm sorry, I was thinking of 212251536946043
What number am I thinking of? 1
Hmmm no. My number was 134250435802692, are you sure you're okay?
What number am I thinking of? 1
I'm getting worried. I was thinking of 29371827723061; you're not doing so well.
What number am I thinking of? 1
I grow tired of your failures. My number was 189619676558750
What number am I thinking of? 1
Nope. 234022781299359 Perhaps you aren't the one I was waiting for?
What number am I thinking of? 1
WRONG! It was 136021856792488
What number am I thinking of? 1
My patience thins... 4394347413737 was my number
What number am I thinking of? 1
You're getting on my nerves. It was 113471694146706
What number am I thinking of? 1
I'm only going to give you one more chance. I was thinking of 185479241432995
What number am I thinking of? 1
I see now that you aren't who I was looking for.
It's too late now but I was thinking of 168630864482204
In case you were wondering how I was thinking of these numbers,
they were for the form x_n+1 = x_n * 207106347728281 + 5532122590609 % 249292453410000
And my initial seed x_0 was 60690097607505
With this you can verify that I wasn't cheating.
Good luck in your future endeavors!

A (multiplier) と B ( increment) と M (modulus) が未知である場合の線形合同法の問題です．

上記に示した方法で解くことができます．

def solve_mentalist():
    states = [9726918447512, 46628235778441, 46641741588810, 26970189847019, 58978496575468, 18214530370557]

    M = solve_unknown_modulus(states)
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    next_value = (A * states[-1] + B) % M
    print(next_value)
    next_value = (A * next_value + B) % M
    print(next_value)

21872728992686
53825285146255
Welcome Chosen One! I have been waiting for you...
The legend fortold of one that could read minds.
If you can read my mind I will reveal my great knowledge.

What number am I thinking of? 1
Actually I was thinking of 9726918447512, try again
What number am I thinking of? 1
No I'm sorry, I was thinking of 46628235778441
What number am I thinking of? 1
Hmmm no. My number was 46641741588810, are you sure you're okay?
What number am I thinking of? 1
I'm getting worried. I was thinking of 26970189847019; you're not doing so well.
What number am I thinking of? 1
I grow tired of your failures. My number was 58978496575468
What number am I thinking of? 1
Nope. 18214530370557 Perhaps you aren't the one I was waiting for?
What number am I thinking of? 21872728992686
Incredible! I WAS thinking of that number! But can you do it again?
What number am I thinking of? 53825285146255
You really are the one that was foretold. Please accept this knowldege:
CTF{rand_should_be_enough_for_anyone}

CTF{rand_should_be_enough_for_anyone}

おわりに

Mの求め方を理解したときは感動しました（法 M上での 0を作ってGCDに使うとこ）．

以下が今回の検証（？）で使用したコードです．

from Crypto.Util.number import inverse, GCD, getRandomNBitInteger
from functools import reduce

class LCG:
    # X_{n+1} = (A \times X_n + B) \bmod M
    A = 9605000926055143081 # multiplier
    B = 9749676397194673813 # increment
    M = 18446744073709551615 # modulus

    def __init__(self, seed):
        # start value
        self.state = seed

    def next(self):
        self.state = (self.A * self.state + self.B) % self.M
        return self.state

    def get_parameters(self):
        return self.A, self.B, self.M

def prediction_test(PRNGs, states, A, B, M):
    next_value = PRNGs.next()
    predicted_value = (A * states[-1] + B) % M

    for i, state in enumerate(states):
        print('X_{0}: {1}'.format(i, state))

    print('\nnext value: {}'.format(next_value))
    print('predicted value: {}'.format(predicted_value))

    if next_value == predicted_value:
        print('correct!')
    else:
        print('incorrect!')

def output_example():
    states = [114514]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    A, B, M = PRNGs.get_parameters()

    prediction_test(PRNGs, states, A, B, M)

def solve_unknown_increment(states, A, M):
    B = (states[1] - A * states[0]) % M
    return B

def test_unknown_increment():
    print('test for unknown increment')
    states = [getRandomNBitInteger(64)]
    # states = [17460462356393494334]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())

    A, _, M = PRNGs.get_parameters()
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

def solve_unknown_multiplier(states, M):
    A = (states[2] - states[1]) * inverse((states[1] - states[0]), M)
    return A

def test_unknown_multiplier():
    print('test for unknown increment and multiplier')
    states = [getRandomNBitInteger(64)]
    # states = [16957592306608621537]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    _, _, M = PRNGs.get_parameters()
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

def solve_unknown_modulus(states):
    diffs = [X_1 - X_0 for X_0, X_1 in zip(states, states[1:])]
    multiples_of_M = [T_2 * T_0 - T_1 ** 2 for T_0, T_1, T_2, in zip(diffs, diffs[1:], diffs[2:])]

    # GCD(GCD(multiples_of_M[0],multiples_of_M[1]), multiples_of_M[2])
    M = reduce(GCD, multiples_of_M)
    return M

def test_unknown_modulus():
    print('test for unknown increment, multiplier and modulus')
    states = [getRandomNBitInteger(64)]
    # states = [12489966254767023172]
    PRNGs = LCG(states[0])
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())
    states.append(PRNGs.next())

    M = solve_unknown_modulus(states)
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    prediction_test(PRNGs, states, A, B, M)

def solve_mentalist():
    states = [9726918447512, 46628235778441, 46641741588810, 26970189847019, 58978496575468, 18214530370557]

    M = solve_unknown_modulus(states)
    A = solve_unknown_multiplier(states, M)
    B = solve_unknown_increment(states, A, M)

    next_value = (A * states[-1] + B) % M
    print(next_value)
    next_value = (A * next_value + B) % M
    print(next_value)

def main():
    output_example()
    # test_unknown_increment()
    # test_unknown_multiplier()
    # test_unknown_modulus()
    # solve_mentalist()

if __name__ == '__main__':
    main()

参考文献

コンテスト中にこれをみて Mの求め方を知りました．