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

@ikutana

招待講演はさすがに人がおおいな。#isec

@ikutana

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

@ikutana

今日の話はどちらかというと、歴史的な話。昔話だけでもなんなので、最近の話題も入れる。#isec

@ikutana

入社したのは1987年でエラー訂正符号を研究していた。MOのエラー訂正のためにGF(2^8)の符号を小さく実装する研究をしていた。結局ROMの方が小さくなってお蔵入りになったｗ #isec

@ikutana

AESでも、このころの研究で作った逆現回路が使われている。当時は思いもよらなかった。 #isec

@ikutana

FEAL暗号が暗号業界にもたらしたものは大きい。線形解読に関する最小パス探索プログラム。計算量的にDESは当時はできなかったけど、2,3年前に完全なパスが計算できた。 #isec

@ikutana

良いS-Boxとはなんなのか。まだ未解決問題が多い。最後に証明可能安全性。 #isec

@ikutana

FEAL。NTTが作った初めて商業的には成功した暗号。DESはハードウェア向きだったが、FEALはソフトウェア向き暗号だった。 #isec

@ikutana

典型的なFeistel構造をとっている。中野F関数にはS-Boxは使われていない。算術演算で実現されている。 #isec

@ikutana

算術加算は最下位ビットが線形なのでこれを出発点に解読研究が始まった。 #isec

@ikutana

最初は選択平文で攻撃。8個で解読。　既知平文で200個という研究がでた。ここから線形解読につながった。 #isec

@ikutana

3段のFEAL暗号は線形な関係がある。4段目以降はパスがつながらない。 #isec

@ikutana

論文中に陽には書いていないが、それぞれのS-Boxの線形関係式を加算することによって鍵のビット数を減らした線形関係式が使われていた。 #isec

@ikutana

平文を場合分けして、それぞれに付いて線形関係式を解析したら、キャリーが上がらない場合定数になる。 #isec

@ikutana

平文の領域を減らすことにより鍵の関与数を減らすことができる。 #isec

@ikutana

Partitioning Cryptanalysisという名前で一般化された。 #isec

@ikutana

DESには適用できなかった。そこで線形近似という考え方につなげていった。 #isec

@ikutana

マスクされた入力のパリティとマスクされた出力のパリティの一致率が0.5からどれくらい離れているか。 #isec

@ikutana

関数が面倒ならばバイパスしてやればいいという考えが元々の始まりだった。 #isec

@ikutana

プロジェクトXでやって欲しいなぁ。 #isec

@ikutana

変数と同じだけ式があれば教科書的には解けるが実際に解くためには変数を減らす必要がある。 #isec

@ikutana

あるビットをとると一致確率が、12/64になる。　1985年にはShamirがCRYPTOで示唆していた。93年に松井さんが再発見。 #isec

@ikutana

S-Boxはいっぱいあるのでつなげていかなければいけない。 Piling-up Lenma 線形特性確率はBiasで計算すればそのまま乗算で計算できる。 #isec

@ikutana

ここまでは簡単な理屈だが、どのパスが一番高いのかというのが問題。ローカルに最大なのがパスが繋がるとは限らない。 #isec

@ikutana

DESでパス探索が可能だったのは奇跡的だった。 #isec