Mặc dù SHA-2 vẫn đang an toàn, nhưng do SHA-2 sử dụng chung cấu trúc Merkle-Damgård với các giải thuật đã bị bẻ
gãy như SHA-1 và MD5 nên đã đặt ra yêu cầu cấp thiết về một phương án dự phòng chiến lược. Vào năm 2007 Viện
Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) khởi xướng cuộc thi thiết kế hàm băm công khai nhằm tìm kiếm một
tiêu chuẩn mới có cấu trúc khác biệt hoàn toàn với các thế hệ trước. Sau nhiều vòng đánh giá khắt khe, thuật
toán Keccak đã được lựa chọn và chính thức chuẩn hóa thành SHA-3 (Secure Hash Algorithm 3) theo tiêu chuẩn FIPS
PUB 202 vào năm 2015.
SHA-3 bao gồm 6 phiên bản:
SHA-3 với độ dài đầu ra cố định: gồm SHA3-224, SHA3-256, SHA3-384, SHA3-512. Các chỉ số phiên
bản trên tương ứng với độ dài bit đầu ra. Ví dụ, SHA3-256 tạo ra mã băm 256 bit.
SHA-3 với độ dài đầu ra tùy chỉnh: gọi là
Extendable-Output Functions (XOFs), gồm SHAKE128 và SHAKE256.
State là mảng 3 chiều làm bộ nhớ tạm trong quá trình tính toán. Giá trị khởi tạo ban đầu đều bằng 0. State gồm 2
phần: Rate (r) và Capacity (c).
Rate (r) là phần State có thể tương tác trực tiếp với input.
Capacity (c) là phần State nội bộ, không tiếp xúc trực tiếp với input.
Trong SHA-3, tổng r + c luôn bằng 1600 bit.
Bảng giá trị r, c, d của SHA-3
SHA-3 variant
r (rate)
c (capacity)
d (số bit độ dài đầu ra)
sha3-224
1152 bits
448 bits
224 bits
sha3-256
1088 bits
512 bits
256 bits
sha3-384
832 bits
768 bits
384 bits
sha3-512
576 bits
1024 bits
512 bits
shake128
1344 bits
256 bits
tùy ý
shake256
1088 bits
512 bits
tùy ý
Hình mô tả các thành phần của state
Lưu ý: State được biểu diễn theo hệ tọa độ tâm (-2,-1,0,1,2 mod 5 → 3,4,0,1,2). Thứ tự ánh xạ bit vào State được
thực hiện theo trình tự ưu tiên các trục: z → x → y.
Tuy nhiên, nhằm mục đích minh họa, trong mô phỏng này State sẽ được hiển thị qua 25 lane x 64 slice với khởi tạo
ban đầu như sau:
2. Luồng hoạt động cấu trúc "Bọt biển"
Thuật toán SHA-3 sử dụng một cấu trúc hoàn toàn khác biệt so với các thế hệ SHA trước đó, gọi là cấu trúc "Bọt
biển" (Sponge Construction):
Chia dữ liệu đầu vào thành các block r bit (r1, r2, ..., rn-1); State khởi
tạo đều là 0.
Phần Rate được thực hiện phép XOR với khối r1 đầu tiên.
Rate và Capacity kết hợp lại được đưa qua một function bao gồm nhiều vòng.
r bit đầu tiên của function là Rate và c bit còn lại là Capacity.
Phần Rate được XOR với r2 và kết hợp với Capacity nạp vào một function khác.
Quá trình này được thực hiện cho đến khi không còn khối dữ liệu nào dư lại.
Ở khối dữ liệu cuối cùng, mã băm (hash) được lấy từ r bit đầu ra của function.
Nếu cần thêm các bit đầu ra, phần Rate và Capacity ở trên sẽ được nạp qua function mà không cần nhập thêm bất
kỳ dữ liệu nào để tiếp tục lấy r bit từ đầu ra đến khi đủ.
Mô phỏng trực quan thuật toán SHA-3 theo từng bước
Tôi muốn tính một mã băm
có độ dài bits. Đầu vào sẽ là
.
1. Thu được mảng bit
Thông thường, SHA-3 được định nghĩa là một hàm mà đầu vào và đầu ra là một mảng các bit. Vì đầu vào của chúng
ta là một chuỗi (string), trước tiên chúng ta phải chuyển chuỗi đó thành một mảng bit. Có nhiều bảng mã khác
nhau, nhưng thông dụng nhất là UTF-8. Trước tiên chúng ta lấy các bytes của
từng chữ cái:
Đảo ngược thứ tự các bit trong mỗi byte để chuyển từ cách biểu diễn MSB-first (bit trọng số cao nhất đứng đầu)
sang LSB-first (bit trọng số thấp nhất đứng đầu)
Đầu tiên, hãy chuyển các gặm/nửa byte (nibbles, từ 0-f) và các bit thành dạng nhị phân (binary). Sau đó kết
hợp tất cả lại với nhau.
Lưu ý rằng thông thường các bytes được nối với nhau sao cho các bit LSB của mỗi byte (các bit ngoài cùng bên
phải) lên đầu, nhưng ở đây chúng ta nối phần nibbles theo thứ tự MSB trước, điều này sẽ tạo ra kết quả khác
biệt.
Các tệp (files) giống như một chuỗi các bytes. Đầu tiên, chúng ta lấy tất cả các byte trong tệp và viết chúng
dưới dạng các bit.
Tiếp theo, chúng ta nối các bytes sao cho các bit LSB của mỗi byte (ngoài cùng bên phải) được lên đầu.
Lưu ý rằng việc không thu được bit nào tại thời điểm này là bình thường. Điều này xảy ra khi nhập vào một chuỗi
rỗng hoặc tệp trống.
2. Thêm padding và chia thành các block
Padding là quá trình thêm các bit bổ sung vào mảng bit để mảng bit thỏa mãn một điều kiện nhất định. Đối với
SHA-3, quy trình tổng quát như sau:
bits + (01 hoặc 1111 nếu là SHAKE) +
1 + n số 0 + 1
Số lượng số 0 thêm vào sao cho độ dài của chuỗi trên là bội số của giá trị r
tương ứng phiên bản SHA-3 đã lựa chọn.
Biến thể SHA-3
r (rate)
sha3-224
1152 bits
sha3-256
1088 bits
sha3-384
832 bits
sha3-512
576 bits
shake128
1344 bits
shake256
1088 bits
Để tìm xem cần đặt bao nhiêu số 0, ta tính toán:
length(bits)
+
length(01 or 1111)
+
length(1)
+
length(n zeros)
+
length(1)
=
+
+
1
+
n
+
1
= + n
Bây giờ chúng ta cần tìm số n nhỏ nhất thỏa mãn điều kiện sau:
( + n ) là một bội số của
n = số 0
Sau khi padding hoàn tất, ta thu được một mảng bit có độ dài chia hết cho r = . Tiếp
theo, mảng bit này được chia thành các block có độ dài r bit. Các block được liệt kê dưới đây, các bit padding
sẽ được hiển thị màu xanh lá cây:
3. Giai đoạn “Hấp thụ”
Sau khi padding và chia thành các block, khởi tạo tất cả bit của State đều bằng 0.
Quy trình tổng quát giai đoạn “Hấp thụ” (Absorbing Phase) như sau:
For mỗi input block:
XOR(state, input block)
For 24 vòng:
θ Theta(state)
ρ Rho(state)
π Pi(state)
χ Chi(state)
ι Iota(state, round)
Mẹo: Di chuột lên từng bit trong State kết quả để xem cách bit đó được tính ra.
Khối đầu vào
, bước
.
Chia State thành 2 phần: Rate (r bit đầu tiên) và Capacity (c bit còn lại). Input block ri được XOR
với phần Rate của State. Giữ nguyên phần Capacity.
Input block đầu vào ri:
State trước khi tính toán:
State sau khi tính toán:
Bước θ (theta) đóng vai trò tạo ra sự khuếch tán dữ liệu, đảm bảo một thay đổi nhỏ ở một bit bất kỳ sẽ nhanh
chóng
lan tỏa và ảnh hưởng đến nhiều bit khác trong state.
Cơ chế: Mỗi bit trong state được cập nhật bằng cách XOR với parity (tính chẵn lẻ) của column (x-1, z) và
parity của column (x+1, z-1)
State trước khi tính toán:
State sau khi tính toán:
Bước ρ (rho) đóng vai trò phân tán dữ liệu theo trục lane. Nếu không có bước này, các bit tại cùng một vị trí
z trên các lane khác nhau sẽ không bao giờ thay đổi vị trí tương đối của chúng.
Cơ chế: Mỗi lane tại tọa độ (x, y) được xoay vòng các bit của nó theo trục z với một giá trị dịch chuyển
(offset) cố định được xác định trước tùy theo vị trí của lane đó trong state
. Lượng xoay lần lượt là 0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8,
18, 2, 61, 56, 14.
State trước khi tính toán:
State sau khi tính toán:
Bước π (pi) đóng vai trò xáo trộn vị trí của các lane trong mỗi slice để phá vỡ các cấu trúc tuyến tính và
tăng cường khả năng khuếch tán dữ liệu trên toàn bộ state.
Thứ tự mới của các lane lần lượt là 1, 7, 13, 19, 25, 4, 10, 11,
17, 23, 2, 8, 14, 20, 21, 5, 6, 12, 18, 24, 3, 9, 15, 16, 22. Nghĩa là lane đầu tiên giữ nguyên vị trí, lane
thứ hai trở thành lane thứ 7, và tiếp tục như vậy.
State trước khi tính toán:
State sau khi tính toán:
Bước χ (chi) là bước phi tuyến tính duy nhất trong hàm hoán vị, đóng vai trò tạo ra sự xáo trộn khiến mối quan hệ giữa các bit đầu vào và đầu ra trở nên cực kỳ phức tạp.
Cơ chế: Mỗi bit trong một row được cập nhật bằng cách XOR với (NOT bitx+1 AND bitx+2).
Minh họa: xanh lá XOR (
(not vàng) and đỏ ).
State trước khi tính toán:
State sau khi tính toán:
Bước ι (iota) đóng vai trò phá vỡ tính đối xứng của các vòng lặp bằng cách thêm một hằng số vòng (round constant) khác nhau vào mỗi vòng, ngăn chặn các cuộc tấn công dựa trên tính chất lặp lại.
Cơ chế: XOR một hằng số vòng (Round Constant - RC) vào duy nhất lane tại tọa độ (0,0). Toàn bộ 24 lane còn lại không thay đổi.
Các bit của hằng số vòng như bên dưới. Lưu ý rằng hằng số vòng phụ thuộc vào round hiện tại.
State trước khi tính toán:
State sau khi tính toán:
4. Giai đoạn "Vắt"
Đối với các biến thể không phải shake, giai đoạn vắt khá đơn giản. Đầu tiên, hãy lấy d bit đầu tiên từ State
cuối cùng. Nhóm các bit này thành các byte 8-bit. Các giá trị của d được cho dưới đây:
Biến thể SHA-3
d (đầu ra)
sha3-224
224 bit
sha3-256
256 bit
sha3-384
384 bit
sha3-512
512 bit
State cuối cùng:
5. Xử lý và biểu diễn kết quả đầu ra
Cuối cùng, đảo ngược các bit trong mỗi nhóm 8-bit, sao cho các bit ở ngoài cùng bên trái trở thành bit ở ngoài
cùng bên phải, và ngược lại.
Chúng ta cũng có thể viết nó dưới dạng ký hiệu thập lục phân (hex):
Và đó là kết quả cuối cùng của chúng ta!
4. Giai đoạn "Vắt"
Đối với các biến thể shake128 và shake256, chúng ta thực hiện như sau:
Cho arr là một mảng bit trống.
Lặp lại cho đến khi cần thiết:
Thêm r bit đầu tiên của State vào mảng arr. Dừng lại nếu arr đã đủ dài.
Trong 24 vòng (rounds):
Theta(state)
Rho(state)
Pi(state)
Chi(state)
Iota(state, round)
Độ dài của đầu ra được cố định đối với các biến thể không phải shake của SHA-3, trong khi đó đối với shake128
và shake256, độ dài đầu ra (d) do người dùng xác định. Trong trường hợp này, bạn đã chọn nó là
ở trên. Giá trị r là cố định và được xác định như sau:
Biến thể SHA-3
r (rate)
shake128
1344 bit
shake256
1088 bit
Khối đầu ra
, bước
.
Trong bước Lấy (Take step), chúng ta lấy r bit đầu tiên (đối với là
) và nối vào mảng đầu ra. Kích thước mảng đầu ra tăng từ
lên . State không thay đổi.
Kích thước của mảng đầu ra chưa đạt đến kích thước mong muốn (d= bit), vì vậy
chúng ta tiếp tục với các bước Theta-Rho-Pi-Chi-Iota.
Kích thước của mảng đầu ra đã đạt và vượt qua kích thước mong muốn (d= bit), vì
vậy chúng ta không cần phải thực hiện các bước Theta-Rho-Pi-Chi-Iota nữa. Chúng ta loại bỏ
-= bit dư.
State:
State sau khi tính toán:
Trong bước Theta, 5 bit từ cùng một slice, 5 bit từ slice bên cạnh và bit gốc đều được XOR với nhau. Cách dễ
hiểu hơn là tính tổng các bit được đánh dấu và kiểm tra xem kết quả có phải số lẻ hay không.
State trước khi tính toán:
State sau khi tính toán:
Trong bước Rho, lane được chọn sẽ được xoay (rotate) sang phải một lượng nhất định, tùy thuộc lane đó là
lane nào. Lượng xoay lần lượt là 0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8,
18, 2, 61, 56, 14.
State trước khi tính toán:
State sau khi tính toán:
Trong bước Pi, các lane được sắp xếp lại. Thứ tự mới của các lane lần lượt là 1, 7, 13, 19, 25, 4, 10, 11,
17, 23, 2, 8, 14, 20, 21, 5, 6, 12, 18, 24, 3, 9, 15, 16, 22. Nghĩa là lane đầu tiên giữ nguyên vị trí, lane
thứ hai trở thành lane thứ 7, và tiếp tục lặp lại như vậy.
State trước khi tính toán:
State sau khi tính toán:
Trong bước Chi, trước hết chúng ta chia State thành các nhóm 5 lane, sau đó chọn bit đang xét và hai bit bên
dưới nó trong cùng một nhóm. Kết quả được tính theo công thức: xanh lá XOR (
(not vàng) and đỏ ).
State trước khi tính toán:
State sau khi tính toán:
Trong bước Iota, chỉ có lane đầu tiên thay đổi, trong khi phần còn lại được giữ nguyên. Các bit của lane đầu
tiên được XOR với một hằng số như bên dưới. Lưu ý rằng hằng số được dùng phụ thuộc vào số thứ tự của vòng
(round).
State trước khi tính toán:
State sau khi tính toán:
5. Xử lý và biểu diễn kết quả đầu ra
Dưới đây là tất cả các bit mà chúng ta đã thu được ở bước trước:
Cuối cùng, đảo ngược các bit trong mỗi nhóm 8-bit, sao cho các bit ở ngoài cùng bên trái trở thành bit ở ngoài
cùng bên phải, và ngược lại.
Chúng ta cũng có thể viết nó dưới dạng ký hiệu thập lục phân (hex):
