加速Haskell PBKDF2算法

Question

加速Haskell PBKDF2算法

3

我已经用Haskell编写了PBKDF2算法的新版本。它通过了RFC 6070中列出的几乎所有HMAC-SHA-1测试向量，但效率不高。我该如何改进代码？

当我在测试向量上运行它时，第三个案例（请参见下文）永远不会完成（我在2010年的Macbook Pro上运行了半个多小时）。

我认为问题出在“foldl'”上。使用“foldr”会更好吗？还是我需要使用可变数组？

{-# LANGUAGE BangPatterns #-}
{- Copyright 2013, G. Ralph Kuntz, MD. All rights reserved. LGPL License. -}

module Crypto where

import Codec.Utils (Octet)
import qualified Data.Binary as B (encode)
import Data.Bits (xor)
import qualified Data.ByteString.Lazy.Char8 as C (pack)
import qualified Data.ByteString.Lazy as L (unpack)
import Data.List (foldl')
import Data.HMAC (hmac_sha1)
import Text.Bytedump (dumpRaw)

-- Calculate the PBKDF2 as a hexadecimal string
pbkdf2
  :: ([Octet] -> [Octet] -> [Octet])  -- pseudo random function (HMAC)
  -> Int  -- hash length in bytes
  -> String  -- password
  -> String  -- salt
  -> Int  -- iterations
  -> Int  -- derived key length in bytes
  -> String
pbkdf2 prf hashLength password salt iterations keyLength =
  let
    passwordOctets = stringToOctets password
    saltOctets = stringToOctets salt
    totalBlocks =
      ceiling $ (fromIntegral keyLength :: Double) / fromIntegral hashLength
    blockIterator message acc =
      foldl' (\(a, m) _ ->
        let !m' = prf passwordOctets m
        in (zipWith xor a m', m')) (acc, message) [1..iterations]
  in
    dumpRaw $ take keyLength $ foldl' (\acc block ->
      acc ++ fst (blockIterator (saltOctets ++ intToOctets block)
                      (replicate hashLength 0))) [] [1..totalBlocks]
  where
    intToOctets :: Int -> [Octet]
    intToOctets i =
      let a = L.unpack . B.encode $ i
      in drop (length a - 4) a

    stringToOctets :: String -> [Octet]
    stringToOctets = L.unpack . C.pack

-- Calculate the PBKDF2 as a hexadecimal string using HMAC and SHA-1
pbkdf2HmacSha1
  :: String  -- password
  -> String  -- salt
  -> Int  -- iterations
  -> Int  -- derived key length in bytes
  -> String
pbkdf2HmacSha1 =
  pbkdf2 hmac_sha1 20

第三个测试向量

 Input:
   P = "password" (8 octets)
   S = "salt" (4 octets)
   c = 16777216
   dkLen = 20

 Output:
   DK = ee fe 3d 61 cd 4d a4 e4
        e9 94 5b 3d 6b a2 15 8c
        26 34 e9 84             (20 octets)

- Ralph

2

一个快速的观察：你没有真正强制 foldl' 参数中的 m。由于 m 是一个列表，您需要使用例如 deepSeq 来强制执行所有内容。 - opqdonut

我可能错了，因为我不是一个真正强大的Haskeller，但你在一个函数中塞入的内容有点难以理解，如果你将其分解成更小、更简单的部分，你可能会发现改进的空间非常明显。 - Jimmy Hoffa

1

我强烈建议将算法更改为在ByteString上运行（可以将其视为Word8向量），而不是Octet列表。虽然这不是减慢速度的唯一原因，但这也是一个有些棘手的算法，因为您可以调整它以花费任何您想要的时间，所以测试起来有些困难。 - J. Abrahamson

我将研究如何使用“ByteString”。 - Ralph

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rampion · Accepted Answer

我能够在我的MacBookPro上完成它，耗时约16分钟：

% time Crypto-Main
eefe3d61cd4da4e4e9945b3d6ba2158c2634e984                          
./Crypto-Main  1027.30s user 15.34s system 100% cpu 17:22.61 total

通过改变折叠的严格程度：

let
  -- ...
  blockIterator message acc = foldl' (zipWith' xor) acc ms
    where ms = take iterations . tail $ iterate (prf passwordOctets) message
          zipWith' f as bs = let cs = zipWith f as bs in sum cs `seq` cs
in
  dumpRaw $ take keyLength $ foldl' (\acc block ->
    acc ++ blockIterator (saltOctets ++ intToOctets block)
                    (replicate hashLength 0)) [] [1..totalBlocks]

请注意，我强制执行每个zipWith xor的完整计算。为了将sum cs计算为WHNF，我们必须知道cs中每个元素的确切值。

这可以防止建立一个thunks链，我认为你现有的代码正在尝试做到这一点，但失败了，因为foldl'只强制使累加器成为WHNF。由于您的累加器是一对，所以WHNF只是(_thunk, _another_thunk)，因此您的中间thunks没有被强制。