CRYPTREC EX-3204-2022

軽量暗号の安全性に関する調査及び評価（Elephant, ISAP, Romulus）
井上明子 (NEC)2022 年 12 月

目次
第 1 章 エグゼクティブサマリー

2

第 2 章 準備3

2.1

記号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

認証暗号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.3

認証暗号を実現するための暗号プリミティブ . . . . . . . . . . . . . . . . . . . . . .

3

第 3 章 Elephant5

3.1

準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.2

仕様 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.2.1

モード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3.2.2

プリミティブ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.3.1

仕様上の安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.3.2

モードの安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.3.3

プリミティブ及び関連方式の安全性 . . . . . . . . . . . . . . . . . . . . . . .

9

3.3.4

その他 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.3

第 4 章 ISAP

12

4.1

準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

4.2

仕様 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

4.2.1

モード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

4.2.2

プリミティブ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4.3.1

仕様上の安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4.3.2

モードの安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.3.3

プリミティブ及び関連方式の安全性 . . . . . . . . . . . . . . . . . . . . . . .

17

4.3.4

その他 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.3

第 5 章 Romulus

20

5.1

準備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.2

仕様 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.2.1

プリミティブ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.2.2

モード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3

5.3.1

仕様上の安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24
25

5.3.2

モードの安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

5.3.3

プリミティブの安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.3.4

その他 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

1

第 1 章 エグゼクティブサマリー
現在開催中の NIST Lightweight cryptography プロジェクト (以下, NIST LWC) 1 においてファイ
ナリストとして残っている 10 候補のうち, 3 つの候補 Elephant [21], ISAP [38], Romulus [55] の安全性について調査を行った. 詳細には, Final round2 に提出されている各候補の仕様に対する安全性評価に関する文献を調査した. その結果として 2022 年 9 月末時点では, 全ての候補に対して提案者らが主張する安全性を損ねるような解析結果は発表されていないことが分かった.
本報告書では, 各候補に対してその仕様 (アルゴリズム) 及び安全性に関する文献の調査結果を記載する. まず 2 章で必要な記法等の準備を行い, 3 章, 4 章, 5 章でそれぞれ Elephant, ISAP, Romulusについて述べる. 各候補の章は準備, 仕様, 安全性の 3 節に分かれている. 準備の節ではその候補の章に必要な記法を記載する. 仕様の節では, Final round に提出されている仕様書 [21, 38, 55] に基づき,各候補のアルゴリズムを記載する. 但し, 1 つの候補に安全性や効率性等の異なる複数のアルゴリズ
ムが含まれるため, そのうち Primary member として挙げられているアルゴリズムのみを詳述し, 他
アルゴリズムは概要を記載する. 安全性の節は以下 4 つの構成になっている.

• 仕様上の安全性: 各候補の提案者らが主張する主要な安全性とそのレベルを概説する.
• モードの安全性: 各候補が用いるモードの証明可能安全性について, 著者らの主張の詳細や安全性評価の調査結果をまとめる.

• プリミティブの安全性及び関連方式の安全性: 各候補で用いる暗号プリミティブの攻撃可能段数の調査結果をまとめる. 必要に応じてそのプリミティブを用いた他方式の攻撃可能段数についても述べる.

• その他: 上記 2 つ以外の安全性解析結果について述べる. 例として, プリミティブのラウンド数を削減した場合の各候補への安全性評価, サイドチャネル攻撃評価, 量子計算機を用いた場合の安全性評価が挙げられる.
注意事項として, ISAP においては NIST LWC ファイナリストの 1 つ Ascon [41] とアルゴリズムを共有する部分があるため, 該当部分のアルゴリズムや共通する安全性調査の結果は概要のみを記載す
ることとする. 詳細は Ascon の安全性調査レポートを参照されたい.

1 https://csrc.nist.gov/projects/lightweight-cryptography
2 https://csrc.nist.gov/Projects/lightweight-cryptography/ﬁnalists2

第 2 章 準備

2.1

記号

自然数 n に対し, {0, 1}n は n ビットのビット列の集合を指し, {0, 1}∗ は任意長のビット列の集合を表す. ビット列 X ∈ {0, 1}∗ に対し, |X| は X のビット長を指す. ビット列 X, Y ∈ {0, 1}∗ に対し,$

X k Y は X と Y の連結であり, X ⊕ Y は X と Y の排他的論理和を表す. 集合 A に対し, a ←−AはA から元 a を一様ランダムに選ぶ操作を指す.

2.2

認証暗号

入力データの秘匿と改ざん検知を同時に実現する共通鍵暗号方式を認証暗号 (Authenticated en-

cryption with associated data; AEAD) と呼ぶ [12]. 秘密鍵を共有する二者間において, 認証暗号の暗号化関数の入力は秘密鍵 K, 初期ベクトルの役割を持つナンス (Nonce) N , 任意長の平文 M , 任意長の AD (Associated data) A である. ここで AD とは暗号化はしたくないが改ざん検知は行いたい情報であり, 例えば通信プロトコルのバージョンなどの情報がこれに該当する. 暗号化関数出力は暗号文 C とタグ T である. 一方, 復号関数の入力は秘密鍵 K, ナンス N , AD A, 暗号文 C, タグ T である. もし (N, A, C, T ) に改ざんが検知されなければ, 復号関数は復号結果の平文 M を出力し, そう
でなければ単一のエラーメッセージ ⊥ を出力する.
安全性指標

認証暗号の安全性は秘匿 (Privacy) と改ざん検知 (Authenticity) の 2 つの指標によって評価される. 秘匿の安全性は, 暗号化オラクルにアクセスできる攻撃者が認証暗号の暗号化関数とランダムオラクル $ を判別できる確率で評価される. 但し, $ のインターフェースや入出力のビット
長は暗号化関数と同一であるとする. 改ざん検知の安全性は, 暗号化オラクルと復号オラクルにアクセスできる攻撃者が復号オラクルから ⊥ 以外の出力を得られる確率で評価される. この 2 つの安全性を定義する攻撃者の設定として「暗号化オラクルに対して同じナンスを 2 度以上クエリしてはならない」というものがあり, この設定は Nonce respecting と呼ばれる. この設定に従わない攻撃者, つまり暗号化クエリに対して同じナンスを 2 度以上クエリする攻撃者の設定を Nonce misuse と呼ぶ.
また, 秘匿と改ざん検知の 2 つの安全性を 1 つにまとめた安全性指標も存在する [95]. その安全性
は, 暗号化オラクルと復号オラクルにアクセスできる攻撃者が Real world (認証暗号の暗号化関数及び復号関数) と Ideal world ($ 及び如何なる入力に対しても ⊥ のみを出力する関数) とを判別できる
確率で評価される. この安全性は上記で述べた秘匿の安全性と改ざん検知の安全性の和で上界を取ることができる.

2.3

認証暗号を実現するための暗号プリミティブ

認証暗号を実現するための固定長入出力の暗号部品として Tweakable ブロック暗号 (Tweakable

block cipher; 以下 TBC) が挙げられる. TBC はブロック暗号の拡張であり, 秘密鍵と平文の他にTweak と呼ばれる公開調整値を入力に持つ, 固定長入出力の鍵付き置換である [82, 83]. TBC は暗号

3

e と復号関数 D
e の対で定義される. 暗号化関数の入力は秘密鍵 K, n ビット平文 M , t ビット
化関数 E
e T (M ) = C と表記する. 復号関数はTweak T であり, 出力は n ビットの暗号文 C である. これを E
K

秘密鍵 K, n ビット暗号文 C, t ビット Tweak T を入力として取り, n ビットの平文 M を出力する.
e T (C) = M と表し, De T (Ee T (M )) = M である. ここで t = 0 の場合は, E
eT , De T はブロッ
これを D
K

K

K

K

K

ク暗号と見なすことができる.
自然数 n に対して Perm(n) を n ビット入出力の置換全体の集合とする. また, π̃ : {0, 1}t ×{0, 1}n →{0, 1}n を, ∀T ∈ {0, 1}t について π̃(T, ·) ∈ Perm(n) となる写像であるとする. ここで TPerm(t, n) を$e←
e を, Tweakable uniform random permutaion
上記のような π̃ の全体集合とする. P− TPerm(n) なる P
(TURP) と呼ぶ. TBC の安全性は TURP との判別成功確率で定義される. 選択平文攻撃を行う攻撃者に対して TURP との判別が困難である TBC を Tweakable pseudo random permutaion (TPRP)$と呼ぶ. ブロック暗号の場合の安全性は P ←− Perm(n) なるランダム置換 P との判別成功確率で定義され, 選択平文攻撃を行う攻撃者に対してランダム置換との判別が困難であるブロック暗号を Pseudo

random permutaion (PRP) と呼ぶ.
また, 認証暗号のプリミティブとして鍵なし置換が用いられる場合もある. その場合の認証暗号の安全性評価においては, 用いる置換を公開ランダム置換と置き換えて証明を行うのが一般的である.

4

第3章

Elephant

Elephant [21] は暗号学的置換をプリミティブとして用いた認証暗号である. 用いる置換は ISO/IEC
29192-5:2016 [68] や FIPS 202 [5] において標準化されているものと同じもしくは同様である. モード
構成については NIST LWC ファイナリストのうち唯一高度な並列実行が可能な方式であり, 他ファ
イナリストとは設計思想が大きく異なるのが特徴である. 2022 年 9 月末時点で, 提案者らが仕様書において主張する安全性を損なう解析結果は発表されていない.

3.1

準備
n

自然数 n について, X1 . . . Xℓ ←− X は X を ℓ = d|X|/ne 個の n ビットブロックに分割することを指す. 但し |X|/n 6= d|X|/ne のとき, 最後のブロック Xℓ は n ビットになるよう 0 でパディングされている. ビット列 X ∈ {0, 1}n , 自然数 i ≤ n について, X  i (resp. X  i) を X の i ビット左論理
シフト (resp. 右論理シフト) とし, X ≪ i (resp. X ≫ i) を X の i ビット左巡回シフト (resp. 右
巡回シフト) とする. ビット列 X ∈ {0, 1}∗ , 自然数 i ≤ |X| について, bXci は X の左 i ビット列を
指す.

3.2

仕様

Elephant は暗号学的置換をプリミティブとして用いた認証暗号利用モードの名称であり, かつ 3 つの認証暗号 Dumbo, Jumbo, Delirium をまとめた総称である. この 3 方式は全てモード構成が Elephant であり, 用いる置換がそれぞれ異なる. Dumbo, Jumbo, Delirium はそれぞれ Spongent-π[160], Spongent-π[176], Keccak-f [200] を暗号プリミティブとして用いる. つまり, Dumbo は Elephant-Spongent-π[160],
Jumbo は Elephant-Spongent-π[176], Delirium は Elephant-Keccak-f [200] である. Primary member
は Dumbo である.

3.2.1

モード

本節では Elephant のモード構成と 3 つのインスタンスの仕様について述べる. まずモードの概要
として, 認証暗号モードとしての Elephant の構成は Enc-then-MAC 構造と呼ばれるもので, まず平文を暗号化したのち暗号文をメッセージ認証コード (Message authentication code; MAC) で処理してタグを導出する. 暗号化部分は CTR モード, MAC 部分は Protected counter sum [14, 84] と同様の構成である. 暗号化や MAC の内部では置換を用いた TBC 構成が使われており, その構成は Masked

Even-Mansour [54] を簡易にしたものである.
より詳細な定義として, Elephant の暗号化関数アルゴリズムを Alg. 1 に, 図を図 3.1 に示す. 但し

P は n ビット入出力の置換である. 復号関数は省略する. 暗号化関数は入力として k ビット秘密鍵
K, m ビットのナンス N , 任意長の AD A, 任意長の平文 M を取り, 出力は |M | ビット暗号文 C, t
ビットタグ T である. 具体的なパラメータや用いる置換等は各インスタンスにより異なる. その違い
は表 3.1 の通りである. また, 関数 mask について φ1 : {0, 1}n → {0, 1}n を線形帰還シフトレジスタ5図 3.1: Elephant の暗号化関数. Elephant のウェブサイト [3] より引用.
表 3.1: Elephant の各インスタンスにおける違い. 文献 [21] より一部引用.

方式

鍵長 k

ナンス長 m

置換サイズ n

タグ長 t

置換 P

φ1

Dumbo

128

96

160

64

Spongent-π[160]

(3.1)

Jumbo

128

96

176

64

Spongent-π[176](3.2)

Delirium

128

96

200

128

