Snippets
Created by
Masafumi Yabu
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 | # coding: ASCII-8BIT
require 'ctf'
S = [ 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2, 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16]
INVS = [ 0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB, 0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB, 0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E, 0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25, 0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92, 0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84, 0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06, 0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B, 0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73, 0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E, 0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B, 0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4, 0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F, 0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF, 0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61, 0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D ]
Lper,Luper=[51, 43, 42, 47, 19, 49, 10, 23, 18, 11, 1, 60, 24, 31, 40, 54, 12, 56, 38, 59, 52, 6, 50, 13, 53, 34, 27, 17, 2, 3, 29, 26, 21, 30, 62, 20, 45, 16, 39, 28, 48, 35, 15, 22, 63, 58, 32, 57, 25, 33, 14, 36, 44, 37, 0, 8, 41, 5, 7, 9, 55, 46, 4, 61], [54, 10, 28, 29, 62, 57, 21, 58, 55, 59, 6, 9, 16, 23, 50, 42, 37, 27, 8, 4, 35, 32, 43, 7, 12, 48, 31, 26, 39, 30, 33, 13, 46, 49, 25, 41, 51, 53, 18, 38, 14, 56, 2, 1, 52, 36, 61, 3, 40, 5, 22, 0, 20, 24, 15, 60, 17, 47, 45, 19, 11, 63, 34, 44]
def subStr(toSub)
toSub.unpack("C*").map{|a|S[a].chr}.join
end
def unSubStr(toSub)
toSub.unpack("C*").map{|a|INVS[a].chr}.join
end
def permute(str)
p1 = str.unpack("Q")[0]
[64.times.inject(0){ |o, i| o |= ((p1 & (1 << i)) >> i) << Lper[i]}].pack('Q')
end
def unpermute(str)
p1 = str.unpack("Q")[0]
[64.times.inject(0){ |o, i| o |= ((p1 & (1 << i)) >> i) << Luper[i]}].pack('Q')
end
def encrypt(str, key)
k1, k2, k3 = key.chars.each_slice(8).map{|a|a.join}
k3.reverse!
str.chars.each_slice(8).map{|a|a.join}.map do |str|
# stage1
str = permute(subStr(str ^ k1))
# stage2
str = permute(subStr(str ^ k2))
# stage3
str.reverse!
[(str.unpack("Q")[0] + k3.unpack("Q")[0]) % (2**64-1)].pack("Q")
end.inject(:+)
end
def inv_stage1(str, key)
unSubStr(unpermute(str)) ^ key[0, 8]
end
def solve2(x, y, z, eql_mode)
# (x - k) ^ (y - k) & z == (x - k) ^ (y - k)になるkが存在するかどうか。eql_modeがtrueの時は(x-k)^(y-k) = zになるkが存在するかどうか
state = [true, false, false, false]
65.times do |i|
nstate = [false, false, false, false]
xbit = x >> i & 1
ybit = y >> i & 1
state.each.with_index.select{|a,_|a}.each do |_,j|
kx = (j >> 0 & 1)
ky = (j >> 1 & 1)
next if kx ^ ky ^ xbit ^ ybit != 0 && z >> i & 1 == 0
next if kx ^ ky ^ xbit ^ ybit != 1 && z >> i & 1 == 1 && eql_mode
nkx = (xbit == 0 && kx == 1) ? 1 : 0
nky = (ybit == 0 && ky == 1) ? 1 : 0
nstate[(nkx << 0) | (nky << 1)] = true
nkx = (xbit == 1 && kx == 0) ? 0 : 1
nky = (ybit == 1 && ky == 0) ? 0 : 1
nstate[(nkx << 0) | (nky << 1)] = true
end
return false if nstate.none? # もう駄目
state = nstate
end
return true
end
def solve(x, y, z, eql = false, m = 2 ** 64 - 1)
solve2(x, y, z, eql) || solve2(x + m, y, z, eql) || solve2(x, y + m, z, eql) || solve2(x + m, y + m, z, eql)
end
if ARGV.size >= 2 # 引数があるなら通信してKeyを得る
require 'digest/sha1'
def encrypt(str, key)
begin
s = TCPSocket.open(ARGV[0], ARGV[1])
start = s.expect(/with ([A-Za-z0-9\/+=]{16})/)[1]
puts 'Encrypting length: %d ' % str.size
while true
rand = Array.new(5){[*'a'..'z'].sample}.join
if Digest::SHA1.hexdigest(start + rand).end_with?('ffff')
s.print start + rand
s.flush
break
end
end
s.print [str.size].pack("s")
s.print str
s.expect("'")
ret = s.expect(/[^\\]'/)[0][0..-2]
ret = ret.gsub(/\\(x[0-9a-f]{2}|[a-w'\\])/) do |c|
eval "\"#{c}\""
end
fail unless ret.size == str.size
return ret
rescue => e
sleep 12
retry
end
end
end
KEY = 'The fifty secret letters' # ローカルテスト用のkey
key = ''
# 最初の8文字を特定する。一回目のsubStr後に1bitの差が出た時に、どこが変化しうるか(bit1, bit2)を求め、それと合致しているようなjを求める。
8.times do |i|
bit1 = bit2 = 0
256.times do |s|
str3 = (str2 = (str1 = "X" * 8).dup).dup
str1[i] = s.chr
str2[i] = (s^1).chr
str3[i] = (s^2).chr
b1 = permute(str1) ^ permute(str2)
b2 = permute(str1) ^ permute(str3)
idx1 = /[\x01-\xff]/ =~ b1
idx2 = /[\x01-\xff]/ =~ b2
str1[idx1] = s.chr
str2[idx2] = s.chr
bit1 |= (permute(subStr(str1)) ^ permute(subStr(str1 ^ b1))).reverse.unpack("Q*")[0]
bit2 |= (permute(subStr(str2)) ^ permute(subStr(str2 ^ b2))).reverse.unpack("Q*")[0]
end
e_all = ''
256.times do |j|
4.times do
s3 = (s2 = (s1 = Array.new(8){rand(256).chr}.join).dup).dup
s1[i] = j.chr ^ INVS[0]
s2[i] = j.chr ^ INVS[1]
s3[i] = j.chr ^ INVS[2]
e_all << s1 << s2 << s3
end
end
e_all = encrypt(e_all, KEY)
256.times do |j|
ok = true
4.times do
d1 = e_all[0,8].unpack("Q*")[0]
d2 = e_all[8,8].unpack("Q*")[0]
d3 = e_all[16,8].unpack("Q*")[0]
e_all = e_all[24..-1]
ok = false unless solve(d1, d2, bit1) && solve(d1, d3, bit2)
end
key << j.chr if ok
end
end
print "Stage1: "
p key
8.times do |i|
str3 = (str2 = (str1 = "\0" * 8).dup).dup
str1[i] = ?B
str2[i] = ?C
str3[i] = ?D
p1 = permute(subStr(str1)).reverse.unpack('Q')[0]
p2 = permute(subStr(str2)).reverse.unpack('Q')[0]
p3 = permute(subStr(str3)).reverse.unpack('Q')[0]
e_all = ''
256.times do |j|
4.times do
s3 = (s2 = (s1 = ?0 * 8).dup).dup
s1[i] = j.chr ^ ?B
s2[i] = j.chr ^ ?C
s3[i] = j.chr ^ ?D
e_all << inv_stage1(s1, key) << inv_stage1(s2,key) << inv_stage1(s3, key)
end
end
e_all = encrypt(e_all, KEY)
256.times do |j|
ok = true
4.times do
d1 = e_all[0, 8].unpack('Q')[0]
d2 = e_all[8, 8].unpack('Q')[0]
d3 = e_all[16, 8].unpack('Q')[0]
e_all = e_all[24..-1]
ok = false unless solve(d1, d2, p1 ^ p2, true) && solve(d1, d3, p1 ^ p3, true)
end
key << j.chr if ok
end
end
print "Stage2: "
p key
# Stage2までで"\0\0\0\0\0\0\0\0"になるような暗号文を作るとStage3のキーがそのまま(逆順で)出てくる
s = inv_stage1(inv_stage1("\0" * 8, key[8, 8]), key)
key << encrypt(s, KEY).reverse
print "Stage3: "
p key
|
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.