Feistel 網路生成的排列有多隨機？

我使用 blake2b 從 Feistel 網路中編寫了一個玩具偽隨機排列。但是，查看小 n = 6 的排列分佈，除非執行許多輪，否則它顯然不均勻。我的印像是3或4輪就足夠了。我錯過了什麼？

下面的程式碼工作如下，生成隨機排列 $ n $ 元素。

• 我們找到最小整數 m 使得 $ n \leq 2^{2m} $
• 我們在 Feistel 網路中使用 blake2b。Blake2b 以種子為密鑰，種子決定隨機排列，並被賦予一個鹽，即整數。
• 我們使用如前所述的 Feistel 網路計算 2m 位整數的排列。
• 我們將這種排列轉化為作用於 $ n $ 元素通過遵循循環，即迭代排列 $ 2^{2m} $ 元素它直到它產生一個值 < $ n $ .

為了測試這段程式碼，我們然後繪製 $ 100~n! $ 偽隨機排列和執行 $ \chi^2 $ 在 Feistel 網路中測試越來越多的輪次。很明顯，只有 3-4 輪，生成的排列並不是均勻分佈的。

import hashlib
import math
from collections import Counter
from scipy.stats import chi2

class Permutation():

   def __init__(self, n, seed, rounds=3):
       self.n = n
       self.rounds = rounds
       # n_bits is least integer suc that n <= 2**(2*n_bits)
       self.n_bits = 1 + math.floor(math.log(n, 4))
       self.seed = seed
       self.low_mask = (1 << self.n_bits) - 1
       self.high_mask = self.low_mask << self.n_bits
       self.digest_size = math.ceil(self.n_bits / 8)

   def __hash(self, msg, salt):
       h = hashlib.blake2b(msg, digest_size=self.digest_size, key=self.seed, salt = salt)
       return int(h.hexdigest(),base=16) & self.low_mask

   def __round(self, i, r):

       def to_bytes(m):
           b = 1 if m ==0 else 1 + math.floor(math.log(m, 256))
           return m.to_bytes(b, byteorder='little')

       low = self.low_mask & i
       high = (self.high_mask & i) >> self.n_bits
       low, high = high ^ self.__hash(to_bytes(low), salt=to_bytes(r)), low << self.n_bits
       return high + low

   def __p(self, i):
       result = i
       for r in range(0, self.rounds):
           result = self.__round(result, r)
       return result

   def __call__(self, i):
       j = self.__p(i)
       while j >= self.n:
           j = self.__p(j)
       return j

n = 6
fact = 1
for i in range(1, n + 1):
   fact *= i

for rounds in range(3, 10):
   cnt = Counter()
   for w in range(0,100 * fact):
       p = Permutation(n, seed = bytes('w=%d' % w, encoding='ascii'), rounds=rounds)
       ss = ''.join([str(p(i)) for i in range(0, n)])
       cnt.update([ss])

   x2 = sum((x - 100.0)**2/ 100.0 for p, x in cnt.items()) + 100.0 * (fact - len(cnt))
   print("n = %d,\trounds = %d,\tx2 = %f,\tchi2-cdf = %f" % (n, rounds, x2, chi2.cdf(x2, fact - 1)))

編輯：作為健全性檢查，我用一個實際的隨機預言機替換了 blake2b

class RandomOracle():

   def __init__(self):
       self.known = {}

   def __call__(self, msg, digest_size, key, salt):
       entry = (msg, digest_size, key, salt)
       if  entry in self.known:
           return self.known[entry]
       else:
           v = os.urandom(digest_size)
           self.known[entry] = v
           return v

oracle = RandomOracle()

這仍然會產生不均勻的隨機結果……

Luby-Rackoff 定理說 3-4 輪 Feistel 網路對於一些足夠大的塊大小是偽隨機排列。正如Patarin 關於 5 輪或更多輪的 Feistel 網路的這篇論文所說：

我們將表示為 $ k $ 輪數和由 $ n $ 整數使得 Feistel 密碼是一個排列 $ 2^n $ 位 → $ 2^n $ 位。在

$$ 3 $$事實證明，當 $ k ≥ 3 $ 當查詢的數量（即獲得的明文/密文對）為 $ m \ll 2^{n/2} $ . 此外，當 $ k ≥ 4 $ 當查詢數量為 $ m \ll 2^{n/2} $ （第二個結果的證明在$$ 9 $$).

如果您的域非常小，那麼確實，您的查詢數量 $ m $ 很容易越界。如果我理解你的程式碼是正確的，那麼你正在一個塊大小為 4 的 Feistel 網路上進行循環行走，所以當你點擊 $ \sqrt{2^4} = $ 您已經達到了這個界限的四個查詢。

順便說一句，這就是為什麼像NIST SP 800-38g中的那些保留真實格式的加密模式使用 8 輪 (FF3) 或 10 輪 (FF1) 的 Feistel 網路。請注意，即便如此，仍發現了針對 FF3 的攻擊，需要對模式進行修改。

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