Lab

汎用的なシミュレーターの設計 from Takaaki Sawa

最近, cloudnetという学会に論文を投稿したのだが, そこでデータを集める際に制作したシミュレータがいい感じにできたのでそれについて書いてみる。 https://github.com/adshidtadka/server-allocation Parameterクラス まず良かった点としてParameter クラスを作ったことである。 import numpy as np import pandas as pd import itertools import sys import Constant class Parameter: USER_NUM_CONST = 500 SERVER_NUM_CONST = 10 CAPACITY_CONST = 50 def __init__(self, seed): np.random.seed(seed) self.USER_NUM = 500 self.SERVER_NUM = 10 self.DELAY_MAX = 10 self.DELAY_SERVER = 1 self.CAPACITY = 50 def create_input(self): # inputs self.e_u = list(itertools.product(range(self.USER_NUM), range(self.SERVER_NUM))) self.e_s = list(itertools.combinations(list(range(0, self.SERVER_NUM)), 2)) self.d_us = np.random.randint(1, self.DELAY_MAX, (self.USER_NUM, self.SERVER_NUM)) self.m_s = np.full(self.SERVER_NUM, self.CAPACITY) def set_param(self, var_name, consts, var): if var_name == 'user': self.USER_NUM = var self.SERVER_NUM = consts['server'] self.CAPACITY = consts['capacity'] elif var_name == 'server': self.USER_NUM = consts['user'] self.SERVER_NUM = var self.CAPACITY = consts['capacity'] elif var_name == 'capacity': self.USER_NUM = consts['user'] self.SERVER_NUM = consts['server'] self.CAPACITY = var else: sys.exit('invalid var_name = ' + str(var_name)) def get_const(var_name): if var_name == 'user': return Parameter.USER_NUM_CONST elif var_name == 'server': return Parameter.SERVER_NUM_CONST elif var_name == 'capacity': return Parameter.CAPACITY_CONST else: sys.exit('invalid var_name = ' + str(var_name)) これを作ることで1つのインスタンスが1つのパラメータに対応することになるので, 全部グローバル変数で書いていた前回のシミュレータよりめちゃめちゃわかりやすくなった。また, インスタンスメソッドを呼び出してパラ調整がしやすく, メソッドとしてパッケージ化することでエラーを極力避けれるようになった。 IlpクラスとMmdクラス class Ilp: def __init__(self, param): self.create_dataframe(param) self.set_input() def set_input(self): # optimization problem problem = LpProblem() # decision variables self.df_e_u['variable'] = [LpVariable('x_us%d' % i, cat=LpBinary) for i in self.df_e_u.index] self.df_e_s['variable'] = [LpVariable('x_st%d' % i, cat=LpBinary) for i in self.df_e_s.index] self.df_v_s['variable'] = [LpVariable('y%d' % i, cat=LpBinary) for i in self.df_v_s.index] self.D_u = LpVariable('D_u', cat=LpInteger) self.D_s = LpVariable('D_s', cat=LpInteger) # objective function problem += 2 * self.D_u + self.D_s self.problem = problem def create_dataframe(self, param): # dataframe for E_U df_e_u = pd.DataFrame([(i, j) for i, j in param.e_u], columns=['user', 'server']) df_e_u['delay'] = param.d_us.flatten() self.df_e_u = df_e_u # dataframe for E_S df_e_s = pd.DataFrame([(i, j) for i, j in param.e_s], columns=['server_1', 'server_2']) df_e_s['delay'] = param.DELAY_SERVER self.df_e_s = df_e_s # dataframe for V_S df_v_s = pd.DataFrame(list(range(0, param.SERVER_NUM)), columns=['server']) df_v_s['capacity'] = param.m_s self.df_v_s = df_v_s def solve_by_ilp(self, solver=None): t_0 = time.perf_counter() # solve try: # constraints self.problem = self.create_constraints(self.problem) if solver == 'cplex': self.problem.solve(GLPK_CMD(msg=0)) else: self.problem.solve(CPLEX_CMD(msg=0)) except PulpSolverError: print(CPLEX_CMD().path, 'is not installed') t_1 = time.perf_counter() return t_1 - t_0 def print_result(self): if self.problem.status == 1: print('objective function is ', value(self.problem.objective)) print('cpu time is ' + str(self.cpu_time) + ' sec') else: print('status code is ', self.problem.status) def create_constraints(self, m): # constraints # (1b) for k, v in self.df_e_u.groupby('user'): m += lpSum(v.variable) == 1 # (1c) for k, v in self.df_e_u.groupby('server'): m += lpSum(v.variable) <= self.df_v_s['capacity'][k] # (1d) for k, v in self.df_e_u.iterrows(): m += v.variable * v.delay <= self.D_u # (1e) for k, v in self.df_e_s.iterrows(): m += v.variable * v.delay <= self.D_s # (1f) for k, v in self.df_e_u.groupby('user'): for l, w in self.df_v_s.iterrows(): m += w.variable >= v.variable # (1g) for k, v in self.df_e_s.iterrows(): m += self.df_v_s.iloc[v.server_1].variable + \ self.df_v_s.iloc[v.server_2].variable - 1 <= v.variable # (1h) for k, v in self.df_e_s.iterrows(): m += v.variable <= self.df_v_s.iloc[v.server_1].variable # (1i) for k, v in self.df_e_s.iterrows(): m += v.variable <= self.df_v_s.iloc[v.server_2].variable return m class Mmd: def __init__(self, param): self.set_input(param) def set_input(self, param): # edges list edges = np.empty(3, dtype=int) for k, v in enumerate(param.d_us): for i, j in enumerate(v): edges = np.vstack((edges, np.array([k, i, j]))) self.edges = edges def start_algorithm(self, param): t_0 = time.perf_counter() L_1 = self.one_server_case(param) L_2 = self.multiple_server_case(param) D_u = min([L_1, L_2]) if D_u > param.DELAY_MAX: self.status = False else: self.status = True self.objective_function = D_u * 2 + param.DELAY_SERVER t_1 = time.perf_counter() return t_1 - t_0 def one_server_case(self, param): # step 1: consider one server case # allocate all user and get L_1 dic_l = dict() for k, v in enumerate(param.m_s): if v >= param.USER_NUM: D_u = param.d_us[:, k].max() dic_l[k] = D_u # search minimum D_u if bool(dic_l): return min(dic_l.values()) else: return Constant.INF def multiple_server_case(self, param): # step 2: consider multiple server case # initialize the bipartite graph added_server = param.SERVER_NUM for k, v in enumerate(param.m_s): for j in range(param.USER_NUM): delay = param.d_us[j][k] for i in range(added_server, added_server + v - 1): self.edges = np.vstack((self.edges, np.array([j, i, delay]))) added_server += v - 1 param.COPY_SERVER_NUM = added_server # search matching for i in range(1, param.DELAY_MAX): hc = HopcroftKarp(param.USER_NUM, param.COPY_SERVER_NUM) for j in np.where(self.edges[:, -1] <= i)[0]: hc.add_edge(self.edges[j][0], self.edges[j][1]) if hc.flow() == param.USER_NUM: return i return Constant.INF def print_result(self): if self.status: print('objective function is ', str(self.objective_function)) print('cpu time is ' + str(self.cpu_time) + ' sec') else: print('Error') inputを入れればoutputが出るツールとして2つのクラスを作った。これにさっき定義したParameterをそのままいれればいいので, ブラックボックスとして扱える。set_inputなんかのメソッドを共通化してもよかった。また Ilp ではPulpを使ってソルバを簡単に切り替えられるようにした。 ...

