ppad-bip39-0.4.0: lib/Crypto/KDF/BIP39.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE UnboxedTuples #-}
-- |
-- Module: Crypto.KDF.BIP39
-- Copyright: (c) 2025 Jared Tobin
-- License: MIT
-- Maintainer: Jared Tobin <jared@ppad.tech>
--
-- [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki)
-- mnemonic codes for deterministic key generation, supporting wordlists in
-- multiple languages.
module Crypto.KDF.BIP39 (
-- * Mnemonic construction and validation
mnemonic
, _mnemonic
, valid
, _valid
-- * Seed derivation
, seed
, _seed
, seed_unsafe
-- * Wordlists
--
-- $wordlists
, Wordlist
, english
, chinese_traditional
, chinese_simplified
, czech
, french
, korean
, italian
, japanese
, portuguese
, spanish
-- for testing
, _words
) where
import Control.Monad (guard)
import Control.Monad.ST (ST, runST)
import qualified Crypto.KDF.BIP39.Wordlist as W
import Crypto.KDF.BIP39.Wordlist (Wordlist(..))
import qualified Crypto.KDF.PBKDF as PBKDF
import qualified Crypto.Hash.SHA256 as SHA256
import qualified Crypto.Hash.SHA512 as SHA512
import Data.Bits ((.&.), (.|.), (.>>.), (.<<.), complement, xor)
import qualified Data.ByteString as BS
import qualified Data.ByteString.Internal as BI
import qualified Data.ByteString.Unsafe as BU
import qualified Data.Foldable as F
import qualified Data.Primitive.ByteArray as BA
import qualified Data.Primitive.PrimArray as PA
import Data.Word (Word8, Word64)
import qualified Data.List as L
import Prelude hiding (words)
import qualified Data.Text as T
import qualified Data.Text.Array as TA
import qualified Data.Text.Encoding as TE
import qualified Data.Text.ICU.Normalize2 as ICU
import qualified Data.Text.Internal as TI
import qualified GHC.Exts as Exts
import GHC.Exts (Int(..), Word(..))
import GHC.Ptr (Ptr(..))
import GHC.ST (ST(..))
import GHC.Word (Word64(..))
fi :: (Integral a, Num b) => a -> b
fi = fromIntegral
{-# INLINE fi #-}
hmac_sha512 :: BS.ByteString -> BS.ByteString -> BS.ByteString
hmac_sha512 k b = case SHA512.hmac k b of
SHA512.MAC mac -> mac
{-# INLINE hmac_sha512 #-}
-- constant time --------------------------------------------------------------
-- an optimization barrier: through it the compiler cannot see that a
-- comparison's bit is zero or one, and so cannot turn the mask made
-- from it, or a selection under that mask, of a loaded value
-- especially, into a branch
barrier :: Word -> Word
barrier x = x
{-# NOINLINE barrier #-}
-- all ones where a == b, and zero otherwise
eqm :: Word -> Word -> Word
eqm a b =
let !d = a `xor` b
!nz = (d .|. negate d) .>>. 63 -- one where a /= b
in negate (barrier (nz `xor` 1))
{-# INLINE eqm #-}
-- all ones where a < b, and zero otherwise
ltm :: Word -> Word -> Word
ltm a b =
let !bit = ((complement a .&. b) .|. ((complement a .|. b) .&. (a - b)))
.>>. 63
in negate (barrier bit)
{-# INLINE ltm #-}
ix8 :: BA.ByteArray -> Int -> Word
ix8 a i = fi (BA.indexByteArray a i :: Word8)
{-# INLINE ix8 #-}
rd8 :: BA.MutableByteArray s -> Int -> ST s Word8
rd8 = BA.readByteArray
{-# INLINE rd8 #-}
wr8 :: BA.MutableByteArray s -> Int -> Word8 -> ST s ()
wr8 = BA.writeByteArray
{-# INLINE wr8 #-}
-- the byte at an offset of a wordlist's table
byte :: Ptr Word8 -> Int -> Word
byte (Ptr a) (I# o) = W# (Exts.word8ToWord# (Exts.indexWord8OffAddr# a o))
{-# INLINE byte #-}
-- the eight bytes at an offset of a wordlist's table, in memory order
lane :: Ptr Word8 -> Int -> Word64
lane (Ptr a) (I# o) = W64# (Exts.indexWord8OffAddrAsWord64# a o)
{-# INLINE lane #-}
-- the eight bytes at an offset of a byte array, in memory order
laneBA :: BA.ByteArray -> Int -> Word64
laneBA (BA.ByteArray b) (I# o) = W64# (Exts.indexWord8ArrayAsWord64# b o)
{-# INLINE laneBA #-}
-- eight bytes written at an offset of a byte array, in memory order
wrLane :: BA.MutableByteArray s -> Int -> Word64 -> ST s ()
wrLane (BA.MutableByteArray m) (I# o) (W64# w) =
ST (\st -> (# Exts.writeWord8ArrayAsWord64# m o w st, () #))
{-# INLINE wrLane #-}
-- the number of eight-byte lanes in a record of s bytes
lanes :: Int -> Int
lanes s = (s + 7) `quot` 8
{-# INLINE lanes #-}
-- all ones where byte q of a phrase separates words: ASCII whitespace,
-- or any byte of U+3000 (e3 80 80). Beyond the phrase is zero.
separator :: TA.Array -> Int -> Int -> Int -> Word
separator arr off len q =
let !b = at q
in eqm b 0x20
.|. (ltm 0x08 b .&. ltm b 0x0e)
.|. ideo q .|. ideo (q - 1) .|. ideo (q - 2)
where
at i
| i < 0 || i >= len = 0
| otherwise = fi (TA.unsafeIndex arr (off + i))
ideo i = eqm (at i) 0xe3
.&. eqm (at (i + 1)) 0x80
.&. eqm (at (i + 2)) 0x80
{-# INLINE separator #-}
-- all ones where a word count is a valid mnemonic length
counted :: Word -> Word
counted c =
eqm c 12 .|. eqm c 15 .|. eqm c 18 .|. eqm c 21 .|. eqm c 24
{-# INLINE counted #-}
-- the number of words in a phrase, in one pass over it whose
-- addresses and loop bounds depend on its length alone
count :: T.Text -> Word
count (TI.Text arr off len) = go 0 (complement 0) 0 where
go !q !prev !c
| q == len = c
| otherwise =
let !sm = separator arr off len q
!st = complement sm .&. prev
in go (q + 1) sm (c + (st .&. 1))
-- | Generate a BIP39 mnemonic from some entropy, using the default English
-- wordlist.
--
-- The entropy must be at least 128 bits long and at most 256 bits
-- long. Providing invalid entropy will result in a 'Nothing' value.
--
-- Runs in constant time with respect to the entropy, but for the
-- length of the resulting mnemonic, which its words determine.
--
-- >>> import qualified System.Entropy as E
-- >>> trop <- E.getEntropy 16
-- >>> mnemonic trop
-- Just "coral maze mimic half fat breeze thought club give brass bone snake"
mnemonic
:: BS.ByteString -- ^ 128-256 bits of entropy
-> Maybe T.Text
mnemonic = _mnemonic english
-- | Generate a BIP39 mnemonic from some entropy, using the provided
-- wordlist.
--
-- The entropy must be at least 128 bits long and at most 256 bits
-- long. Providing invalid entropy will result in a value of
-- 'Nothing'.
--
-- >>> import qualified System.Entropy as E
-- >>> trop <- E.getEntropy 16
-- >>> _mnemonic czech trop
-- Just "naslepo lysina dikobraz slupka beseda rorejs ostraha kobliha napevno blahobyt kazivost jiskra"
_mnemonic
:: Wordlist
-> BS.ByteString -- ^ 128-256 bits of entropy
-> Maybe T.Text
_mnemonic wlist entropy@(BI.PS _ _ l) = do
guard (l >= 16 && l <= 32)
let has = SHA256.hash entropy
h = BU.unsafeHead has
n = l `quot` 4
kek = h .&. (0b1111_1111 .<<. (8 - n)) -- top n bits
cat = BS.snoc entropy kek -- no table indexed by kek, as singleton
pure $! phrase wlist (indices cat)
{-# INLINE _mnemonic #-}
-- remaining, bits pool, number of bits in pool
type Acc = (BS.ByteString, Word64, Int)
-- the 11-bit word indices of a byte string
indices :: BS.ByteString -> [Word]
indices bs = L.unfoldr coalg (bs, 0, 0) where
mask = 0b0111_1111_1111
coalg :: Acc -> Maybe (Word, Acc)
coalg (etc, acc, len)
| len > 10 =
let w11 = fi ((acc .>>. (len - 11)) .&. mask) -- take bits from pool
nacc = acc .&. ((1 .<<. (len - 11)) - 1) -- adjust pool
nlen = len - 11 -- track less bits
in pure (w11, (etc, nacc, nlen))
| not (BS.null etc) =
let next = BU.unsafeHead etc
rest = BU.unsafeTail etc
nacc = (acc .<<. 8) .|. fi next -- add bits to pool
nlen = len + 8 -- track additional bits
in coalg (rest, nacc, nlen)
| otherwise =
Nothing
{-# INLINE indices #-}
-- the phrase of some word indices: each word selected from every
-- record of the wordlist, eight bytes at a time, and each byte of the
-- phrase gathered from every byte of every word, under masks, into a
-- buffer as long as the longest such phrase, so that no address or
-- loop bound depends on the indices. Only the phrase's length, which
-- its words fix, does.
phrase :: Wordlist -> [Word] -> T.Text
phrase (Wordlist w t) is = TI.Text arr 0 (fi total) where
!n = length is
!s = w + 1
!r = 8 * lanes s
!size = n * s
recs = BA.runByteArray $ do
m <- BA.newByteArray (n * r)
F.for_ (zip [0 ..] is) $ \(k, ix) ->
F.for_ [0 .. lanes s - 1] $ \l -> do
let sel !acc i =
acc .|. (lane t (i * s + 8 * l) .&. fi (eqm (fi i) ix))
wrLane m (k * r + 8 * l) (F.foldl' sel 0 [0 .. 2047])
pure m
lengths = [ ix8 recs (k * r) | k <- [0 .. n - 1] ]
offsets = scanl (\o l -> o + l + 1) 0 lengths
!total = F.foldl' (\a l -> a + l + 1) 0 lengths - 1
slots = zip3 [0 ..] offsets lengths
arr = TA.run $ do
m <- TA.new size
F.for_ [0 .. size - 1] $ \p -> do
let !q = fi p
word !acc (k, o, l) =
let !sp | k < n - 1 = 0x20 .&. eqm q (o + l)
| otherwise = 0
!ws = F.foldl'
(\a j ->
a .|. (ix8 recs (k * r + 1 + j) .&. eqm q (o + fi j)))
0 [0 .. w - 1]
in acc .|. sp .|. ws
TA.unsafeWrite m p (fi (F.foldl' word 0 slots))
pure m
-- | Derive a master seed from a provided mnemonic and passphrase, where the
-- mnemonic has been generated from the default English wordlist.
--
-- The mnemonic's length and words are validated. If you want to
-- validate the mnemonic's words against a non-English wordlist, use
-- '_seed'.
--
-- >>> let mnem = "coral maze mimic half fat breeze thought club give brass bone snake"
-- >> let pass = "hunter2"
-- >>> seed mnem pass
-- Just <512-bit long seed>
seed
:: T.Text -- ^ mnemonic
-> T.Text -- ^ passphrase (use e.g. "" or 'mempty' if not required)
-> Maybe BS.ByteString -- ^ seed
seed = _seed english
-- | Derive a master seed from a provided mnemonic and passphrase, where the
-- mnemonic has been generated from an arbitrary wordlist.
--
-- The provided mnemonic is checked for validity using '_valid'.
-- Providing an invalid mnemonic will result in a 'Nothing' value.
--
-- >>> let mnem = "coral maze mimic half fat breeze thought club give brass bone snake"
-- >> let pass = "hunter2"
-- >>> _seed english mnem pass
-- Just <512-bit long seed>
_seed
:: Wordlist -- ^ wordlist
-> T.Text -- ^ mnemonic
-> T.Text -- ^ passphrase (use e.g. "" or 'mempty' if not required)
-> Maybe BS.ByteString -- ^ seed
_seed wlist mnem pass = do
guard (_valid wlist mnem)
let salt = TE.encodeUtf8 ("mnemonic" <> ICU.nfkd pass)
norm = TE.encodeUtf8 (ICU.nfkd mnem)
PBKDF.derive hmac_sha512 norm salt 2048 64
{-# INLINE _seed #-}
-- | Derive a master seed from a provided mnemonic and passphrase.
--
-- The mnemonic's length is validated, but its individual words are
-- /not/. This function thus works for every wordlist. Words are
-- separated by runs of ASCII whitespace or U+3000 IDEOGRAPHIC SPACE.
--
-- >>> let mnem = "coral maze mimic half fat breeze thought club give brass bone snake"
-- >> let pass = "hunter2"
-- >>> seed_unsafe mnem pass
-- Just <512-bit long seed>
seed_unsafe
:: T.Text -- ^ mnemonic
-> T.Text -- ^ passphrase (use e.g. "" or 'mempty' if not required)
-> Maybe BS.ByteString -- ^ seed
seed_unsafe mnem pass = do
guard (counted (count mnem) /= 0)
let salt = TE.encodeUtf8 ("mnemonic" <> ICU.nfkd pass)
norm = TE.encodeUtf8 (ICU.nfkd mnem)
PBKDF.derive hmac_sha512 norm salt 2048 64
-- | Validate a mnemonic against the default English wordlist.
--
-- Verifies that the mnemonic has a valid length, and that every word
-- is contained in the wordlist. Words are separated by runs of ASCII
-- whitespace or U+3000 IDEOGRAPHIC SPACE.
--
-- Runs in constant time with respect to the mnemonic, but for its
-- length in bytes.
--
-- >>> valid "coral maze mimic half fat breeze thought club give brass bone snake"
-- True
-- >>> valid "coral maze mimic half fat breeze thought club give brass bone"
-- False
valid
:: T.Text -- ^ mnemonic
-> Bool -- ^ 'True' if valid
valid = _valid english
-- | Validate a mnemonic against a wordlist.
--
-- Verifies that the mnemonic has a valid length, and that every word
-- is contained in the provided wordlist. Words are separated by runs
-- of ASCII whitespace or U+3000 IDEOGRAPHIC SPACE.
--
-- Runs in constant time with respect to the mnemonic, but for its
-- length in bytes.
--
-- >>> let mnem = "持 樓 粗 殺 承 圖 湧 整 拿 路 式 棋"
-- >>> _valid chinese_traditional mnem
-- True
-- >>> _valid chinese_simplified mnem
-- False
_valid
:: Wordlist
-> T.Text -- ^ mnemonic
-> Bool -- ^ 'True' if valid
_valid (Wordlist w t) (TI.Text arr off len) = ok /= 0 where
!s = w + 1
!r = 8 * lanes s
-- each word extracted into a slot of a length byte and w bytes, in
-- one pass over the phrase whose addresses and loop bounds depend on
-- its length alone
(!c, slots, lens) = runST $ do
sl <- BA.newByteArray (24 * r)
BA.setByteArray sl 0 (24 * r) (0 :: Word8)
ln <- PA.newPrimArray 24
PA.setPrimArray ln 0 24 (0 :: Word)
let go !q !prev !n !cs
| q == len = pure n
| otherwise = do
let !sm = separator arr off len q
!ns = complement sm
!st = ns .&. prev
!n' = n + (st .&. 1)
!qw = fi q
!cs' = (qw .&. st) .|. (cs .&. complement st)
!k' = n' - 1
!jj = qw - cs'
!b = fi (TA.unsafeIndex arr (off + q)) :: Word
F.for_ [0 .. 23] $ \k -> do
let !m = eqm k' (fi k) .&. ns
l <- PA.readPrimArray ln k
PA.writePrimArray ln k (l + (m .&. 1))
F.for_ [0 .. w - 1] $ \j -> do
let !i = k * r + 1 + j
a <- rd8 sl i
wr8 sl i (a .|. fi (b .&. m .&. eqm jj (fi j)))
go (q + 1) sm n' cs'
n <- go 0 (complement 0) 0 0
F.for_ [0 .. 23] $ \k -> do
l <- PA.readPrimArray ln k
wr8 sl (k * r) (fi l)
sl' <- BA.unsafeFreezeByteArray sl
ln' <- PA.unsafeFreezePrimArray ln
pure (n, sl', ln')
!nl = lanes s
-- the first s bytes of a record's lanes, the rest belonging to the
-- next record
masks = PA.generatePrimArray nl $ \l ->
let !b = s - 8 * l
in laneBA ones (8 - min 8 b)
ones = BA.runByteArray $ do
m <- BA.newByteArray 16
BA.setByteArray m 0 8 (0xff :: Word8)
BA.setByteArray m 8 8 (0 :: Word8)
pure m
-- all ones where slot k matches some record, each compared in full,
-- eight bytes at a time
found k =
let !v = PA.generatePrimArray nl (\l -> laneBA slots (k * r + 8 * l))
diff !i !l !a
| l == nl = a
| otherwise =
diff i (l + 1)
(a .|. ((lane t (i * s + 8 * l) .&. PA.indexPrimArray masks l)
`xor` PA.indexPrimArray v l))
go !i !acc
| i == 2048 = acc
| otherwise = go (i + 1) (acc .|. eqm (fi (diff i 0 0)) 0)
in go (0 :: Int) 0
!known = F.foldl'
(\a k -> a .&. (found k .|. complement (ltm (fi k) c)))
(complement 0) [0 .. 23]
!over = F.foldl'
(\a k -> a .|. ltm (fi w) (PA.indexPrimArray lens k))
0 [0 .. 23]
!ok = known .&. counted c .&. complement over
-- wordlists ------------------------------------------------------------------
-- $wordlists
--
-- Wordlists for various languages.
--
-- For the following examples:
--
-- >>> import qualified Data.Text.IO as TIO
-- >>> let trop = "0123456789abcdef"
-- | The default English wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic english trop
-- coral maze mimic half fat breeze thought club give brass bone snake
english :: Wordlist
english = W.english
-- | The default Traditional Chinese wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic chinese_traditional trop
-- 持 樓 粗 殺 承 圖 湧 整 拿 路 式 棋
chinese_traditional :: Wordlist
chinese_traditional = W.chinese_traditional
-- | The default Simplified Chinese wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic chinese_simplified trop
-- 持 楼 粗 杀 承 图 涌 整 拿 路 式 棋
chinese_simplified :: Wordlist
chinese_simplified = W.chinese_simplified
-- | The default Korean wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic korean trop
-- 대문 어쩐지 여덟 설거지 볶음 그늘 태권도 단맛 상반기 균형 국왕 진출
korean :: Wordlist
korean = W.korean
-- | The default French wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic french trop
-- chlorure kimono légume flamme endroit bénéfice soulever céleste falaise belette banlieue reprise
french :: Wordlist
french = W.french
-- | The default Spanish wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic spanish trop
-- charla marido mente guía explicar banco tapa casco gemelo balcón ayuda ropa
spanish :: Wordlist
spanish = W.spanish
-- | The default Czech wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic czech trop
-- hadr omladina oslepit metr krajina deflace varovat flirt lovec dechovka cudnost svitek
czech :: Wordlist
czech = W.czech
-- | The default Italian wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic italian trop
-- conferma nevrotico obbligo indole florido benigno svista cigno grotta belva barbaro sfocato
italian :: Wordlist
italian = W.italian
-- | The default Portuguese wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic portuguese trop
-- capacho juba lareira figurado ejetar avaliar sonhador cachorro exposto autismo aterro refinar
portuguese :: Wordlist
portuguese = W.portuguese
-- | The default Japanese wordlist.
--
-- >>> TIO.putStrLn $ _mnemonic japanese trop
-- きおん たさい たまご しゃおん こふん えきたい ますく がはく しかい えおり うろこ ひとごみ
japanese :: Wordlist
japanese = W.japanese
-- | The words of a wordlist, in order. For testing.
_words :: Wordlist -> [T.Text]
_words (Wordlist w t) = fmap word [0 .. 2047] where
s = w + 1
word i =
let l = fi (byte t (i * s))
in TE.decodeUtf8
(BS.pack [ fi (byte t (i * s + 1 + j)) | j <- [0 .. l - 1] ])