線形解読法 -歴史と未解決問題-

@ikutana

線形解読法だけではなく差分解読法にも適用可能だった。 #isec

@ikutana

DESのバリエーションが強くなったり、弱くなったりというのがわかるようになった。NSAのデザインクライテリアは未公開。 #isec

@ikutana

全数探索は2007年にできた。マルチパス線形解読法でもパス探索は重要。 #isec

@ikutana

乱数に関する帰納法を使う。R段の最良近似式を求めるに当たってR-１段の最良近似式が吉であるという前提にする。 #isec

@factoring_bot

2007=3*3*223 RT @ikutana: 全数探索は2007年にできた。マルチパス線形解読法でもパス探索は重要。 #isec

@ikutana

より良い偏差が見つかれば、現在のものを上書きして、最後に残っているものが最良なもの。　全数探索は無理なので、望みのない木を刈る必要がある。 #isec

@ikutana

再帰方法で桂庵する。I段までの特性があったときに、1段追加してどれくらいまで達成可能かというのを計算して、それがベストに達成不可能であれば枝を刈ってしまう。 #isec

@ikutana

つながりを考えれば、複数のS-Boxバリエーションを増やしておいたほうが良い。 #isec

@ikutana

非常に枝が多い。 #isec

@ikutana

いつプログラムが終わるのか予言できない。DESに関しては当時のコンピュータで5分で終了した。AESなら終わらない。 #isec

@ikutana

DESのS-Boxの順番を入れ替えたときにどれくらい強くなるか。すべてについて計算してみた。 #isec

@ikutana

差分解読法に対する強度を並べたグラフ。実際のDESのS-Boxは非常に強いバリアントになっている。適当に入れ替えると弱くなることが多い。 #isec

@ikutana

15段DESでの差分確率を考えたら上位0.6％に入っている。Coppersmithは差分解読法について対策しているという発言をしたが、裏付けができた。と考えている。 #isec

@ikutana

DESの差分解読法に対するベストなパターンがBihamに予言されていたが、実際にそのとおりだった。 #isec

@ikutana

計算時間は平均6分程度。最悪値は80分。 #isec

@ikutana

線形解読法からすると、全体の中ではむしろ弱いほうに位置する。これは松井さんからすると凄くラッキーだった。 #isec

@ikutana

15段では下から1.8％の強度に入っている。おそらく私が幸運だったと思う。 #isec

@ikutana

今の計算機で平均150秒、最大8時間。 #isec

@ikutana

DESの最初の実験的解読。2ー300万くらいのHP-UXを13台使って2週間かかった。今のPCなら2,3日でできる。 #isec

@ikutana

今の研究の方向性。線形解読法の精密性を上げる、一般化する、コンポーネントを線形解読法にベストにする。　こ#isec

@ikutana

実験解読の時は二つの線形近似式を使って鍵を求めた。鍵候補が信頼度付きで出てきたのでそれを組み合わせて計算して求めた。偏差が大きければ大きいほど鍵候補の順位の信頼性が高い。 #isec

@ikutana

多くの式を使って線形解読をする方法。一時期すたれていたが2004年からまたちょっと流行っている。 #isec

@ikutana

実際の現用暗号で攻撃が成功するかというと難しいかもしれない。 #isec

@ikutana

最良のS-Boxとはどんなものか。最大差分確率と最大線形偏差が最小になるものが欲しい。 #isec

@ikutana

差分は必ず偶数になるので、最小差分確率は加減がある。x^3は最小になるが、偶数ビットだと全単射にならない。逆元関数だと4になってします。 #isec