論文を投稿するときに, epsの表示周りでめちゃめちゃエラーがでていたときに, ドライバオプションの設定でうまくビルドできた. それを最近忘れていて時間食ったので, 備忘録として残しておく. 詳しくは この方 がまとめてくれている. epsを表示する \usepackage[dvips]{graphicx} と, dvips をドライバで指定する. pdf, jpg, pngを表示する \usepackage[dvipdfmx]{graphicx} と, dvipdfmx をドライバで指定する. 感想 texの設定は理解しにくいので備忘録をこまめに書いていきたい.

先週, 神戸デジタルラボにお邪魔してkaggleの勉強会に参加してきました。研究室の先輩の稲垣さんに講義してもらった。そこでの講義資料がこちら。 u++さんという有名な人のQiitaに従って解説してもらった。kaggleは何回か参加したことがあるが, 改めて勉強になった。

seccon beginners ctf前の最後の勉強会. 今回はアルゴリズムに関する問題が多かった. Math I RSAの公開鍵暗号に関する問題. ちなみに、 RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 c(暗号文)とm(平文)は以下のようにして求める. c = m^e mod n m = c^d mod n よってdさえ求まれば復号できる. dを求める式は以下の通り. d = e^(-1)(mod(p-1)(q-1)) dを求めるには, n = pqを求める p-1とq-1の最大公倍数lcm(p-1, q-1) = (p-1)(q-1)/gcd(p-1)(q-1)を求める ed≡1(mod L)となるようなedの組みを求める 拡張ユークリッドの互除法が使われている. このサイトを参考にして実装した. import math e = 65537 n = 1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029 c = 225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163 p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323 q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223 # step1 L = (p-1)*(q-1)//math.gcd(p-1, q-1) # step2 def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return a0 d = ex_euclid(e, L) # step3 m = pow(c,d,n) print ("%0512x"%m).decode("hex") Math II モジュロ演算という割り算の余りを求める計算と関わっている. xの101乗根を普通に求めようとしてもオーバーフローが起きてしまうので, 二分探索を実装する. このサイトを参考にした. ...

