无意中看到一个名字比较有意思的哈希函数，这个哈希函数也是SHA3的候选算法之一，虽然最后没有选他，不过他这个名字起的着实是蛮有意思的，所以呢本文来看一下它的具体的结构。
背景知识
根据参考资料，这个名字来自于德语，原来指的是一道奥地利菜，该菜式的英文名称为哈希，为啥第一眼相中了这个算法呢，因为这个算法俺不会读，然后就去翻了一下他应该是怎么发音的，结果就是 「一入算法深似海，从此天涯是路人」，这里直接截图一段原始论文的原文吧，我也懒得从pdf当中复制出来了。
本以为这里会给个音标啥的，结果一句话给我整破防了，如果想要了解更多的发音的例子，我还需要看一下另一篇paper，这不就是套娃吗，然后我满怀期待的看了一下所提到的地址，发现这根本不是我这种学渣能够理解的了的，所以干脆我就不纠结他的发音了，咱惹不起还躲不起吗，溜了溜了。
算法过程
虽然说，咱不知道这个算法的名字应该怎么读，但是吧，写文章又不要求我会读，如果有会读的读者，欢迎来告诉我，下面还是来具体的看一下这个算法是怎么玩的吧。
算法构造
这个算法也是按照分块来处理消息的，根据最终所得到的消息摘要的长度，分割长度可以为 512或者为 1024。
上图是我从原始的论文里面借鉴过来的，如果看过之前的文章有关 Merkle-Damgård结构的介绍，会发现这个也是符合这个结构的，这里最后的输出就是一个单独的函数，而不是直接就输出最终的向量。
压缩函数构造
在任何一个哈希函数当中，压缩函数的构造都是整个算法的核心，对于Grøstl算法来说，它的压缩函数主要是通过两个置换函数来处理的，如下所示:
有关P和Q两个置换函数的介绍，咱们等会在讲（因为原来的论文他就是这么干的）。
输出转换
我们定义一个新的函数 表示一个n比特的串的末尾x比特，最终的输出函数 可以表示为:
P和Q的设计
对于P和Q的具体过程主要是分为如下的四步:
-
AddRoundConstant -
SubBytes -
ShiftBytes -
MixBytes
看到这个，有没有莫名的熟悉感，如果没有，当我没说，这个和AES当中的轮函数是比较相似的，作者也说了，他的灵感也是来自于此，具体的函数定义如下：
下面来具体看一下这四步具体的过程
AddRoundConstant
这一步其实比较简单，实际上就是每个状态和某个常量进行一个异或操作
对于有关具体的轮常量的内容，读者们可以自行翻阅一下参考资料当中的论文，在这里我就不贴出来了，对于P和Q两个的轮常量是不一样的。
SubBytes
字节替代，这个和当时的AES是一样的，这里不熟悉的读者可以去翻一翻之前我写过的有关AES介绍的文章，这里也不过多的描述了。
ShiftBytes
对于这个过程，其实如果能理解了AES当中的行移位的操作，这个也不难理解，这里直接借用一下原始论文当中的图，因为这个图实在是不好画，我这里直接搬过来了。
实际上就是对状态矩阵的当中的每一个字节按照某个约定的移动位数，进行一次位置的变换操作。
MixBytes
这个运算同样是在有限域上的运算，有关于有限域的相关知识，可以去参考一下我之前写过的文章，如果说有不熟悉这方面知识的读者。这个有限域和AES取的有限域是一个，都是基于多项式 上的，这个变换实际上就是一个矩阵的乘法，如下所示
B矩阵的详细内容，这里我也不贴出来了，感兴趣的读者可以自行翻阅一下文末的参考资料。
补充
对于一个完整的哈希函数，介绍完了压缩函数，其实也就没啥了，我们来看一下剩余的部分，一个就是初始化项链，另一个就是padding，这两个好像也没啥能说的，初始化向量就是固定的常数值，padding在之前的哈希函数的介绍当中也介绍了不少了，在这里就不啰嗦了。
代码实现
这里回归老本行了，还是拿rust来写一下这个代码的实现吧，rust给的一个库是采用查表法来实现的，这里咱们还是用本文当中讲解的做法来写，咋感觉又给我挖了个坑呢，查表法下次一定把。
mod compress;
mod utils;
use crate::compress::{compress, PermutationType};
use core::fmt;
use std::array::from_ref;
use std::fmt::Formatter;
use digest::{block_buffer::Eager, core_api::{
AlgorithmName, Block, BlockSizeUser, Buffer, BufferKindUser, CoreWrapper,
OutputSizeUser, UpdateCore,
}, typenum::{Unsigned, U128, U64}, HashMarker, Output, Reset};
use digest::core_api::FixedOutputCore;
#[derive(Clone)]
pub struct GroestlCore {
block_len: u64,
state: [u64; 8],
}
impl HashMarker for GroestlCore {}
impl BlockSizeUser for GroestlCore {
type BlockSize = U64;
}
impl BufferKindUser for GroestlCore {
type BufferKind = Eager;
}
impl OutputSizeUser for GroestlCore {
type OutputSize = U128;
}
impl UpdateCore for GroestlCore {
#[inline]
fn update_blocks(&mut self, blocks: &[Block<Self>]) {
self.block_len = self.block_len.wrapping_add(blocks.len() as u64);
compress(&mut self.state, convert(blocks));
}
}
impl FixedOutputCore for GroestlCore {
#[inline]
fn finalize_fixed_core(&mut self, buffer: &mut Buffer<Self>, out: &mut Output<Self>) {
let blocks_len = if buffer.remaining() <= 8 {
self.block_len + 2
} else {
self.block_len + 1
};
buffer.len64_padding_be(blocks_len, |b| compress(&mut self.state, convert(from_ref(b))));
let res = compress::round(self.state, PermutationType::P);
self.state = compress::xor(&res, &self.state);
let n = 4;
for (chunk, v) in out.chunks_exact_mut(8).zip(self.state[n..].iter()) {
chunk.copy_from_slice(&v.to_be_bytes());
}
}
}
impl Default for GroestlCore {
#[inline]
fn default() -> Self {
Self {
block_len: 0,
state: [0, 0, 0, 0, 0, 0, 0, 256],
}
}
}
impl Reset for GroestlCore {
#[inline]
fn reset(&mut self) {
*self = Default::default();
}
}
impl AlgorithmName for GroestlCore {
fn write_alg_name(f: &mut Formatter<'_>) -> fmt::Result {
f.write_str("Grøstl")
}
}
impl fmt::Debug for GroestlCore {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.write_str("Grøstl { ... }")
}
}
/// Grøstl hasher state
pub type Groestl = CoreWrapper<GroestlCore>;
const BLOCK_SIZE: usize = <GroestlCore as BlockSizeUser>::BlockSize::USIZE;
#[inline(always)]
fn convert(blocks: &[Block<GroestlCore>]) -> &[[u8; BLOCK_SIZE]] {
// SAFETY: GenericArray<u8, U64> and [u8; 64] have
// exactly the same memory layout
let p = blocks.as_ptr() as *const [u8; BLOCK_SIZE];
unsafe { core::slice::from_raw_parts(p, blocks.len()) }
}
const SBOX: [u8; 256] = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16,
];
#[derive(Clone, Copy)]
pub enum PermutationType {
P,
Q,
}
fn pick_row(col: u64, i: usize) -> u8 {
return ((col >> (8 * (7 - i))) & 0xFF) as u8;
}
fn add_round_constant(mut state: [u64; 8], r: usize, variant: PermutationType) -> [u64; 8] {
match variant {
PermutationType::P => {
let mut i = 0;
let l = state.len();
while i < l {
state[i] ^= (((i << 4) ^ r) << (8 * 7)) as u64;
i += 1;
}
}
PermutationType::Q => {
let mut i = 0;
let l = state.len();
while i < l {
state[i] ^= ((!0) ^ ((i << 4) ^ r)) as u64;
i += 1;
}
}
}
return state;
}
fn sub_bytes(mut state: [u64; 8]) -> [u64; 8] {
let mut new_col = [0u8; 8];
let mut i = 0;
let l = state.len();
while i < l {
for j in 0..8 {
new_col[j] = SBOX[pick_row(state[i], j) as usize];
}
state[i] = new_col.iter().fold(0, |x, &i| x << 8 | i as u64);
i += 1;
}
return state;
}
fn shift_bytes(state: [u64; 8], variant: PermutationType) -> [u64; 8] {
let shift_vector = match variant {
PermutationType::P => {
[0, 1, 2, 3, 4, 5, 6, 7]
}
PermutationType::Q => {
[1, 3, 5, 7, 0, 2, 4, 6]
}
};
let l = state.len();
let mut ret = [0u64; 8];
for i in 0..l {
ret[i] = pick_row(state[(i + shift_vector[0]) % l], 0) as u64;
for j in 1..8 {
ret[i] <<= 8;
ret[i] ^= pick_row(state[(i + shift_vector[j]) % l], j) as u64;
}
}
return ret;
}
fn gmul(ap: u8, bp: u8) -> u8 {
let mut p = 0u8;
let mut a = ap;
let mut b = bp;
while a != 0 && b != 0 {
if b & 1 != 0 {
p ^= a;
}
if a & 0x80 != 0 {
// XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible
a = (((a << 1) as u16) ^ 0x11b) as u8;
} else {
a = a << 1;
}
b >>= 1;
}
return p & 0xFF;
}
fn mix_bytes(mut state: [u64; 8]) -> [u64; 8] {
let mut temp = [0; 8];
for i in 0..state.len() {
for j in 0..8 {
temp[j] =
gmul(pick_row(state[i], (j + 0) % 8), 2) ^
gmul(pick_row(state[i], (j + 1) % 8), 2) ^
gmul(pick_row(state[i], (j + 2) % 8), 3) ^
gmul(pick_row(state[i], (j + 3) % 8), 4) ^
gmul(pick_row(state[i], (j + 4) % 8), 5) ^
gmul(pick_row(state[i], (j + 5) % 8), 3) ^
gmul(pick_row(state[i], (j + 6) % 8), 5) ^
gmul(pick_row(state[i], (j + 7) % 8), 7);
}
state[i] = temp.iter().fold(0, |x, &i| x << 8 | i as u64);
}
return state;
}
pub fn round(mut state: [u64; 8], variant: PermutationType) -> [u64; 8] {
for i in 0..10 {
state = add_round_constant(state, i, variant);
state = sub_bytes(state);
state = shift_bytes(state, variant);
state = mix_bytes(state);
}
return state;
}
pub fn xor(a: &[u64; 8], b: &[u64; 8]) -> [u64; 8] {
let mut out = [0; 8];
for i in 0..8 {
out[i] = a[i] ^ b[i];
}
return out;
}
fn compress_block(state: &mut [u64; 8], block: &[u64; 8]) {
// f(h,m) = P(h ＋ m) ＋ Q(m) ＋ h
let temp = round(xor(state, block), PermutationType::P);
let q = round(block.clone(), PermutationType::Q);
let temp = xor(&xor(&temp, &q), state);
for i in 0..8 {
state[i] = temp[i];
}
}
fn build_columns(data: &[u8; 64]) -> [u64; 8] {
let mut out = [0; 8];
for i in 0..8 {
out[i] = (data[(i * 8)..(i * 8 + 8)]).iter().fold(0, |x, &i| x << 8 | i as u64);
}
return out;
}
pub fn compress(state: &mut [u64; 8], blocks: &[[u8; 64]]) {
for block in blocks {
compress_block(state, &build_columns(block));
}
}
参考资料
-
http://www.groestl.info/ -
https://github.com/kacpal/groestl
原文始发于微信公众号（Coder小Q）：【密码学】一文读懂Grøstl
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论