SHA-256の回路を設計してみる
背景
新年ですね。
去年からの流れで、もう少し複雑な半導体の回路を設計してみよう。
SHA-256がテーマとしては、良いのではないだろうか？
SHA-256とは
SHA-256は、データを固定長の文字列（ハッシュ）に変換する仕組みで、特定のデータがハッシュに対応するため、改ざんを防ぐ重要な役割を果たします。たとえば、パスワード管理やデジタル署名で利用されます。ビットコインとの関係では、SHA-256はトランザクションデータを安全にまとめるために使われています。マイニングでは膨大な計算を通じて特定の条件を満たすハッシュ値を探し当てることで、新しいビットコインを得る仕組みになっています。SHA-256はこのプロセスの要であり、ビットコインの安全性と信頼性を支える技術の一つです。
SHA-256で変換すると、一文字ごとにSHA-256の出力結果が変わってきます。どこで改ざんしたか分かるわけですね。
ですが、SHA-256には欠点があって、例えば「password」という値をいれ、SHA256 でハッシュ化すると 「5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8」 という値に必ずなります。
エニグマ暗号と同じ欠点があるわけですね（笑）
ですが「password」のどこか一文字でも変えると、まったく異なるSHA256のハッシュ値になります。ここがエニグマ暗号とは異なるところ。
今のビットコインでは2回、SHA256の暗号化を二重に通してるそうです。
SHA-256のアルゴリズム
簡易な説明では下記。
1. SHA-256 アルゴリズムメッセージの準備
ハッシュ化したいデータ（メッセージ）を取得します。
2. パディング
メッセージの末尾に 0x80 を追加します。
メッセージの長さを 512 ビット（64 バイト）の倍数になるように 0x00 を追加します。
元のメッセージのビット長を 64 ビットのデータとして付加します。
3. 初期ハッシュ値を設定
定められた 8 個の初期値（32 ビットずつ）を使用してハッシュ値を初期化します。
4. メッセージをブロックに分割
メッセージを 512 ビット（64 バイト）ごとに分割します。
5. メッセージスケジュールを生成
各ブロックから 64 個の 32 ビットデータを計算します。
6. ハッシュ値の初期化
初期ハッシュ値を作業用の 8 個の変数にコピーします。
7. 圧縮関数を実行
64 ラウンドのループを実行して作業変数を更新します。
8. ハッシュ値の更新
ラウンド計算後の結果を初期ハッシュ値に加算して更新します。
9. すべてのブロックを処理
各ブロックに対して圧縮関数を繰り返します。
10. 最終的なハッシュ値を取得
8 個の 32 ビットハッシュ値を連結し、256 ビットのハッシュ値を得ます。
Rustでコーディングすると
ここから
Rustのコードは
コード
// Main function
fn main() {
println!("{}", digest_to_hex(&sha256(b"hello")));
println!("{}", digest_to_hex(&sha256(b"world")));
println!("{}", digest_to_hex(&sha256(b"cat")));
println!("{}", digest_to_hex(&sha256(b"dog")));
println!("{}", digest_to_hex(&sha256(b"password")));
}
// Array of round constants (initial values)
const K: [u32; 64] = [
0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5,
0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3,
0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC,
0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7,
0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13,
0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3,
0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5,
0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208,
0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2,
];
// Initial hash values (IV)
const H0: [u32; 8] = [
0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19,
];
// Main SHA-256 function
fn sha256(input: &[u8]) -> [u8; 32] {
// Define necessary helper functions as closures
let rotr = |x: u32, n: u32| -> u32 { (x >> n) | (x << (32 - n)) }; // Right rotate
let small_sigma0 = |x: u32| -> u32 { rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3) };
let small_sigma1 = |x: u32| -> u32 { rotr(x, 17) ^ rotr(x, 19) ^ (x >> 10) };
let big_sigma0 = |x: u32| -> u32 { rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22) };
let big_sigma1 = |x: u32| -> u32 { rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25) };
let ch = |x: u32, y: u32, z: u32| -> u32 { (x & y) ^ ((!x) & z) };
let maj = |x: u32, y: u32, z: u32| -> u32 { (x & y) ^ (x & z) ^ (y & z)};
// Padding process
let bit_len = (input.len() as u64) * 8; // Bit length
// Add one byte of 0x80 to the message
let mut padded = input.to_vec();
padded.push(0x80);
// Align to 512-bit (64-byte) block minus 8 bytes (bit length) minus 1 byte (0x80)
while (padded.len() % 64) != 56 {
padded.push(0x00);
}
// Append message bit length in 64-bit big-endian format
padded.extend_from_slice(&bit_len.to_be_bytes());
// Divide message into blocks
let block_count = padded.len() / 64;
// Initialize hash value (copy H0)
let mut state = H0;
// Apply compression function for each block
for i in 0..block_count {
// Extract a 512-bit (64-byte) block
let block = &padded[i * 64..(i + 1) * 64];
let mut w = [0u32; 64];
// Expand the first 16 words
for j in 0..16 {
w[j] = u32::from_be_bytes([
block[j * 4],
block[j * 4 + 1],
block[j * 4 + 2],
block[j * 4 + 3]]);
}
// Calculate the remaining 48 words (from w[16] to w[63])
for j in 16..64 {
w[j] = small_sigma1(w[j - 2])
.wrapping_add(w[j - 7])
.wrapping_add(small_sigma0(w[j - 15]))
.wrapping_add(w[j - 16]);
}
// Copy the current state into working variables a, b, c, d, e, f, g, h
let (mut a, mut b, mut c, mut d, mut e, mut f, mut g, mut h) = (
state[0], state[1], state[2], state[3],
state[4],state[5], state[6], state[7]);
// 64 rounds of compression
for j in 0..64 {
let temp1 = h
.wrapping_add(big_sigma1(e))
.wrapping_add(ch(e, f, g))
.wrapping_add(K[j])
.wrapping_add(w[j]);
let temp2 = big_sigma0(a).wrapping_add(maj(a, b, c));
h = g;
g = f;
f = e;
e = d.wrapping_add(temp1);
d = c;
c = b;
b = a;
a = temp1.wrapping_add(temp2);
}
// Add the calculated result to the current state
state[0] = state[0].wrapping_add(a);
state[1] = state[1].wrapping_add(b);
state[2] = state[2].wrapping_add(c);
state[3] = state[3].wrapping_add(d);
state[4] = state[4].wrapping_add(e);
state[5] = state[5].wrapping_add(f);
state[6] = state[6].wrapping_add(g);
state[7] = state[7].wrapping_add(h);
}
// Convert state to byte array
let mut hash = [0u8; 32];
for (i, val) in state.iter().enumerate() {
hash[i * 4..i * 4 + 4].copy_from_slice(&val.to_be_bytes());
}
hash
}
// Convert byte array to hexadecimal string
fn digest_to_hex(digest: &[u8; 32]) -> String {
let mut hex_string = String::new();
for &byte in digest {
hex_string.push_str(&format!("{:02x}", byte));
}
hex_string
}
実行結果
haruhiko@haruhiko-Default-string:~/Program/sha256$ cargo run
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.00s
Running `target/debug/sha256`
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
486ea46224d1bb4fb680f34f7c9ad96a8f24ec88be73ea8e5a6c65260e9cb8a7
77af778b51abd4a3c51c5ddd97204a9c3ae614ebccb75a606c3b6865aed6744e
cd6357efdd966de8c0cb2f876cc89ec74ce35f0968e11743987084bd42fb8944
5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
haruhiko@haruhiko-Default-string:~/Program/sha256$
dslxに変換すると
最初は自分で必死にコーディングしてましたが、実は
google dslxのgithubにサンプルがすでにありました。
コード
// Copyright 2020 The XLS Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
import std;
// ---
//
// SHA algorithm based on the description in:
//
// https://en.wikipedia.org/wiki/SHA-2#Pseudocode
//
// We attempt to mirror the pseudocode presented there fairly directly for ease
// of reproducing correct results.
pub type Digest = (u32, u32, u32, u32, u32, u32, u32, u32);
fn sha256_chunk_w_table(chunk: bits[512]) -> u32[64] {
// Seed the "w" table with the message chunk.
let w_init: u32[64] = (chunk ++ bits[1536]:0) as u32[64];
// Build up the remaining values of the "w" table.
// TODO(b/149962183): Make range go from 16 - 64 once counted for
// ranges can start at values other than 0.
let w: u32[64] = for (i, w): (u32, u32[64]) in range(u32:0, u32:48) {
let w_im15: u32 = w[i + u32:16 - u32:15];
let s_0: u32 = std::rotr(w_im15, u32:7) ^ std::rotr(w_im15, u32:18) ^ (w_im15 >> u32:3);
let w_im2: u32 = w[i + u32:16 - u32:2];
let s_1: u32 = std::rotr(w_im2, u32:17) ^ std::rotr(w_im2, u32:19) ^ (w_im2 >> u32:10);
let value: u32 = w[i + u32:16 - u32:16] + s_0 + w[i + u32:16 - u32:7] + s_1;
update(w, i + u32:16, value)
}(w_init);
w
}
// Evolves the digest for a single chunk in the overall message being
// SHA256-hashed.
fn sha256_chunk(chunk: bits[512], digest_init: Digest) -> Digest {
let w: u32[64] = sha256_chunk_w_table(chunk);
// The constant "K" table of addends.
const K = u32[64]:[
u32:0x428a2f98, u32:0x71374491, u32:0xb5c0fbcf, u32:0xe9b5dba5, u32:0x3956c25b,
u32:0x59f111f1, u32:0x923f82a4, u32:0xab1c5ed5, u32:0xd807aa98, u32:0x12835b01,
u32:0x243185be, u32:0x550c7dc3, u32:0x72be5d74, u32:0x80deb1fe, u32:0x9bdc06a7,
u32:0xc19bf174, u32:0xe49b69c1, u32:0xefbe4786, u32:0x0fc19dc6, u32:0x240ca1cc,
u32:0x2de92c6f, u32:0x4a7484aa, u32:0x5cb0a9dc, u32:0x76f988da, u32:0x983e5152,
u32:0xa831c66d, u32:0xb00327c8, u32:0xbf597fc7, u32:0xc6e00bf3, u32:0xd5a79147,
u32:0x06ca6351, u32:0x14292967, u32:0x27b70a85, u32:0x2e1b2138, u32:0x4d2c6dfc,
u32:0x53380d13, u32:0x650a7354, u32:0x766a0abb, u32:0x81c2c92e, u32:0x92722c85,
u32:0xa2bfe8a1, u32:0xa81a664b, u32:0xc24b8b70, u32:0xc76c51a3, u32:0xd192e819,
u32:0xd6990624, u32:0xf40e3585, u32:0x106aa070, u32:0x19a4c116, u32:0x1e376c08,
u32:0x2748774c, u32:0x34b0bcb5, u32:0x391c0cb3, u32:0x4ed8aa4a, u32:0x5b9cca4f,
u32:0x682e6ff3, u32:0x748f82ee, u32:0x78a5636f, u32:0x84c87814, u32:0x8cc70208,
u32:0x90befffa, u32:0xa4506ceb, u32:0xbef9a3f7, u32:0xc67178f2,
];
// Compute the digest using the "w" table over 64 "rounds".
let (a, b, c, d, e, f, g, h): Digest = for (i, (a, b, c, d, e, f, g, h)): (u32, Digest) in
range(u32:0, u32:64) {
let S1 = std::rotr(e, u32:6) ^ std::rotr(e, u32:11) ^ std::rotr(e, u32:25);
let ch = (e & f) ^ ((!e) & g);
let temp1 = h + S1 + ch + K[i] + w[i];
let S0 = std::rotr(a, u32:2) ^ std::rotr(a, u32:13) ^ std::rotr(a, u32:22);
let maj = (a & b) ^ (a & c) ^ (b & c);
let temp2 = S0 + maj;
let (h, g, f) = (g, f, e);
let e = d + temp1;
let (d, c, b) = (c, b, a);
let a = temp1 + temp2;
(a, b, c, d, e, f, g, h)
}(digest_init);
// The new digest mixes together values from the original digest with the
// derived values (a, b, c, ...) we've computed.
let (h0, h1, h2, h3, h4, h5, h6, h7): Digest = digest_init;
(h0 + a, h1 + b, h2 + c, h3 + d, h4 + e, h5 + f, h6 + g, h7 + h)
}
// Returns the number of bits required to add on to turn bit_count into a
// multiple of 512.
fn compute_pad_bits(bit_count: u32) -> u32 {
std::round_up_to_nearest(bit_count, u32:512) - bit_count
}
#[test]
fn sha256_abc_test() {
let message = u8[3]:['a', 'b', 'c'];
let chunk = pad_to_512b_chunk(message as u24);
let digest: Digest = sha256(chunk);
assert_eq(
(
u32:0xba7816bf, u32:0x8f01cfea, u32:0x414140de, u32:0x5dae2223, u32:0xb00361a3,
u32:0x96177a9c, u32:0xb410ff61, u32:0xf20015ad,
), digest)
}
（中略）
#[test]
fn sha256_password_test() {
let message = u8[8]:['p', 'a', 's', 's', 'w', 'o', 'r', 'd'];
let chunk = pad_to_512b_chunk(message as u64);
let digest: Digest = sha256(chunk);
trace!(digest);
assert_eq(
(
u32:0x5e884898, u32:0xda280471, u32:0x51d0e56f, u32:0x8dc62927, u32:0x73603d0d,
u32:0x6aabbdd6, u32:0x2a11ef72, u32:0x1d1542d8,
), digest)
}実行結果
googleのコードから少し書き換えたのですが基本は同じコードです。
haruhiko@haruhiko-Default-string:~/Program/GoogleXLS_test-main/sha256$ make interpret
/home/haruhiko/xls/bazel-bin/xls/dslx/interpreter_main --alsologtostderr sha256_google_ref.x
[ RUN UNITTEST ] compute_pad_bits_test
[ OK ]
[ RUN UNITTEST ] sha256_empty_payload_test
[ OK ]
[ RUN UNITTEST ] sha256_abc_test
I0102 02:25:53.532306 10458 sha256_google_ref.x:151] trace of digest: (3128432319, 2399260650, 1094795486, 1571693091, 2953011619, 2518121116, 3021012833, 4060091821)
[ OK ]
[ RUN UNITTEST ] sha256_password_test
I0102 02:25:53.671240 10458 sha256_google_ref.x:165] trace of digest: (1585989784, 3660055665, 1372644719, 2378574119, 1935686925, 1789640150, 705818482, 487932632)
[ OK ]
[===============] 4 test(s) ran; 0 failed; 0 skipped.trace of digest: (1585989784, 3660055665, 1372644719, 2378574119, 1935686925, 1789640150, 705818482, 487932632)
これは10進数ですので、
password = 「5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8」
とあってます。
Verilogに変換すると
--pipeline_stages=4
module sha256(
input wire clk,
input wire [511:0] message,
output wire [255:0] out
);
// ===== Pipe stage 0:
// Registers for pipe stage 0:
reg [511:0] p0_message;
always @ (posedge clk) begin
p0_message <= message;
end
// ===== Pipe stage 1:
wire [28:0] p1_add_54191_comb;
wire [30:0] p1_add_54195_comb;
（以下略）
考察
let (a, b, c, d, e, f, g, h): Digest = for (i, (a, b, c, d, e, f, g, h)): (u32, Digest) in
range(u32:0, u32:64) {
ここで64回まわすループを回してますので、
Verilogに変換するときはpipeline=2とか4とか
変換結果も見ましたが、無理がある設計ではないのでしょうか。
素数の計算のdslx設計のように無理がある。
あとは、
cocotbで検証します。
Verilogを検証してみた
verilogコード生成は
codegen: optimize
$(CODEGEN_MAIN) \
--module_name=$(TOP) \
--multi_proc \
--pipeline_stages=36 \
--delay_model=unit \
--use_system_verilog=false \
$(OPT_IR_FILE) > $(OUTPUT_FILE)として変換
--pipeline_stages=36 です。
1CLKごとに結果が出力されるように。
回路規模は考慮しないことにします。
実は、procを使って最初に48CLK回して初期パラメーターを計算して、次に64CLK回して計算する
proc sub_sha256_proc と、
proc sha256_proc
を設計したのですが、それでは「CPU」を使って計算するのと大差ない。ので止めました。
パイプライン＝36とします。
cocotbでの検証
結果は
(cocotb_env) haruhiko@haruhiko-Default-string:~/Program/GoogleXLS_test-main/sha256$ make simulate
iverilog -o sim.vvp -D COCOTB_SIM=1 -g2012 sha256.v
MODULE=sha256_testbench TOPLEVEL=sha256 TOPLEVEL_LANG=verilog \
SIM=icarus vvp -M /home/haruhiko/Program/GoogleXLS_test-main/sha256/cocotb_env/lib/python3.12/site-packages/cocotb/libs \
-m libcocotbvpi_icarus sim.vvp
-.--ns INFO gpi ..mbed/gpi_embed.cpp:108 in set_program_name_in_venv Using Python virtual environment interpreter at /home/haruhiko/Program/GoogleXLS_test-main/sha256/cocotb_env/bin/python
-.--ns INFO gpi ../gpi/GpiCommon.cpp:101 in gpi_print_registered_impl VPI registered
0.00ns INFO cocotb Running on Icarus Verilog version 12.0 (stable)
0.00ns INFO cocotb Running tests with cocotb v1.9.2 from /home/haruhiko/Program/GoogleXLS_test-main/sha256/cocotb_env/lib/python3.12/site-packages/cocotb
0.00ns INFO cocotb Seeding Python random module with 1735938243
0.00ns INFO cocotb.regression pytest not found, install it to enable better AssertionError messages
0.00ns INFO cocotb.regression Found test sha256_testbench.test_sha256
0.00ns INFO cocotb.regression running test_sha256 (1/1)
Test the sha256 module.
0.00ns INFO cocotb.sha256 Starting test for SHA256 module
5.00ns INFO cocotb.sha256 Input Bits Padded (Calculated):
High: 0x6162638000000000000000000000000000000000000000000000000000000000
Low: 0x0000000000000000000000000000000000000000000000000000000000000018
5.00ns INFO cocotb.sha256 Expected Input Bits Padded:
High: 0x6162638000000000000000000000000000000000000000000000000000000000
Low: 0x0000000000000000000000000000000000000000000000000000000000000018
5.00ns INFO cocotb.sha256 Input bits padded correctly!
375.00ns INFO cocotb.sha256 Cycle 37: DUT Output Hash: da5698be17b9b46962335799779fbeca8ce5d491c0d26243bafef9ea1837a9d8
385.00ns INFO cocotb.sha256 Cycle 38: DUT Output Hash: ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
385.00ns INFO cocotb.sha256 Test passed! Output hash matches expected value.
385.00ns INFO cocotb.regression test_sha256 passed
385.00ns INFO cocotb.regression **************************************************************************************
** TEST STATUS SIM TIME (ns) REAL TIME (s) RATIO (ns/s) **
**************************************************************************************
** sha256_testbench.test_sha256 PASS 385.00 0.02 19489.61 **
**************************************************************************************
** TESTS=1 PASS=1 FAIL=0 SKIP=0 385.00 0.02 16904.06 **
**************************************************************************************
38クロック後の
385.00ns INFO cocotb.sha256 Cycle 38: DUT Output Hash: ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
rustコードでの、"abc"のsha256の結果は、
Running `target/debug/sha256`
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
→合ってます！
FPGAで合成してみた
ミニPCで待つこと15分
結果は下記。
20MHzで動作可能なようです！
リソース25%使用。。
所感
同じハッシュ値を出力する入力データが存在するのでは？と思いましたが、同じハッシュ値を出力する入力データを発見するのは非常に困難とのことです。とはいえ、CRC32とは異なる目的の処理みたいですね。
現実的な可能性：衝突耐性衝突の難しさ
SHA-256 は設計上、異なる入力データが同じハッシュ値を生成する（衝突する）確率を極めて低くしています。
誕生日のパラドックスにより、衝突を見つけるには 平均 21282^{128}2128 回 の計算が必要とされます。
計算量の現実的な制約
現代の計算機リソースをもってしても 21282^{128}2128 通りのハッシュを試すことは非現実的です。
現在のところ、SHA-256 の衝突を見つけたという報告はありません。
（年越し蕎麦を茹でる時間ですよね・・・）
→茹でるの失敗しました。。
1/3の所感
これで、このNoteは完成とします。
旅行先でGoogle dslxをインストールして一ヶ月。
SHA-256の暗号は解読できないのだろうか？
それが可能なら、ビットコインや全てのネットセキュリティが終わるわけですが、
無いよね？