Qualsに参加しました。みんなでまじめに参加して、結果はなんとか10位となりました。アドベントカレンダー登録時の予定では、Web問あたりがいくつか解けて、ここでwriteupを書くはずだったんですが、かなりエスパー要素があるわ1問あたりの段階数がおおいやらで、全体的にいいところまでは進めても解ききれませんでした。cr4cKM3のwriteupを書きます。Calendarに投稿しようと思ってずっと放置していたのがあったのに、登録するのを忘れていたことを思い出したので、雑に供養します。Algorithmというのを実装したくなったので実装させてもらいました。当時のスライドから面白くないものを削除したスライドです。それなりにイメージは伝わると思っています。146www.slideshare.net実装は公開しています。見るに堪えないかもわかりませんが。Algorithmは、整数乗算アルゴリズムで、まあもちろん速いわけなんですが、速いと言っても定数倍がかなり重くて日常的な乗算にはむしろ不利なやつです。000桁の大きさ」でSSAを初めて用いるようになるとあります。ソースに当たると、MUL_FFT_THRESHOLDというのが関係してくるらしくって、その値はx86_64で11520らしいんですが、limbってなんだかわからないしこれがなんなのかはわかりません。Kortekaas」とか参考にするといいです。オンラインで見つかるPDFです。manualとかも参考になったのかもしれないと思いますが、当時は見つけられなかったのでしかたない。bit同士の乗算あたりからKaratsuba法を上回ったようです。そんなちゃんと実装したわけじゃないので、同じbit数同士の乗算しかできなかったり(当然0埋めすれば違ってもできるが、計算量的に劣る)、詳しくは書きませんが計算途中に特別な条件を満たすと続行不可能になってエラー返したりします*1。*1:参考PDFでも触れられているのと、「続行不可能」でスライド検索すればなんとなく分かります。adventar.org昨日はMisterプロによる「簡潔ビットベクトル(完備辞書)」でした。misteer.hatenablog.com17erのこおしいずです。CPU実験は1年前です。同アドベントカレンダー2日目の記事に、moratoriumプロによる「min-camlのプログラムからシェルが取れるか?」というのがあって、そこでpwn問題が出されていました。2週間経ちますので、writeupをやっていこうと思います。いえ、出題者からはもっと良質な想定解が提示される予定なので、12/23のアドベントカレンダー記事も読みましょう。subsetコンパイラがあるのですが、この問題では、min-camlソースコードを与えると、そのコンパイラ(に制限を加えたもの)でコンパイルした結果を実行してくれるので、シェルをとれという問題です。CTFでコンパイラへの入力を与えるタイプはあんまり見ない気がしますが、OCamlはめっちゃ型つける系だし、今回glibcも外されて*1、自明ではない、ということです。コンパイラはなぜかArrayのPUT構文を潰されています。blindなかなか好きな問題でした。break固定値pをmodとした世界で、コネクションごとに乱数yが生成されます。g=1と乱数yを暗号化した結果を接続時に与えられます。暗号化は、AESで毎回keyはrandomにgenerateされますが、ECBです。yの暗号文を得ることができます。1024クエリ以内に、yがいくらであったのかをexactに求めてください。今回の回答は、1/18未満の確率でうまくいくものです。(クエリ回数超過の可能性と、最後の解答が17/18で間違う可能性)まず、今回のAES暗号化は、ECBなので(じゃなくてもか?)同じメッセージに対する暗号文は不変です。xに対していろいろと操作をして、またxにもどったかどうかを判定することができます。-xは正直ほとんど役に立てられません。pは素数なので、足し算や反数をとってもだいたい対称な操作で、求めることにあまり意味を感じられません。yにひたすらg=1を足していって、g=1と等しくなったかで判明するくらいでしょうか。dhpを繰り返し行うことで、x^nを求めることができます。nはこちらで自由に設定できる数字です。回数程度で求めることができます。あり、こちらの世界では値ごとに特徴が十分見いだせます。以外を使うのは考えられません。