namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

DES暗号を実装する(2) ~データ暗号化・復号編~

前回はサブ鍵の構成方法について説明しましたが, 今回はデータの暗号化と復号アルゴリズムについて見ていきましょう.

データ暗号化・復号アルゴリズム

早速アルゴリズムを以下に示したいと思います. 暗号化と復号ではほぼ同じアルゴリズムを使用することができます.

データ暗号化アルゴリズム

入力:平文 m (64bit), サブ鍵 k_1, k_2, ..., k_{16} (それぞれ48bit)
出力:暗号文 c (64bit)

(1) n = 1とする.

(2) 平文 mに初期転置 IPを適用します.

(3) 左右に2分割し, 左の32bitを L_0, 右の32bitを R_0とします.

(4)  n \leq 16の間, 次の処理を繰り返します.

 \ \  (4-1)  R_{n-1}とサブ鍵 k_nを入力して, ラウンド関数 fを計算します. ( fについては後述)

 \ \ (4-2)  L_{n-1} y排他的論理和を取り, それを L_n'とします.  R_n' R_{n-1}と同じです.


 L_n' = L_{n-1} \oplus y
 R_n' = R_{n-1}

 \ \ (4-3) n = 16でなければ, 左右32bitごとを入れ替えます.


 L_n = R_n'
 R_n = L_n'

 \ \ (4-4) n = n + 1とします.

(5)  L_{16} R_{16}を連結して, 最終転置 IP^{-1}を適用して出力します.

f:id:tomonori4565:20181211125907p:plain
データ暗号化アルゴリズム

データ復号アルゴリズム

入力:暗号文 c (64bit), サブ鍵 k_1, k_2, ..., k_{16} (それぞれ48bit)
出力:平文 m (64bit)

(1) n = 1とする.

(2) 平文 mに初期転置 IPを適用します.

(3) 左右に2分割し, 左の32bitを L_0, 右の32bitを R_0とします.

(4)  n \leq 16の間, 次の処理を繰り返します.

 \ \ (4-3) n = 1でなければ, 左右32bitごとを入れ替えます.


 L_n = R_n'
 R_n = L_n'

 \ \  (4-1)  R_{n-1}とサブ鍵 k_nを入力して, ラウンド関数 fを計算します. ( fについては後述)

 \ \ (4-2)  L_{n-1} y排他的論理和を取り, それを L_n'とします.  R_n' R_{n-1}と同じです.


 L_n' = L_{n-1} \oplus y
 R_n' = R_{n-1}

 \ \ (4-4) n = n + 1とします.

(5)  L_{16} R_{16}を連結して, 最終転置 IP^{-1}を適用して出力します.


転置 IP, IP^{-1}

上記のアルゴリズムで使用する IP, IP^{-1}の正体は以下の通りとなっています.

f:id:tomonori4565:20181211131057p:plainf:id:tomonori4565:20181211131108p:plain
初期転置 IP (青), 最終転置 IP^{-1} (橙)

最終転置は初期転置の逆転置であり, 次の関係式を満たします.


 IP(IP^{-1}(x)) = x

ラウンド関数 f

上記アルゴリズムで使用されているラウンド関数は非線形関数であり, この関数 fの設計が暗号的強度に大きな影響を与えます.

ラウンド関数 fアルゴリズム

入力: R(32bit), サブ鍵 k (48bit)
出力:演算結果 (32bit)

(1) Rに拡大転置 Eを適用して, 鍵と同じ48bitにします.


 R' = E(R)

(2)得られたデータとサブ鍵の排他的論理和を取ります.


 R'' = R' \oplus k

(3) R''を6bitごとに分割して8個のグループを作成します. 各グループに対して, S-box変換 S_nを適用することで, 6bitを4bitに変換します. 得られた結果を全て連結することで32bitの R'''が得られます.


 R''' = S(R'')

(4)出力転置 Pを適用し, 結果を出力します.

拡大転置 E, 出力転置 P

拡大転置 Eと出力転置 Pは以下のようになっています.

f:id:tomonori4565:20181211134514p:plain
拡大転置 E

f:id:tomonori4565:20181211134540p:plain
出力転置 P

S-boxの仕組み

S-boxの転置表は以下のサイトに載っています(自分で作るのは流石に大変すぎた).
kazukichi.hatenablog.jp

コード

import math
import random

pc1_table = [57,49,41,33,25,17,9,
            1,58,50,42,34,26,18,
            10,2,59,51,43,35,27,
            19,11,3,60,52,44,36,
            63,55,47,39,31,23,15,
            7,62,54,46,38,30,22,
            14,6,61,53,45,37,29,
            21,13,5,28,20,12,4]

pc2_table = [14,17,11,24,1,5,
            3,28,15,6,21,10,
            23,19,12,4,26,8,
            16,7,27,20,13,2,
            41,52,31,37,47,55,
            30,40,51,45,33,48,
            44,49,39,56,34,53,
            46,42,50,36,29,32]

E = [32,1,2,3,4,5,
    4,5,6,7,8,9,
    8,9,10,11,12,13,
    12,13,14,15,16,17,
    16,17,18,19,20,21,
    20,21,22,23,24,25,
    24,25,26,27,28,29,
    28,29,30,31,32,1]

P = [16,7,20,21,
    29,12,28,17,
    1,15,23,26,
    5,18,31,10,
    2,8,24,14,
    32,27,3,9,
    19,13,30,6,
    22,11,4,25]

S1 = [[14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
      [0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
      [4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
      [15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13]]

S2 = [[15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
      [3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
      [0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
      [13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9]]

S3 = [[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
      [13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
      [13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
      [1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12]]

S4 = [[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
      [13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
      [10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
      [3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14]]

S5 = [[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
      [14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
      [4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
      [11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3]]

S6 = [[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
      [10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
      [9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
      [4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13]]

S7 = [[4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
      [13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
      [1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],
      [6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12]]

S8 = [[13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
      [1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
      [7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
      [2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]]

S_list = [S1, S2, S3, S4, S5, S6, S7, S8]

IP = [58,50,42,34,26,18,10,2,
     60,52,44,36,28,20,12,4,
     62,54,46,38,30,22,14,6,
     64,56,48,40,32,24,16,8,
     57,49,41,33,25,17,9,1,
     59,51,43,35,27,19,11,3,
     61,53,45,37,29,21,13,5,
     63,55,47,39,31,23,15,7]

IP_inverse = [40,8,48,16,56,24,64,32,
             39,7,47,15,55,23,63,31,
             38,6,46,14,54,22,62,30,
             37,5,45,13,53,21,61,29,
             36,4,44,12,52,20,60,28,
             35,3,43,11,51,19,59,27,
             34,2,42,10,50,18,58,26,
             33,1,41,9,49,17,57,25]

bit_list = [0,1]

#
# odd_parity()
# 入力:リストl
# 出力:0 or 1
# lにおけるハミング重みが奇数個ならば0, 偶数個ならば1
#
def odd_parity(l):
    odd_count = 0
    for l_bit in l:
        if l_bit == 1:
            odd_count += 1

    if (odd_count % 2 == 0):
        return 1
    else:
        return 0

#
# key_generate()
# 入力:なし
# 出力:秘密鍵64bit
# 秘密鍵を生成する.
#
def key_generate():
    key = []
    for i in range(8):
        l = random.choices(bit_list, k=7)
        key += l
        key.append(odd_parity(l))

    return key

#
# PC1
# 入力:配列secret_key...64bit
# 出力: C0, D0...それぞれ28bit
# C0は左28bit, D0は右28bit
#
def pc1(secret_key):
    c0 = []
    d0 = []
    for i in range(56):
        if i <= 27:
            c0.append(secret_key[pc1_table[i]-1])
        else:
            d0.append(secret_key[pc1_table[i]-1])
    return c0, d0

#
# PC2
# 入力:配列c_d_list(C0とD0を連結させたもの)...56bit
# 出力: k 48bit
#
def pc2(c_d_list):
    k = []
    for i in range(48):
        k.append(c_d_list[pc2_table[i]-1])

    return k


#
# shift
# 入力:リストl, 移動ビット数n
# 出力:巡回シフト結果
#
def shift(l, n):
    return l[n:] + l[:n]


#
# sub_key_generate()
# 入力: 秘密鍵key(64bit)
# 出力:sub_key_list
#
def enc_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if (i == 1) or (i == 2) or (i == 9) or (i == 16):
            c = shift(c, 1)
            d = shift(d, 1)
        else:
            c = shift(c, 2)
            d = shift(d, 2)
        sub_key_list.append(pc2(c + d))

    return sub_key_list


#
# dec_sub_key_generate()
# 入力:秘密鍵key(64bit)
# 出力:sub_key_list
#
def dec_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if i == 1:
            c = c
            d = d
        elif (i == 2) or (i == 9) or (i == 16):
            c = shift(c, -1)
            d = shift(d, -1)
        else:
            c = shift(c, -2)
            d = shift(d, -2)
        sub_key_list.append(pc2(c + d))

    return sub_key_list


#
# xorを計算
#
def calc_xor(x, k):
    if (x == k):
        return 0
    else:
        return 1

#
# 10進数numを2進数に変換して配列に格納(4bitで固定)
#
def calc_binary(num):
    list = []
    while num > 0:
        list.append(num % 2)
        num = num // 2

    while len(list) != 4:
        list.append(0)

    list.reverse()
    return list

#
# ラウンド関数f
# 入力:x(32bit), サブ鍵k(48bit)
# 出力:y(計算結果, 32bit)
#
def f(x, k):

    x1 = []
    x2 = []
    x3 = []
    y = []
    for i in range(48):
        x1.append(x[E[i]-1])

    for x1_item, k_item in zip(x1, k):
        x2.append(calc_xor(x1_item, k_item))

    for i in range(0, 48, 6):
        arg1 = (i//6)
        arg2 = x2[i+0] * 2 + x2[i+5] * 1
        arg3 = x2[i+1] * 8 + x2[i+2] * 4 + x2[i+3] * 2 + x2[i+4] * 1
        x3 = x3 + calc_binary(S_list[arg1][arg2][arg3])

    for i in range(32):
        y.append(x3[P[i]-1])

    return y

#
# 暗号化アルゴリズム
#
def encryption(m, sub_key_list):
    n = 1

    m_list = []
    for i in range(64):
        m_list.append(m[IP[i]-1])

    L = m_list[:32]
    R = m_list[32:]

    for k in sub_key_list:
        y = f(R, k)
        for i in range(32):
            L[i] = calc_xor(L[i], y[i])
        if n != 16:
            L, R = R, L
        n += 1

    c = []
    LR = L + R
    for i in range(64):
        c.append(LR[IP_inverse[i]-1])

    return c

#
# 復号化アルゴリズム
#
def decryption(c, reverse_sub_key_list):
    n = 1

    c_list = []
    for i in range(64):
        c_list.append(c[IP[i]-1])

    L = c_list[:32]
    R = c_list[32:]

    for k in reverse_sub_key_list:
        if n != 1:
            L, R = R, L
        y = f(R, k)
        for i in range(32):
            L[i] = calc_xor(L[i], y[i])
        n += 1

    m = []
    LR = L + R
    for i in range(64):
        m.append(LR[IP_inverse[i]-1])

    return m


#
# メイン関数
#
if __name__ == '__main__':

    tmp = []
    for i in range(1, 65):
        tmp.append(i % 10)

    #print(tmp)
    m = random.choices(bit_list, k=64)
    print(m)

    key = key_generate()
    sub_key_list = enc_sub_key_generate(key)
    reverse_sub_key_list = dec_sub_key_generate(key)

    c = encryption(m, sub_key_list)
    m = decryption(c, reverse_sub_key_list)

    print(c)
    print(m)

出力結果

上から, 「ビット桁表示」, 「元の平文 m」, 「暗号文 c」, 「暗号文を復号した結果 m'

python des.py 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4]
[0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1]

まとめ

元の平文と暗号文を復号した結果が一致しているので, DESを実装することができた. 気が向いたらDESの仕組みをもっと掘り下げて説明したり, 危険性について説明していこうと思う(書いてる途中で挫折しそう).

DES暗号を実装する(1) ~サブ鍵生成アルゴリズム編~

共通鍵暗号方式の代表的な暗号方式である「DES暗号」を実装してみたいと思います.
今回の記事では, DESで使用する「サブ鍵」の生成アルゴリズムを実装していきます.

使用言語

Python 3系

DES暗号とは

DES暗号は, 「ブロック暗号」の一種です. 1977年ごろに開発され, 米国政府の標準暗号となりました. 1984年にはANSI(米国規格協会)によって, 民間標準規格となりました.

DES暗号については, 過去の記事で詳しく説明をしていますので, こちらを参照してください.
tomonori4565.hatenablog.com

サブ鍵の生成方法

DESでは秘密鍵(共通鍵)keyを入力として, 16個の「サブ鍵」というものを生成します. ここでサブ鍵の生成方法を見ていきましょう.

f:id:tomonori4565:20181210203717p:plainf:id:tomonori4565:20181210203722p:plain
サブ鍵の生成方法

まずkeyが入力されたら, PC1という縮小転置を実行します. PC1によって64bitのkeyは56bitに縮小されます. PC1は以下の転置表によって実行されます.

f:id:tomonori4565:20181210204053p:plain
縮小転置PC1の表

数式で表すと以下のようになります.  key = k_1k_2...k_{64}に対して,


 PC1(key) = PC1(k_1, k_2, ..., k_{64}) = (k_{57}, k_{49}, ..., k_{12}, k_{4})

PC1が実行されたら, 左28bit, 右28bitに分割し, それぞれ C_0, D_0とします.  C_0, D_0はそれぞれLSという手続きによって, 左に1ビット巡回シフトさせます(シフトし終わったものをそれぞれ C_1, D_1とします).

そして,  C_1, D_1を連結させたものをPC2という縮小転置に適用させ, 48bitのサブ鍵を生成します. PC2 は以下の転置表によって実行されます.

f:id:tomonori4565:20181210205044p:plain
縮小転置PC2の表

これらの動作を16ラウンド続けていきます.

ただ一点注意しておくことがあります. 左に1bit巡回シフトを実行するのは,1,2,9,16ラウンド目のときです. それ以外は左に2bit巡回シフトさせる必要があります.

サブ鍵生成アルゴリズム

入力
key:秘密鍵(64bit)
出力
 k_1, k_2, ..., k_{16}:サブ鍵(それぞれ48bit)

(1)64bitのkeyを56bitに変換する縮小転置PC1を適用.すなわち,


 (C_0, D_0) = PC1( key)

(2)  i = 1とする.

(3)  i \leq 16の間, 以下を繰り返す.

(3-1)  i = 1,2,9,16ならば左に1bit巡回シフトする. それ以外なら左に2bit巡回シフトする.


 C_i, D_i = (LS_i(C_{i-1}) , LS_i(D_{i-1}))

(3-2)  C_i, D_iを連結させ, 縮小転置PC2を適用. すなわち,


 k_i = PC2( C_i, D_i)

(3-3) i = i + 1とする.


(4)  k_1, k_2, ..., k_{16}を出力.

プログラム

各メソッドについてはコメントを参照してください.

import math
import random

pc1_table = [57,49,41,33,25,17,9,
            1,58,50,42,34,26,18,
            10,2,59,51,43,35,27,
            19,11,3,60,52,44,36,
            63,55,47,39,31,23,15,
            7,62,54,46,38,30,22,
            14,6,61,53,45,37,29,
            21,13,5,28,20,12,4]

pc2_table = [14,17,11,24,1,5,
            3,28,15,6,21,10,
            23,19,12,4,26,8,
            16,7,27,20,13,2,
            41,52,31,37,47,55,
            30,40,51,45,33,48,
            44,49,39,56,34,53,
            46,42,50,36,29,32]

bit_list = [0,1]

#
# odd_parity()
# 入力:リストl
# 出力:0 or 1
# リストlにおけるハミング重みが奇数個ならば0, 偶数個ならば1
#
def odd_parity(l):
    odd_count = 0
    for l_bit in l:
        if l_bit == 1:
            odd_count += 1

    if (odd_count % 2 == 0):
        return 1
    else:
        return 0

#
# key_generate()
# 入力:なし
# 出力:秘密鍵64bit
# 秘密鍵を生成する.
#
def key_generate():
    key = []
    for i in range(8):
        l = random.choices(bit_list, k=7)
        key += l
        key.append(odd_parity(l))

    return key

#
# PC1
# 入力:配列secret_key...64bit
# 出力: C0, D0...それぞれ28bit
# C0は左28bit, D0は右28bit
#
def pc1(secret_key):
    c0 = []
    d0 = []
    for i in range(56):
        if i <= 27:
            c0.append(secret_key[pc1_table[i]-1])
        else:
            d0.append(secret_key[pc1_table[i]-1])
    return c0, d0

#
# PC2
# 入力:配列c_d_list(C0とD0を連結させたもの)...56bit
# 出力: サブ鍵k 48bit
#
def pc2(c_d_list):
    k = []
    for i in range(48):
        k.append(c_d_list[pc2_table[i]-1])

    return k


#
# shift
# 入力:リストl, 移動ビット数n
# 出力:巡回シフト結果 (n=1のとき左に1bit巡回シフト)
#
def shift(l, n):
    return l[n:] + l[:n]


#
# enc_sub_key_generate()
# 入力:秘密鍵key
# 出力:sub_key_list
#
def enc_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if (i == 1) or (i == 2) or (i == 9) or (i == 16):
            c = shift(c, 1)
            d = shift(d, 1)
        else:
            c = shift(c, 2)
            d = shift(d, 2)
        sub_key_list.append(pc2(c + d))

    for k in sub_key_list:
        print(k)

    return sub_key_list


#
# dec_sub_key_generate(key)
# 入力:秘密鍵
# 出力:sub_key_list (encのときと逆順)
#
def dec_sub_key_generate(key):
    c = []
    d = []
    sub_key_list = []

    c, d = pc1(key)

    for i in range(1, 1+16):
        if i == 1:
            c = c
            d = d
        elif (i == 2) or (i == 9) or (i == 16):
            c = shift(c, -1)
            d = shift(d, -1)
        else:
            c = shift(c, -2)
            d = shift(d, -2)
        sub_key_list.append(pc2(c + d))

    for k in sub_key_list:
        print(k)

    return sub_key_list


if __name__ == '__main__':

    sub_key_list = enc_sub_key_generate(key)

共通鍵暗号の攻撃モデル

今回は, 共通鍵暗号の攻撃モデルについて説明していきたいと思います.

暗号文単独攻撃(Ciphertext Only Attack; COA)

暗号文単独攻撃とは, 同一の秘密鍵によって暗号化された複数の暗号文を利用することで, 鍵や平文に関する情報を取得しようとする攻撃です.

例えば, 単一換字暗号を解析するには「頻度分析」というものを使用します(知らなかったor忘れていた方は以下のリンクをクリック)
tomonori4565.hatenablog.com

頻度分析は, 暗号文に出現する文字の頻度から平文に関する情報を取得する分析方法でしたね. これは暗号文単独攻撃の1つと言えます.

既知平文攻撃(Known Plaintext Attack; KPA)

既知平文攻撃とは, ある特定の平文に対してその暗号文が既知である場合に利用される攻撃手法です. ただし, すべての暗号文は同一の秘密鍵によって暗号化されているものとします.

例えば, "I LOVE YOU"という平文に対する暗号文が"QWERTY"であるとします. このとき, 取得した暗号文がたまたま"QWERTY"であったら, 秘密鍵に関する情報を何も知らなくても, 平文が"I LOVE YOU"であることがわかります.

このように, ある特定の平文と暗号文のペアがわかっている場合に仕掛けられる攻撃が既知平文攻撃となります.

選択平文攻撃(Chosen Plaintext Attack; CPA)

選択平文攻撃とは, 自分で選んだ任意の平文に対する暗号文を得られる状況において, 攻撃を実行するモデルです.
攻撃者は暗号化オラクルと呼ばれる, 入力した平文に対して適切な暗号文を返す装置を利用して暗号文を得ます. 暗号化オラクルを入手するには, 暗号化装置を入手したり, 認証サーバを悪用したりします.
暗号化オラクルを入手することで, 秘密鍵を知らなくとも平文に対して適切な暗号文を得られることになり, 暗号を解読する大きな手がかりを入手することになります.

選択暗号文攻撃

選択暗号文攻撃とは, 解読対象の暗号文 c^*を受け取るの時点で, 復号オラクルを利用して自分で選んだ任意の暗号文に対する平文を得られるという状況下で攻撃するモデルのことです.

適応的選択暗号文攻撃

適応的選択暗号文攻撃とは, 解読対象の暗号文 c^*を受け取る前後の時点で, 復号オラクルを利用して自分で選んだ任意の暗号文に対する平文を得られるという状況下で攻撃するモデルのことです.

シーザー暗号をUNIXで試す

UNIXでシーザー暗号を使いたいとき, 以下のようにコマンドを打てばOKです.

Hirata:~ hiratatomonori$ echo AKADEMIA | tr A-Z D-ZA-C
DNDGHPLD
Hirata:~ hiratatomonori$ echo DNDGHPLD | tr D-ZA-C A-Z
AKADEMIA
Hirata:~ hiratatomonori$ 

trコマンドについては以下を参照にしてください.

www.atmarkit.co.jp

pwnable.kr writeup [blackjack]

この問題は, blackjackのゲームでmillionareになればflagゲットとなります.

問題

Hey! check out this C implementation of blackjack game!
I found it online

http://cboard.cprogramming.com/c-programming/114023-simple-blackjack-program.html

I like to give my flags to millionares.
how much money you got?

cboard.cprogramming.com


Running at : nc pwnable.kr 9009

解説

とりあえずゲームをやってみましょう. ゲームの仕組みは以下のとおりです.

(1)所持金は$500.
(2)掛け金を設定.
(3)ブラックジャックゲームに勝利したら掛け金分の報酬をゲット.
(4)負けたら所持金から掛け金分を差し引かれる.

普通に考えて, 所持金$500からミリオネアになるのは非現実的ですね. 何かゲームに存在する脆弱性を利用してミリオネアになることを考えましょう.

こっからはソースコードをじっくり読んでいくしかないのですが, 掛け金に関するコードでおかしい部分が存在します.

int betting() //Asks user amount to bet
{
 printf("\n\nEnter Bet: $");
 scanf("%d", &bet);
 
 if (bet > cash) //If player tries to bet more money than player has
 {
        printf("\nYou cannot bet more money than you have.");
        printf("\nEnter Bet: ");
        scanf("%d", &bet);
        return bet;
 }
 else return bet;
} // End Function

掛け金を設定するとき, 所持金より大きい値に設定すると, 1回目は「You cannot bet more money than you have」といってもう1回入力させるのですが, 2回目は入力された値をそのままリターンしてしまっています.

つまり, 1回目2回目ともに$1,000,000となるように掛け金を設定し, そのゲームに勝てばミリオネアになれます.




              222                111                            
            222 222            11111                              
           222   222          11 111                            
                222              111                               
               222               111                           

CCCCC     SS            DD         HHHHH    C    C                
C    C    SS           D  D       H     H   C   C              
C    C    SS          D    D     H          C  C               
CCCCC     SS          D DD D     H          C C              
C    C    SS         D DDDD D    H          CC C             
C     C   SS         D      D    H          C   C               
C     C   SS        D        D    H     H   C    C             
CCCCCC    SSSSSSS   D        D     HHHHH    C     C            

                        21                                   
     DDDDDDDD      HH         CCCCC    S    S                
        DD        H  H       C     C   S   S              
        DD       H    H     C          S  S               
        DD       H HH H     C          S S              
        DD      H HHHH H    C          SS S             
        DD      H      H    C          S   S               
     D  DD     H        H    C     S   S    C             
      DDD      H        H     CCCCC    S     S            

         222                     111                         
        222                      111                         
       222                       111                         
      222222222222222      111111111111111                       
      2222222222222222    11111111111111111                         


                 Are You Ready?
                ----------------
                      (Y/N)
                        Y


Enter 1 to Begin the Greatest Game Ever Played.
Enter 2 to See a Complete Listing of Rules.
Enter 3 to Exit Game. (Not Recommended)
Choice: 1







Cash: $500
-------
|D    |
|  J  |
|    D|
-------

Your Total is 10

The Dealer Has a Total of 3

Enter Bet: $1000

You cannot bet more money than you have.
Enter Bet: 100000000000


Would You Like to Hit or Stay?
Please Enter H to Hit or S to Stay.
H
-------
|S    |
|  A  |
|    S|
-------

Your Total is 21

The Dealer Has a Total of 7
Unbelievable! You Win!

You have 1 Wins and 0 Losses. Awesome!

Would You Like To Play Again?
Please Enter Y for Yes or N for No
Y

YaY_I_AM_A_MILLIONARE_LOL


Cash: $1215752692
-------
|H    |
|  7  |
|    H|
-------

Your Total is 7

The Dealer Has a Total of 6

Enter Bet: $    



flagゲットですね.

pwnable.kr writeup [cmd1]

この問題は, 一時的にPATHを変更された場合にどのようにシェルを動かすかっていう話ですね.

問題

Mommy! what is PATH environment in Linux?

ssh cmd1@pwnable.kr -p2222 (pw:guest)

解答

まずはcmd1.cを見てみましょう.

#include <stdio.h>
#include <string.h>

int filter(char* cmd){
	int r=0;
	r += strstr(cmd, "flag")!=0;
	r += strstr(cmd, "sh")!=0;
	r += strstr(cmd, "tmp")!=0;
	return r;
}
int main(int argc, char* argv[], char** envp){
	putenv("PATH=/thankyouverymuch");
	if(filter(argv[1])) return 0;
	system( argv[1] );
	return 0;
}

main関数の1行目でPATHが一時的に変更されてしまっています. 2行目では, コマンドライン引数argv[1]に, 「flag」, 「sh」, 「tmp」という文字列が含まれていないかをフィルタリングしています. 含まれていたらそこでmain関数を終了させます.
3行目では, system関数にargv[1]を渡し, シェルを実行させます.

まず, 一時的にPATHが変更されていることを確認してみましょう.

cmd1@ubuntu:~$ ./cmd1 export
export HOME='/home/cmd1'
export LANG='en_US.UTF-8'
export LANGUAGE='en_US:'
export LOGNAME='cmd1'
export MAIL='/var/mail/cmd1'
export PATH='/fuckyouverymuch'
export PWD='/home/cmd1'
export SHELL='/bin/bash'
export SHLVL='1'
export SSH_CLIENT='126.219.156.42 49899 22'
export SSH_CONNECTION='126.219.156.42 49899 192.168.1.186 22'
export SSH_TTY='/dev/pts/14'
export TERM='xterm-256color'
export USER='cmd1'
export XDG_RUNTIME_DIR='/run/user/1025'
export XDG_SESSION_ID='8063'
export _='./cmd1'

PATHが変更されていることが確認できますね(なんでfuckyouverymuchになっているのだろう...のちにソースコードを変更して, バイナリファイルはそのままにしたのだろうか...).

したがって, コマンドライン引数でPATHを再び設定するようなシェルをかいてやればOKですね.

「./cmd1 "export PATH=/bin/; cat flag;"」というコマンドを打てばflagを出力してくれそうですね.
しかし, flagという文字列が含まれているとフィルタリングに引っかかってしまうので, f*という形にしておきましょう.

cmd1@ubuntu:~$ ./cmd1 "export PATH=/bin/; cat f*;"
mommy now I get what PATH environment is for :)