はじめに（Introduction）
とある発表を読んでいたところ、SHA3のSHAKEアルゴリズムを使うということで、以前実装したSHA3の見直していたところテストが不十分なのでNISTが出している暗号アルゴリズム検証プログラム（Cryptographic Algorithm Validation Program CAVP）を試してみたところモンテカルロテストで躓いたので記事にしてみました。
Cryptographic Algorithm Validation Program (CAVP)
6.3.3 The Pseudorandomly Generated Messages (Monte Carlo) Test
原文
> The SHA3VS tests the correctness of output data generated from pseudorandomly generated messages. The SHA3VS provides an initial message, Seed, which is processed by the SHAKE algorithm to generate output. Each Monte Carlo test generates 100,000 outputs. 100 of the 100,000 outputs, every 1,000th output, is recorded as checkpoints to the operation of the SHAKE generator. The IUT uses the same procedure to generate the same 100,000 outputs and 100 checkpoint values. The SHA3VS compares each of the recorded 100 outputs with those generated by the IUT.SHA3VS は、疑似ランダムに生成されたメッセージから生成された出力データの正確性をテストします。
SHA3VS は、SHAKE アルゴリズムによって処理されて出力を生成する初期メッセージである Seed を提供します。各モンテ カルロ テストでは 100,000 個の出力が生成されます。
100,000 個の出力のうち 1,000 個ごとに 100 個が SHAKE ジェネレーターの動作のチェックポイントとして記録されます。
IUT は同じ手順を使用して、同じ 100,000 個の出力と 100 個のチェックポイント値を生成します。
SHA3VS は、記録された 100 個の出力のそれぞれを IUT によって生成された出力と比較します。
INPUT: The initial Msg of 128 bits long
Initial Outputlen = (floor(maxoutlen/8) )*8
//makes maxoutlen a multiple of 8 and remains within the range specified.
{
Output0 = Msg;
for (j=0; j<100; j++) {
for (i=1; i<1001; i++) {
Msgi = 128 leftmost bits of Outputi-1;
Outputi = SHAKE(Msgi,Outputlen);
If (i == 1000){
Outputlenj = Outputlen;
}
Rightmost_Output_bits = rightmost 16 bits of Outputi;
Range = (maxoutbytes – minoutbytes + 1);
Outputlen = minoutbytes + (Rightmost_Output_bits mod Range);
}
Outputj = Output1000;
OUTPUT: Outputlenj, Outputj
}
}
Figure 2: Code for Generating Pseudorandom Messages
図2: 疑似ランダムメッセージを生成するコード
原文
The procedure used to generate the 100 checkpoint outputs is as follows:
- 100,000 pseudorandom messages are generated. Initially, the message is a 128-bit message, Msg, supplied by the SHA3VS.
For subsequent input messages, the leftmost 128 bits of the previous output is used as input to the SHAKE algorithm.
If the previous output has less than 128 bits, then zeros are concatenated to the end of the bits of output.- The minoutlen is the minimum length (in bits) tested for the output value.
The maxoutlen is the maximum length in (bits) tested for the output value.
The Monte Carlo test operates on byte-oriented data so these values are rounded to the nearest multiple of 8 bits while staying within the specified range.
minoutbytes is the minoutlen rounded up to the nearest multiple of 8.
maxoutbytes is the maxoutlen rounded down to the nearest multiple of 8. (Note by rounding the minoutlen up and the maxoutlen down, the values stay within the range to be tested as specified by the IUT.) (Note2: If minoutlen = maxoutlen and if the value is a multiple of 8, that value is used as the length for all rounds.
If the value is NOT a multiple of 8, a message appears instructing the lab to contact the CAVP for guidance on this special case.)- Initially the output length is maxoutbytes. Subsequently, the rightmost 16 bits of the output is used in the calculation of the next iterations output length.
Let Rightmost_Output_bits = rightmost 16 bits of output interpreted as an integer.
Let Range (in bytes) = (maxoutbytes – minoutbytes + 1).
The next output length (in bytes) = minoutbytes + (Rightmost_Output_bits mod Range).
For example, let the minoutbytes be 2 bytes (16 bits), the maxoutbytes be 8192 bytes (2^16 = 65536 bits) and the 16 Rightmost_Output_bits = C596 (in hexadecimal).
The initial output length is 8192 bytes (65536 bits).
The Rightmost_Output_bits = int (C596) = 50582, Range = 8192 - 2 + 1 = 8191 bytes, and Outputlen = 2 + (50582 mod 8191) = 1438 bytes.
This is the new output length in bytes; and- After every 1,000 outputs, a sample is taken and is provided as a checkpoint.
These checkpoints are denoted Output0 in Figure 2.
100 個のチェックポイント出力を生成するために使用される手順は次のとおりです。
- 100,000 個の疑似ランダム メッセージが生成されます。最初のメッセージは、SHA3VS によって提供される 128 ビット メッセージ (Msg) です。
後続の入力メッセージでは、前の出力の左端の 128 ビットが SHAKE アルゴリズムの入力として使用されます。
前の出力が 128 ビット未満の場合、出力のビットの末尾にゼロが連結されます。 - minoutlen は、出力値に対してテストされる最小の長さ (ビット単位) です。
maxoutlen は、出力値に対してテストされる最大の長さ (ビット単位) です。
モンテカルロ テストはバイト指向のデータに対して実行されるため、これらの値は指定された範囲内にとどまりながら、最も近い 8 ビットの倍数に丸められます。
minoutbytes は、最も近い 8 の倍数に切り上げられた minoutlen です。
maxoutbytes は、最も近い 8 の倍数に切り下げられた maxoutlen です。(minoutlen を切り上げ、maxoutlen を切り下げることで、値は IUT によって指定されたテスト対象範囲内にとどまることに注意してください。) (注 2: minoutlen = maxoutlen で、値が 8 の倍数の場合、その値がすべてのラウンドの長さとして使用されます。
値が 8 の倍数でない場合は、この特別なケースに関するガイダンスについて CAVP に連絡するようラボに指示するメッセージが表示されます。) - 初期出力長は maxoutbytes です。その後、出力の右端の 16 ビットが次の反復出力長の計算に使用されます。
Rightmost_Output_bits = 出力の右端の 16 ビットを整数として解釈します。
Range (バイト単位) = (maxoutbytes – minoutbytes + 1) とします。
次の出力長 (バイト単位) = minoutbytes + (Rightmost_Output_bits mod Range)。
たとえば、minoutbytes を 2 バイト (16 ビット)、maxoutbytes を 8192 バイト (2^16 = 65536 ビット)、16 Rightmost_Output_bits = C596 (16 進数) とします。
初期出力長は 8192 バイト (65536 ビット) です。
Rightmost_Output_bits = int (C596) = 50582、Range = 8192 - 2 + 1 = 8191 バイト、Outputlen = 2 + (50582 mod 8191) = 1438 バイト。
これはバイト単位の新しい出力長です。 - 1,000 出力ごとにサンプルが取得され、チェックポイントとして提供されます。
これらのチェックポイントは、図 2 では Output0 として示されています。
実装
コードイメージと手順（１~４）からコードを作成します。
function monte(SHAKE, initialMsg, minoutlen, maxoutlen) {
// INPUT: The initial Msg of 128 bits long
// Initial Outputlen = (floor(maxoutlen/8) )*8
let Outputlen = (Math.floor(maxoutlen / 8));
// //makes maxoutlen a multiple of 8 and remains within the range specified.
const minoutbytes = (Math.floor(minoutlen / 8));
const maxoutbytes = (Math.floor(maxoutlen / 8));
// {
let Output = new Array(1001);
let Outputlenj = null;
let Outputj = null;
let Msg = new Array(1001);
// Output0 = Msg;
Output[0] = hex2bs(initialMsg);
// for (j=0; j<100; j++) {
for (let j = 0; j < 100; j++) {
// for (i=1; i<1001; i++) {
for (let i = 1; i < 1001; i++) {
// Msgi = 128 leftmost bits of Outputi-1;
Msg[i] = Output[i - 1].slice(0, 128 / 8);
while (Msg[i].length < 128 / 8) {
Msg[i].push(0);
}
// Outputi = SHAKE(Msgi,Outputlen);
Output[i] = hex2bs(SHAKE(Msg[i], Outputlen * 8));
// If (i == 1000){
if (i == 1000) {
// Outputlenj = Outputlen;
Outputlenj = Outputlen;
}
// }
// Rightmost_Output_bits = rightmost 16 bits of Outputi;
let Rightmost_Output_bits = Output[i][Output[i].length - 2] * 256 + Output[i][Output[i].length - 1];
// Range = (maxoutbytes – minoutbytes + 1);
let Range = (maxoutbytes - minoutbytes + 1);
// Outputlen = minoutbytes + (Rightmost_Output_bits mod Range);
Outputlen = minoutbytes + (Rightmost_Output_bits % Range);
}
// }
// Outputj = Output1000;
Outputj = Output[1000];
// OUTPUT: Outputlenj, Outputj
console.log(j, Outputlenj * 8, bs2hex(Outputj));
Output[0] = Output[1000];
}
// }
// }
}
コードイメージに書いて無い部分を説明します。
const minoutbytes = (Math.floor(minoutlen / 8));
const maxoutbytes = (Math.floor(maxoutlen / 8));
minoutbytes は、最も近い 8 の倍数に切り上げられた minoutlen です。
maxoutbytes は、最も近い 8 の倍数に切り下げられた maxoutlen です。
後半で使用する値を計算しています。
手順２に記載されていますが、ループに入る前で計算しています。
// Msgi = 128 leftmost bits of Outputi-1;
Msg[i] = Output[i - 1].slice(0, 128 / 8);
while (Msg[i].length < 128 / 8) {
Msg[i].push(0);
}
前の出力が 128 ビット未満の場合、出力のビットの末尾にゼロが連結されます。
手順１にあるメッセージのデータ長が128ビット（16バイト）未満の場合に128ビット（16バイト）になるようにゼロを連結させます。
Output[0] = Output[1000];
チェックポイントを次のチェックポイントの最初のアウトプットとして使用します。
まとめ（Conclusion）
モンテカルロ法はテストデータによって計算方法が異なります。
各テストデータの計算方法について調べる必要があります。
今回はCAVPのテストデータを使用して作成してみました。
実際に動かしたところ全て正常となりSHAKEの実装はたぶん正しいと考えられます。
ソースコードはGithubにあります。