Keccak-f [200](3.3)(Linear feedback shift register; LFSR), id を恒等関数とし, φ2 = φ1 ⊕ id と定義する. このとき, 関
数 mask は以下の通り定義される.
ban−kmaska,b).
K = φ2 ◦ φ1 ◦ P(K k 0

φ1 の定義はインスタンスにより異なる. 0 ≤ i ≤ 24 について, xi を 8 ビットワードとするとき,
Dumbo, Jumbo, Delirium における φ1 はそれぞれ以下の通り定義される.

3.2.2(x0 , . . . , x19 ) 7→ (x1 , . . . , x19 , x0 ≪ 3 ⊕ x3  7 ⊕ x13  7),(3.1)(x0 , . . . , x21 ) 7→ (x1 , . . . , x21 , x0 ≪ 1 ⊕ x3  7 ⊕ x19  7),(3.2)(x0 , . . . , x24 ) 7→ (x1 , . . . , x24 , x0 ≪ 1 ⊕ x2 ≪ 1 ⊕ x13  1).

(3.3)

プリミティブElephant で用いられている暗号プリミティブはインスタンスにより異なる. 本節では, 用いられている 3 つの置換についてそれぞれ概要を説明したのち, Primary member の Dumbo で使用されている Spongent-π[160] の仕様を説明する.
概要

Spongent-π[160] は 160 ビット入出力の置換である. そのラウンド関数は, CHES 2011 でBogdanov らによって提案されたハッシュ関数 Spongent [24] で用いられている内部置換のラウンド関数を基に Elephant 提案者らによって設計されている [21]. なお, Spongent は ISO/IEC 29192-

5:2016 [68] において標準化されている. またラウンド数は, 文献 [24] にて用いられている Spongent
内部置換のラウンド数決定方法に則って 80 段と決定されている.

6

Algorithm 1 Elephant encryption algorithm enc
Input key (K, N, A, M ) ∈ {0, 1}k × {0, 1}m × {0, 1}∗ × {0, 1}∗
Output (C, T ) ∈ {0, 1}|M | × {0, 1}tn1: M1 . . . MℓM ←−M
2: for i = 1, . . . , ℓM do
3:

i−1,1
Ci ← Mi ⊕ P(N k 0n−m ⊕ maskK) ⊕ maski−1,1
K

4: C ← bC1 . . . CℓM c|M |n

5: A1 . . . AℓA ←− N kAk1n

6: C1 . . . CℓC ←− C k1
7: T ← A1
8: for i = 2, . . . , ℓA do
9:

i−1,0
T ← T ⊕ P(Ai ⊕ maskK) ⊕ maski−1,0K

10: for i = 1, . . . , ℓC do
11:

T ← T ⊕ P(Ci ⊕ maski−1,2) ⊕ maski−1,2
K
K0,0T ← P(T ⊕ mask0,0
K ) ⊕ maskK

12: return(C, bT ct )Spongent-π[176] は 176 ビット入出力の置換である. Spongent-π[176] はハッシュ関数 Spongent のインスタンス Spongent-160 1 の内部で用いられている 176 ビット入出力の内部置換と同じであり, ラ
ウンド数は 90 段である.

Keccak-f [200] は 200 ビット入出力の置換である. Keccak-f [200] はハッシュ関数 Keccak [17] の 200
ビット入出力内部置換として定義されているものと同じであり, ラウンド数は 18 段である. なお,

Keccak ハッシュは 1600 ビット入出力置換を用いたインスタンスが FIPS 202 [5] において標準化されている.

Spongent-π[160] の仕様

160 ビットの入力 X に対し, Spongent-π[160] の出力は以下のように定義

される.

for i = 1, . . . , 80 do
X ← X ⊕ 0153 k ICounter160 (i) ⊕ rev(0153 k ICounter160 (i))
X ← sBoxLayer160 (X)X ← pLayer160 (X)
ここで, rev は入力のビット順番を逆にする操作である. ICounter160 は 7 ビット LFSR で, 帰還多項式が x7 + x6 + 1 であり, 初期値が 1110101 のものである. sBoxLayer160 は表 3.2 で定義される 4 ビット

S-box を 40 個並列に並べたものである. pLayer160 は入力の j 番目のビットを以下で定義する P160 (j)番目のビットに移動させる操作である.
(
40 · j mod 159
P160 (j) =159(j ∈ {0, . . . , 158})(j = 159)

1 ハッシュ関数 Spongent-160 はハッシュ長が 160 ビットであることを指す. Spongent-π[160] との混同に注意されたい.

7

表 3.2: Spongent-π[160] の sBoxLayer160 内部で用いる 4 ビット S-box. 16 進数表現で記載.

3.3

X

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

S(X)

E

D

B

0

2

1

4

F

7

A

8

5

9

C

3

6

安全性

2022 年 9 月現在, Elephant はいずれの方式についても仕様書で主張される安全性を脅かす攻撃は提案されていない. 本節では, まず 3.3.1 節で提案者らが主張する安全性を概説し, 3.3.2 節でモードの安全性の根拠及び第三者評価について述べる. 3.3.3 節にて用いる置換及び関連方式の解析状況, 3.3.4
節にてその他の解析について述べる.

3.3.1

仕様上の安全性
表 3.3: Elephant のインスタンス 3 方式に対する安全性 [3, 21].

方式

解読・改ざんに必要な
オフライン計算量

オンライン計算量の上限

Dumbo

2112

250 バイト

Jumbo

2127

250 バイト

Delirium

2127

274 バイト

提案者らが主張する安全性を表 3.3 に示す. ここで表内の「オンライン計算量の上限」とは, 1 つの鍵で処理可能なデータ量の上限を指す. また「解読・改ざんに必要なオフライン計算量」とは, 公開
ランダム置換へのアクセス回数を指す. これは, 攻撃者に対してオンライン計算量の上限まで暗号化
オラクルと復号オラクルへのアクセスを許した場合に, 暗号文解読やタグ改ざんのために攻撃者が必要となる時間計算量に相当する. 表 3.3 で示す安全性は, 提案者らによって与えられている Elephant
モードの安全性証明 [21] から導出される. その安全性証明では, 2.2 節にて述べた秘匿と改ざん検知の安全性を合わせた安全性定義 [95] において用いる置換を公開ランダム置換としたときに, Nonce

respecting の下で Elephant モードの安全性が示されている.

3.3.2

モードの安全性

文献 [21, 22] において Elephant モードの安全性証明が示されている. その安全性証明は, Enc-then-

MAC 構造については Bellare と Namprempre による証明 [12] 及び Namprempre らによる証明 [92],
MAC 部分については Bernstein による証明 [14] 及び Luykx らによる証明 [84], 置換ベース TBC につ
いては Granger らによる証明 [54] のアイディアがそれぞれベースとなっている. 加えて, マルチユー
ザーセキュリティの安全性証明も文献 [22] にて示されており, シングルユーザーで示されていた表 3.3の安全性がマルチユーザーの場合でも成立することが示されている. また提案者らは, Nonce misuse
設定の場合には秘匿の安全性は担保できないものの, 改ざん検知についての安全性は保たれると述べている [21]. 加えて, 未検証平文が攻撃者に与えられる設定 (Release of unveriﬁed plaintext [7]) の場合の安全性も担保できると述べている [21].

Elephant モードへの第三者評価としては, 土生と岩田による Elephant モードに対する鍵回復，識別及び偽造攻撃 [117] が挙げられる. これらの攻撃に必要な計算量が, Elephant モードの安全性証明
により示される安全性バウンドが要求する攻撃成功に必要な計算量と同等であるため, そのバウンド

8

がタイトであることを示す結果である. よって仕様書で主張される安全性を脅かすものではない. 他にも, Elephant やその内部で用いるモード構成の耐量子安全性に関して攻撃や証明がいくつか発表されている [6, 26, 98] が, 提案者らは Elephant の耐量子安全性については特に主張していないため, 仕様上の安全性とは矛盾しない.

3.3.3

プリミティブ及び関連方式の安全性

本節では, Elephant で用いられている 3 つの置換 Spongent-π[160], Spongent-π[176], Keccak-f [200]に対する安全性について述べる.

Spongent-π[160] と Spongent-π[176]3.2.2 節にて述べた通り, Spongent-π[160] は厳密には Elephant

提案者らによって定義された置換である. そのため本節ではまず, Spongent-π[160] のラウンド数決定
方法について述べたのち, Spongent-π[160] 及び Spongent-π[176] の第三者評価について述べる.
ハッシュ関数 Spongent の内部置換に対して, 次の定理が知られている.
定理 3.3.1 (文献 [24] の Theorem 1, 文献 [21] の Theorem 5.1.) b ≥ 64 に対し, Spongent-π[b]をブロックサイズ b の Spongent 内部置換とする. このとき, いかなる差分に対しても 5 ラウンドのSpongent-π[b] には少なくとも 10 個の active S-box が存在する.
Bogdanov らは Spongent 提案論文 [24] にて, この定理及び Spongent 内部置換で用いている S-box の最大差分確率が 2−2 であることを用いて, (安全性マージンを含めて) 少なくとも b 個の active S-boxが存在するように Spongent 内部置換のラウンド数を決定した. また Bogdanov らは同論文において,そのように決めたラウンド数の Spongent 内部置換が線形解析に対しても安全性を持つことを述べている. Elephant 提案者らもこのラウンド決定方法に従って Spongent-π[160] のラウンド数を決定して
おり, 同様に Spongent-π[160] が線形解析に対しても十分な安全性を持つことを示している [21].
次に, Spongent-π[160] と Spongent-π[176] に対する第三者評価について述べる. 伊藤による調査 [116] によると, 2021 年 9 月時点では Zhang と Liu による中間一致手法を用いた切り詰め差分
攻撃 [110] が Spongent 内部置換に対する最良の攻撃であった. 文献 [110] では Spongent-π[176] に対して中間一致攻撃のラウンド数が 7 段, 切り詰め差分攻撃のラウンド数が 46 段であり, 識別攻撃
可能段数が合わせて 53 段であることが示されている. これ以降の解析として, Sun らによる 21 段

Spongent-π[176] に対するゼロサム識別器の提案2 [102] と, 後ほど述べる Schrottenloher と Stevensによる中間一致攻撃 [97] が挙げられるが, 現時点では Spongent-π[160], Spongent-π[176] 共に致命的な脆弱性は報告されていない. Spongent-π[176] に対する現在最良の識別攻撃は, 文献 [110] の攻撃とSchrottenloher と Stevens による攻撃 [97] の組み合わせである. Spongent-π[176] に対して, 文献 [110]における中間一致攻撃のラウンド数が文献 [97] によって 2 段改良されたことにより, Spongent-π[176]の識別攻撃可能段数は現在 55 段である. 文献 [97] では Spongent-π[160] に対する中間一致攻撃のラ
ウンド数が 9 段であることも示されているが, 文献 [110] では Spongent-π[160] への切り詰め差分攻
撃可能段数が示されていないため, 中間一致手法を用いた切り詰め差分攻撃による Spongent-π[160]の識別攻撃可能段数は不明である.

Keccak-f [200]Keccak-f [200] に対する解析状況として以下 3 つについて述べる.

• Keccak-f [200] に対する解析.

Keccak-f [200] への識別攻撃について表 3.4 にまとめる. 表中の 2 つの解析結果はそれぞれ攻撃者の設定が異なるため, 直接的な比較は困難であることに注
2 この結果は文献 [21] において Spongent-π[160] に対する解析として引用されているが, それは間違いである. Sun らによる解析では Spongent-160 を 160 ビット出力のハッシュとして表記しており, その内部置換の解析を行っているため, 正し
くは Spongent-π[176] に対する解析となる.

9

表 3.4: Keccak-f [200] に対する識別攻撃.

Type

TargetDistinguisher

RoundsTime

Permutation

7 / 182

46.0

Permutation

6 / 182142.0

MethodReference

Limited-Birthday[50]

Diﬀerential[87]

表 3.5: Keccak-f [200] を内部置換として用いた Keccak ハッシュへの解析. Keccak[r, c] はスポンジ構造のレートが r ビット, キャパシティが c ビットであることを示す. 文献 [116] 表 5.1 より一部引用.

Instance
Keccak[40, 160]
Keccak[72, 128]

Rounds2
2

Attack type
Algebraic collision
Algebraic collision

Time

Reference

2

73.0

[25]

2

52.5

[25]

意されたい. また, 表では明示的に Keccak-f [200] への解析結果を示した文献のみを挙げているが, 異なる入出力サイズの Keccak-f 置換に対する有効な解析手法としてゼロサム攻撃 [108] 等が知られている. それらが Keccak-f [200] に対して適用可能であるかどうかは本報告書では検証していない.

• Keccak-f [200] を用いた Keccak ハッシュに対する解析. Keccak [17] はスポンジ構造のハッシュ関数であり, Keccak-f [200] を内部置換として用いるインスタンスが存在する. 伊藤による調査 [116] によると, 2021 年 9 月時点では 2 段の Keccak-f [200] を用いた Keccak に対する Boissierらによる代数衝突攻撃 [25] が最良の攻撃であり, 現時点においてもこれが最良である.

• 認証暗号 Ketje Jr v1, Ketje Jr v2 に対する解析. Ketje Jr v1, Ketje Jr v2 はスポンジ構造の認証
暗号 Ketje [18] のインスタンスである. なお, Ketje は認証暗号コンペティション CAESAR [2]の第三ラウンド候補である. Ketje Jr v1, Ketje Jr v2 の内部置換として Keccak-f [200] のバリ
アントでラウンド数 12 段のものが用いられており, レートは 16 ビットである. 伊藤による調査 [116] でまとめられている解析結果 [48, 52, 99, 112] と, それに含まれないいくつかの解析結
果 [109, 113] を表 3.5 にまとめる. 鍵回復攻撃については, ラウンド数が 5 段及び 6 段までの(条件付き) キューブ攻撃が提案されており, ステート回復攻撃については 12 段の分割統治攻撃が提案されている.
Delirium で用いられる Keccak-f [200] は 18 ラウンドであることや, スポンジ構造のレートに当たる部
分が Elephant には存在しない, つまり攻撃者が置換の入出力を直接計算できる部分が Elephant にはないことから, これらの攻撃は Keccak-f [200] 及び Delirium の安全性を脅かすものではない. しかしながら, Keccak ハッシュや認証暗号 Ketje は内部置換として Keccak-f [200] と同様の構造を用いているため, 今後も安全性評価の上では考慮に入れる必要がある.

3.3.4

その他

その他の解析としては, Zhou らによるラウンド数を 8 段に削減した Keccak-f [200] を用いた Deliriumへの補間攻撃 [114] が挙げられる. 攻撃に必要な時間計算量は 298.3 XOR 相当, 空間計算量は 270 ビット, 必要なデータ量は 270 ブロックである. Delirium では 18 段の Keccak-f [200] が用いられているため, 仕様書において主張される安全性を脅かすものではない.
また, サイドチャネル攻撃等の非ブラックボックス安全性に関する解析として, Vialar によるサイドチャネル攻撃を用いた Dumbo 及び Jumbo の鍵回復攻撃 [106], Takemoto らによるハードウェアト
ロイが埋め込まれた Elephant 実装に対する安全性評価 [103], Joshi と Mazumdar によるフォールト攻撃を用いた Dumbo の鍵回復攻撃 [74], Madushan らによるフォールト攻撃を用いた Dumbo の鍵回

10表 3.6: Ketje Jr への解析. 文献 [116] 表 7.5 より一部引用.

Instance

Key size

RoundsAttack type

MethodTime

Reference

68.0

[99]

Ketje Jr v1

72

6

Key recovery

Cube

2

Ketje Jr v1

96

5

Key recovery

Cube

256.0

[48]

36.9

Ketje Jr v1
Ketje Jr v1

96
96

5
5

Ketje Jr v1

96

12(full)

Ketje Jr v1
Ketje Jr v1

96
96

12(full)12(full)

Key recovery
Key recovery

Cube
Conditional cube

2
226.6

[99]
[113]

State recovery (rate: 16)

Divide and conquer

2152.0[52]

Divide and conquer

128.0

[52]

2

92.0

[52]

87.6

[109]

State recovery (rate: 24)
State recovery (rate: 32)

Divide and conquer

2

Ketje Jr v1

96

12(full)State recovery (rate: 32)

Divide and conquer

2

Ketje Jr v1

96

12(full)State recovery (rate: 40)

Divide and conquer

271.9

[52]

Divide and conquer

2

71.6

[109]

2

59.2

[99]

50.3

[48]

Ketje Jr v1
Ketje Jr v2

96
80

12(full)
6State recovery (rate: 40)
Key recovery

Cube

Ketje Jr v2

96

5

Key recovery

Cube

2

Ketje Jr v2

96

5

Key recovery

Cube

234.9

[99]

Cube

2

30.5

[112]

2

27.5

[113]

152.0

Ketje Jr v2
Ketje Jr v2
Ketje Jr v2
Ketje Jr v2
Ketje Jr v2
Ketje Jr v2

96

5

Key recovery

96
96

5
12(full)

Key recovery
State recovery (rate: 16)

Conditional cube
Divide and conquer

96

12(full)State recovery (rate: 24)

Divide and conquer

22128.0

[52]
[52]

96

12(full)State recovery (rate: 32)

Divide and conquer

2104.0[52]

Divide and conquer

82.3

[52]

96

12(full)State recovery (rate: 40)

2

復攻撃 [85] が挙げられる. 提案者らは Elephant の非ブラックボックス安全性については特に主張していないため, これらの解析も仕様書で主張される安全性とは矛盾しない. 提案者らは, ユーザーがこれらの攻撃を防ぎたい場合は実装レベルでの適切な対策が必要であると文献 [21] にて述べている.

11

第4章

ISAP

Isap [38] は暗号学的置換をプリミティブとして用いた方式である. 用いる置換の一部は FIPS 202 [5]において標準化されているものと同じである. モードは他の多くの NIST LWC ファイナリストと同
じくスポンジ構造 [16] を採用しているが, Fresh rekeying [86] から着想を得てサイドチャネル攻撃に対して堅牢となるような設計となっているのが特徴である. 2022 年 9 月末時点で, 提案者らが仕様書において主張する安全性を損なう解析結果は発表されていない.

4.1

準備

ビット列 X ∈ {0, 1}∗ と自然数 n ≤ |X| に対し, dXen を X の上位 n ビットのビット列, bXcn をX の下位 n ビットのビット列を表す. スポンジ構造の n ビットステート S に対し, Sr は S の r ビット外部パート (つまりレート部分), Sc は S の c ビット内部パート (つまりキャパシティ部分) を指す.

4.2

仕様

Isap は暗号学的置換をプリミティブとして用いた認証暗号利用モードの名称であり, かつ 4 つの認証
暗号 Isap-A-128a, Isap-K-128a, Isap-A-128, Isap-K-128 をまとめた総称である. この 4 方式は全てモード構成が Isap であり, 用いる置換やパラメータがそれぞれ異なる. Isap-A-128a, Isap-A-128
はプリミティブとして Ascon-p, Isap-K-128a, Isap-K-128 はプリミティブとして Keccak-p[400]を用いる. Primary member は Isap-A-128a である.
加えて提案者らは Isap のハッシュ関数として, 既存のハッシュ関数で, かつ各インスタンスと同じ置換を用いる方式を推奨している. 詳細には, Isap-A-128a 又は Isap-A-128 を用いる場合は NISTLWC ファイナリスト Ascon [41] のハッシュ関数 AsconHash を, Isap-K-128a, Isap-K-128 を用い∗る場合は NIST FIPS 202 [5] で定められる sponge[Keccak-p[400, 16], pad10 1, 144](M k 01, 256)∗及び sponge[Keccak-p[400, 20], pad10 1, 144](M k 01, 256) をそれぞれ用いることを推奨している.

4.2.1

モード

本節では Isap のモード構成と 4 つのインスタンスの仕様について述べる. Isap は FSE 2017 で提案された同名の方式 [40] をベースに作られている. まずモードの概要として, 認証暗号全体の構成はElephant と同じく Enc-then-MAC 構造であるが, Isap にはそれに加えて Rekey と呼ばれる内部関数が存在する. Rekey 関数は, Isap 内部の暗号化部分とメッセージ認証コード (MAC) 部分で用いる鍵を, (マスター) 秘密鍵とナンスから導出する関数である. Rekey 関数, 内部の暗号化, MAC 部分はそれぞれ IsapRk, IsapEnc, IsapMac と呼ばれ, その全てがスポンジ構造を用いて構成されている.
より詳細な定義として, Isap の暗号化アルゴリズムを Alg. 2 に, 内部関数 IsapRk, IsapEnc,

IsapMac の図をそれぞれ図 4.1a, 4.1b, 4.1c に示す. 復号関数は省略する. 暗号化関数は入力として
k ビット秘密鍵 K, k ビットナンス N , 任意長 AD A, 任意長平文 M を取り, 出力は |M | ビット暗号
文 C, k ビットタグ T である. 具体的なパラメータや用いる置換等は各インスタンスにより異なる.

12

Algorithm 3 IsapEnc(K, N, M )Algorithm 2 E(K, N, A, M )Input key K ∈ {0, 1}k , nonce N ∈ {0, 1}k ,Input key K ∈ {0, 1} , nonce N ∈ {0, 1} ,kplaintext M ∈ {0, 1}∗kassociated data A ∈ {0, 1}∗ ,Output ciphertext C ∈ {0, 1}|M |∗plaintext M ∈ {0, 1}|M |Output ciphertext C ∈ {0, 1}

1: M1 . . . Mt ← rh -bit blocks of M k 0−|M | mod rh, tag T ∈ {0, 1}

2: Ke∗ ← IsapRk(K, enc, N ), S ← Ke∗ k N

k1: C ← IsapEnc(K, N, M )3: for i = 1, . . . , t do

2: T ← IsapMac(K, N, A, C)

4:

3: return

5: C ← dC1 k . . . k Ct e|M |C, TS ← pe (S), Ci ← Srh ⊕ Mi

6: returnC

Algorithm 4 IsapRk(K, f, Y )Algorithm 5 IsapMac(K, N, A, C)

Input key K ∈ {0, 1} , ﬂag ∈ {enc, mac},

Input key K ∈ {0, 1}k , nonce N ∈ {0, 1}k ,kassociated data A ∈ {0, 1}∗ , ciphertext C ∈ {0, 1}∗string N ∈ {0, 1}

kOutput session key K ∗ ∈ {0, 1}z

Output tag T ∈ {0, 1}k

1: if f = enc then

1: A1 . . . As ← rh -bit blocks of A k 1 k 0−|A|−1 mod rh

2:

2: C1 . . . Ct ← rh -bit blocks of C k 1 k 0−|C|−1 mod rh(IV, z) ← (IVke , n − k)3: S ← N k IVa , S ← ph (S)3: else4:(IV, z) ← (IVka , k)

4: for i = 1, . . . , s do

5: Y1 . . . Yw ← rb -bit blocks of Y k 0−k mod rb

5:

6: S ← K k IV

6: S ← S ⊕ (0n−1 k 1)

7: S ← pk (S)7: for i = 1, . . . , t do

8: for i = 1, . . . , w − 1 do

8:

9:

10: S ← ph (Ka∗ k bScn−k )10: S ← pk ((Srb ⊕ Yw ) k Scb )
11: K

← dSe

12: returnS ← ph ((Srh ⊕ Ci ) k Sch )9: Ka∗ ← IsapRk(K, mac, dSek )S ← pb ((Srb ⊕ Yi ) k Scb )∗S ← ph ((Srh ⊕ Ai ) k Sch )z

11: C ← dC1 k . . . k Ct e|M | , T ← dSek∗

12: return

KT

その違いは表 4.1 の通りである. また, 内部で用いる初期ベクトルも各インスタンス等により異なる.
その違いは表 4.2 の通りである.
耐漏洩安全性のための実装

Isap はサイドチャネル攻撃に対して堅牢となるように設計されているが, その耐漏洩安全性を達成するための実装上の要件が存在する. その詳細は文献 [13, 38, 105] を参照されたいが, 概要としては Fresh rekeying [86] のアイディアと同じく, マスター秘密鍵から一時鍵を導出する IsapRk は Diﬀerential power analysis (DPA) 攻撃に対して安全, 一時鍵が入力される

IsapEnc と IsapMac は Simple power analysis (SPA) 攻撃に対して安全となるような実装が求め
られる.

4.2.2

プリミティブ

Isap で用いられている暗号プリミティブはインスタンスにより異なる. Ascon-p は 320 ビット入出力の置換であり, そのラウンド関数は NIST LWC ファイナリストの Ascon [41] で用いられている置換と同じである. その詳細は Ascon に対する安全性評価レポートを参照されたい. ラウンド数
は各インスタンスや内部プロセスにより異なり, 表 4.1 の通りである. Ascon は NIST LWC 前に開かれた認証暗号コンペティション CAESAR [2] においても Lightweight applications のカテゴリで最終ポートフォリオに選出されている. Keccak-p[400] は 400 ビット入出力の置換であり, そのラウンド関数は FIPS 202 [5] で定められている置換と同じである. ラウンド数は各インスタンスや内部プ
ロセスにより異なり, 表 4.1 の通りである. なお, Elephant で用いられている Keccak-f と Keccak-p

13

K∗

Yi

Yw

rb

rb

pk

cb

pb

z

N
k

pk

cb

Mi

Ke∗n−kCi

Mtpe

IsapRk

Ct
≤ rh

rh

pe

ch

k

K k IV
Initialize(IVke , n−k) K

Squeeze

Re-keying

Encrypt Plaintext

Initialize(a) IsapRk.

(b) IsapEnc.

N

Ai

As

Ci

Ct

k

rh

rh

rh

rh

ph

ch

ph

ch

ph

ch

ph

ch

Y

k

ph

T

Ka∗

k

k

IsapRk phk0∗ k 1

IVa

Initialize Authenticate Ass. Data

(IVka , k) K
Authenticate Ciphertext

Finalize(c) IsapMac.

図 4.1: Isap の内部関数 3 つの図. Isap のウェブサイト [4] より引用. 厳密には, 図 4.1b と図 4.1c の IsapRkにはそれぞれ (IVke , n − k), (IVka , k) でなく ﬂag f が入力される.
表 4.1: Isap の各インスタンスで用いる置換及びパラメータ. 文献 [38] より引用. ここで, Permutation の列
は Isap 各インスタンスで用いる置換 ph , pb , pe , pk の種類を指し, ph , pb , pe , pk のラウンド数はそれ
ぞれ sh , sb , se , sk で表される.

Name

Permutation

Security level

Bit size ofknRounds

rh

rb

sh

sb

se

sk

Isap-A-128a

Ascon-p

128

320

64

1

12

1

6

12

Isap-K-128a

Keccak-p[400]

128

400

144

1

16

1

8

8

Isap-A-128

Ascon-p

128

320

64

1

12

12

12

12

Isap-K-128

Keccak-p[400]

128

400

144

1

20

12

12

12

との違いはラウンド数が仕様上で明示的に定められているかどうかのみであり, ラウンド関数は同じである. Keccak-f は固定されたラウンド数を持つが, Keccak-p はラウンド数を変数として持つ.

4.3

安全性

2022 年 9 月末時点において, Isap はいずれの方式についても仕様書で主張される安全性を脅かす
攻撃は提案されていない. 本節では, まず 4.3.1 節で提案者らが主張する安全性を概説し, 4.3.2 節でモードのブラックボックス安全性と耐漏洩安全性の 2 つについて, 根拠及び第三者評価について述べる. 4.3.3 節にて用いる置換の現時点での攻撃可能段数と, 同じ置換を用いる他の関連方式の攻撃可能段数について述べる. 4.3.4 節にてその他の解析について述べる.

4.3.1

仕様上の安全性

提案者らが主張する安全性レベルを表 4.3 に示す. 提案者らはこの安全性のために, 暗号化関数では同じナンスを使ってはならないこと (Nonce respecting) 及び, 復号関数における復号プロセスは,14

表 4.2: Isap の各インスタンスで用いる初期ベクトル. 16 進数表現で記載. [38] より引用.

インスタンス

Isap-A-128a

Isap-K-128a

Isap-A-128

Isap-K-128

IVa

1 k k k rh k rb k sh k sb k se k sk k 0∗IVka

2 k k k rh k rb k sh k sb k se k sk k 0∗IVke

3 k k k rh k rb k sh k sb k se k sk k 0∗

IVa
IVka

01 80 4001 0C01060C 00∗
02 80 4001 0C01060C 00∗

IVke

03 80 4001 0C01060C 00∗

IVa

01 80 9001 10010808 00∗

IVka

02 80 9001 10010808 00∗

IVke

03 80 9001 10010808 00∗

IVa

01 80 4001 0C0C0C0C 00∗

IVka

02 80 4001 0C0C0C0C 00∗

IVke

03 80 4001 0C0C0C0C 00∗

IVa

01 80 9001 140C0C0C 00∗

IVka

02 80 9001 140C0C0C 00∗

IVke

03 80 9001 140C0C0C 00∗

表 4.3: Isap 各インスタンスの安全性レベル. [38] より引用.

Security in bits

Requirement
Isap-A-128a

Isap-K-128a

Isap-A-128

Isap-K-128

Conﬁdentiality of plaintext

128

128

128

128

Integrity of plaintext

128

128

128

128

Integrity of associated data

128

128

128

128

Integrity of nonce

128

128

128

128

タグ検証が成功してからでないと動いてはいけない仮定が必要であると述べている [38]. 文献 [38] では安全性定義が明示されてはいないものの, 以下の記述があることから表 4.3 の安全性は 2.2 節で述
べたブラックボックス (つまりサイドチャネル攻撃を考慮しない) の安全性定義に基づくものであると推測する.

All Isap family members provide 128-bit security against cryptographic attacks in thenotion of nonce-based authenticated encryption with associated data (AEAD)
また文献 [38] の 5.1 節 Security of the Mode や文献 [39] の 2 章 Proofs の記述等から, 表 4.3 の安全性レベルはスポンジ構造に関するいくつかの安全性証明が根拠になっていると考えられる. これらの安全性証明はブラックボックスモデルであり, かつ用いる置換を公開ランダム置換と見なした場合に与えられるものである. しかしながら, 提案者らは文献 [38] で以下のように述べている.

We emphasize that we do not require ideal properties for the permutations ph , pb , pe , pk .
Non-random properties, including but not limited to inside-out zero sum distinguishers,of the permutations ph , pe , pk , and of course pb are known and do not automaticallyaﬄict the claimed security properties of the entire encryption algorithm.
文献 [39] でも同様の記述が複数見られる. つまり, Isap の安全性は一般的なスポンジ構造の証明可能安全性を１つの根拠にしてはいるものの, その証明可能安全性と実際の仕様に対する安全性には解15離があることに注意したい. このことから, Isap の安全性を解析するためには, 用いる置換単体の解析や, 公開ランダム置換を仮定したモード単体の解析だけでなく, Isap 全体の仕様を考慮した解析が必要不可欠である.
提案者らは加えて, Isap に対する耐漏洩安全性 (Leakage-resilient security) の証明も与えている.
この証明もまた, 用いる置換を公開ランダム置換と見なした場合に与えられるものである. 詳細は4.3.2 節にて述べる.

4.3.2

モードの安全性

本節では, Isap モードの証明可能安全性についてブラックボックス安全性に関するものと耐漏洩安全性に関するものについて述べる. つまり本節において, 用いる置換は全て公開ランダム置換であるという仮定を置く.
ブラックボックス安全性

IsapRk 及び IsapEnc の安全性は, Daemen らによる Keyed duplex の証

明可能安全性 [33] に依拠していることが提案者らによって述べられている [38] が, 厳密な安全性証明が与えられている訳ではない. 筆者個人の意見としては, 主張される 128 ビット安全性は Bertoni らによるスポンジ構造への安全性証明で, キャパシティ長の半分が安全性レベルとなるという結果 [20]に依拠しているのではないかと推測する. IsapMac に関しては Dobraunig と Mennink [44] によって Suﬃx keyed sponge の安全性証明が与えられており, ここから IsapMac の 128 ビット安全性が導出される. 但し, IsapMac の安全性バウンドを導出する際には, IsapRk にあたる部分が特定の性
質 (出力の一様性と衝突困難性) を満たす部品として理想化されていることに注意されたい. また,同文献で示される Suﬃx keyed sponge の安全性バウンドがタイトであることが, 後に Dobraunig とMennink によって示されている [45]. ハッシュ関数の安全性に関しては, スポンジ構造がランダムオ
ラクルと Indiﬀerentiability を持ち, そのバウンド O(2c/2 ) であること [19] に依拠していると提案者
らは述べている [39]. 但し c はキャパシティ長である.
その他, Isap のブラックボックス安全性に関連する研究として Lefevre と Mennink によるスポンジ構造の衝突, 原像計算, 第二原像計算の困難性の評価 [79] が挙げられる. これは, Bertoni らによって示されたバウンド O(2c/2 ) の Indiﬀerentiability [19] から導出される 3 つの困難性に対する安全性
バウンドが, 衝突と第二原像計算についてはタイトであり, 原像計算についてはより良い安全性バウンドを導出できるということを示した結果である.
耐漏洩安全性

Isap の認証暗号としての耐漏洩安全性は提案者らによって証明されている [36, 43].

用いられている耐漏洩安全性定義や漏洩モデルの詳細は本報告書では省略するが, 概要として耐漏洩
安全性は, 攻撃者が漏洩情報を出力する暗復号オラクルにアクセスできる場合に, 攻撃者が漏洩情報のない Real world (暗復号オラクル) と漏洩情報のない Ideal world (ランダムオラクルとエラーメッ
セージのみを返すオラクル) を判別できる確率として定義される. この安全性は Romulus のインスタ
ンスの Romulus-T で用いられている耐漏洩安全性定義である CIML2 や CCAmL2 [15] とは異なる定義である. また, 漏洩情報の仮定として Non-adaptive leakage と Bounded leakage model [88] を用いている. 前者は, 攻撃者が全てのクエリを通じて固定された漏洩情報出力関数を用いる設定で, ク
エリの度に適応的にその関数を選ぶことはできない設定を指す. 後者は, その漏洩情報出力関数から得られる漏洩情報量の上界が定められている設定である. 証明内部は, 提案者らによるいくつかの既存文献の結果がベースとなっている. IsapRk 及び IsapEnc の安全性は Dobraunig と Mennink に
よる Keyed duplex の耐漏洩安全性の証明 [42], IsapMac の安全性は Dobraunig と Mennink による

Suﬃx keyed sponge の耐漏洩安全性の証明 [44] がそれぞれベースとなっている.

16

表 4.4: Keccak-p[400] に対する解析. 文献 [39] の Table 11 より一部引用.

Type

TargetDistinguisher

RoundsTime

Permutation

20 / 20

396.0

MethodReference2

Zero-sum[27]

Permutation

12 / 202396.0Integral[27]

Permutation
Permutation

7 / 206 / 20284.02278.0Limited-Birthday
Diﬀerential

[50]
[87]

表 4.5: Ketje Sr v1, Ketje Sr v2 に対する解析. 文献 [116] の表 7.5, 及び文献 [39] の Table 9 より一部引
用.

Type

TargetRoundsTime

MethodReference

Key recovery

Ketje Sr v1
Ketje Sr v1

7 / 137 / 132115.32113.6

Cube
Cube

[48]
[99]

Ketje Sr v1

7 / 13291.0

Conditional cube

[100]

Ketje Sr v2

7 / 13275.0

Conditional cube

[81]

Ketje Sr v2

7 / 132113.9Cube[48]

7 / 13

2

99.0

Cube

[99]

2

77.0

Conditional cube

[81]

Ketje Sr v2
Ketje Sr v2

7 / 13

加えて提案者らは Isap が, Nonce misuse での改ざん検知の安全性, 未検証平文が攻撃者に与えられる設定 (Release of unveriﬁed plaintext [7]) での安全性, 同一の暗号文から別々の (⊥ でない) 復号
結果が得られるような鍵のペアが存在しないことを保証する安全性 (Key committing [51]) を持つと主張している [39].
その他, Isap の耐漏洩安全性に関連する研究として Guo らによる Duplex の耐漏洩安全性の証明,
及びそれを用いた認証暗号の提案 [59] が挙げられる. 漏洩モデルは Hard-to-invert [46] と呼ばれるもので Isap の漏洩モデルとは異なるため, Isap 提案者らはこの証明が文献 [36] における Isap の耐漏洩安全性証明の補完となっていると述べている [37].

4.3.3

プリミティブ及び関連方式の安全性

本節では用いるプリミティブへの解析状況についてまとめる. 加えて, Isap と同じプリミティブを用いている方式で, かつ Isap とモード構成が類似する方式に対する解析をまとめる. 但しここで挙げる解析は公開ランダム置換を仮定したモードへの解析ではなく, ラウンド数を削減したプリミティ
ブを用いた方式への解析である.
プリミティブ

Ascon-p に対する解析状況の詳細は Ascon の安全性評価レポートを参照されたいが,

現時点における識別攻撃可能段数の最大は 12 段であり, これはゼロサム攻撃によるものである [65].

Isap ではこれより少ないラウンド数の Ascon-p を用いている箇所があるものの, 提案者らは Isap
内で用いる置換に対してランダム置換との識別不可能性は必要ないとしており, 上記の解析は Isap
全体の安全性には影響しないと述べている [39].
次に Keccak-p[400] に対する識別攻撃について表 4.4 にまとめる. 現時点における攻撃可能段数の最大は 20 段で, ゼロサム攻撃によるものである. 但し, 必要な計算量が Isap が主張する安全性レベ
ルを大きく超えていることに注意されたい. Isap ではこれより少ないラウンド数の Keccak-p[400]を用いている箇所があるが, Ascon-p の場合と同じく, 提案者らは Isap 全体の安全性には影響しないと述べている [39].

17表 4.6: Keccak-p[400] を用いた Keccak ハッシュへの解析結果. 文献 [116] の表 5.1, 文献 [39] の Table 10 より一部引用. Keccak[r, c] はスポンジ構造のレートが r ビット, キャパシティが c ビットであることを示
す.

Type

TargetOutput size
80

RoundsTime

MethodReference3 / 2045.0

Algebraic[1, 80]Diﬀerential[1, 76]

Algebraic collision[25]

Preimage

Keccak[240,160]

Collision

Keccak[240,160]

160

4 / 20-Keccak[144,256]

Arbitrary2 / 202101.5Isap-A-128a 及び Isap-A-128 の関連方式

2

Isap-A-128a 及び Isap-A-128 に対して提案者らは,Ascon と AsconHash の攻撃可能段数から, 内部関数 IsapEnc と IsapMac の安全性をそれぞれ測ることができると述べている [39]. Ascon は Ascon-p を内部置換として用いたスポンジ構造の認
証暗号であり, AsconHash は Ascon-p を内部置換として用いたスポンジ構造のハッシュであってIsapMac の AD・暗号文処理部分と類似した構成である.
Ascon と AsconHash に対する解析状況の詳細は Ascon の安全性レポートを参照されたいが,
現時点における Ascon の鍵回復攻撃可能段数の最大は 7 段 [96] であり, これは Ascon の初期化フェーズに対する攻撃である. 提案者らは Isap-A-128a と Isap-A-128 においては, ナンス処理後から平文処理までに要するラウンド数 (sk + se ) がそれぞれ 18 段, 24 段と十分に大きいため, 現状の仕様が十分にセキュリティマージンを持つと述べている [39]. また, Nonce respecting 設定下
における Ascon のステート回復攻撃可能段数の最大は 3 段 [53] であり, これは Ascon インスタ
ンスの Ascon-128a における平文処理フェーズに対する攻撃である. 提案者らは Isap-A-128a とIsap-A-128 においては, 平文処理部分のラウンド数 (se ) がそれぞれ 6 段と 12 段であり, 且つレートが 64 ビットで Ascon-128a の 128 ビットよりも小さいことから, 現状の仕様が十分にセキュリティ
マージンを持つと述べている [39]. AsconHash においては現時点で 2 段 [53, 115] までの衝突攻撃が提案されており, Isap-A-128a と Isap-A-128 に直接適用できるものの, 仕様上のラウンド数はど
ちらも 12 段であるため十分なセキュリティマージンがあると提案者らは述べている [39].

Isap-K-128a 及び Isap-K-128 の関連方式

Isap-K-128a 及び Isap-K-128 に対して提案者らは,Ketje [18] と Keccak [17] ハッシュの攻撃可能段数から, 内部関数 IsapEnc と IsapMac の安全性をそれぞれ測ることができると述べている [39]. Ketje は用いる置換が Keccak-p と同様の構成をしているスポンジ構造の認証暗号であり, 400 ビット入出力の置換を用いたインスタンス Ketje Sr v1,

Ketje Sr v2 が存在する. Keccak ハッシュは AsconHash の場合と同様に IsapMac の AD・暗号
文処理部分に類似しており, Keccak-p[400] を用いたインスタンスが存在する.

Ketje Sr への解析結果を表 4.5 にまとめる. 攻撃可能段数の最大は 7 段であり, これは Ketje Srの初期化フェーズに対する攻撃である. Ketje Sr のレートは 32 ビットで IsapEnc の 144 ビット
よりも小さいものの, 提案者らは Ascon の場合と同様に Isap-K-128a と Isap-K-128 においては,
ナンス処理後から平文処理までに要するラウンド数がそれぞれ 16 段, 24 段と十分に大きいため, この解析結果は仕様上の安全性を脅かすものではないと述べている [39].

Keccak ハッシュへの解析結果を表 4.6 にまとめる. 最大 3 段までの原像計算攻撃, 及び 4 段までの衝突攻撃が存在しているが, どちらの結果も Isap よりも小さいキャパシティのスポンジ構造を用いている. Isap と同じキャパシティを用いている文献 [25] の攻撃可能段数は 2 段であり, この解析はIsap-K-128a と Isap-K-128 に直接適用できるものの, 仕様上のラウンド数は Isap-K-128a が 16段, Isap-K-128 が 20 段であるため十分なセキュリティマージンがあると提案者らは述べている [39].

184.3.4

その他

Isap や関連する方式に対するサイドチャネル攻撃耐性の解析がいくつか発表されている [10, 75,
104, 111]. 提案者らは Isap モードの耐漏洩安全性について証明可能安全性を示しているものの, Isap
全体に対して現実的に実現される具体的な耐漏洩安全性レベルを主張している訳ではないため, 何れも仕様書で主張している安全性と矛盾しない. また, Janson と Struck によって Isap の暗号化部分に対して量子識別攻撃ができることが示されている [73] が, 提案者らは耐量子安全性については特に主張していないため, この解析も仕様書で主張している安全性とは矛盾しない.

19

第5章

Romulus

Romulus [55] は NIST LWC ファイナリストの中で唯一, ブロック暗号の拡張である Tweakable
ブロック暗号 (TBC) をプリミティブとして用いた方式である. 用いる TBC は ISO/IEC 18033-

7:2022 [69] において標準化されているものと同様である. モードは複数用意されており, それぞれ達成する安全性の種類が異なる. 2022 年 9 月末時点で, 提案者らが仕様書において主張する安全性を損
なう解析結果は発表されていない.

5.1

準備

空文字列を ε と定義し, |ε| = 0 とする. {0, 1}0 = ε としたとき, {0, 1}≤n = ∪i=0,...,n {0, 1}iと定義する. ビット列 X ∈ {0, 1}∗ , 自然数 n について, |X|n = max{1, d|X|/ne} とする. また,nX[1] . . . X[x] ←− X は X を n ビットブロックに分割することを指し, X[1] k X[2] k · · · k X[x] = X かn

つ x = |X|n である. もし X = ε の場合は X[1] ←− X かつ X[1] = ε であり, |ε|n = 1 である. ビット
列 X ∈ {0, 1}n , 自然数 x ≤ n について, msbx (X) (resp. lsbx (X)) を X の上位 (resp. 下位) x ビッ
トのビット列とする. 自然数 i に対し, 0i を 0 を i 個並べたビット列とし, JiK0 = {0, 1, . . . , i − 1} とする. l を 8 の倍数とし, X ∈ {0, 1}≤l を長さが 8 の倍数となるビット列 (つまりバイト列) とするとき, パディング関数 pad を以下のように定義する.

(
padl (X) =X
X k0(|X| = l)
l−|X|−8k len8 (X) (0 ≤ |X| < l)

ここで, len8 (X) は 1 バイトの X のバイト長表現である.

5.2

仕様

Romulus は Tweakable ブロック暗号 (TBC) の Skinny-128-384+ をプリミティブとして用いた認証暗号, Romulus-N, Romulus-M, Romulus-T と, Skinny-128-384+ をプリミティブとして用いたハッシュ関数 Romulus-H をまとめた総称である. この 4 方式は全て同じプリミティブを用いるがモード
構成が異なる. Primary member は Romulus-N である.

5.2.1

プリミティブ

Skinny-128-384+ はブロックサイズ 128 ビット, Tweakey サイズ 384 ビットの TBC である. Romulus-N,
Romulus-M, Romulus-T については鍵長が 128 ビット, Tweak 長が 256 ビットである. Skinny-128-384+の構成は, CRYPTO 2016 で提案された Skinny [11] のインスタンスの 1 つである Skinny-128-384 のラウンド数を, 56 段から 40 段に削減したものである. なお, Skinny は ISO/IEC 18033-7:2022 において標準化されている [69]. 本節では Skinny-128-384+ の暗号化の仕様について述べる.

Skinny-128-384+ の内部ステートは 1 要素が 1 バイトの 4 × 4 の配列で表される. この配列を ISとおく. i, j ∈ {0, 1, 2, 3} に対し, ISi,j を IS の i 行 j 列における要素とする. また, i ∈ {0, 1, . . . , 15}20に対し, IS を 1 つのベクトルとして見なした場合にその i 番目の要素を ISi と表記する. つまりISi,j = IS4i+j である. Tweakey ステートも内部ステートと同様に, 1 要素が 1 バイトの 4 × 4 の配列 3つによって表される. この配列を順番に T K1, T K2, T K3 とする. z ∈ {1, 2, 3}, i, j ∈ {0, 1, 2, 3} に対し, T Kzi,j を z 番目の Tweakey ステート配列 T Kz の i 行 j 列における要素とする. また, z ∈ {1, 2, 3},i ∈ {0, 1, . . . , 15} に対し, T Kz を 1 つのベクトルとして見なした場合にその i 番目の要素を T Kzi と表記する. 入力する 128 ビットの平文 m を m = m0 k m1 k · · · k m15 とおく. ここで i ∈ {0, . . . , 15}に対して mi は 1 バイトである. 入力する 384 ビットの Tweakey tk を tk = tk0 k tk1 k · · · k tk46 k tk47
とおく. ここで i ∈ {0, . . . , 47} に対して tki は 8 ビットであり, T K1i = tki , T K2i = tk16+i ,T K3i = tk32+i とする.
Skinny-128-384+ のラウンド関数は SubCells, AddConstants, AddRoundTweakey, ShiftRows,
MixColumns の 5 つの手順によって構成される.
SubCells では内部ステート配列の各要素に対して, それぞれ以下で定義する Sbox を適用する.
i ∈ {0, 1, . . . , 7}, xi ∈ {0, 1} に対し, (x7 , . . ., x0 ) を Sbox への入力ビットとする. まず入力ビットに対し以下の変換を施す.

(x7 , x6 , x5 , x4 , x3 , x2 , x1 , x0 ) → (x7 , x6 , x5 , x4 ⊕ (x7 ∨ x6 ), x3 , x2 , x1 , x0 ⊕ (x3 ∨ x2 ))次に以下の通りビット置換を行う.

(x7 , x6 , x5 , x4 , x3 , x2 , x1 , x0 ) → (x2 , x1 , x7 , x6 , x4 , x0 , x3 , x5 )上記 2 つの変換を 4 回繰り返す. 但し, 最後のビット置換は x1 と x2 部分の入れ替えのみである.

AddConstants では内部ステート配列とラウンド定数との排他的論理和をとる. ラウンド定数は以下で定義する 6 ビット線形帰還シフトレジスタ (LFSR) を用いて決定される.

(rc5 k rc4 k rc3 k rc2 k rc1 k rc0 ) → (rc4 k rc3 k rc2 k rc1 k rc0 k rc5 ⊕ rc4 ⊕ 1)
なお i ∈ {0, . . . , 5} に対して rci ∈ {0, 1} であり, 初期値は rci = 0 である. 上記 LFSR は各ラウンド
開始前に状態を遷移させておき, 以下のように配置する.

c0 0 0 0c1 0 0 0
c2 0 0 0



0

0

0

0

ここで, c2 = 0x2, (c0 , c1 ) = (0 k 0 k 0 k 0 k rc3 k rc2 k rc1 k rc0 , 0 k 0 k 0 k 0 k 0 k 0 k rc5 k rc4 ) である. 内部ステート配列と上記配列との排他的論理和をとる.

AddRoundTweakey では各ラウンドで更新される Tweakey と内部ステートとの排他的論理和をとる. まず, 3 つの Tweakey 配列の 1 行目及び 2 行目と内部ステート配列の 1 行目及び 2 行目の排他的論理和をとる. つまり i ∈ {0, 1}, j ∈ {0, 1, 2, 3} に対して ISi,j = ISi,j ⊕ T K1i,j ⊕ T K2i,j ⊕T K3i,j とする. 次に各 Tweakey 配列を更新する. z ∈ {1, 2, 3}, i ∈ {0, 1, . . . , 15} に対し配列
PT = [9, 15, 8, 13, 10, 14, 12, 11, 0, 1, 2, 3, 4, 5, 6, 7] を用いて T Kzi ← T KPT [i] とする. 最後に T K2 とT K3 の 1 行目及び 2 行目の各要素をそれぞれ LFSR を用いて更新する. 適用する LFSR は T K2 とT K3 でそれぞれ異なり, 以下の通り定義される.
T K2 (x7 k x6 k x5 k x4 k x3 k x2 k x1 k x0 ) → (x6 k x5 k x4 k x3 k x2 k x1 k x0 k x7 ⊕ x5 )T K3 (x7 k x6 k x5 k x4 k x3 k x2 k x1 k x0 ) → (x0 ⊕ x6 k x7 k x6 k x5 k x4 k x3 k x2 k x1 )ここで, i ∈ {0, 1, . . . , 7} に対し xi ∈ {0, 1} である. T K1 に関しては LFSR を適用しない.

21

ShiftRows では, 内部ステート配列の行をそれぞれ右に回転させる. 詳細には, i ∈ {0, 1, . . . , 15}に対し配列 P = [0, 1, 2, 3, 7, 4, 5, 6, 10, 11, 8, 9, 13, 14, 15, 12] を用いて ISi ← ISP [i] とする.

MixColumns では以下のバイナリ行列 M と内部ステート行列の各列との積をとる.

1 0 1 1
1 0 0 0 


M =

0 1 1 0 
1 0 1 0

モード

5.2.2

本節では Romulus に含まれる 4 方式のモード構成について概説した後, Primary member である

Romulus-N の仕様について詳細に述べる.
概要

認証暗号の 3 方式はそれぞれ達成する安全性の種類が異なる. それに応じてモードの構成も変わる.

Romulus-N は Nonce-based AEAD であり, Nonce respecting の下安全性が保証される認証暗号である. 構成は CHES 2017 で Chakraborti らによって提案されたブロック暗号ベース認証暗号 COFB モー
ド [29] の TBC ベース版がベースとなっている. なお, COFB についてはその後 Journal of cryptology
でも掲載 [31] され, NIST LWC のファイナリスト GIFT-COFB [9] のモード構成にも用いられている.

Romulus-M は Misuse-resistant AE (MRAE) であり, Nonce misuse の下安全性が保証される認証暗号である. 認証暗号全体の構成は SIV [95] がベースとなっており, 入力全体に対してメッセージ
認証コード (MAC) を適用した後, 出力されたタグを用いて暗号化を行う構成である. 内部で用いる

MAC や暗号化の構成は Romulus-N と同様である.
Romulus-T は Leakage-resilient AE (LRAE) であり, サイドチャネル情報等の暗号内部からの漏洩情報を利用することができる攻撃者に対しても安全性が保証できる認証暗号である. 構成は CHES 2020で提案された TEDT [15] がベースとなっている. また, 内部で用いるハッシュで Romulus-H を用いている. Romulus-T はサイドチャネル攻撃に対して堅牢となるように設計されているが, Isap と同様にその耐漏洩安全性を達成するための実装上の要件が存在する. その詳細は文献 [13, 55, 105] を参照されたい.

Romulus-N, Romulus-M, Romulus-T の暗号化関数は入力として k ビット秘密鍵 K, nl ビットナン
ス N , 任意長 AD A, 任意長平文 M を取り, 出力は |M | ビット暗号文 C, τ ビットタグ T である. 但し
仕様上の制約として, 1 回の暗号化 (resp. 復号) につき AD と平文 (resp. 暗号文) は合わせて 259 バ
イトのサイズまで入力を許すというものがある. つまり, |A| + |M | (resp. |A| + |C|) は高々259 バイ
トである. また Romulus-N, Romulus-M, Romulus-T において, (k, nl, τ ) = (n, n, n) = (128, 128, 128)と定められている. 但し, Romulus-N に関しては必要に応じてタグを規定の 128 ビットから切り詰めて小さくしてもよいが, その場合はタグを切り詰めた分だけ安全性レベルが落ちることに注意された
い. Romulus-M と Romulus-T に関してはタグの全てが復号に必要となるため, タグを切り詰めることはできない.
ハッシュ関数 Romulus-H の構成は Latincrypt 2019 で提案された MDPH [90] と同じ構成であり,その構成は Hirose によって FSE 2006 で提案されたブロック暗号ベースの Double-block ハッシュ関
数 [63] と Hirose らによって Asiacrypt 2007 で提案された MDP domain extension 方式 [64] を合わせた構成となっている. 入力として任意長の平文 M を取り, 2τ ビットのハッシュ値 T を出力する.
ここで, τ = n = 128 なのでハッシュ値は 256 ビットである.

22

Algorithm Romulus-N.EncK (N, A, M )n

1. S ← 0n , (A[1], . . . , A[a]) ←−A
2. if |A[a]| < n then wA ← 26 else 24
3. A[a] ← padn (A[a])4. for i = 1 to ba/2c5.

e (A[2i],8,2i−1) (S)(S, η) ← ρ(S, A[2i − 1]), S ← E
K

6. end for
7. if a mod 2 = 0 then V ← 0n else A[a]e8. (S, η) ← ρ(S, V ), S ← E
K(N,wA ,a)(S)n

9. (M [1], . . . , M [m]) ←−M
10. if |M [m]| < n then wM ← 21 else 20
11. for i = 1 to m − 1
12.

e(S, C[i]) ← ρ(S, M [i]), S ← E
K(N,4,i)(S)

13. end for
14. M 0 [m] ← padn (M [m]), (S, C 0 [m]) ← ρ(S, M 0 [m])e15. C[m] ← lsb|M [m]| (C 0 [m]), S ← E
K(N,wM ,m)(S)

16. (η, T ) ← ρ(S, 0n ), C ← C[1] k . . . k C[m − 1] k C[m]17. return (C, T )Algorithm ρ(S, M )1. C ← M ⊕ G(S), S 0 ← S ⊕ M
2. return (S 0 , C)eK は秘密鍵 K を入力した n ビット入出力の TBC である. また, [if図 5.1: Romulus-N の暗号化関数 [55]. E(statement) then X ← x else x0 ] は [if (statement) then X ← x else X ← x0 ] の省略である.
η はダミー変数でありアルゴリズムには用いられない.

23

0n

A[1]

A[2]

n

t

ρ
n

8,1

EK
g

n

A[a − 1]pad(A[a])

N

8,a−2

ρ

EKA

EK
g

g

ω ,a

S

ωA ∈ {24, 26}

M [1]
ρ
n

4,1

ρ

EK
g

n

0n

ω ,a−2ρωM ∈ {20, 21}

lsb

t

n

S

N

pad(M [m])

N

n

EKM

lsb

C[1]

g

C[m]

T

図 5.2: Romulus-N の暗号化. [71] より引用.

詳細

より詳細な定義として, Romulus-N の暗号化アルゴリズムを図. 5.1 に, 図を図 5.2 に示す.

Romulus-N の復号関数とその他のインスタンスの詳細なアルゴリズムについては省略する. 図 5.1 中の G は n × n のバイナリ行列で, 以下のように 8×8 のバイナリ行列 Gs を用いて定義される.


0

0


0


0

Gs = 
0


0


0

1

0



1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0


0


0


0

,
0


0


1


0

0

0

0

0

0

1


Gs

0



G = ...


0

0

0

0

...

Gs

0

...

0



...

0

Gs


0 


..  .
. 


0 


...

0

0

Gs

..

.

ここで, G の要素として 0 と表記した部分は 8×8 のゼロ行列を表す. 次に Skinny-128-384+ の 384
ビット Tweakey に対する鍵及び Tweak の入力方法について述べる. 秘密鍵 K ∈ {0, 1}128 , ナンス若
しくは AD ブロック T ∈ {0, 1}128 , Domain separation 用の数値 w ∈ J256K0 , カウンタ i ∈ J256 − 1K0e (T,w,i) と表記したとき, Skinny-128-384+ の Tweakey には以下の 384 ビットが入力される.
に対して EK

lfsr56 (i) k (w)8 k 064 k T k K
ここで, (w)8 は w を 8 ビットエンコードした数値とする. w = 26 なら (w)8 = (00011010) である.
また, lfsr56 (i) は帰還多項式 x56 + x7 + x4 + x2 + x + 1 の 56 ビット LFSR で初期値 1 を i 回遷移させたときの 56 ビット値を表す.

5.3

安全性

2022 年 9 月現在, Romulus はいずれの方式についても仕様書で主張される安全性を脅かす攻撃は提案されていない. 本節では, まず 5.3.1 節で提案者らが主張する安全性を概説する. 5.3.2 節で各イ
ンスタンスにおけるモードの安全性の根拠及び第三者評価, 5.3.3 節で用いる TBC の解析状況について述べ, 5.3.4 節でその他の安全性解析状況について述べる.

24

表 5.1: Romulus に含まれる認証暗号 3 方式の安全性. [55] より引用. 単位はビット安全性. n は用いる TBC の入出力長であり, 全ての方式において n = 128 である. また, Romulus-T の各安全性数値は Romulus-T
を破るために攻撃者が必要なデータ量と時間計算量の和のビット長を示す.

方式

NR-Priv

NR-AuthNM-Priv

NM-AuthRomulus-N

n

n

-

-

Romulus-Mnnn/2 ∼ nn/2 ∼ nRomulus-Tn − log2 nn − log2 n-n − log2 n

表 5.2: Romulus-H の各安全性レベル. [55] より引用. 単位はビット安全性. 各数値は Romulus-H の各安全性を破るために攻撃者が必要なデータ量と時間計算量の和のビット長を示す. n は用いる TBC の入出力長であり, n = 128 である.

5.3.1

衝突困難性

原像計算困難性

第 2 原像計算困難性

n − log2 nn − log2 nn − log2 n

仕様上の安全性

提案者らが主張する Romulus-N, Romulus-M, Romulus-T の安全性の概要を表 5.1 に示す. ここで, NR-Priv, NR-Auth はそれぞれ Nonce respecting の下での秘匿と改ざん検知の安全性を指し,

NM-Priv, NM-Auth はそれぞれ Nonce misuse の下での秘匿と改ざん検知の安全性 (Nonce misuse
resistance) を指す. また Romulus-M における n/2 ∼ n という表記は, 同じナンスが繰り返し用いられる回数に応じて安全性レベルが n/2 以上 n 以下の値となることを指す. 表 5.1 で示される安全性レベルは全て提案者らによって与えられているモードの安全性証明から導出される. Romulus-N,

Romulus-M の安全性証明では用いる TBC を TPRP としたときの安全性 [72], Romulus-T の安全性証明では用いる TBC を Ideal cipher としたときの安全性 [57] がそれぞれ示されている. その他にも Romulus-N, Romulus-M, Romulus-T が満たす安全性はいくつか存在するが, 詳細は 5.3.2 節にて述べる.
次に提案者らが主張する Romulus-H の安全性を表 5.2 に示す. この安全性は Naito によって示されている MDPH の安全性証明 [90], 及び提案者らによるその改良 [58] により導出される. これらの安全性証明では用いる (Tweakable) ブロック暗号は Ideal cipher として証明が示される.

5.3.2

モードの安全性

前節で述べた通り, Romulus は全てのインスタンスにおいてモードの安全性証明が示されている.
本節では, Romulus 各インスタンスのモードに対して証明されている安全性やその根拠についてまとめた後, 第三者評価について述べる.

Romulus-N の Nonce respecting 設定下における証明 [72] は iCOFB [30] と PFB [91] の安全性証
明がベースとなっている. また, 表 5.1 で示した通り Romulus-N は NM-Priv, NM-Auth の安全性

(Nonce-misuse resistant) が担保出来ないが, これらの安全性定義を弱めた Nonce-misuse resilience [8]という安全性であれば安全性が示せることが示されている [67]. この安全性は, ナンスを誤用した場合であっても, 誤用していないナンスが含まれるクエリに関してはその安全性を担保できるというもので, Romulus-N については Nonce-misuse resilience 設定下で, 秘匿については n ビット, 改ざん検知についてはナンス誤用の回数に応じて n/2 ビット以上 n ビット以下の安全性を達成できることが示されている.

Romulus-M は Nonce respecting と Nonce misuse の安全性証明がそれぞれ与えられている [72].
Nonce misuse に関する安全性証明では, 同じナンスが繰り返し使われるほど安全性が n ビットから

25

n/2 ビットへ減少する (Graceful degradation [93]) ことが示されている. また表 5.1 記載の安全性以外のものについては, 未検証平文が攻撃者に与えられる設定 (Release of unveriﬁed plaintext [7], 以
下 RUP) における安全性について, 提案者らによって証明が与えられている [70]. まず RUP 設定下における改ざん検知の安全性, 通称 INT-RUP 安全性に関しては, Nonce respecting と Nonce misuse
両方の設定において, RUP でない場合とほぼ同様の証明ができ, 同じレベルの安全性が担保できることが示されている. 次に RUP 設定下における秘匿の安全性, 通称 plaintext awareness に関しては,PA2 と呼ばれる強い方の安全性は満たさないことが文献 [55] にて述べられている. しかし PA1 と呼ばれる弱い方の安全性については, 入力平文長が n ビットの倍数の場合に n/2 ビットの安全性レベルが担保できることが示されている.

Romulus-T の安全性証明は文献 [57] で与えられる. その証明では, Romulus-H が 2 つの耐漏洩安全性 CIML2, CCAmL2 [15] を持ち, その安全性レベルがそれぞれ n − log n ビット, n/2 ビットであることが示されている. 詳細な安全性定義及び仮定する漏洩モデルについては [57] を参照されたいが, 概要として 2 つの耐漏洩安全性は以下のような意味を持つ. CIML2 は Ciphertext integrity withmisuse-resistance and leakage の略で, Nonce misuse (resistance) 設定かつ暗復号オラクルから漏洩情報を得られる攻撃者を仮定した下での改ざん検知の安全性を指す. CCAmL2 は Chosen-ciphertext

attack with misuse-resilience and leakage の略で, Nonce misuse (resilience) 設定かつ暗復号オラク
ルから漏洩情報を得られる攻撃者を仮定した下での秘匿の安全性を指す. 加えて同文献では, ブラックボックス設定下においても Romulus-T が Nonce-misuse resilience の秘匿の安全性を持つことが示されており, その安全性レベルが n − log n ビットであることが証明されている.

Romulus-H の安全性は MDPH の安全性証明 [58, 90] より導出される. その証明では, 用いる TBC
を Ideal cipher としたとき, MDPH がランダムオラクルとの Indiﬀerentiability を持ち, そのバウン
ドが O(2n /n) であることが示されている. 表 5.2 における安全性レベルはここから導出される.
次に第三者評価について述べる. Romulus の各モードへの第三者評価としては以下が挙げられる
が, 仕様上の安全性を脅かすものではない.

• Lee による Romulus-N と Romulus-M の安全性証明に対する第三者評価 [78]. 提案者らと独立して Romulus-N の Nonce respecting 下での安全性証明, Romulus-M の Nonce respecting, 及びNonce misuse の下での安全性証明を行い, それらと提案者らが主張する安全性レベルに齟齬がないことを示している.

• 土生らによる Romulus-N と Romulus-M に対する識別攻撃及び偽造攻撃 [118]. Romulus-N に対する Nonce respecting の下での識別攻撃と偽造攻撃, 及び Romulus-M に対する Nonce misuseの下での識別攻撃と偽造攻撃を提案した. これらの攻撃に必要な計算量が, 安全性証明により示される安全性バウンドが要求する攻撃成功に必要な計算量とそれぞれ同等であるため, それらのバウンドがタイトであることを示す結果である.

• Habu らによる Romulus-M に対するマッチング攻撃 [60]. Romulus-M に対する Nonce misuse の下での識別攻撃と偽造攻撃を提案した. これらの攻撃に必要な計算量が, 安全性証明により示される安全性バウンドが要求する攻撃成功に必要な計算量と同等であるため, それらのバウンドがタイトであることを示す結果である. また同文献において提案した偽造攻撃により, Romulus-Mの INT-RUP 安全性バウンドがタイトであることも示されている.

5.3.3

プリミティブの安全性

2022 年 9 月現在, Skinny-128-384+ の安全性を脅かす攻撃は発表されていない. Skinny-128-384+
は Skinny-128-384 のラウンド数を 56 段から 40 段に削減したものであるが, Skinny-128-384 に対する26

表 5.3: Skinny-128-384 に対する Related-key 設定下での鍵回復攻撃.

RoundsTime

Data

MethodRef

30 / 56

2

361.7

125.3

2

Rectangle[61]

30 / 562341.12122.0

Rectangle[94]

32 / 562355.02123.5

Rectangle[49]

32 / 562344.82123.5

Rectangle[101]

表 5.4: Skinny-128-384 に対する Single-key 設定下での鍵回復攻撃. 但し, 文献 [62] は 360 ビット
Single-key で Chosen tweak 設定.

RoundsTime

Data

MethodRef

23 / 56

376.0

104.0

MITM

[47]

2

376.0

2

32.0

22 / 56

2

2

MITM

[66]

25 / 56

2372.52122.3

Diﬀ-MITM[28]

26 / 562344.02121.0Integral[62]

現時点での最良解析として, 32 段の Skinny-128-384 に対する Related-key 設定下での Rectangle 攻撃 [49, 101] が挙げられる. また現時点における 128 ビット鍵の Skinny-128-384+ に対する攻撃可能
段数として, 提案者らは Related-key 設定下の識別攻撃については 25 段, Single-key 設定下の鍵回復
攻撃については 23 段未満であると述べている [56].
本節では主に Skinny-128-384 に対して 2022 年に発表された解析, 及び Related-key 設定と Single-

key 設定においてそれぞれ現時点での最良の解析をまとめる.
Related-key 設定

Related-key 設定における Skinny-128-384 への鍵回復攻撃を表 5.3 にまとめる. 但し, これらの解析は Skinny-128-384 の 384 ビット鍵に対する攻撃であり, 128 ビット鍵を持つ

Skinny-128-384+ に対するものではないことに注意されたい. より小さい鍵長を持つ Skinny への解析例として, Skinny-128-384 の 1 つの Tweakey 配列 T K を固定した場合の解析で以下のものが挙げられるが, これらも 256 ビット鍵への攻撃であるため 128 ビット鍵を持つ Skinny-128-384+ に対する解析とはならない [56].

• Hadipour らによる Rectangle 攻撃 [61]. 24 段に削減した Skinny-128-256 を時間計算量 2209.9 ,
データ量 2125.2 で攻撃できることを示した.

• Qin らによる Rectangle 攻撃 [94]. 25 段に削減した Skinny-128-256 を時間計算量 2226.4 , デー
タ量 2124.5 で攻撃できることを示した.

• Dong らによる Rectangle 攻撃 [49]. 26 段に削減した Skinny-128-256 を時間計算量 2254.4 , デー
タ量 2126.5 で攻撃できることを示した.
また, 識別攻撃は以下の通りである.

• Hadipour らによる Boomerang 攻撃 [61]. 25 段に削減した Skinny-128-384 を確率 2−116.6 で識別できることを示した. また, 1 つの T K を固定した設定の下では 21 段に削減した Skinny-128-256に対して確率 2−114.1 で識別できることを示した.

• Delaune らによる Boomerang 攻撃 [35]. 24 段に削減した Skinny-128-384 を確率 2−86.1 で識別できることを示した. また, 1 つの T K を固定した設定の下では 20 段に削減した Skinny-128-256に対して確率 2−85.8 で識別できることを示した.

Single-key 設定

Single-key 設定における鍵回復攻撃を表 5.4 にまとめる. 但し Related-key 設定の場合と同様に, これらの攻撃に必要な計算量は 2128 を大きく超えるため, Skinny-128-384+ の 128
ビット安全性に対する攻撃にはならないことに注意されたい. 384 ビット未満の安全性レベルについて, 提案者らは Skinny-128-256 の 256 ビット安全性に対して計算量 2216 で 22 段まで攻撃可能であり, Skinny-64-192 の 128 ビット安全性に対して計算量 2116.5 で 17 段まで攻撃可能であると述べている [56].

27

その他

上に挙げた解析以外の最近の結果としては, Kuijsters らによる線形特性の評価 [77] が挙げられる. 2 ラウンドの Subtweakey1 の部分集合に対して, 線形特性が 1 のものを発見したという結果
であるが, 提案者らはこの解析結果は特に驚くべきものではなく, Skinny の安全性には影響しないと述べている [56]. また, 量子計算機を用いた解析として David らによる 21 段 Skinny-128-256 への量
子不能差分攻撃 [34] や, Bijwe らによる Grover アルゴリズムの量子コスト評価 [23] が挙げられるが,何れも安全性を脅かすものではない.

5.3.4

その他

モード単体, プリミティブ単体の解析以外のものとしては以下が挙げられるが, 仕様上の安全性を脅かすものではない.

• Dong らによるラウンド数を削減し Skinny-128-384+ を用いた Romulus-H に対する原像攻撃及び Romulus-H の内部圧縮関数に対する衝突攻撃 [47]. Skinny-128-384+ フルラウンド 40 段のうち 23 段に削減した場合に, Romulus-H に対して時間計算量 2248 で原像攻撃が可能であることを示している. この計算量は提案者らが主張する Romulus-H の安全性レベルを大きく超えているため, 主張される安全性と矛盾しない. また, 23 段に削減した Romulus-H の内部圧縮関数
に対して, Free-start 設定下における衝突攻撃が時間計算量 2124 , 空間計算量 2124 で可能であることを示している.

• Nageler らによるラウンド数を削減した Skinny-128-384+ を用いた Romulus-H での衝突発見 [89].
Skinny-128-384+ フルラウンド 40 段のうち 10 段に削減した場合に衝突を, 14 段に削減した場
合に Semi-free-start 設定での衝突を現実的な時間で発見している.
また, Romulus-N のサイドチャネル攻撃に対する安全性解析として, Vialar によるサイドチャネル攻撃を用いた Romulus-N の鍵回復 [107], Chakraborty らによる投機的実行を利用した Romulus-N の鍵
回復 [32] が挙げられる. また, 文献 [111] 内に Romulus-N のサイドチャネル情報を評価したレポートが存在する. 但し, 提案者らは Romulus-N の非ブラックボックス安全性については特に主張していな
いため, これらの解析も仕様書で主張される安全性とは矛盾しない.

1 AddRoundTweakey において内部ステートと排他的論理和を取る Tweakey 部分のことを指す.

28

参考文献

[1] The Keccak crunchy crypto collision and pre-image contest.

https://keccak.team/crunchy_contest.html.
[2] Lightweight Cryptography. http://competitions.cr.yp.to/caesar.html.
[3] Elephant, 2022. https://www.esat.kuleuven.be/cosic/elephant/.
[4] ISAP, 2022. https://isap.iaik.tugraz.at/index.html.
[5] FIPS 202. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions,
August 2015.
[6] Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz, and Patrick Struck. Postquantum security of the (tweakable) fx construction, and applications. Cryptology ePrint
Archive, Paper 2022/1097, 2022. https://eprint.iacr.org/2022/1097.
[7] Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, and Kan
Yasuda. How to Securely Release Unveriﬁed Plaintext in Authenticated Encryption. In ASIACRYPT (1), volume 8873 of Lecture Notes in Computer Science, pages 105–125. Springer,
2014.
[8] Tomer Ashur, Orr Dunkelman, and Atul Luykx. Boosting authenticated encryption robustness with minimal modiﬁcations.

In Jonathan Katz and Hovav Shacham, editors,

CRYPTO 2017, Part III, volume 10403 of LNCS, pages 3–33. Springer, Heidelberg, August 2017.
[9] Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi,Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.1. Submission to the NIST Lightweight Cryptography project, 2021.
[10] Lejla Batina, Ileana Buhan, Lukasz Chmielewski, Ellen Gunnarsdóttir, Vahid Jahandideh,
Tom Stock, and Léo Weissbart. Side-Channel Evaluation Report on Implementations of Several NIST LWC Finalists. 2022. https://cryptography.gmu.edu/athena/LWC/Reports/
Radboud/Radboud_Report_SW_3_candidates.pdf.
[11] Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin,
Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY family of block ciphersand its low-latency variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors,
CRYPTO 2016, Part II, volume 9815 of LNCS, pages 123–153. Springer, Heidelberg, August
2016.
[12] Mihir Bellare and Chanathip Namprempre. Authenticated encryption: Relations amongnotions and analysis of the generic composition paradigm. In Tatsuaki Okamoto, editor,

29

ASIACRYPT 2000, volume 1976 of LNCS, pages 531–545. Springer, Heidelberg, December
2000.
[13] Davide Bellizia, Olivier Bronchain, Gaëtan Cassiers, Vincent Grosso, Chun Guo, Charles
Momin, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Mode-level vs.
implementation-level physical security in symmetric cryptography - A practical guide throughthe leakage-resistance jungle.

In Daniele Micciancio and Thomas Ristenpart, editors,

CRYPTO 2020, Part I, volume 12170 of LNCS, pages 369–400. Springer, Heidelberg, August
2020.
[14] Daniel J. Bernstein. How to stretch random functions: The security of protected countersums. Journal of Cryptology, 12(3):185–192, June 1999.
[15] Francesco Berti, Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert.
TEDT: a leakage-resistant AEAD mode. IACR TCHES, 2020(1):256–320, 2019. https://tches.iacr.org/index.php/TCHES/article/view/8400.
[16] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Sponge functions.
Ecrypt Hash Workshop 2007, 2007. http://sponge.noekeon.org/SpongeFunctions.pdf.
[17] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. The Keccak reference,
January 2011.
[18] Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, and Ronny Van Keer.
CAESAR submisiion: Ketje v2, 2016.
[19] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. On the indiﬀerentiability of the sponge construction. In Nigel P. Smart, editor, EUROCRYPT 2008, volume4965 of LNCS, pages 181–197. Springer, Heidelberg, April 2008.
[20] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Duplexing the sponge:
Single-pass authenticated encryption and other applications. In Ali Miri and Serge Vaudenay,
editors, SAC 2011, volume 7118 of LNCS, pages 320–337. Springer, Heidelberg, August 2012.
[21] Tim Beyne, Yu Long Chen, Christoph Dobraunig, and Bart Mennink. Elephant v2.0. Submission to the NIST Lightweight Cryptography project, 2021.
[22] Tim Beyne, Yu Long Chen, Christoph Dobraunig, and Bart Mennink. Multi-user securityof the elephant v2 authenticated encryption mode. In Riham AlTawy and Andreas Hülsing,editors, Selected Areas in Cryptography, pages 155–178, Cham, 2022. Springer International
Publishing.
[23] Subodh Bijwe, Amit Kumar Chauhan, and Somitra Kumar Sanadhya. Implementing grover
oracle for lightweight block ciphers under depth constraints. In ACISP, volume 13494 of
Lecture Notes in Computer Science, pages 85–105. Springer, 2022.
[24] Andrey Bogdanov, Miroslav Knežević, Gregor Leander, Deniz Toz, Kerem Varici, and Ingrid Verbauwhede. Spongent: A lightweight hash function. In Bart Preneel and Tsuyoshi
Takagi, editors, CHES 2011, volume 6917 of LNCS, pages 312–325. Springer, Heidelberg,
September / October 2011.

30

[25] Rachelle Heim Boissier, Camille Noûs, and Yann Rotella. Algebraic collision attacks on
Keccak. IACR Trans. Symm. Cryptol., 2021(1):239–268, 2021.
[26] Xavier Bonnetain and Samuel Jaques. Quantum period ﬁnding against symmetric primitives
in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(1):1–27, 2022.
[27] Christina Boura, Anne Canteaut, and Christophe De Cannière. Higher-order diﬀerential
properties of Keccak and Luﬀa. In Antoine Joux, editor, FSE 2011, volume 6733 of LNCS,
pages 252–269. Springer, Heidelberg, February 2011.
[28] Christina Boura, Nicolas David, Patrick Derbez, Gregor Leander, and María Naya-Plasencia.
Diﬀerential meet-in-the-middle cryptanalysis. Cryptology ePrint Archive, Paper 2022/1640,
2022. https://eprint.iacr.org/2022/1640.
[29] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based
authenticated encryption: How small can we go? In CHES 2017, volume 10529 of Lecture
Notes in Computer Science, pages 277–298. Springer, 2017.
[30] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based
authenticated encryption: How small can we go? (full version of [29]). IACR Cryptology
ePrint Archive, 2017:649, 2017.
[31] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based
authenticated encryption: How small can we go? Journal of Cryptology, 33(3):703–741, July
2020.
[32] Anirban Chakraborty, Nikhilesh Singh, Sarani Bhattacharya, Chester Rebeiro, and Debdeep
Mukhopadhyay. Timed speculative attacks exploiting store-to-load forwarding bypassing
cache-based countermeasures. In Proceedings of the 59th ACM/IEEE Design Automation
Conference, DAC ’22, page 553–558, New York, NY, USA, 2022. Association for Computing
Machinery.
[33] Joan Daemen, Bart Mennink, and Gilles Van Assche. Full-state keyed duplex with built-in
multi-user support. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017,
Part II, volume 10625 of LNCS, pages 606–637. Springer, Heidelberg, December 2017.
[34] Nicolas David, María Naya-Plasencia, and André Schrottenloher. Quantum impossible diﬀerential attacks: Applications to aes and skinny. Cryptology ePrint Archive, Paper 2022/754,
2022. https://eprint.iacr.org/2022/754.
[35] Stéphanie Delaune, Patrick Derbez, and Mathieu Vavrille. Catching the fastest boomerangs
application to SKINNY. IACR Trans. Symmetric Cryptol., 2020(4):104–129, 2020.
[36] Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, Florian Mendel, Bart Mennink,Robert Primas, and Thomas Unterluggauer. ISAP v2.0. IACR Trans. Symm. Cryptol.,2020(S1):390–416, 2020.
[37] Christoph Dobraunig,
Mennink,

Maria Eichlseder,

Robert Primas,

Stefan Mangard,

and Thomas Unterluggauer.

Florian Mendel,

Bart

NIST update:

ISAP

v2.0, 2020. https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/
documents/round-2/status-update-sep2020/ISAP_update_isap.pdf.
31

[38] Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, Florian Mendel, Bart Mennink,Robert Primas, and Thomas Unterluggauer. ISAP v2.0. Submission to the NIST Lightweight
Cryptography project, 2021.
[39] Christoph Dobraunig,
Mennink,

Maria Eichlseder,

Robert Primas,

Stefan Mangard,

and Thomas Unterluggauer.

Florian Mendel,

Bart

NIST update:

ISAP

v2.0, 2022. https://csrc.nist.gov/csrc/media/Projects/lightweight-cryptography/
documents/finalist-round/status-updates/isap-update.pdf.
[40] Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, Florian Mendel, and Thomas Unterluggauer. ISAP – towards side-channel secure authenticated encryption. IACR Trans.
Symm. Cryptol., 2017(1):80–105, 2017.
[41] Christoph Dobraunig, Maria Eichlseder, Florian Mendel, and Martin Schläﬀer. Ascon v1.2.
Submission to the NIST Lightweight Cryptography project, 2021.
[42] Christoph Dobraunig and Bart Mennink. Leakage resilience of the duplex construction. In
Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923
of LNCS, pages 225–255. Springer, Heidelberg, December 2019.
[43] Christoph Dobraunig and Bart Mennink. Leakage resilience of the ISAP mode: a vulgarizedsummary. NIST Lightweight Cryptography Workshop 2019, 2019.
[44] Christoph Dobraunig and Bart Mennink. Security of the suﬃx keyed sponge. IACR Trans.
Symm. Cryptol., 2019(4):223–248, 2019.
[45] Christoph Dobraunig and Bart Mennink. Tightness of the suﬃx keyed sponge bound. IACR
Trans. Symm. Cryptol., 2020(4):195–212, 2020.
[46] Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary
input. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 621–630. ACM Press,
May / June 2009.
[47] Xiaoyang Dong, Jialiang Hua, Siwei Sun, Zheng Li, Xiaoyun Wang, and Lei Hu. Meet-inthe-middle attacks revisited: Key-recovery, collision, and preimage attacks. In CRYPTO (3),volume 12827 of Lecture Notes in Computer Science, pages 278–308. Springer, 2021.
[48] Xiaoyang Dong, Zheng Li, Xiaoyun Wang, and Ling Qin. Cube-like attack on round-reduced
initialization of Ketje Sr. IACR Trans. Symm. Cryptol., 2017(1):259–280, 2017.
[49] Xiaoyang Dong, Lingyue Qin, Siwei Sun, and Xiaoyun Wang. Key guessing strategies forlinear key-schedule algorithms in rectangle attacks. In EUROCRYPT (3), volume 13277 of
Lecture Notes in Computer Science, pages 3–33. Springer, 2022.
[50] Alexandre Duc, Jian Guo, Thomas Peyrin, and Lei Wei. Unaligned rebound attack: Application to Keccak. In Anne Canteaut, editor, FSE 2012, volume 7549 of LNCS, pages 402–421.
Springer, Heidelberg, March 2012.
[51] Pooya Farshim, Claudio Orlandi, and Răzvan Roşie. Security of symmetric primitives underincorrect usage of keys. IACR Trans. Symm. Cryptol., 2017(1):449–473, 2017.

32

[52] Thomas Fuhr, María Naya-Plasencia, and Yann Rotella. State-recovery attacks on modiﬁed
Ketje Jr. IACR Trans. Symmetric Cryptol., 2018(1):29–56, 2018.
[53] David Gerault, Thomas Peyrin, and Quan Quan Tan. Exploring diﬀerential-based distinguishers and forgeries for ASCON. IACR Trans. Symm. Cryptol., 2021(3):102–136, 2021.
[54] Robert Granger, Philipp Jovanovic, Bart Mennink, and Samuel Neves. Improved masking
for tweakable blockciphers with applications to authenticated encryption. In Marc Fischlin
and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages
263–293. Springer, Heidelberg, May 2016.
[55] Chun Guo, Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin.
Romulus v1.3. Submission to the NIST Lightweight Cryptography project, 2021.
[56] Chun Guo, Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas
Peyrin. Final-round updates on Romulus, 2022. https://csrc.nist.gov/csrc/media/
Projects/lightweight-cryptography/documents/finalist-round/status-updates/
romulus-update.pdf.
[57] Chun Guo, Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin.
Security Proof for Romulus-T. https://romulusae.github.io/romulus/docs/Romulus_
T_proof.pdf, 2022.
[58] Chun Guo, Tetsu Iwata, and Kazuhiko Minematsu. New indiﬀerentiability security proof of
MDPH hash function. IET Inf. Secur., 16(4):262–281, 2022.
[59] Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert.

Towards

low-energy leakage-resistant AE from the duplex sponge. IACR Trans. Symm. Cryptol.,2020(1):6–42, 2020.
[60] Makoto Habu, Kazuhiko Minematsu, and Tetsu Iwata. Matching attacks on Romulus-M.
IET Inf. Secur., 16(6):459–469, 2022.
[61] Hosein Hadipour, Nasour Bagheri, and Ling Song. Improved rectangle attacks on SKINNY
and CRAFT. IACR Trans. Symmetric Cryptol., 2021(2):140–198, 2021.
[62] Hosein Hadipour, Sadegh Sadeghi, and Maria Eichlseder. Finding the impossible: Automatedsearch for full impossible diﬀerential, zero-correlation, and integral attacks (preliminary version). Cryptology ePrint Archive, Paper 2022/1147, 2022. https://eprint.iacr.org/
2022/1147.
[63] Shoichi Hirose. Some Plausible Constructions of Double-Block-Length Hash Functions. In
FSE 2006, volume 4047 of Lecture Notes in Computer Science, pages 210–225. Springer,
2006.
[64] Shoichi Hirose, Je Hong Park, and Aaram Yun. A simple variant of the merkle-damgård
scheme with a permutation. In ASIACRYPT, volume 4833 of Lecture Notes in Computer
Science, pages 113–129. Springer, 2007.
[65] Kai Hu and Thomas Peyrin. Revisiting higher-order diﬀerential(-linear) attacks from analgebraic perspective – applications to ascon, grain v1, xoodoo, and chacha. Cryptology
ePrint Archive, Paper 2022/1335, 2022. https://eprint.iacr.org/2022/1335.
33

[66] Jialiang Hua, Tai Liu, Yulong Cui, Lingyue Qin, Xiaoyang Dong, and Huiyong Cui. Low-Data
Cryptanalysis On SKINNY Block Cipher. The Computer Journal, 02 2022. bxab208.
[67] Akiko Inoue, Chun Guo, and Kazuhiko Minematsu. Nonce-misuse resilience of romulus-n
and gift-cofb. Cryptology ePrint Archive, Paper 2022/1012, 2022. https://eprint.iacr.
org/2022/1012.
[68] ISO/IEC. 29192-5:2016 – Information technology – Security techniques – Lightweight cryptography – Part 5: Hash-functions, 2016.
[69] ISO/IEC. 18033-7:2022 – Information security – Encryption algorithms – Part 7: Tweakable
block ciphers, 2022.
[70] Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. New Resultson Romulus. NIST Lightweight Cryptography Workshop 2020, 2006. Available at https://csrc.nist.gov/CSRC/media/Events/lightweight-cryptography-workshop-2020/
documents/papers/new-results-romulus-lwc2020.pdf.
[71] Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. Updates on
Romulus, Remus and TGIF. NIST Lightweight Cryptography Workshop 2019, 2019.
[72] Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. Duel of the
Titans: The Romulus and Remus Families of Lightweight AEAD Algorithms. IACR Trans.
Symmetric Cryptol., 2020(1):43–120, 2020.
[73] Christian Janson and Patrick Struck. Sponge-based authenticated encryption: Security
against quantum attackers. In PQCrypto, volume 13512 of Lecture Notes in Computer Science, pages 230–259. Springer, 2022.
[74] Priyanka Joshi and Bodhisatwa Mazumdar. Single event transient fault analysis of ELEPHANT cipher. CoRR, abs/2106.09536, 2021.
[75] Matthias J. Kannwischer, Peter Pessl, and Robert Primas. Single-trace attacks on Keccak.
IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020(3):243–268, 2020.
[76] Stefan Kölbl, Florian Mendel, Tomislav Nad, and Martin Schläﬀer. Diﬀerential cryptanalysis
of Keccak variants. In Martijn Stam, editor, 14th IMA International Conference on Cryptography and Coding, volume 8308 of LNCS, pages 141–157. Springer, Heidelberg, December
2013.
[77] Daniël Kuijsters, Denise Verbakel, and Joan Daemen. Weak subtweakeys in SKINNY. Cryptology ePrint Archive, Paper 2022/1042, 2022. https://eprint.iacr.org/2022/1042, To
appear in INDOCRYPT 2022.
[78] Jooyoung Lee. Security evaluation of romulus. https://romulusae.github.io/romulus/
docs/Security_evaluation_Romulus_Jooyoung_Lee.pdf.
[79] Charlotte Lefevre and Bart Mennink. Tight preimage resistance of the sponge construction. In CRYPTO (4), volume 13510 of Lecture Notes in Computer Science, pages 185–204.
Springer, 2022.

34

[80] Ting Li, Yao Sun, Maodong Liao, and Dingkang Wang. Preimage attacks on the roundreduced Keccak with cross-linear structures. IACR Trans. Symm. Cryptol., 2017(4):39–57,
2017.
[81] Zheng Li, Xiaoyang Dong, Wenquan Bi, Keting Jia, Xiaoyun Wang, and Willi Meier. New
conditional cube attack on Keccak keyed modes. IACR Trans. Symm. Cryptol., 2019(2):94–
124, 2019.
[82] Moses Liskov, Ronald L. Rivest, and David Wagner. Tweakable block ciphers. In Moti Yung,
editor, CRYPTO 2002, volume 2442 of LNCS, pages 31–46. Springer, Heidelberg, August
2002.
[83] Moses Liskov, Ronald L. Rivest, and David Wagner. Tweakable block ciphers. Journal of
Cryptology, 24(3):588–613, July 2011.
[84] Atul Luykx, Bart Preneel, Elmar Tischhauser, and Kan Yasuda. A MAC mode for lightweightblock ciphers. In Thomas Peyrin, editor, FSE 2016, volume 9783 of LNCS, pages 43–59.
Springer, Heidelberg, March 2016.
[85] Hasindu Madushan, Iftekhar Salam, and Janaka Alawatugoda.

A review of the NIST

lightweight cryptography ﬁnalists and their fault analyses. Electronics, 11(24), 2022.
[86] Marcel Medwed, François-Xavier Standaert, Johann Großschädl, and Francesco Regazzoni.
Fresh re-keying: Security against side-channel and fault attacks for low-cost devices. In
Daniel J. Bernstein and Tanja Lange, editors, AFRICACRYPT 10, volume 6055 of LNCS,
pages 279–296. Springer, Heidelberg, May 2010.
[87] Silvia Mella, Joan Daemen, and Gilles Van Assche. New techniques for trail bounds andapplication to diﬀerential trails in Keccak. IACR Trans. Symm. Cryptol., 2017(1):329–357,
2017.
[88] Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In
Moni Naor, editor, TCC 2004, volume 2951 of LNCS, pages 278–296. Springer, Heidelberg,
February 2004.
[89] Marcel Nageler, Felix Pallua, and Maria Eichlseder. Finding collisions for round-reduced
romulus-h. Cryptology ePrint Archive, Paper 2022/1630, 2022. https://eprint.iacr.
org/2022/1630.
[90] Yusuke Naito.

Optimally indiﬀerentiable double-block-length hashing without post-processing and with support for longer key than single block. In LATINCRYPT, volume11774 of Lecture Notes in Computer Science, pages 65–85. Springer, 2019.
[91] Yusuke Naito and Takeshi Sugawara. Lightweight authenticated encryption mode of operation for tweakable block ciphers. IACR TCHES, 2020(1):66–94, 2019. https://tches.
iacr.org/index.php/TCHES/article/view/8393.
[92] Chanathip Namprempre, Phillip Rogaway, and Thomas Shrimpton. Reconsidering genericcomposition. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014,
volume 8441 of LNCS, pages 257–274. Springer, Heidelberg, May 2014.

35

[93] Thomas Peyrin and Yannick Seurin. Counter-in-tweak: Authenticated encryption modes fortweakable block ciphers. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016,
Part I, volume 9814 of LNCS, pages 33–63. Springer, Heidelberg, August 2016.
[94] Lingyue Qin, Xiaoyang Dong, Xiaoyun Wang, Keting Jia, and Yunwen Liu. Automatedsearch oriented to key recovery on ciphers with linear key schedule applications to boomerangs
in SKINNY and forkskinny. IACR Trans. Symmetric Cryptol., 2021(2):249–291, 2021.
[95] Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap
problem. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages
373–390. Springer, Heidelberg, May / June 2006.
[96] Raghvendra Rohit, Kai Hu, Sumanta Sarkar, and Siwei Sun. Misuse-free key-recovery anddistinguishing attacks on 7-round Ascon. IACR Trans. Symm. Cryptol., 2021(1):130–155,
2021.
[97] André Schrottenloher and Marc Stevens. Simpliﬁed mitm modeling for permutations: New(quantum) attacks. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 717–747, Cham, 2022. Springer Nature Switzerland.
[98] Tairong Shi, Wenling Wu, Bin Hu, Jie Guan, and Sengpeng Wang. Breaking LWC candidates:
sESTATE and Elephant in quantum setting. Des. Codes Cryptogr., 89(7):1405–1432, 2021.
[99] Ling Song and Jian Guo. Cube-attack-like cryptanalysis of round-reduced KECCAK using
MILP. IACR Trans. Symm. Cryptol., 2018(3):182–214, 2018.
[100] Ling Song, Jian Guo, Danping Shi, and San Ling. New MILP modeling: Improved conditional
cube attacks on Keccak-based constructions. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 65–95. Springer, Heidelberg,
December 2018.
[101] Ling Song, Nana Zhang, Qianqian Yang, Danping Shi, Jiahao Zhao, Lei Hu, and Jian Weng.
Optimizing rectangle attacks: A uniﬁed and generic framework for key recovery. IACR
Cryptol. ePrint Arch., page 723, 2022.
[102] Ling Sun, Wei Wang, and Meiqin Wang. Milp-aided bit-based division property for primitives
with non-bit-permutation linear layers. IET Inf. Secur., 14(1):12–20, 2020.
[103] Shu Takemoto, Yoshiya Ikezaki, Yusuke Nozaki, and Masaya Yoshikawa. Hardware trojan
for lightweight cryptoraphy elephant. In 2021 IEEE 10th Global Conference on Consumer
Electronics (GCCE), pages 944–945, 2021.
[104] Balazs Udvarhelyi, Olivier Bronchain, and François-Xavier Standaert. Security analysis ofdeterministic re-keying with masking and shuﬄing: Application to ISAP. In COSADE,
volume 12910 of Lecture Notes in Computer Science, pages 168–183. Springer, 2021.
[105] Corentin Verhamme, Gaëtan Cassiers, and François-Xavier Standaert. Analyzing the leakage
resistance of the nist’s lightweight crypto competition’s ﬁnalists. Cryptology ePrint Archive,
Paper 2022/1628, 2022. https://eprint.iacr.org/2022/1628, , To appear in CARDIS
2022.

36

[106] Louis Vialar. Fast side-channel key-recovery attack against elephant dumbo. Cryptology
ePrint Archive, Paper 2022/446, 2022. https://eprint.iacr.org/2022/446.
[107] Louis Vialar. Side Channel Analysis of NIST Lightweight Cryptography Candidates. Master’s
thesis, Swiss Federal Institute of Technology in Lausanne, 2022.
[108] Hailun Yan, Xuejia Lai, Lei Wang, Yu Yu, and Yiran Xing. New zero-sum distinguishers on
full 24-round Keccak-f using the division property. IET Inf. Secur., 13(5):469–478, 2019.
[109] Guo-Shuang Zhang, Yin Li, and Xiao Chen. Improved state-recovery attacks on modiﬁed
KETJE JR. 2021.
[110] Guoyan Zhang and Meicheng Liu. A distinguisher on PRESENT-like permutations withapplication to SPONGENT. Cryptology ePrint Archive, Report 2016/236, 2016. https://eprint.iacr.org/2016/236.
[111] Xiaolin Zhang, Tengfei Wang, and Pei Cao. Side-Channel Evaluation on Protected Implementations of Several NIST LWC Finalists. 2022. https://cryptography.gmu.edu/athena/
LWC/Reports/SJTU/SJTU_Report_HW_4_candidates_RUB.pdf.
[112] Zishen Zhao, Shiyao Chen, Meiqin Wang, and Wei Wang. Improved cube-attack-like cryptanalysis of reduced-round Ketje-Jr and Keccak-MAC. Inf. Process. Lett., 171:106124, 2021.
[113] Haibo Zhou, Zheng Li, Xiaoyang Dong, Keting Jia, and Willi Meier. Practical key-recovery
attacks on round-reduced Ketje Jr, Xoodoo-AE and xoodyak. Comput. J., 63(8):1231–1246,
2020.
[114] Haibo Zhou, Rui Zong, Xiaoyang Dong, Keting Jia, and Willi Meier. Interpolation attacks onround-reduced elephant, kravatte and xooﬀf. Cryptology ePrint Archive, Report 2020/781,
2020. https://eprint.iacr.org/2020/781.
[115] Rui Zong, Xiaoyang Dong, and Xiaoyun Wang. Collision attacks on round-reduced gimlihash/ascon-xof/ascon-hash. Cryptology ePrint Archive, Paper 2019/1115, 2019. https://eprint.iacr.org/2019/1115.
[116] 伊藤竜馬. 「CRYPTREC 暗号技術ガイドライン（軽量暗号）」掲載の暗号方式に関する安全性評価の動向調査（文書番号: CRYPTREC EX-3101-2021）, 2022. https://www.cryptrec.

go.jp/exreport/cryptrec-ex-3101-2021.pdf.
[117] 土生亮 and 岩田哲. Elephant に対する鍵回復, 識別及び偽造攻撃. SCIS2022, 1F2-5, 2022.
[118] 土生亮, 峯松一彦, and 岩田哲. Romulus-N 及び Romulus-M に対する識別攻撃及び偽造攻撃.
信学技報, 121(22, ISEC2021-6):25–31, 2022.

37