FEAL-NXのソフトウェア実装

NTT 情報流通プラットフォーム研究所
大塚 浩昭

2000年9月29日 ISEC研究会

植田 広樹

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

1 /25

概要

8-bit CPU 上でのFEAL-32Xの速度面での最適化について報告
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

2 /25

背景
• ネットワーク接続された小型簡易端末<e.g.> スマートカードが普及• ネットワーク上でのなりすまし問題↓• 小型簡易端末を認証することが必要
FEAL-NXのソフトウェア実装により実現
FEAL-NXのソフトウェア実装により実現
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

3 /25

小型簡易端末での認証• 認証プログラムの動作場所– 耐タンパ性を備えたチップ上• チップ– 安価： 数十円～数百円で購入可能– CPU 低速、メモリ 極小<e.g.> low-endのスマートカード→ 8-bit CPU が中心
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

4 /25

想定する実装環境
Low-end のスマートカード
CPUアーキテクチャ…

Z80 (8bit-CPU)

8-bit CPUのディファクトスタンダード

CPUクロック

1～8 MHz
数Kバイト程度
256バイト程度
…

ROM

…

RAM

…

認証プログラムが利用出来るメモリは、さらに少2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

5 /25

認証方式

共通鍵暗号による認証を採用
理由： • 公開鍵暗号– 多くのメモリと演算能力が必要• ハッシュ関数– 内部演算が32-bit単位

2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

6 /25

暗号アルゴリズム

FEAL-32Xを採用
理由： • 8-bit CPUでの実装に有利– 内部演算 … 8-bit単位– S-box用テーブルが不必要 → 少メモリ• 安全性 … 現状では問題なし– 全数探索法 → 鍵長 128-bit– 差分解読法 → 32段以上のFEALには適用不可– 線形解読法 → 26段以上のFEALには適用不可
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

7 /25

実装にあたっての前提
前提 :実際にスマートカード上で利用できるプログラム構成

・プログラムはROM上に配置→ プログラム自己書き換え なし・スマートカード上の別アプリケーションと共存→ SP書き換え なし
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

8 /25

実装にあたっての仕様
プログラム仕様・CALL文で呼び出される・レジスタによるポインタ受け渡し
実装条件
・プログラムサイズ … 数百バイト・テーブル参照 なし
・データランダム部のみ実装
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

9 /25

データランダム部
データランダム部

参照

拡大鍵実装対象
実装対象• low-endのスマートカードでは鍵更新頻度 低↓• あらかじめ拡大鍵を計算しておき保存
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

10 /25

最適化への道
レジスタ内での処理を最優先
スタック退避、メモリ退避 … 原則行わない

IX,IYレジスタの使用制限
8-bitに分割不可なレジスタ … なるべく使用しない

表裏レジスタの役割分担
レジスタ切替回数 … 最少化

ポインタアドレスの制限
実用上支障がない程度にアドレス位置を制限
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

11 /25

実装結果
実装 総 state 数 …… 6169 states
ROM(byte)

データ
ランダム部

212

RAM(byte)

処理速度・処理時間[ 5MHz ]6

51.8 kbit/s(1.2 ms/block )・ ROM …プログラム規模のバイト数
・ RAM …動的に使われるメモリのバイト数
スタックを含み、平文、暗号文、拡大鍵を除く
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

12 /25

考察
本当に最適化されたのか？
(これ以上最適化の余地は無いのか？)↓
予測値を算出
理想的な 8-bit CPU での 総 state 数を算出
Z80上における修正を加える↓
予測値と実装結果とを比較考察
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

13 /25

理想的な 8-bit CPU とは？
レジスタ数 … 無限命令形… 直交
算術演算 … 3オペランド：レジスタ指定
ソース

2

ディスティネーション

1

メモリアクセス … 8-bit LD命令のみ
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

14 /25

データランダム部 構造
Plaintext {Ciphertext block}(64 bits)⊕(64 bits)(KN , K N+1, K N+2 , K N+3){(KN+4, KN+5 , KN+6, K N+7 )}(32 bits)
L 0{RN}⊕ R0{L N}

L 0{RN }⊕前処理(32 bits)f

K0{KN-1 }R0{LN}
K1{KN-2}

L1{RN-1}⊕f

R1{LN-1}

K2{KN-3 }L2{RN-2}⊕Feistel構造×
32段

R2{LN-2}f

KN-1{K 0}

L N-1 {R1}⊕f

RN-1{L1}⊕ L N{R0}

RN{L 0}⊕

後処理(KN+4 , KN+5 , KN+6 , KN+7){(KN, KN+1, KN+2, KN+3)}

Ciphertext {Plaintext} block

2000年9月29日 ISEC研究会{ } : DecipheringFEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

15 /25F関数 構造β(16 bits)
β0

β1

S0

拡大鍵 2バイトα0

出力値 4バイトS11⊕⊕α1f ( α,β)(32 bits)

入力値 4バイトα(32 bits)

S0

⊕

X2
YS1X1

⊕

α2

αi, βi : 8 bits

α3

Y = S0 (X1, X2) = Rot2 ((X1+X2) mod 256)
Y = S1 (X1, X2) = Rot2 ((X1+X2+ 1) mod 256)
Y : output (8 bits), X1/ X2 : inputs (8 bits),Rot2 (Y) : a 2-bit left rotation on 8-bit data Y
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

