Last active
October 11, 2022 07:34
-
-
Save hakatashi/67d04f55e29b44982da4db260fe17757 to your computer and use it in GitHub Desktop.
#kurenaifChallenge solvers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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}") |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# おまけ: 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