先週に卒研発表があり、無事に終わりました。来年度からは別の研究テーマ、というより、分野を暗号から違うものにするため、このようにやったことや考えたことをまとめようと思います。
今回は、私の研究した暗号である、”Chacha”についてです。
目次
1.暗号とは
暗号は主に、ブロック暗号とストリーム暗号があります。 もちろん、ハッシュ型暗号(例:SHA-3)など他にもありますが、大きく分けてこの2つで良いと思います。
共通鍵ブロック暗号とは？
ブロック暗号では、平文をあるビットの長さで区切りブロックとし、そのブロックと鍵生成部から生成した段鍵をデータ撹拌部に入力して、暗号文を作り出します。(図1参照)
復号の場合は、その暗号文と段鍵から平文を復号化します。
特徴としては、平文があるビットの長さに到達するまで暗号化が行われないことにあります。
図1における緑色の部分が公開情報、青色の部分が秘密情報になります。
※図1は研究室の発表スライドから引用しました。
ストリーム暗号とは
ストリーム暗号は、共通鍵暗号の一種でありますが、共通鍵ブロック暗号と違って、平文があるビットの長さになるまで待つ必要がありません。
暗号化手順は以下の通りです。
1.鍵と初期値を疑似乱数生成器に入力し、疑似乱数列を得る。
2.平文と疑似乱数列の排他的論理和を取る。結果が暗号文。
復号化の場合はその逆を行います。
※図2は研究室の発表スライドから引用しました。
2.Chachaとは？
ストリーム暗号Chachaとは、2007年にDaniel J. Bernsteinによって発表されたSalsa20の派生の暗号です。現在、Googleが提唱している新しい共通鍵暗号方式、ChaCha20-Poly1305に用いられています。
ChachaとSalsa20の違いは、初期状態とDouble-Roundsと呼ばれる関数の変数です。
初期状態
Chachaの初期状態ですが、wikipediaに書いてあるのは、以下の図になります。
1ブロック32bitsで、全体で512bitsあります。各ブロックの意味は以下の通りです。
- Cons:定数。4wordsで”expand 32-byte k”を代入する。
- Key:秘密鍵。鍵長は256bits。
- Pos:ストリーム位置。平文が512bitsを超える毎に1加算される。
- Nonce:ワンタイムパスワードのようなもの。任意に定める。
Keyに関して、128bitsの鍵長もあるようですが、256bitsを使えと書かれているので無視しています。また、128bitsの場合の初期状態への代入の仕方は謎です。
さて、提案者論文には次のように書かれています。
図3と図4の違いは4行目にあります。図3では2wordsがストリーム位置、2wordsがNonceとなっています。しかし、図4では4wordsは全てInputになっています。このInputは次のように書かれています。
The key words are simply copied in order; the input words are the block counter followed by the nonce; the constants are the same as in Salsa20.
http://cr.yp.to/chacha/chacha-20080128.pdf
ブロックカウントとNonceの位置関係のみで、words数の指定はありません。そのため、RFCにおいては次のように初期状態を定めています。
ストリーム位置は1wordsのみ、Nonceが3wordsです。
では、図3はどこから来たのかですが、 New Features of Latin Dances:Analysis of Salsa, ChaCha, and RumbaのChachaの初期状態には次のように書かれています。
tはブロックカウント、vはNonceです。つまり、図3がオリジナルです。
Note also that the original ChaCha had a 64-bit nonce and 64-bit block count.
https://tools.ietf.org/html/rfc7539
しかし、次の理由で図5となったようです。
This limits the use of a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that is enough for most uses. In cases where a single key is used by multiple senders, it is important to make sure that they don’t use the same nonces.
This can be assured by partitioning the nonce space so that the first 32 bits are unique per sender, while the other 64 bits come from a counter.
ps://tools.ietf.org/html/rfc7539
ブロックカウントに64bitを割くと256GBまで対応できるが、それは十分すぎる。そのため、Nonceを3wordsとすることで安全性を高めたらしいです。
どれぐらい安全性が高まったかはわかりません。理由についてはここに書いてあるらしいです。
今回私が用いたのはオリジナル(図3の方)になります。
ブロックカウントについて
ここの項目ではゼミで指摘された部分になります。
指摘された内容は「平文512bitsを超えるとブロックカウントを加算するが、その時keyやnonceはどうするのか？」というものでした。
これについては、次のようにありました。
Each block is an independent hash of the key, the nonce, and a 64-bit block number; there is no chaining from one block to the next.
http://cr.yp.to/snuffle/salsafamily-20071225.pdf
それぞれのブロック毎に独立したkey、nonce、ブロックナンバーを用いて、それぞれは次のブロックと関係を持たないようにすべき、ということだと思います。
こちらはSalsa20の論文に書かれていた文面ですがChachaでこの部分が変わっているとは思わないので、Chachaでもこのようにしました。
しかし、調べていると、RFCの方ではTest Vectorがこれと逆らったような演算をしていました。
RFC 7539の2.4.2におけるTest Vectorでは、平文が512bitsを超えているのでブロックカウントが動くはずです。その時、keyとnonceを変えるのであればそのkeyとnonceも明記されているはずですし、実際私の組んだコードでTest VectorのkeyとNonceを入れて出してみたところ、keyとNonceを一定にさせた場合、Key streamと一致しました。
これについては結局よくわかっていません。なにか見落としているのだと思いますが、今は”わからなかった”ということで区切らせてもらいます。
今回の研究では、ブロック毎にKeyとNonceを変える方でやりました。
1/4ラウンド関数
Salsaファミリーの演算の中心が1/4ラウンド関数です。内部状態(State)から4つの値を取り出し、以下の演算を行います。
これを図にしたものが図8です。
これをChachaでは次のように行います。
1/4ラウンド関数を8回行っているので、この一連の操作は2ラウンドとなります。Chachaでは20ラウンド演算を行うため、この一連の操作を10回行うことになります。
暗号化手順
Chachaにおける暗号化手順は以下のとおりです。
- 初期状態をセットアップする
- 20ラウンド撹拌を行い、Key streamを作る
- 初期状態とKey streamを加算する
3.Chachaの実装
GitHubなどに様々な実装が載っています。しかし、私は自分で実装しました。参考にしたコードは以下のとおりです。
[blogcard url=” https://asecuritysite.com/encryption/chacha”]
そして書いたコードは以下の通り。
RFC 7539 のTeat Vectorは全部通ってるので正しいはずです。
以上、ストリーム暗号Chachaの紹介でした。