今日は4人しかこなかった… 火曜の8:45からってのがきつすぎるんかな… 31 Kangacha PHPで書かれた簡単なwebアプリケーションの問題. Gachaというボタンを押せば日本の戦艦の名前がランダムでリストに追加されていく. ソースコードも与えられているので読んでいく. if (isset($_POST['submit'])) { // Gacha if ($_POST['submit'] === 'Gacha') { // Yamato is ultra rare $ship[] = mt_rand(0, count($shipname)-2); $s = implode(',', $ship); $sign = hash('sha512', $salt.$s); setcookie('ship', $s); setcookie('signature', $sign); } // Clear if ($_POST['submit'] === 'Clear') { setcookie('ship', '', 0); setcookie('signature', '', 0); } header("Location: {$_SERVER['REQUEST_URI']}"); exit(); } このソースから, $_COOKIE['ship']に戦艦の番号の配列が, $_COOKIE['signature']にあらかじめ決められた$saltと戦艦番号のハッシュ値が格納される. // Check signature and read if (isset($_COOKIE['ship']) and isset($_COOKIE['signature']) and hash('sha512', $salt.$_COOKIE['ship']) === $_COOKIE['signature']) $ship = explode(',', $_COOKIE['ship']); else $ship = array(); ここで$_COOKIE['signature']のバリデーションを確認され, 不正であれば配列の中身が空になってしまう. ...

第3回CTF勉強会 ksnctfの9, 11, 12, 13が課題で, 14が演習問題である. 11が難しいらしい 9 Digest is secure! pcapファイルをダウンロードして, wiresharkでhttp通信をフィルタリングしてみると, digest認証の通信が行われている. ちなみにDigest認証とは、 Digest認証とは、Basic認証と同じくApacheで利用できるアクセス制限です。ユーザーIDとパスワードを求める点までは全く同じですが、入力されたユーザーIDとパスワードをハッシュ関数であるMD5を用いて解析されにくい状態で送信する仕組みです。しかし、Basic認証と比べて後発の機能なので、かつては一部対応していないブラウザがありました。現在ではほとんどのブラウザに対応しているため、Basic認証ではなくDigest認証が使われるケースが増えています。レンタルサーバー比較なび ここで, 認証の際に渡しているパラメータをみてみる. Digest username=“q9” realm=“secret” nonce=“bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b” uri="/~q9/" algorithm=MD5 response=“c3077454ecf09ecef1d6c1201038cfaf” qop=auth nc=00000001 cnonce=“9691c249745d94fc” これから以下のようにresponseが作成される. A1 = ユーザ名 ":" realm ":" パスワード A2 = HTTPのメソッド ":" コンテンツのURI response = MD5( MD5(A1) ":" nonce ":" nc ":" cnonce ":" qop ":" MD5(A2) ) これをみると. パスワードがわからなくてもA1さえわかればサーバーから送られてきたnonceを元にresponseを生成できることがわかる. ここで, A1を得るためにresponseを解読する. MD5は脆弱性が存在し鍵長も短いので復号ツールで復号できてしまう. 追記 後のパケットにA1が帰ってきているので, ツールを使わなくて良い. Qiita:暗号化とハッシュ化に関する基本的な事柄まとめ Hash Toolkit: 復号ツール c627e19450db746b739f41b64097d449:bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b:00000001:9691c249745d94fc:auth:31e101310bcd7fae974b921eb148099c この結果A1がわかった. ちなみにA1は解読できなかったのでパスワードがわからない. しかし他の全てのパラメータがわかるのでresponseを生成できる. ...

リアルタイム性に厳しいアプリケーションに対する通信遅延を考慮した実装と通信遅延を抑えるための研究 from Takaaki Sawa

前回は, CpawCTF2の1問を解いたが難易度が高かったので, ksnctfをみんなで解くことにした. 今回の課題は2, 3, 5, 6である. write up [2] Easy Cipher EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT. 見るからにシーザ暗号なので, 文字をずらすことを考える. 文字コードはUnicodeに従うとして, 空白の文字コードは32 大文字の文字コードは65~90 小文字の文字コード97~122 である. これを加味して以下のような解読するための関数をpythonでかく. # シーザー暗号の解読 def decrypt(text, rot): decrypt_text = '' for ch in text: # 文字コードに変換 code = ord(ch) if code == 32: # 空白ならそのまま出力 decrypt_text += ch continue if code <= 90: # 小文字 code += rot if code > 90: code = code - 90 + 64 else: # 大文字 code += rot if code > 122: code = code - 122 + 96 # 文字に変換 decrypt_text += chr(code) return decrypt_text text = "EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT" for i in range(1, 26): if decrypt(text, i).find("FLAG") != -1: print(decrypt(text, i)) # ROT XIII is a simple letter substitution cipher that replaces a letter with the letter XIII letters after it in the alphabet; ROT XIII is an example of the Caesar cipher9 developed in ancient Rome; Flag is FLAGSwzgxBJSAMqwxxAU; Insert an underscore immediately after FLAG また, ROT13はPythonに実装されているので一瞬で解読できる. ...

はじめに… これをといてみます CTFとはこんな感じでハッキングするゲームである。 目的 ゲーム感覚で楽しみながらセキュリティに強くなる 実際に解いてみよう 今回解くのは以下の問題. CpawCTF2 [2] PRANK Yesterday, someone played a Telenet prank and left this file on my machine. ziiiiiiiiiiiiiip.zipI hope this pcap file will help you. prank.pcap 圧縮ファイルとパケットファイルが入っている. 圧縮ファイルを見ると, 0のパスワードを要求される. パケットファイルはTCPとtelnetの通信が行われている. 解法 Telnetは、ネットワークに接続された機器を遠隔操作するために使用するアプリケーション層プロトコル。 オフィスのデスクにいながら、マシンルームにあるサーバ、ルータ等の機器をパソコン上で操作できます。 PCにはtelnetクライアント、ルータなどの機器にはtelnetサーバのサービスが有効であることが前提ですネットワークエンジニアとして らしいので, telnetの中身を覗いたらいろんなコマンドがわかってパスワードがわかるんじゃないかという気持ちでパケットを見る. パケット1つ1つのData部を見ればいいのだが日が暮れるので, TCP streamを見る. 最後に圧縮の操作をしてるんじゃないかと思ってみたらビンゴ. そのパスワードを使って圧縮ファイルを開くとめちゃめちゃいろんなファイルがある. なんかtelnetを眺めているとmvとかの操作でいろんなファイルができている. そこで, 最初にあるflag.txtにフラグがあるんじゃないかと予想して追ってみる. すると flag.txt があるファイルに変換されている. それを見ればビンゴ. 感想 いいぐらいの難易度だった.