Zh3r0 CTF V2 | Real Mersenne

zh3ro_ctf_2021 mersenne_twister ieee_754 bit欠落したmersenne_twister z3

#zh3ro_CTF_2021

import random
from secret import flag
from fractions import Fraction

def score(a,b):
    if abs(a-b)<1/2**10:
        # capping score to 1024 so you dont get extra lucky
        return Fraction(2**10)
    return Fraction(2**53,int(2**53*a)-int(2**53*b))

total_score = 0
for _ in range(2000):
    try:
        x = random.random()
        y = float(input('enter your guess:\n'))
        round_score = score(x,y)
        total_score+=float(round_score)
        print('total score: {:0.2f}, round score: {}'.format(
            total_score,round_score))
        if total_score>10**6:
            print(flag)
            exit(0)
    except:
        print('Error, exiting')
        exit(1)
else:
    print('Maybe better luck next time')

  • Mersenne Twister で値を予測する系だが、予測対象が random.random になっている。 pythonのrandom.randomの実装 は↓のように64bit生成して11bit落とす、という感じになっている。利用するのが53bitなのは IEEE 754 の倍精度のfraction（仮数部）がその値だから

    • static PyObject *
_random_Random_random_impl(RandomObject *self)
/*[clinic end generated code: output=117ff99ee53d755c input=afb2a59cbbb00349]*/
{
    uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;
    return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}

    • 9007199254740992 == 2^53 , 67108864 == 2^26

    • ということで x が得られた値として x * 2^53 したあと下27bit、上28bitに分けるとそれぞれ b >> 6 , a >> 5 が手に入る

  • さてそれでは Bit欠落したMersenne Twister を復元できるのかと言うと…… z3 power でできる（場合もある）

  • 過去の MeePwn 2018 | StillOldSchool でも出題されていた