chacha

The ChaCha20 stream cipher (docs.ppad.tech/chacha).
git clone git://git.ppad.tech/chacha.git
Log | Files | Refs | README | LICENSE

ChaCha20.hs (11816B)


      1 {-# OPTIONS_HADDOCK prune #-}
      2 {-# LANGUAGE BangPatterns #-}
      3 {-# LANGUAGE MagicHash #-}
      4 {-# LANGUAGE RecordWildCards #-}
      5 {-# LANGUAGE UnboxedTuples #-}
      6 {-# LANGUAGE ViewPatterns #-}
      7 
      8 -- |
      9 -- Module: Crypto.Cipher.ChaCha20
     10 -- Copyright: (c) 2025 Jared Tobin
     11 -- License: MIT
     12 -- Maintainer: Jared Tobin <jared@ppad.tech>
     13 --
     14 -- A fast ChaCha20 implementation, as specified by
     15 -- [RFC 8439](https://datatracker.ietf.org/doc/html/rfc8439).
     16 
     17 module Crypto.Cipher.ChaCha20 (
     18     -- * ChaCha20 stream cipher
     19     cipher
     20 
     21     -- * ChaCha20 block function
     22   , block
     23 
     24     -- * Error information
     25   , Error(..)
     26 
     27     -- testing
     28   , ChaCha(..)
     29   , _chacha
     30   , _cipher
     31   , _parse_key
     32   , _parse_nonce
     33   , _quarter
     34   , _quarter_pure
     35   , _rounds
     36   ) where
     37 
     38 import Control.Monad.ST
     39 import qualified Crypto.Cipher.ChaCha20.Native as Native
     40 import qualified Data.Bits as B
     41 import Data.Bits ((.|.), (.<<.), (.^.))
     42 import qualified Data.ByteString as BS
     43 import qualified Data.ByteString.Builder as BSB
     44 import qualified Data.ByteString.Internal as BI
     45 import qualified Data.ByteString.Unsafe as BU
     46 import Control.Monad.Primitive (PrimMonad, PrimState)
     47 import Data.Foldable (for_)
     48 import qualified Data.Primitive.PrimArray as PA
     49 import Foreign.ForeignPtr
     50 import GHC.Exts
     51 import GHC.Word
     52 
     53 -- utils ----------------------------------------------------------------------
     54 
     55 -- keystroke saver
     56 fi :: (Integral a, Num b) => a -> b
     57 fi = fromIntegral
     58 {-# INLINE fi #-}
     59 
     60 -- parse strict ByteString in LE order to Word32 (verbatim from
     61 -- Data.Binary)
     62 unsafe_word32le :: BS.ByteString -> Word32
     63 unsafe_word32le s =
     64   (fi (s `BU.unsafeIndex` 3) `B.unsafeShiftL` 24) .|.
     65   (fi (s `BU.unsafeIndex` 2) `B.unsafeShiftL` 16) .|.
     66   (fi (s `BU.unsafeIndex` 1) `B.unsafeShiftL`  8) .|.
     67   (fi (s `BU.unsafeIndex` 0))
     68 {-# INLINE unsafe_word32le #-}
     69 
     70 data WSPair = WSPair
     71   {-# UNPACK #-} !Word32
     72   {-# UNPACK #-} !BS.ByteString
     73 
     74 -- variant of Data.ByteString.splitAt that behaves like an incremental
     75 -- Word32 parser
     76 unsafe_parseWsPair :: BS.ByteString -> WSPair
     77 unsafe_parseWsPair (BI.BS x l) =
     78   WSPair (unsafe_word32le (BI.BS x 4)) (BI.BS (plusForeignPtr x 4) (l - 4))
     79 {-# INLINE unsafe_parseWsPair #-}
     80 
     81 -- chacha quarter round -------------------------------------------------------
     82 
     83 -- RFC8439 2.2
     84 _quarter
     85   :: PrimMonad m
     86   => ChaCha (PrimState m)
     87   -> Int
     88   -> Int
     89   -> Int
     90   -> Int
     91   -> m ()
     92 _quarter (ChaCha m) i0 i1 i2 i3 = do
     93   !(W32# a) <- PA.readPrimArray m i0
     94   !(W32# b) <- PA.readPrimArray m i1
     95   !(W32# c) <- PA.readPrimArray m i2
     96   !(W32# d) <- PA.readPrimArray m i3
     97 
     98   let !(# a1, b1, c1, d1 #) = quarter# a b c d
     99 
    100   PA.writePrimArray m i0 (W32# a1)
    101   PA.writePrimArray m i1 (W32# b1)
    102   PA.writePrimArray m i2 (W32# c1)
    103   PA.writePrimArray m i3 (W32# d1)
    104 {-# INLINEABLE _quarter #-}
    105 
    106 _quarter_pure
    107   :: Word32 -> Word32 -> Word32 -> Word32 -> (Word32, Word32, Word32, Word32)
    108 _quarter_pure (W32# a) (W32# b) (W32# c) (W32# d) =
    109   let !(# a', b', c', d' #) = quarter# a b c d
    110   in  (W32# a', W32# b', W32# c', W32# d')
    111 {-# INLINE _quarter_pure #-}
    112 
    113 -- RFC8439 2.1
    114 quarter#
    115   :: Word32# -> Word32# -> Word32# -> Word32#
    116   -> (# Word32#, Word32#, Word32#, Word32# #)
    117 quarter# a b c d =
    118   let a0 = plusWord32# a b
    119       d0 = xorWord32# d a0
    120       d1 = rotateL# d0 16#
    121 
    122       c0 = plusWord32# c d1
    123       b0 = xorWord32# b c0
    124       b1 = rotateL# b0 12#
    125 
    126       a1 = plusWord32# a0 b1
    127       d2 = xorWord32# d1 a1
    128       d3 = rotateL# d2 8#
    129 
    130       c1 = plusWord32# c0 d3
    131       b2 = xorWord32# b1 c1
    132       b3 = rotateL# b2 7#
    133 
    134   in  (# a1, b3, c1, d3 #)
    135 {-# INLINE quarter# #-}
    136 
    137 rotateL# :: Word32# -> Int# -> Word32#
    138 rotateL# w i
    139   | isTrue# (i ==# 0#) = w
    140   | otherwise = wordToWord32# (
    141             ((word32ToWord# w) `uncheckedShiftL#` i)
    142       `or#` ((word32ToWord# w) `uncheckedShiftRL#` (32# -# i)))
    143 {-# INLINE rotateL# #-}
    144 
    145 -- key and nonce parsing ------------------------------------------------------
    146 
    147 data Key = Key {
    148     k0 :: {-# UNPACK #-} !Word32
    149   , k1 :: {-# UNPACK #-} !Word32
    150   , k2 :: {-# UNPACK #-} !Word32
    151   , k3 :: {-# UNPACK #-} !Word32
    152   , k4 :: {-# UNPACK #-} !Word32
    153   , k5 :: {-# UNPACK #-} !Word32
    154   , k6 :: {-# UNPACK #-} !Word32
    155   , k7 :: {-# UNPACK #-} !Word32
    156   }
    157   deriving Show
    158 
    159 -- parse strict 256-bit bytestring (length unchecked) to key
    160 _parse_key :: BS.ByteString -> Key
    161 _parse_key bs =
    162   let !(WSPair k0 t0) = unsafe_parseWsPair bs
    163       !(WSPair k1 t1) = unsafe_parseWsPair t0
    164       !(WSPair k2 t2) = unsafe_parseWsPair t1
    165       !(WSPair k3 t3) = unsafe_parseWsPair t2
    166       !(WSPair k4 t4) = unsafe_parseWsPair t3
    167       !(WSPair k5 t5) = unsafe_parseWsPair t4
    168       !(WSPair k6 t6) = unsafe_parseWsPair t5
    169       !(WSPair k7 t7) = unsafe_parseWsPair t6
    170   in  if   BS.null t7
    171       then Key {..}
    172       else error "ppad-chacha (_parse_key): internal error, bytes remaining"
    173 
    174 data Nonce = Nonce {
    175     n0 :: {-# UNPACK #-} !Word32
    176   , n1 :: {-# UNPACK #-} !Word32
    177   , n2 :: {-# UNPACK #-} !Word32
    178   }
    179   deriving Show
    180 
    181 -- parse strict 96-bit bytestring (length unchecked) to nonce
    182 _parse_nonce :: BS.ByteString -> Nonce
    183 _parse_nonce bs =
    184   let !(WSPair n0 t0) = unsafe_parseWsPair bs
    185       !(WSPair n1 t1) = unsafe_parseWsPair t0
    186       !(WSPair n2 t2) = unsafe_parseWsPair t1
    187   in  if   BS.null t2
    188       then Nonce {..}
    189       else error "ppad-chacha (_parse_nonce): internal error, bytes remaining"
    190 
    191 -- chacha20 block function ----------------------------------------------------
    192 
    193 newtype ChaCha s = ChaCha (PA.MutablePrimArray s Word32)
    194   deriving Eq
    195 
    196 _chacha
    197   :: PrimMonad m
    198   => Key
    199   -> Word32
    200   -> Nonce
    201   -> m (ChaCha (PrimState m))
    202 _chacha key counter nonce = do
    203   state <- _chacha_alloc
    204   _chacha_set state key counter nonce
    205   pure state
    206 
    207 -- allocate a new chacha state
    208 _chacha_alloc :: PrimMonad m => m (ChaCha (PrimState m))
    209 _chacha_alloc = fmap ChaCha (PA.newPrimArray 16)
    210 {-# INLINE _chacha_alloc #-}
    211 
    212 -- set the values of a chacha state
    213 _chacha_set
    214   :: PrimMonad m
    215   => ChaCha (PrimState m)
    216   -> Key
    217   -> Word32
    218   -> Nonce
    219   -> m ()
    220 _chacha_set (ChaCha arr) Key {..} counter Nonce {..}= do
    221   PA.writePrimArray arr 00 0x61707865
    222   PA.writePrimArray arr 01 0x3320646e
    223   PA.writePrimArray arr 02 0x79622d32
    224   PA.writePrimArray arr 03 0x6b206574
    225   PA.writePrimArray arr 04 k0
    226   PA.writePrimArray arr 05 k1
    227   PA.writePrimArray arr 06 k2
    228   PA.writePrimArray arr 07 k3
    229   PA.writePrimArray arr 08 k4
    230   PA.writePrimArray arr 09 k5
    231   PA.writePrimArray arr 10 k6
    232   PA.writePrimArray arr 11 k7
    233   PA.writePrimArray arr 12 counter
    234   PA.writePrimArray arr 13 n0
    235   PA.writePrimArray arr 14 n1
    236   PA.writePrimArray arr 15 n2
    237 {-# INLINEABLE _chacha_set #-}
    238 
    239 _chacha_counter
    240   :: PrimMonad m
    241   => ChaCha (PrimState m)
    242   -> Word32
    243   -> m ()
    244 _chacha_counter (ChaCha arr) counter =
    245   PA.writePrimArray arr 12 counter
    246 
    247 -- two full rounds (eight quarter rounds)
    248 _rounds :: PrimMonad m => ChaCha (PrimState m) -> m ()
    249 _rounds state = do
    250   _quarter state 00 04 08 12
    251   _quarter state 01 05 09 13
    252   _quarter state 02 06 10 14
    253   _quarter state 03 07 11 15
    254   _quarter state 00 05 10 15
    255   _quarter state 01 06 11 12
    256   _quarter state 02 07 08 13
    257   _quarter state 03 04 09 14
    258 {-# INLINEABLE _rounds #-}
    259 
    260 _block
    261   :: PrimMonad m
    262   => ChaCha (PrimState m)
    263   -> Word32
    264   -> m BS.ByteString
    265 _block state@(ChaCha s) counter = do
    266   _chacha_counter state counter
    267   i <- PA.freezePrimArray s 0 16
    268   for_ [1..10 :: Int] (const (_rounds state))
    269   for_ [0..15 :: Int] $ \idx -> do
    270     let iv = PA.indexPrimArray i idx
    271     sv <- PA.readPrimArray s idx
    272     PA.writePrimArray s idx (iv + sv)
    273   serialize state
    274 
    275 -- | Error values.
    276 data Error =
    277     CounterOverflow -- ^ the counter overflowed
    278   | InvalidKey      -- ^ the provided key was not 256 bits long
    279   | InvalidNonce    -- ^ the provided nonce was not 96 bits long
    280   deriving (Eq, Show)
    281 
    282 -- RFC8439 2.3
    283 
    284 -- | The ChaCha20 block function. Useful for generating a keystream.
    285 --
    286 --   Per [RFC8439](https://datatracker.ietf.org/doc/html/rfc8439), the
    287 --   key must be exactly 256 bits, and the nonce exactly 96 bits.
    288 block
    289   :: BS.ByteString    -- ^ 256-bit key
    290   -> Word32           -- ^ 32-bit counter
    291   -> BS.ByteString    -- ^ 96-bit nonce
    292   -> Either Error BS.ByteString    -- ^ 512-bit keystream
    293 block key@(BI.PS _ _ kl) counter nonce@(BI.PS _ _ nl)
    294   | kl /= 32 = Left InvalidKey
    295   | nl /= 12 = Left InvalidNonce
    296   | Native.chacha20_native_available =
    297       Right (Native.block key counter nonce)
    298   | otherwise = pure $ runST $ do
    299       let k = _parse_key key
    300           n = _parse_nonce nonce
    301       state@(ChaCha s) <- _chacha k counter n
    302       i <- PA.freezePrimArray s 0 16
    303       for_ [1..10 :: Int] (const (_rounds state))
    304       for_ [0..15 :: Int] $ \idx -> do
    305         let iv = PA.indexPrimArray i idx
    306         sv <- PA.readPrimArray s idx
    307         PA.writePrimArray s idx (iv + sv)
    308       serialize state
    309 
    310 serialize :: PrimMonad m => ChaCha (PrimState m) -> m BS.ByteString
    311 serialize (ChaCha m) = do
    312     w64_0 <- w64 <$> PA.readPrimArray m 00 <*> PA.readPrimArray m 01
    313     w64_1 <- w64 <$> PA.readPrimArray m 02 <*> PA.readPrimArray m 03
    314     w64_2 <- w64 <$> PA.readPrimArray m 04 <*> PA.readPrimArray m 05
    315     w64_3 <- w64 <$> PA.readPrimArray m 06 <*> PA.readPrimArray m 07
    316     w64_4 <- w64 <$> PA.readPrimArray m 08 <*> PA.readPrimArray m 09
    317     w64_5 <- w64 <$> PA.readPrimArray m 10 <*> PA.readPrimArray m 11
    318     w64_6 <- w64 <$> PA.readPrimArray m 12 <*> PA.readPrimArray m 13
    319     w64_7 <- w64 <$> PA.readPrimArray m 14 <*> PA.readPrimArray m 15
    320     pure . BS.toStrict . BSB.toLazyByteString . mconcat $
    321       [w64_0, w64_1, w64_2, w64_3, w64_4, w64_5, w64_6, w64_7]
    322   where
    323     w64 a b = BSB.word64LE (fi a .|. (fi b .<<. 32))
    324 
    325 -- chacha20 encryption --------------------------------------------------------
    326 
    327 -- RFC8439 2.4
    328 
    329 -- | The ChaCha20 stream cipher. Generates a keystream and then XOR's
    330 --   the supplied input with it; use it both to encrypt plaintext and
    331 --   decrypt ciphertext.
    332 --
    333 --   Per [RFC8439](https://datatracker.ietf.org/doc/html/rfc8439), the
    334 --   key must be exactly 256 bits, and the nonce exactly 96 bits.
    335 --
    336 --   >>> let key = "don't tell anyone my secret key!"
    337 --   >>> let non = "or my nonce!"
    338 --   >>> let Right cip = cipher key 1 non "but you can share the ciphertext"
    339 --   >>> cip
    340 --   "\192*c\248A\204\211n\130y8\197\146k\245\178Y\197=\180_\223\153\151+_\197\&6\SUBF\197\160"
    341 --   >>> cipher key 1 non cip
    342 --   Right "but you can share the ciphertext"
    343 cipher
    344   :: BS.ByteString    -- ^ 256-bit key
    345   -> Word32           -- ^ 32-bit counter
    346   -> BS.ByteString    -- ^ 96-bit nonce
    347   -> BS.ByteString    -- ^ arbitrary-length plaintext
    348   -> Either Error BS.ByteString    -- ^ ciphertext
    349 cipher
    350         raw_key@(BI.PS _ _ kl)
    351         counter
    352         raw_nonce@(BI.PS _ _ nl)
    353         plaintext@(BI.PS _ _ (fi -> pl))
    354     | kl /= 32  = Left InvalidKey
    355     | nl /= 12  = Left InvalidNonce
    356     | pl > room = Left CounterOverflow
    357     | Native.chacha20_native_available =
    358         Right (Native.cipher raw_key counter raw_nonce plaintext)
    359     | otherwise = pure $ runST $ do
    360         let key = _parse_key raw_key
    361             non = _parse_nonce raw_nonce
    362         _cipher key counter non plaintext
    363   where
    364     room = (0x100000000 - fi counter) * 64 :: Word64
    365 
    366 _cipher
    367   :: PrimMonad m
    368   => Key
    369   -> Word32
    370   -> Nonce
    371   -> BS.ByteString
    372   -> m BS.ByteString
    373 _cipher key counter nonce plaintext = do
    374   ChaCha initial <- _chacha key counter nonce
    375   state@(ChaCha s) <- _chacha_alloc
    376 
    377   let loop acc !j bs = case BS.splitAt 64 bs of
    378         (chunk@(BI.PS _ _ l), etc@(BI.PS _ _ le))
    379           | l == 0 && le == 0 -> pure $
    380               BS.toStrict (BSB.toLazyByteString acc)
    381           | otherwise -> do
    382               PA.copyMutablePrimArray s 0 initial 0 16
    383               stream <- _block state j
    384               let cip = BS.packZipWith (.^.) chunk stream
    385               loop (acc <> BSB.byteString cip) (j + 1) etc
    386 
    387   loop mempty counter plaintext
    388 {-# INLINE _cipher #-}
    389