大塊密碼作為記憶硬函式

我想知道，如果像塊密碼這樣大塊大小的東西是一個很好的記憶硬功能？

我見過的所有記憶硬鍵派生函式看起來都比這更複雜，這讓我質疑我對記憶硬性的理解。

以下函式對我來說看起來很難記憶（記憶體權衡看起​​來很昂貴）：

size = 16MB / (F() word size in bytes)
rounds = 1024
state = constants ⊕ (key || salt)

for (i = 0; i < rounds * size; i++)
  state[i mod size] = state[i mod size] ⊕ F(state[i + 1 mod size])

result = state ⊕ key

這種類型 I 的廣義 Feistel 網路密鑰推導函式有多難記憶？

我一直在玩弄你的功能，我得出的結論是它並不難記憶。所需的記憶體量最多可以減少到digestsize * 3 * rounds.

第一個問題是熵不會在整個州內雪崩，而是保持局部化。例如，在 1 輪之後，第 2 塊的狀態僅取決於第 3 塊的狀態。在 2 輪之後，它（間接地）僅取決於第 3 塊和第 4 塊的初始狀態。這意味著攻擊者可以在常量的大部分上預先計算 1024 輪，並且不需要每個密碼的記憶體。

一個可能的改進是將混合轉向，state[i mod size] = state[i mod size] ⊕ F(state[i - 1 mod size])以便每個塊都依賴於前一個而不是下一個，但是您以相同的順序生成和散列的事實將始終使權衡成為可能。更改該順序，最好以與數據無關的方式（例如通過在每一輪之後顛倒塊的順序），將使該方式更加困難。

為了說明我的觀點，這裡有 2 個程式碼：1 個有，1 個沒有對你的函式進行記憶體權衡：

#!/usr/bin/env python3
from hashlib import sha512

blocks = 1000
rounds = 100
# pseudorandom constants created by hashing the literals "0", "1", ... "1000"
constants = [sha512(str(i).encode()).digest() for i in range(0, blocks)]


def mix(a, b):
   global operations
   operations += 1  # statistics
   b = sha512(b).digest()
   return bytearray(a ^ b for (a, b) in zip(a, b))


def more_memory(constant):
   state = list(constant)

   for i in range(0, rounds * blocks):
       state[i % blocks] = mix(state[i % blocks], state[(i + 1) % blocks])

   # Make a checksum for the entire state
   state_hash = sha512()
   for s in state:
       state_hash.update(s)

   return state_hash.hexdigest()[:32]


def less_memory(constant):
   def perform_round(sequence):
       first = None
       cur = next(sequence)

       try:
           while True:
               after = next(sequence)
               result = mix(cur, after)
               yield result
               if not first:
                   first = result
               cur = after
       except StopIteration:
           pass

       yield mix(cur, first)

   current = (s for s in constant)
   for _ in range(0, rounds):
       current = perform_round(current)

   # Make a checksum for the entire state
   state_hash = sha512()
   for s in current:
       state_hash.update(s)

   return state_hash.hexdigest()[:32]

operations = 0
print('Using a lot of memory: {} ({} mixing-operations)'.format(more_memory(constants), operations))
operations = 0
print('Using little memory: {} ({} mixing-operations)'.format(less_memory(constants), operations))

# Prints:
# Using a lot of memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)
# Using little memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)

引用自：https://crypto.stackexchange.com/questions/30918