Haskell AES 密钥扩展有什么问题？

Question

按照 Jeff Moser's popular tutorial 中描述键扩展的步骤，我编写了用于键扩展的代码。这是整个文件（它还计算了 S-Box），因此人们可以编译并尝试它。

{-# LANGUAGE NoMonomorphismRestriction #-}

import Control.Applicative (liftA2)
import Data.Bits (xor, shiftL, shiftR, (.|.), (.&.))
import Data.List (transpose, sortBy)
import Data.Ord (comparing)
import Data.Word (Word8)
import Numeric (showHex)

keys = f 16 $ f 8 $ f 4 $ f 2 $ f 1 key
 where
  f w n = xpndC . xpndB . xpndA $ xpndD w n

xpndC   :: [[Word8]] -> [[Word8]]
xpndC ws = transpose [head ws, b, zipWith xor b c, last ws]
 where
  (b,c) = (ws !! 1, ws !! 2)

xpndB   :: [[Word8]] -> [[Word8]]
xpndB ws = a : zipWith xor a b : drop 2 ws
 where
  (a,b) = (head ws, ws !! 1)

xpndA   :: [[Word8]] -> [[Word8]]
xpndA ws = zipWith xor a d : tail ws
 where
  (a,d) = (head ws, last ws)

xpndD rc ws = take 3 tW ++ [w']
 where
  w' = zipWith xor (map sub w) [rc, 0, 0, 0]
  tW = transpose ws
  w  = take 4 $ tail $ cycle $ last tW

--------------------------------------------------------------
sub w = get sbox (fromIntegral lo) $ fromIntegral hi
 where
  (hi, lo) = nibs w

get wss x y = (wss !! y) !! x

print' = print . w128 . concat . transpose
 where
  w128 = concatMap (f . (`showHex` ""))
  f w  = (length w < 2) ? (' ':'0':w, ' ':w)

grid _ [] = []
grid n xs = take n xs : grid n (drop n xs)

nibs w    = (shiftR (w .&. 0xF0) 4, w .&. 0x0F)
(⊕)       = xor
p ? (a,b) = if p then a else b; infix 2 ?

---------------------------------------------------
sbox :: [[Word8]]
sbox = grid 16 $ map snd $ sortBy (comparing fst) $ sbx 1 1 []

sbx :: Word8 -> Word8 -> [(Word8, Word8)] -> [(Word8, Word8)]
sbx p q ws
  | length ws == 255 = (0, 0x63) : ws
  | otherwise = sbx p' r $ (p', xf ⊕ 0x63) : ws
 where
  p' = p  ⊕  shiftL p  1 ⊕  ((p .&. 0x80 /= 0) ? (0x1B, 0))
  q1 = foldl (liftA2 (.) xor shiftL) q [1, 2, 4]
  r  = q1 ⊕  ((q1 .&. 0x80 /= 0) ? (0x09, 0))
  xf = r  ⊕  rotl8 r 1 ⊕  rotl8 r 2 ⊕  rotl8 r 3 ⊕  rotl8 r 4

rotl8 w n = (w `shiftL` n) .|. (w `shiftR` (8 - n))

key = [[0,0,0,0],
       [0,0,0,0],
       [0,0,0,0],
       [0,0,0,0]] :: [[Word8]]

当我针对全零测试密钥测试此代码时，它与发布的期望相匹配直到第四次迭代：ee 06 da 7b 87 6a 15 81 75 9e 42 b2 7e 91 ee 2b。

但是当我尝试下一次迭代时：keys = f 16 $ f 8 $ f 4 $ f 2 $ f 1，结果的最后 32 位是错误的：7f 2e 2b 88 f8 44 3e 09 8d da 7c bb 91 28 f1 f3.

同样的行为 - 最后 32 位错误 - 当我使用所有 0xFF 作为初始密钥时发生。在随后的迭代中，所有位都是错误的。

如果我使用测试向量 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f，出错的速度会更快 - 我在第二次迭代时开始出错。

这是怎么回事？我注意到 Moser 先生在 2b 部分写道：4 到 xor 与 previous round key 的第一列 - 但是有初始密钥没有前一轮，所以这让我很困惑。这是我做错了吗？

供参考，here are the test vectors.

Answer 1

你少了一步。

xpndC ws = transpose [head ws, b, zipWith xor b c, last ws]

第四列应该是前第四列（您在第一遍中丢弃的）和新的第三列的异或。

xor x x = 0 以某种方式导致此错误的事实仅在第五次迭代时才被注意到。

小的文体评论

固定结构上的模式匹配比 (!!) 更简单。

xpndC :: [[Word8]] -> [[Word8]]
xpndC [a,b,c,d] = [a, b, zipWith xor b c, d]

另请注意，步骤 2b4 和 3 实际上是一次扫描。粗略地说，它最终看起来像这样（名字 schedule_core 是从你上一个 link 借来的）：

new = tail $ scanl (zipWith xor) (schedule_core (last old)) old

编辑：修复

解决方案本质上是 而不是 丢弃最后一列。作为快速修复，您可以通过这种方式在额外的传递中注入它：

keys = f 16 $ f 8 $ f 4 $ f 2 $ f 1 key
 where
  f w n = xpndE (transpose n) . xpndC . xpndB . xpndA $ xpndD w n

xpndE n [a,b,c,_] = transpose [a,b,c,zipWith xor c (last n)]

xpndC = (...) {- remove transpose here -}

一旦您意识到列表非常小，xpnd* 函数可能有点过于细化。如果你想保留它，我也会将 transpose 排除在外。

keys = transpose $ f 16 $ f 8 $ f 4 $ f 2 $ f 1 $ transpose key
  where
    f rc [a, b, c, d] =
      let e = schedule rc d
          a' = zipWith xor a e
          b' = zipWith xor b a'
          c' = zipWith xor c b'
          d' = zipWith xor c c'
      in [a', b', c', d']  -- Here is where one may recognize `scanl` or a fold.

至于schedule，就是取最后一列（上面d，下面last tW）打乱（[=27=上面，[=28] =] 下面）。您可以从 xpndD:

的定义中提取它

xpndD rc ws = take 3 tW ++ [w']
 where
  w' = zipWith xor (map sub w) [rc, 0, 0, 0]
  tW = transpose ws
  w  = take 4 $ tail $ cycle $ last tW

我们得到（取模纯粹的修饰重写 take 4 $ tail $ cycle d = tail d ++ [head d]）：

schedule rc d = zipWith xor (map sub $ tail d ++ [head d]) [rc, 0, 0, 0]

Haskell AES 密钥扩展有什么问题？

What's wrong with this Haskell AES key expansion?

haskell

aes

rijndael

编辑：修复