Skip to content

Instantly share code, notes, and snippets.

@hakatashi
Last active October 11, 2022 07:34
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save hakatashi/67d04f55e29b44982da4db260fe17757 to your computer and use it in GitHub Desktop.
Save hakatashi/67d04f55e29b44982da4db260fe17757 to your computer and use it in GitHub Desktop.
#kurenaifChallenge solvers
def modinv(a, m)
m0, inv, x0 = m, 1, 0
while a > 1
inv -= (a / m) * x0
a, m = m, a % m
inv, x0 = x0, inv
end
inv += m0 if inv < 0
inv
end
e = 65537
n = 7504521114311153672308826977564891107288058227100173341193360340321176562970983694756086045753375611733443716948010092176135133045533366956059169702726409
c = 3120246791506259955679234385495683489853187127801200033777823093969698684663885288175101358075188702658492281935014546035799989917015048182861857825663454
p = (1..n).bsearch {|i| i * i >= n}
phi = p * p - p
d = modinv(e, phi)
m = c.pow(d, n)
puts([m.to_s(16)].pack('H*'))
# Flag: kurenaifCTF{phi_is_not_p-1_p-1}
def modinv(a, m)
m0, inv, x0 = m, 1, 0
while a > 1
inv -= (a / m) * x0
a, m = m, a % m
inv, x0 = x0, inv
end
inv += m0 if inv < 0
inv
end
N = 8208175638972200577186038102634114258848486365767463332763957381946985480397227219800325703361508208728778216773973313756762762324416016301819271949512427
c3 = 510199524103978915755062119293765889950938959100085136114101960072728304594090942964306874023123457091885387418124063977610496306587745044542739034336862
c65537 = 4673531855283872496727093452348048121242854682829577660566947295656149440028839210065857595110277181842297946378296819272562912619683355333762343087859186
target = (65537 * 2 - 1) / 3
a = c3.pow(target, N)
b = c65537.pow(2, N)
inv_a = modinv(a, N)
m = b * inv_a % N
puts [m.to_s(16)].pack('H*')
# Flag: kurenaifCTF{you_4re_redundant_master}
from Crypto.Util.number import *
from Crypto.Cipher import AES
x5 = 74994485449019875805749743810715945771
key = x5
nonce = b'\x0b:\xce<\xb0\xe8@,'
ct_bytes = b'\\\x8f\xfayc\xce\xfc<`\xc7\xe1\x91Jh\x0c6 \x8a\xd8\x0f\xdc^\xa3\xb9\xa1Kv\x96O<\xbcx\x8e\xea\xc3&'
cipher_dec = AES.new(long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
print(cipher_dec.decrypt(ct_bytes))
# Flag: kurenaifCTF{Less_numbers_are_better}
require 'openssl'
def modinv(a, m)
m0, inv, x0 = m, 1, 0
while a > 1
inv -= (a / m) * x0
a, m = m, a % m
inv, x0 = x0, inv
end
inv += m0 if inv < 0
inv
end
x0 = 171988490999968958074461906163126253991
x1 = 149759767375550138601832127658924300851
x2 = 21392649857558566532141954695914673807
x3 = 52236160143411890255640980579270361316
x4 = 22081153611165744867415455406756477578
r0 = x1 - x0
r1 = x2 - x1
r2 = x3 - x2
r3 = x4 - x3
m1 = r0 * r3 - r1 * r2
m2 = r0 * r2 - r1 * r1
puts(m1.gcd(m2))
m = 176112297761995517109581492781981180247
x = x0
a = r1 * modinv(r0 % m, m) % m
b = (x1 - a * x) % m
puts(x1)
puts((a * x + b) % m)
puts(x2)
puts((a * x1 + b) % m)
puts(x3)
puts((a * x2 + b) % m)
x5 = (a * x4 + b) % m
puts("x5 = #{x5}")
from z3 import *
m = 16411099384203967235
cipher = 258578933248047129070234127076818734931906736562394908260192233729045538766864090271939203007290696772322321
bits = [0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]
x = Int('x')
initial_x = x
s = Solver()
s.add(x < m)
for bit in bits:
if bit == 0:
s.add(x * 2 < m)
x = x * 2
else:
s.add(x * 2 >= m)
x = x * 2 - m
print('Solving...')
assert s.check() == sat
model = s.model()
x = model[initial_x].as_long()
print(x)
rev_bits = []
rev2 = (m + 1) // 2
for i in range(311 - len('kurenaifCTF') * 8):
rev_bits.append(str(x % 2))
x = x * rev2 % m
mask = ''.join(map(str, bits[::-1])) + ''.join(rev_bits)
print(mask)
print(bin(cipher))
print((int(mask, 2) ^ cipher).to_bytes(1000, 'big'))
# Flag: kurenaifCTF{lowest_bit_oracle_is_funny}
m = 16411099384203967235
length = 311
cipher = 258578933248047129070234127076818734931906736562394908260192233729045538766864090271939203007290696772322321
d = 'kurenaifCTF'.unpack1('H*').hex << ((length + 1) - 'kurenaifCTF'.size * 8)
b_str = (cipher ^ d).to_s(2).rjust(length + 50, '0')
bs = b_str.chars.map(&:to_i)
p bs[0...'kurenaifCTF'.size * 8 + 50].reverse
#!/usr/bin/env python3.7
# Charles Fol
# @cfreal_
# 2020-01-04 (originally la long time ago ~ 2010)
# Breaking mt_rand() with two output values and no bruteforce.
#
"""
R = final rand value
S = merged state value
s = original state value
"""
import random
import sys
N = 624
M = 397
MAX = 0xffffffff
MOD = MAX + 1
# STATE_MULT * STATE_MULT_INV = 1 (mod MOD)
STATE_MULT = 1812433253
STATE_MULT_INV = 2520285293
MT_RAND_MT19937 = 1
MT_RAND_PHP = 0
def php_mt_initialize(seed):
"""Creates the initial state array from a seed.
"""
state = [None] * N
state[0] = seed & 0xffffffff;
for i in range(1, N):
r = state[i-1]
state[i] = ( STATE_MULT * ( r ^ (r >> 30) ) + i ) & MAX
return state
def undo_php_mt_initialize(s, p):
"""From an initial state value `s` at position `p`, find out seed.
"""
# We have:
# state[i] = (1812433253U * ( state[i-1] ^ (state[i-1] >> 30) + i )) % 100000000
# and:
# (2520285293 * 1812433253) % 100000000 = 1 (Modular mult. inverse)
# => 2520285293 * (state[i] - i) = ( state[i-1] ^ (state[i-1] >> 30) ) (mod 100000000)
for i in range(p, 0, -1):
s = _undo_php_mt_initialize(s, i)
return s
def _undo_php_mt_initialize(s, i):
s = (STATE_MULT_INV * (s - i)) & MAX
return s ^ s >> 30
def php_mt_rand(s1):
"""Converts a merged state value `s1` into a random value, then sent to the
user.
"""
s1 ^= (s1 >> 11)
s1 ^= (s1 << 7) & 0x9d2c5680
s1 ^= (s1 << 15) & 0xefc60000
s1 ^= (s1 >> 18)
return s1
def undo_php_mt_rand(s1):
"""Retrieves the merged state value from the value sent to the user.
"""
s1 ^= (s1 >> 18)
s1 ^= (s1 << 15) & 0xefc60000
s1 = undo_lshift_xor_mask(s1, 7, 0x9d2c5680)
s1 ^= s1 >> 11
s1 ^= s1 >> 22
return s1
def undo_lshift_xor_mask(v, shift, mask):
"""r s.t. v = r ^ ((r << shift) & mask)
"""
for i in range(shift, 32, shift):
v ^= (bits(v, i - shift, shift) & bits(mask, i, shift)) << i
return v
def bits(v, start, size):
return lobits(v >> start, size)
def lobits(v, b):
return v & ((1 << b) - 1)
def bit(v, b):
return v & (1 << b)
def bv(v, b):
return bit(v, b) >> b
def php_mt_reload(state, flavour):
s = state
for i in range(0, N - M):
s[i] = _twist_php(s[i+M], s[i], s[i+1], flavour)
for i in range(N - M, N - 1):
s[i] = _twist_php(s[i+M-N], s[i], s[i+1], flavour)
def _twist_php(m, u, v, flavour):
"""Emulates the `twist` and `twist_php` #defines.
"""
mask = 0x9908b0df if (u if flavour == MT_RAND_PHP else v) & 1 else 0
return m ^ (((u & 0x80000000) | (v & 0x7FFFFFFF)) >> 1) ^ mask
def undo_php_mt_reload(S000, S227, offset, flavour):
#define twist_php(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
# m S000
# u S227
# v S228
X = S000 ^ S227
# This means the mask was applied, and as such that S227's LSB is 1
s22X_0 = bv(X, 31)
# remove mask if present
if s22X_0:
X ^= 0x9908b0df
# Another easy guess
s227_31 = bv(X, 30)
# remove bit if present
if s227_31:
X ^= 1 << 30
# We're missing bit 0 and bit 31 here, so we have to try every possibility
s228_1_30 = (X << 1)
for s228_0 in range(2):
for s228_31 in range(2):
if flavour == MT_RAND_MT19937 and s22X_0 != s228_0:
continue
s228 = s228_0 | s228_31 << 31 | s228_1_30
# Check if the results are consistent with the known bits of s227
s227 = _undo_php_mt_initialize(s228, 228 + offset)
if flavour == MT_RAND_PHP and bv(s227, 0) != s22X_0:
continue
if bv(s227, 31) != s227_31:
continue
# Check if the guessed seed yields S000 as its first scrambled state
rand = undo_php_mt_initialize(s228, 228 + offset)
state = php_mt_initialize(rand)
php_mt_reload(state, flavour)
if not (S000 == state[offset]):
continue
return rand
return None
def undo_php_mt_reload_candidates(S000, S227, flavour):
#define twist_php(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))
# m S000
# u S227
# v S228
X = S000 ^ S227
# This means the mask was applied, and as such that S227's LSB is 1
s22X_0 = bv(X, 31)
# remove mask if present
if s22X_0:
X ^= 0x9908b0df
# Another easy guess
s227_31 = bv(X, 30)
# remove bit if present
if s227_31:
X ^= 1 << 30
# We're missing bit 0 and bit 31 here, so we have to try every possibility
s228_1_30 = (X << 1)
candidates = []
for s228_0 in range(2):
for s228_31 in range(2):
if flavour == MT_RAND_MT19937 and s22X_0 != s228_0:
continue
s228 = s228_0 | s228_31 << 31 | s228_1_30
candidates.append(s228)
return candidates
def main(_R000, _R227, _R454):
# Both were >> 1, so the leftmost byte is unknown
_R000 <<= 1
_R227 <<= 1
_R454 <<= 1
flavour = MT_RAND_MT19937
for R000_0 in range(2):
for R227_0 in range(2):
for R454_0 in range(2):
R000 = _R000 | R000_0
R227 = _R227 | R227_0
R454 = _R454 | R454_0
S000 = undo_php_mt_rand(R000)
S227 = undo_php_mt_rand(R227)
S454 = undo_php_mt_rand(R454)
candidates228 = undo_php_mt_reload_candidates(S000, S227, flavour)
candidates455 = undo_php_mt_reload_candidates(S227, S454, flavour)
for S228 in candidates228:
for S455 in candidates455:
seed = undo_php_mt_reload(S228, S455, 228, flavour)
if seed:
print(seed)
def test_do_undo(do, undo):
for i in range(10000):
rand = random.randrange(1, MAX)
done = do(rand)
undone = undo(done)
if not rand == undone:
print(f"-- {i} ----")
print(bin(rand).rjust(34))
print(bin(undone).rjust(34))
break
def test():
test_do_undo(
php_mt_initialize,
lambda s: undo_php_mt_initialize(s[227], 227)
)
test_do_undo(
php_mt_rand,
undo_php_mt_rand
)
exit()
main(1355541750, 602658525, 173373131)
#test()
'''
if len(sys.argv) < 5:
print('Finds out a PHP mt_rand() seed from two outputs of mt_rand()'
' separated by 226 other calls.')
print('')
print('Usage:')
print(f' {sys.argv[0]} <rand_n+0> <rand_n+227> <n> <flavour>')
print('')
print('Parameters:')
print(' rand_n+0: First random value')
print(' rand_n+227: Second random value')
print(' The second value comes 226 mt_rand() calls after the first.')
print(' n: Number of mt_rand() calls in between the seeding and')
print(' the first value (rand_n+0)')
print(' flavour: 0 (PHP5) or 1 (PHP7+)')
else:
main(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]), int(sys.argv[4]))
'''
# Flag: kurenaifCTF{twice_reloaded_mersenne_twister}
# おまけ: kusanoさんのwriteupのwriteup
# https://gist.github.com/kusano/77517989fba0ef9ffe5f8ef3011250bf
P = [44, 10, 51, 19, 52, 6, 50, 37, 54, 28, 21, 4, 39, 20, 2, 14, 41, 33, 27, 47, 46, 26, 12, 53, 30, 45, 17, 9, 40, 18, 22, 5, 13, 49, 42, 1, 23, 0, 25, 8, 38, 15, 36, 48, 29, 16, 7, 32, 3, 43, 31, 35, 11, 34, 24]
n = 3537944106486801125155649656134775533156182452977359703205130657340880206428445301432948612127316920
url = 'ai8mt:/tq7kcat/b.reddpno_3i52/vac5/53iu7ps6k/tco8b8hs51'
G = PermutationGroup([Permutation([i + 1 for i in P])])
perm = G.gen() ^ -n
projection = perm.tuple()
print(''.join([url[i - 1] for i in projection]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment