Steganography(ステガノグラフィ)入門
出田 守です。 情報セキュリティに興味を持ち、独学で勉強中です。 主にPythonを使用します。時々勉強のためにCを使用することもあります。
目的
CTFの問題を解いていると、Steganographyに出会いました。名前は聞いたことあるけど、詳しくは知らなかったので調べました。調べた内容の説明後、実装までが今回の目的です。
Steganographyとは
Steganographyとはあるデータを他のデータに埋め込み秘匿してしまう技術の一種です。埋め込まれるデータをvesselやdummyと呼ばれるそうです。データとしては画像の他、音声データ、動画データなども対象になるようです。 従来のSteganography技術には以下があるようです。
ただし、これらの技術のデータ埋め込み容量は小さいそうです。一方BPCS-Steganographyではデータ埋め込み容量は約50%にもなるようです。 今回は特に画像を対象にBPCS-Steganographyについて学んでみます。
BPCS-Steganography
BPCS-SteganographyはSteganography技術の一種です。ビットプレーン分解と人間の視覚情報認識能力を利用した手法のようです。
ビットプレーン分解
1情報のうちに複数のビット情報を持つものを1ビット毎に分解すること。例えば24色画像の場合1ピクセルあたり224色あります。224色の内訳はRED、GREEN、BLUEそれぞれ28色で構成されています。つまり282828色ということです。ビットプレーンは抽出した特定のビットのことを言います。ここで例えばREDの28の最上位ビットをMSBといい、最下位ビットをLSBといいます。
ここでビットプレーン分解を行うプログラムを実装してみます。
import numpy as np from PIL import Image def read_image_as_numpy(path): img = Image.open(path) # read img arr = np.array(img) # convert to numpy array return arr def to_binary(arr): if len(arr.shape)==3: # 3 channels (R, G, B) bits = np.unpackbits(arr, axis=2) # [[[128,128,128]...]...] => [[[100000001000000010000000]...]...] bits = bits.reshape(bits.shape[:2]+(arr.shape[2], 8,)) # divide each color (h, w, c*8) => (h, w, c, 8) return bits elif len(arr.shape)==2: # 2 channels gray-scale bits = np.unpackbits(arr, axis=1) bits = bits.reshape(bits.shape[:1]+(arr.shape[1], 8,)) # (h, w*8) => (h, w, 8) return bits elif len(arr.shape)==1: org = arr.shape # original shape arr = np.unpackbits(arr) arr = arr.reshape(org+(8,)) # (original shape*bits) => (original shape, 8) return arr else: print("Unsupported shape of image") exit(1) return None def to_image(arr): if len(arr.shape)==4: # for 3 channels (R, G, B) arr = arr.reshape(arr.shape[:2]+(arr.shape[2]*arr.shape[3],)) # (h, w, c, 8) => (h, w, c*8) arr = np.packbits(arr, axis=2) return arr elif len(arr.shape)==3: # for 2 channels gray-scale arr = arr.reshape(arr.shape[:1]+(arr.shape[1]*arr.shape[2],)) # (h, w, 8) => (h, w*8) arr = np.packbits(arr, axis=1) return arr else: print("Unsupported shape of image") exit(1) return None def extract_bitplane(arr, color, bit): if len(arr.shape)==4: # RGB bitplane = arr[:,:,color,bit] # bitplane shape is (h, w) 2d array elif len(arr.shape)==3: # gray-scale bitplane = arr[:,:,bit] # bitplane shape is (h, w) 2d array else: print("Unsupported shape of image") exit(1) return bitplane
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<4: print("USAGE: {0} <PATH> <COLOR> <BIT>".format(sys.argv[0])) print(" PATH: image path") print(" COLOR: GRAY=-1, RED=0, GREEN=1, BLUE=2") print(" BIT : 0~7 (0:MSB, 7:LSB)") exit(1) PATH = sys.argv[1] COLOR = int(sys.argv[2]) BIT = int(sys.argv[3]) def merge_bitplane_to_image(bitplane, arr, color): arr = bp.to_image(arr) img = np.zeros(arr.shape) img[:,:,color] = bitplane return img arr = bp.read_image_as_numpy(PATH) if len(arr.shape)<2 or len(arr.shape)>3: print("Unsupported shape of image") exit(1) arr = bp.to_binary(arr) # arr.shape = (h, w, 3(color), 8(byte)) or (h, w, 8(byte)) # arr = bp.to_image(arr) # arr.shape = (h, w, 3) or (h, w) bitplane = bp.extract_bitplane(arr, COLOR, BIT) bitplane[bitplane>0] = 255 if COLOR!=-1 and len(arr.shape)==4: arr = merge_bitplane_to_image(bitplane, arr, COLOR) else: arr = bitplane Image.fromarray(np.uint8(arr)).show() # show image # Image.fromarray(np.uint8(arr)).save("test.png") # save image
$ python show_specific_bits.py sample.jpg 0 7
第一引数に画像パス、第二引数に抽出カラー、第三引数に抽出ビットです。
結果が以下になりました。
下位ビットにいくにつれて元画像が分からなくなっていますね。
視覚情報認識能力
上記のビットプレーン分解を見ると、LSBよりMSBのほうが、より元画像に近く見えます。このことは人間にとって重要な情報はMSBに近いビットさえあれば元画像として認識可能ということです。
PBCとCGC
画像にデータを埋め込む際、PBC(Pure Binary Code)よりもCGC(Canonical Gray Code)の方が埋め込み後の画像の変化が少ないそうです。
PBCからCGCへの変換は以下の参照ページを参照してください。
では、PBCからCGCとCGCからPBCの変換を行うプログラムを実装してみます。
... def pbc_to_cgc(arr): """ ref:http://datahide.org/BPCSj/pbc-vs-cgc-j.html """ if len(arr.shape)==3 and arr.shape[2]==3: print("Please first convert to binary. i.e. arr = to_binary(arr)") exit(1) cgc = arr.copy() if len(cgc.shape)==4: # RGB for i in range(1, 8): cgc[:,:,:,i] = np.logical_xor(arr[:,:,:,i-1], arr[:,:,:,i]) # gi = bi-1^bi elif len(cgc.shape)==3: # gray-scale for i in range(1, 8): cgc[:,:,i] = np.logical_xor(arr[:,:,i-1], arr[:,:,i]) # gi = bi-1^bi else: print("Unsupported shape of image") exit(1) return cgc def cgc_to_pbc(arr): """ ref:http://datahide.org/BPCSj/pbc-vs-cgc-j.html """ if len(arr.shape)==3 and arr.shape[2]==3: print("Please first convert to binary. i.e. arr = to_binary(arr)") exit(1) pbc = arr.copy() if len(pbc.shape)==4: # RGB for i in range(1, 8): pbc[:,:,:,i] = np.logical_xor(arr[:,:,:,i], pbc[:,:,:,i-1]) # bi = gi^bi-1 elif len(pbc.shape)==3: # gray-scale for i in range(1, 8): pbc[:,:,i] = np.logical_xor(arr[:,:,i], pbc[:,:,i-1]) # bi = gi^bi-1 else: print("Unsupported shape of image") exit(1) return pbc
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<2: print("USAGE: {0} <PATH>".format(sys.argv[0])) print(" PATH: image path") exit(1) PATH = sys.argv[1] arr = bp.read_image_as_numpy(PATH) if len(arr.shape)<2 or len(arr.shape)>3: print("Unsupported shape of image") exit(1) arr = bp.to_binary(arr) arr = bp.pbc_to_cgc(arr) # arr = bp.cgc_to_pbc(arr) arr = bp.to_image(arr) Image.fromarray(np.uint8(arr)).show() # show image # Image.fromarray(np.uint8(arr)).save("test.png") # save image
試した結果が以下です。味のある感じになりましたね笑
参照: Two Binary Number Coding Systems
複雑さ
埋め込まれる画像が埋め込まれる対象として適しているかを示す尺度のようです。下記参照ページでは白黒の境界の合計値にその画像での最大境界数を割った割合を複雑さとしています。この複雑さは画像全体としても局所的にも適用できます。まずは、画像全体のそれぞれのbitplaneでの複雑さを出力してみます。
... def get_block_as_iter(bitplane, blocksize): n_rows, n_cols = bitplane.shape for y in range(0, n_rows, blocksize[0]): for x in range(0, n_cols, blocksize[1]): block = bitplane[y:y+blocksize[0], x:x+blocksize[1]] if block.shape==blocksize: yield x, y, block return None def complexity(bitplane): n_rows, n_cols = bitplane.shape # bitplane shape is (h, w) 2d array max_cpx = ((n_rows-1)*n_cols)+((n_cols-1)*n_rows) # max complexity k = 0 xor = np.logical_xor(bitplane[1:], bitplane[:-1]) # row complexity k += len(xor[xor==True]) xor = np.logical_xor(bitplane[:,1:], bitplane[:,:-1]) # col complexity k += len(xor[xor==True]) return k/max_cpx*1.0
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<4: print("USAGE: {0} <PATH> <COLOR> <BIT>".format(sys.argv[0])) print(" PATH: image path") print(" COLOR: GRAY=-1, RED=0, GREEN=1, BLUE=2") print(" BIT : 0~7 (0:MSB, 7:LSB)") exit(1) PATH = sys.argv[1] COLOR = int(sys.argv[2]) BIT = int(sys.argv[3]) arr = bp.read_image_as_numpy(PATH) if len(arr.shape)<2 or len(arr.shape)>3: print("Unsupported shape of image") exit(1) # arr = bp.pbc_to_cgc(arr) arr = bp.to_binary(arr) # image complexity bitplane = bp.extract_bitplane(arr, COLOR, BIT) # extract bitplane as binary, shape is (h, w) cpx = bp.complexity(bitplane) print("image complexity =", cpx) # block complexity for i, (x, y, block) in enumerate(bp.get_block_as_iter(bitplane, (8,8))): cpx = bp.complexity(block) print("block[{0}] complexity =".format(i), cpx)
MSBに近いと複雑さはないです。LSBは0.5付近の複雑さを多く持っています。
埋込みデータ
秘密データは決められたサイズに小ブロック化します。もしそのブロックの複雑さが閾値以下なら、白黒データ(1から始まる縞々データ)とXORさせて複雑にします。秘密データ抽出のために、そのブロックをXORしたかどうかをコンジュゲーションマップとしてどこかに記録しておく必要があります。ということは埋め込む際に何かしらフォーマットを決めておくと良さそうです。
ではまず、秘密データを小ブロック化して、白黒データをXORするプログラムを実装してみます。なお、今回は秘密データとしてASCII文字列メッセージを対象とします。
I am hiding. Please do not search.\n
... def padding(arr, blocksize): block_row,block_col = blocksize n_row = len(arr) lack_row = block_row-n_row%block_row if lack_row>0: wb = create_wb((lack_row, 8)) # ascii only,so 8bit. wb is [[1,0,1,0,1,0,1,0]*lack_row] arr = np.concatenate((arr, np.packbits(wb))) # concatenate arr and packed wb return arr def read_message_as_numpy(path, blocksize): fp = open(path, "r") msg = fp.read() msg = np.array([ord(c) for c in msg], dtype=np.uint8) msg = np.concatenate((msg, SHINOBI)) msg = padding(msg, blocksize) fp.close() return msg def create_wb(size): if size[1]==1: return np.array([[1]*size[0]]) wb = np.tile([1, 0], (size[0],size[1]))[:size[0], :size[1]] if len(wb[1::2])>0: wb[1::2] = 1-wb[1::2] # invert only odd rows return wb def complication(block): wb = create_wb(block.shape) return np.uint8(np.logical_xor(block, wb))
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<2: print("USAGE: {0} <PATH>".format(sys.argv[0])) print(" PATH: secret file path") exit(1) PATH = sys.argv[1] blocksize = (8,8) ath = 0.45 # complexity threshold arr = bp.read_message_as_numpy(PATH, blocksize) arr = bp.to_binary(arr) for x, y, block in bp.get_block_as_iter(arr, blocksize): cpx = bp.complexity(block) print(block) print(block.shape) print("original complexity =", cpx) if cpx<ath: block = bp.complication(block) print("converted complexity =", bp.complexity(block)) print("="*30)
秘密データの終わりに特定の文字を仕込みました。
各ブロックの複雑さを見てみると、0.45以下のものを白黒データでXORしてあげると、複雑さが増しているのが分かります。
データ埋込み
いよいよデータを埋め込む準備ができました。
埋め込みはREDのLSBのビットプレーンから順番に各ブロックを走査し、複雑さが閾値以上のブロックと秘密データのブロックを入れ替えます。
なお、埋め込み後の画像出力はPNGです。JPGだと埋め込んだデータが壊れていためです。おそらく原因は非可逆圧縮だからでしょうか。
コンジュゲーションマップは秘密データの各ブロックがXORしたかを0または1で表すことにしました。これの埋め込みは秘密データの各ブロックの埋め込み前に埋め込まれるデータブロックの複雑さに関係なく埋め込まれます。注意として、コンジュゲーションマップは複雑さが閾値以下でも複雑化していません。
def secret_blocks(arr, blocksize, ath): # create secret blocks secret_blocks = [] conj_map = np.array([0]*int(arr.shape[0]/arr.shape[1]), dtype=np.uint8) for i, (x, y, block) in enumerate(get_block_as_iter(arr, blocksize)): cpx = complexity(block) if cpx<ath: block = complication(block) conj_map[i] = 1 secret_blocks.append(block) # create conjugation map (NOTE: not complication) conj_map = conjugation_map(conj_map, blocksize) return secret_blocks, conj_map def encode(arr, secret_blocks, conj_map, blocksize, ath): COLOR = 1 if len(arr.shape)==4: # RGB COLOR = 3 elif len(arr.shape)==3: # gray-scale arr = arr.reshape(arr.shape[:2]+(1, arr.shape[2],)) COLOR = 1 else: print("Unsupported shape of image") exit(1) secret_blocks = secret_blocks[:] conj_map = conj_map[:] for color in range(COLOR): for bit in (7, -1, -1): bitplane = extract_bitplane(arr, color, bit) for i, (x, y, block) in enumerate(get_block_as_iter(bitplane, blocksize)): if conj_map: bitplane[y:y+blocksize[0], x:x+blocksize[1]] = conj_map.pop(0) elif complexity(block)>ath: bitplane[y:y+blocksize[0], x:x+blocksize[1]] = secret_blocks.pop(0) if not secret_blocks: break arr[:,:,color,bit] = bitplane if not secret_blocks: if arr.shape[2]==1: # gray-scale arr = arr.reshape(arr.shape[:2]+(arr.shape[3],)) return arr return None
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<3: print("USAGE: {0} <IPATH> <SPATH>".format(sys.argv[0])) print(" IPATH: image path") print(" SPATH: secret file path") exit(1) IPATH = sys.argv[1] SPATH = sys.argv[2] blocksize = (8,8) ath = 0.45 # complexity threshold # prepare secret blocks arr = bp.read_message_as_numpy(SPATH, blocksize) arr = bp.to_binary(arr) secret_blocks, conj_map = bp.secret_blocks(arr, blocksize, ath) # encode arr = bp.read_image_as_numpy(IPATH) arr = bp.to_binary(arr) arr = bp.encode(arr, secret_blocks, conj_map, blocksize, ath) arr = bp.to_image(arr) Image.fromarray(np.uint8(arr)).show() Image.fromarray(np.uint8(arr)).save("images/encoded.png")
元画像が以下です。
ついでに、MSBのビットプレーンにも埋め込んでみました。
データ抽出
一応埋め込めましたが、実際に取り出せないとただの落書きになってしまうので、埋め込んだデータを抽出してみます。
... def decode_block(block): decoded = np.packbits(block).tolist() decoded = "".join([chr(c) for c in decoded]) return decoded def decode(arr, blocksize, ath): COLOR = 1 if len(arr.shape)==4: # RGB COLOR = 3 elif len(arr.shape)==3: # gray-scale arr = arr.reshape(arr.shape[:2]+(1, arr.shape[2],)) COLOR = 1 else: print("Unsupported shape of image") exit(1) conj = True conj_map = [] decoded = "" shinobi = "".join([chr(c) for c in SHINOBI]) tail = "".join([chr(c) for c in TAIL]) for color in range(COLOR): for bit in (7, -1, -1): bitplane = extract_bitplane(arr, color, bit) for x, y, block in get_block_as_iter(bitplane, blocksize): if conj: decoded += decode_block(block) if tail in decoded: conj_map = [ord(c) for c in decoded[:decoded.index(tail)]] conj = False decoded = "" elif complexity(block)>ath: if conj_map and conj_map.pop(0): decoded += decode_block(complication(block)) else: decoded += decode_block(block) if shinobi in decoded: return decoded[:decoded.index(shinobi)] return None
import sys import numpy as np import bpcs as bp from PIL import Image if len(sys.argv)<2: print("USAGE: {0} <PATH>".format(sys.argv[0])) print(" PATH: encoded image path") exit(1) PATH = sys.argv[1] blocksize = (8,8) ath = 0.45 # complexity threshold arr = bp.read_image_as_numpy(PATH) arr = bp.to_binary(arr) decoded = bp.decode(arr, blocksize, ath) print("[decoded code]") print(decoded)
githubに公開
完全版を公開しました。
