cubing 暗号

この暗号化アルゴリズムはセキュリティ・キャンプ全国大会 2019 暗号化通信ゼミにて開発されました．

cubing 暗号の暗号化/復号アルゴリズム

執筆中

cubing 暗号の暗号化利用モード

概要

• 平文ブロック長：45 文字
• 暗号文ブロック長：54 文字
• 鍵長：可変
• 暗号化処理の並列化：部分的に可 (※但し，Shuffle がボトルネックとなる)
• 復号処理の並列化：部分的に可 (※但し，Sort がボトルネックとなる)
• Random Read：不可

図

暗号化-復号の図

各ブロックの内容

流れ

暗号化

1. 平文をブロックに分ける
2. 必要があればパディングを用意する
3. 全ての平文に対してマスク処理 1 を行う
4. 全てのブロックに対し，エンコードを行う
5. 全てのブロックのハッシュに対してマスク処理 2 を行う
6. ブロックごとに暗号化を行う
7. ブロックをシャッフルする (下記「shuffle」参照)

復号

1. 暗号文をブロックに分ける
2. 全てのブロックに対して復号を行う
3. 暗号化の(5)で使用したマスク処理を元に戻す
4. (3)により現れるシーケンス番号を元に，ブロック間ソートを行う
5. 暗号化の(3)で使用したマスク処理を元に戻す
6. 全てのブロックに対し，デコードを行う
7. 全てのブロックを結合させ，平文を生成する

パディング

平文ブロックが 45 文字 に満たない場合，1 文字 分 null 入れ，残りはランダムな英数列を入れる．

98 進数の説明

下記の文字集合を用いて表現できる数であり，この集合を表示可能文字と呼ぶ．表示可能文字は下記の順に順序を持っている．エスケープシーケンスに関しては ASCII コード参照．

{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '!', '"', '#', '$', '%', '&', ''', '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\', ']', '^', '_', '`', '{', '|', '}', '~', ' ', '\n', '\0', '\t'}

エンコード

本節では以下の記号を用いる．

$n$：現在操作しているブロックの番号(0,1,2,...) $C_i$：ブロックの$i$ 文字目の文字 $\mathrm{toas}(C)$：特定の文字$C$の ASCII コードにおける番号 $\mathrm{fras}(N)$：特定の数字$N$の ASCII コードにおける文字 $\mathrm{rand}()$：アルファベット又は数字から 1 文字を一様に選ぶ関数 $\mathrm{to62}(x)$：$[0, 98)$ の自然数 x を 98 進数に従って文字に変換する関数

この時，

$$\begin{aligned} C_{45+i} &= \mathrm{fras}\left(\left(\left(\sum_{j=9(i-1)+1}^{9i}{\mathrm{toas}(C_j)}\right)\bmod 26\right)+\mathrm{toas}\left(\mathrm{A}\right)\right)\\\ C_{51} &= \mathrm{to62}\left (\left \lfloor\frac{n}{98}\right \rfloor \right)\\\ C_{52} &= \mathrm{to62}\left ( n \bmod 98 \right)\\\ C_{53} &= \mathrm{rand}()\\\ C_{54} &= \mathrm{rand}()\\\ \end{aligned}$$

とする．ただし，$i=1,2,3,4,5$ とする．これを全てのブロックに対して行う．

デコード

上記「エンコード」で付与した値を削除する．また，ハッシュが一致しているかチェックする．これにより改ざんやビット反転を検知することができる．

mask(1)

mask(1)では各ブロックの平文の先頭 45 文字にマスク処理を行う．まず，以下を定義する．

平文の$i$文字目：$Pi$ > $i$番目のマスク：$Mi$ 表示可能文字内の文字$Pi$のインデックス：$\mathrm{Idx}(Pi)$

とすると，

$$Pi=\mathrm{printable\_table}[(\mathrm{Idx}(Pi)+Mi) \bmod 98]\\$$

とする．

mask(2)

mask(2)ではハッシュとシーケンス番号にマスクをかける．計算方法は上記「mask(1)」と同様．

encrypt

暗号化処理

decrypt

復号処理

shuffle

暗号化後に全ブロックをシャッフルする．Fisher–Yates のアルゴリズムを用いることによって高速に実現可能となる．

sort

各ブロックの 51,52 番目を 98 進数として扱い，この値が昇順になるようにブロックごとにソートする．

送信内容

1. 暗号文 ( $N$ ブロック)
2. mask(1) ( $N*45$ 文字)
3. mask(2) ( $N*5$ 文字)

リプレイ攻撃対策

上記shuffleを行うことによって，どのブロックがもともとどこに在ったのか，という情報が隠蔽され，ブロックのすり替えができなくなる．

ブロックが$98^2$より多くある時の処理

$62^2$個のブロックを１つの大きなブロックとして考え，各大きなブロックを ECB モードで暗号化する． 上記「shuffle」では，$98^2$個の大きなブロックごとにシャッフルする．