[crypto] Feistel構造の時代は終わったのか?

[Yoshitaka Ikeda]

dW : Security : DES $B$KBe$o$k(B Rijndael ($B%i%$%s%@!<%k(B)
http://www-06.ibm.com/jp/developerworks/security/010316/j_s-rijn.html#5

Feistel $B9=B$$N;~Be$O=*$o$C$?(B

$B$H$$$&$J$+$J$+D)@oE*$J%?%$%H%k$G$9!#(B

$BJ8>OFI$s$G$_$k$H!"$=$s$J$3$H$O=q$$$F$^$;$s(B(w
$B$=$b$=$b!"(BAES$B8uJd$@$C$?(BIBM$B$N(BMARS$B$OJQ7A(BFeistel$B9=B$$@$C$?$7!"(B
NESSIE$B$G:G=*E*$K;D$C$?(BMISTY($B8E$$$1$I(B)$B$b(BCamellia$B$b(BFeistel$B9=B$(B

$B$C$F$$$&$+!"(BCRYPTREC$B$N%V%m%C%/0E9f$@$H(BFeistel$B$8$c$J$$$N$O!"(B
Hierocrypt$B%7%j!<%:$H(B($B%O%$%V%j%C%I$J(B)SC2000$B$@$1$@$C$?$h$&$J!#(B

$B8D?ME*$K$O!"@_7W$NMF0W$5$dI|9f$,0E9f2=$HF10l$G$"$k$3$H$+$i9M$($k$H(B
Feistel$B9=B$$K$b$=$l$J$j$NMxE@$O$"$k$H;W$&!#(B

[Hideo "Sir MaNMOS" Morishita]

Post by Yoshitaka Ikeda
http://www-06.ibm.com/jp/developerworks/security/010316/j_s-rijn.html#5
Feistel $B9=B$$N;~Be$O=*$o$C$?(B
$BJ8>OFI$s$G$_$k$H!"$=$s$J$3$H$O=q$$$F$^$;$s(B(w

$BFI$s$G$_$^$7$?!#$J$<!"$3$s$J%?%$%H%k$,IU$$$?$N$+Ff$G$9$M!#(B

Post by Yoshitaka Ikeda
NESSIE$B$G:G=*E*$K;D$C$?(BMISTY($B8E$$$1$I(B)$B$b(BCamellia$B$b(BFeistel$B9=B$(B

$B<+J,$G<BAu$7$?4X78>e!";d$,$h$/;H$&(BCAST-[56]$B$b(BFeistel$B9=B$$G$9$M!#(B
$B$"$H!"(BCAST$B$GH=$kDL$j!"(B64bit$B%V%m%C%/$+$i(B128bit$B%V%m%C%/$X$N3HD%$b!"4JC1(B
$B$K9T$($?$j$7$^$9!#(B

$B%O!<%I%&%'%"<BAu$J$I$G$O(Bf$B$NItJ,$O$$$8$i$:$K!"$A$g$C$H%M%C%H%o!<%/$r$$(B
$B$8$k$@$1$G$h$$$G$9!#(B

$B$"$H!"(B($B;d$,CN$C$F$$$k8B$j!"4{CNJ?J8967b$H$+@~7A967b$H$+$G(B)$B$I$N$h$&$J(Bf
$B$r;H$($P!"967b$K6/$/$J$k$+$***@J8$OK-IY$G$9!#(B

SPN$B9=B$$@$H!"$=$N$"$?$j!"<+J,$G9M$($J$-$c$J$i$J$$$N$G!"<RFbFbIt$G;HMQ(B
$B$9$k$?$a$K!"$A$g$C$H$7$?0E9f$***@_7W$7$^$7$g$&!"$J$s$F$3$H$O$H$F$b$G$-$^(B
$B$;$s!#(B

$B$=$NE@(BFeistel$B$@$H!"$A$g$C$H!"(BSHA-1$B$K$"$o$;$F(B160bit$B%V%m%C%/$N0E9f$r(BCAST
$B$N(BS-Box$B$H(Bf[1-3]$B;H$C$F:n$C$F$_$h$&$H$+!"4JC1$K$G$-$^$9!#(B

[Yoshitaka Ikeda]

文章読んでみると、そんなことは書いてません(w

読んでみました。なぜ、こんなタイトルが付いたのか謎ですね。

なんなんでしょうね。
もしかして、IBMがMARSのCRYPTRECへの応募を取り下げたのも
関係しているのかもしれません。

そもそも、AES候補だったIBMのMARSは変形Feistel構造だったし、
NESSIEで最終的に残ったMISTY(古いけど)もCamelliaもFeistel構造
っていうか、CRYPTRECのブロック暗号だとFeistelじゃないのは、
Hierocryptシリーズと(ハイブリッドな)SC2000だけだったような。

自分で実装した関係上、私がよく使うCAST-[56]もFeistel構造ですね。

CAST-256ですよね？ いや、56bit版もあるんですか？
CASTはぜんぜん構造は知りませんでしたが、すくなくとも、
Applied Cryptgraphyを読む限りでは、Feistel構造でビット数可変
なんですよね？

個人的には、設計の容易さや復号が暗号化と同一であることから考えると
Feistel構造にもそれなりの利点はあると思う。

あと、CASTで判る通り、64bitブロックから128bitブロックへの拡張も、簡単
に行えたりします。

RC5とかRC6も同様ですよね。
これも、たぶんラウンド関数が全単射である必要がない
(構造自体から全単射であることが保障される)というFeistel構造のメリット
でしょうね。

ハードウェア実装などではfの部分はいじらずに、ちょっとネットワークをい
じるだけでよいです。

あんまりハードウェア実装はまじめに見たことはないんですが、
SPNだと、そのまんまダイレクトにビット幅が影響してきますよね。

あと、(私が知っている限り、既知平文攻撃とか線形攻撃とかで)どのようなf
を使えば、攻撃に強くなるかの論文は豊富です。

これについては、どっちが豊富なんだろうなぁ。
ただ、3段繰り返し攻撃とか見てると、Feistel構造は、線形攻撃・差分攻撃では
糸口は見つけやすいような気がします。

SPN構造だと、そのあたり、自分で考えなきゃならないので、社内内部で使用
するために、ちょっとした暗号を設計しましょう、なんてことはとてもできま
せん。

これは難しいでしょうね。

そういえば、暗号アルゴリズムの名前は失念したんですが、うまくSPN構造を
使って、暗号化と復号が同一処理(鍵の順番入れ替えるだけ)でできるような
暗号がありました。ゼミで誰かが論文紹介してたんだけどな。忘れちゃいました。

その点Feistelだと、ちょっと、SHA-1にあわせて160bitブロックの暗号をCAST
のS-Boxとf[1-3]使って作ってみようとか、簡単にできます。

まあ、速度さえ気にしなければ簡単に実現できますよね。

[Hideo "Sir MaNMOS" Morishita]

Post by Hideo "Sir MaNMOS" Morishita
$B<+J,$G<BAu$7$?4X78>e!";d$,$h$/;H$&(BCAST-[56]$B$b(BFeistel$B9=B$$G$9$M!#(B

CAST-256$B$G$9$h$M!)(B $B$$$d!"(B56bit$BHG$b$"$k$s$G$9$+!)(B
CAST$B$O$<$s$<$s9=B$$OCN$j$^$;$s$G$7$?$,!"$9$/$J$/$H$b!"(B
Applied Cryptgraphy$B$rFI$`8B$j$G$O!"(BFeistel$B9=B$$G%S%C%H?t2DJQ(B
$B$J$s$G$9$h$M!)(B

$B$4$a$s$J$5$$!#$o$+$j$K$/$+$C$?$G$9!#(B
CASt-5(64bit block)$B$H(BCAST-6(128bit block)$B$N$3$H$r=q$/$N$***@55,I=8=$r;H(B
$BMQ$7$F$7$^$$$^$7$?!#(B

$B!t0x$_$K(BCAST-5$B$K$O(B56bit$B80D9$NA*Br$O$"$j$^$;$s!#:GDc(B80bit$B$G$9!#(B

bit$BD92DJQ$H$$$&$N$O80D9$N$3$H$G!"J#?t$N80D9$5$r;HMQ$G$-!"$=$ND9$5$K$h$C(B

Post by Hideo "Sir MaNMOS" Morishita
$B$"$H!"(BCAST$B$GH=$kDL$j!"(B64bit$B%V%m%C%/$+$i(B128bit$B%V%m%C%/$X$N3HD%$b!"4JC1(B
$B$K9T$($?$j$7$^$9!#(B

RC5$B$H$+(BRC6$B$bF1MM$G$9$h$M!#(B
$B$3$l$b!"$?$V$s%i%&%s%I4X?t$,A4C1<M$G$"$kI,MW$,$J$$(B
($B9=B$<+BN$+$iA4C1<M$G$"$k$3$H$,J]>c$5$l$k(B)$B$H$$$&(BFeistel$B9=B$$N%a%j%C%H(B
$B$G$7$g$&$M!#(B

CAST-5$B$G$O(B64bit$B$r#2$D$KJ,3d$7$?!"C1=c$O(BFeistel$B9=B$$r$H$j$^$9$,!"(BCAST-6
$B$G$O(B128bit$B$r#4$D$KJ,3d$7(B

X2 ^= f1(X3,Km0i,Kr0i);
X1 ^= f2(X2,Km0i,Kr0i);
X0 ^= f3(X1,Km0i,Kr0i);
X3 ^= f1(X0,Km0i,Kr0i);

$B$H$$$&$h$&$J(B($B8eH>$O>/$70c$&(B)$B3HD%$7$?(BFeistel$B9=B$$r$H$j$^$9!#(B

Post by Hideo "Sir MaNMOS" Morishita
$B%O!<%I%&%'%"<BAu$J$I$G$O(Bf$B$NItJ,$O$$$8$i$:$K!"$A$g$C$H%M%C%H%o!<%/$r$$(B

$B$"$s$^$j%O!<%I%&%'%"<BAu$O$^$8$a$K8+$?$3$H$O$J$$$s$G$9$,!"(B

$B>e5-$GH=$kDL$j!"%i%&%s%I4X?t(B($B$d!"$=$l$KIU?o$9$k(BS-box$BEy(B)$B$O?7$7$/:***@.$9(B
$B$kI,MW$OL5$/!"$R$H$D$N%A%C%W$KF17OE}$N#2$D$N0E9f$r<BAu$9$k$3$H$bMF0W$K(B
$B$J$k$H9M$($i$l$^$9!#(B

$B;e8}$O8+$D$1$d$9$$$h$&$J5$$,$7$^$9!#(B

$B$^$"!"(BFeistel$B$K$7$F$b%i%&%s%I4X?t$***@_7W$R$H$D$R$H$D$KBP$7$F!"***@J8$,$"(B
$B$k$G$7$g$&$,!"$b$N$,4JC1$JJ,!"H/8+$5$l$?@H<e@-$b2~NI$7$d$9$$$N$+$H$O;W(B
$B$&$N$G$9!#(B

Post by Hideo "Sir MaNMOS" Morishita
$B$;$s!#(B

$B$3$l$OFq$7$$$G$7$g$&$M!#(B
$B$=$&$$$($P!"0E9f%"%k%4%j%:%`$NL>A0$O<:G0$7$?$s$G$9$,!"$&$^$/(BSPN$B9=B$$r(B

Post by Hideo "Sir MaNMOS" Morishita
$B$N(BS-Box$B$H(Bf[1-3]$B;H$C$F:n$C$F$_$h$&$H$+!"4JC1$K$G$-$^$9!#(B

$B$^$"!"B.EY$5$(5$$K$7$J$1$l$P4JC1$K<B8=$G$-$^$9$h$M!#(B

$B>e5-$N$h$&$J3HD%$G9T$C$F$$$/$H!"0F30!"B.EY$OMn$A$J$$$N$G$9!#$^$"!"%i%&(B
$B%s%I?t$,8z$$$F$/$k$@$1$G$9$,!#(B

[Yoshitaka Ikeda]

$B$H$j$$$=$.!"0E9f2=$HI|9f$,F10l=hM}$N(BSPN$B0E9f$r<($7$^$9!#(B
$B$b$A$m$s$G$9$,!"80%9%1%8%e!<%k$O5U$K$J$j$^$9!#(B
$B$3$l$O(BFeistel$B$G$bF1$8$G$9$h$M!#(B

$B$3$l$OFq$7$$$G$7$g$&$M!#(B
$B$=$&$$$($P!"0E9f%"%k%4%j%:%`$NL>A0$O<:G0$7$?$s$G$9$,!"$&$^$/(BSPN$B9=B$$r(B

ICEBERG$B$H$$$&%"%k%4%j%:%`$G$9!#(BFSE2004$B$GH/I=$5$l$?$C$]$$$G$9!#(B
$***@J8$O!"(B
http://www.di.ens.fr/~piret/publ/fse2004.pdf
$B$G!"FI$a$^$9!#(B

$BI|9f$,0E9f2=$HF10l$G$"$k$H$$$&OC$O!"(B3.8$B$K=q$$$F$"$j$^$9!#(B

3.8 Decryption Process
We now show that ICEBERG is an involutional cipher in the sense that
the only difference between encryption and decryption is in the key
schedule.

$B>ZL@$b:\$C$F$$$^$9!#8&5f<<$N%<%_$GFI$s$@;~$KF10l$G$"$k$H$$$&$3$H$K(B
$B5?Ld$r;}$C$?$N$G8!>Z$7$F$_$?$i8+;v$KF10l$K$J$k9*L/$***@_7W$G$7$?!#(B
$B$3$l$O!"$A$g$C$H$7$?46F0%b%N!#(B

$B$A$J$_$K!"F|K\8l$G(B ICEBERG cipher$B$G8!:w$9$k$H!"CN$C$F$k?M$,=q$$$?(B
NICT$B$N5!K/$K$"$?$C$?$j!#(B
#$B9b3,:9J8967b$G967b$7$F$^$9!#(B

[Hideo "Sir MaNMOS" Morishita]

Post by Yoshitaka Ikeda
$B$3$l$O!"$A$g$C$H$7$?46F0%b%N!#(B

$B$"$j$,$H$&$4$6$$$^$9!#<h$j9g$($:(BApendix$B$N>ZL@$rFI$s$G$_$^$7$?$,!"(Bs-box
$B$H(Bbit permutation$B$,BP>N$J$b$N$r;HMQ$9$k$N$,%_%=$G$9$M!#(B

$B$H$/$K(Bapendix c$B$rFI$`$H(Bs-box$B$OMM!9$J$b$N$G<BAu$G$-$k$h$&$G$9$,!"(B
permitation table$B$b0c$&$b$N$G$b$J$s$H$+$J$j$=$&$J5$$,$7$^$9!#(B

bit permitation$B<+BN$O!"(Bsoftware$B$h$j!"$`$7$m%O!<%I>e$G<BAu$7$?$[$&$,3Z(B
$B$G$9$+$i!"BP>N$J(BSPN$B$O%O!<%I20$5$s$K$O$H$/$K$"$j$,$?$$$G$7$g$&$M!#(B