Data Encryption Standard
総当り攻撃よりも少ない計算量で16ラウンドのDESを破ることができる攻撃法が3種類知られている。差分解読法 (DC)、線形解読法 (LC)、Davies' attack である。しかし、これらの攻撃法は理論上のものであって、実際に応用するのは現実的ではない。これらを certificational weaknesses と呼ぶこともある。
図2にあるF-関数はブロックの半分(32ビット)を一度に処理する。以下の4段階がある。
Expansion - expansion permutation と呼ばれる方式で32ビットを48ビットに拡張する。図では E で示されている部分である。入力のうち半分のビットの複製16ビット分を出力のビット列に追加する。その出力は8個の6ビットの部分からなり、それら6ビットのうちの中央4ビットは入力の対応する4ビットの部分と同じで、両端の1ビットずつは入力上で隣接する部分のビットの複製である。
Key mixing - ラウンド鍵と上の出力結果をXOR操作で結合する。ラウンド鍵は48ビットで、もともとの鍵から「鍵スケジュール」(後述)によって16個のラウンド鍵が生成される。
Substitution - ラウンド鍵を混ぜた後、6ビットずつに分けてSボックス (substitution box) に入力する。8個のSボックスは入力の6ビットから4ビットの出力を生成し、このときルックアップテーブルの形で提供される非線形な変換を行う。SボックスがDESの安全性の根幹であり、これが無かったならば暗号化の処理は線形であり容易に破ることができることになる。
Permutation - Sボックス群の出力である32ビットに固定の並べ替えを施す。図では P で示した部分である。このとき、各Sボックスの出力が次のラウンドでSボックスに展開されるとき、6個の異なるSボックスに分散するよう並べ替える。
Sボックスでの置換とPボックスでの並べ替えとEでの拡張を交互に行うことで、クロード・シャノンが安全で実用的な暗号に必要な条件とした「拡散とかく乱」を提供する。
1980年代末にエリ・ビハムとアディ・シャミアが再発見した。IBMとNSAにはそれ以前から知られていたが、秘密にされていた。16ラウンドのDESを破るには、2の選択平文を必要とする。DESはDCへの耐性を考慮して設計されている。