差分特性

差分特性とは、ラウンドごとの差分の列であり、既知の入力差分から既知の出力差分へ至る道筋を表す。各ラウンドが独立というマルコフ仮定のもとで、その確率は各ラウンドの確率の積になる。差分解読法の基本部品である。

Biham と Shamir は1990年に、DES を全数探索より速く攻撃できることを示した。ただし、確率の高いラウンドが一つあれば足りるわけではない。重要なのは全体の確率をランダム置換と比べたときの値で、新しい暗号に良い特性を見つける作業は、攻撃そのものとほぼ同じくらい手間がかかる。