16 /25

Feistel構造 1段当たり
動作内容
拡大鍵コピー
拡大鍵ポインタ+1S-box

排他的論理和加算
インクリメント
左ローテート@state回数228428764444

合計

14123216832114

Feistel構造 1段あたりのstate数 = 114 states
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

17 /25

Feistel構造 32段繰り返し
動作内容
Feistel構造 1段
条件分岐(分岐あり)
条件分岐(分岐なし)

回数

3231
1@state

114
138

合計

3468
403
84059

Feistel構造 32段繰り返し の state 数= 4059 states
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

18 /25

前処理・後処理
動作内容
平文コピー
拡大鍵コピー
暗号文コピー
拡大鍵ポインタ+1
排他的論理和回数

81683224@state

合計

77764561125619296512

前処理・後処理での state 数= 512 states
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

19 /25

理想的な 8-bit CPU 上での概算値
理想的な 8-bit CPU上での総 state 数＝ Feistel構造 32段繰り返し＋前後処理 ＋メインルーチンリターン＝ 4059＝

2000年9月29日 ISEC研究会+ 512 + 104581 states
FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

20 /25

Z80 CPUによる修正
演算結果はAレジのみに格納↓

レジスタ数が有限↓命令

回数@state

段数

合計

命令

EXX2432256

LD(F 関数)
LD(前後処理)回数@state回数

合計88443221024641088

Z80 CPU上での予測値＝理想的な 8-bit CPU での概算値＋ 上記修正項目による増加＝ 4581 + 256 + 1088＝
2000年9月29日 ISEC研究会

5925 states
FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

21 /25

実装結果との比較
総 state 数

F関数[総ステート数 ÷ 32]

実装結果

6169

192.8

予測値

5925

185.2

誤差

2447.6

誤差は、全体の約 4％→ 十分な最適化が行われている と判断2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

22 /25

他の共通鍵暗号との比較
T-DES と比較
処理速度
本稿：
1.2 ms/block
T-DES：30 ms/block [5MHz,ST16CF54B(8bitCPU)]
出典: RSA LABORATORIES,”CryptoByte”

ROM
本稿：216バイト
T-DES：512バイト + α(S-boxテーブルのみで512バイト)
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

23 /25まとめ• FEAL-32X(データランダム部)を、Z80上で実装した– RAM 6バイト , ROM 212バイト– 6169 states/block (51.8kbit/s [5MHz] )• 十分最適化されていることを示した• 他の共通鍵暗号と比較して、少ないROMで実装できることを示した
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

24 /25

URL

http://info.isl.ntt.co.jp/• FEAL-NX– 暗号技術概要説明書– 仕様書– 自己評価書2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

25 /25

《参考》実装結果一覧

データ鍵拡大部
ランダム部ROM(byte)

RAM(byte)

処理速度／時間[ 5MHz ]

最適化
あり

212

651.8 kbit/s

最適化
なし

278

14

11.4 kbit/s

最適化
あり

465

8

1.67 ms/block

最適化
なし

225

35

7.17 ms/block[2000年9月29日現在]

2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

26 /25

《参考》 データランダム部 構造
Plaintext {Ciphertext block}(64 bits)⊕(64 bits)(KN , K N+1, K N+2 , K N+3){(KN+4, KN+5 , KN+6, K N+7 )}(32 bits)← データランダム部 構造(32 bits)

L 0{RN}⊕ R0{L N}

L 0{RN }⊕f↓ F関数 構造K0{KN-1 }β(16 bits)

R0{LN}β0
S0

K1{KN-2}

L1{RN-1}⊕f

α0

R1{LN-1}

S11
K2{KN-3 }L2{RN-2}⊕α1α(32 bits)

X2

KN-1{K 0}f⊕f ( α,β)S0

L N-1 {R1}⊕(32 bits)

R2{LN-2}

f

⊕

β1

Y

RN-1{L1}

S1X1

⊕

⊕

α2

αi, βi : 8 bits

α3

⊕ L N{R0}

RN{L 0}⊕(KN+4 , KN+5 , KN+6 , KN+7){(KN, KN+1, KN+2, KN+3)}

Ciphertext {Plaintext} block

2000年9月29日 ISEC研究会

Y = S0 (X1, X2) = Rot2 ((X1+X2) mod 256)
Y = S1 (X1, X2) = Rot2 ((X1+X2+ 1) mod 256)
Y : output (8 bits), X1/ X2 : inputs (8 bits),Rot2 (Y) : a 2-bit left rotation on 8-bit data Y{ } : Deciphering

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

27 /25

《参考》 増加要因

F関数内のレジスタ切り替え命令
レジスタの割り当てによって、レジスタを切り替える回数がさらに増加

レジスタ内容退避
レジスタに保存しきれない値をスタックやメモリに退避
2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

28 /25

《参考》 プログラム呼び出し例

LDHL , plain-text

LDDE , cipher-text

LDBC , expanded-key
CALL encrypt

2000年9月29日 ISEC研究会

FEAL-NXのソフトウェア実装

Ｃｏｐｙright (C) NTT 2000

29 /25