Random ladder for public-key encryption

Question

{-
| Copyright 2022 Pierre Abbat
* RandomLadder
This module performs a public-key encryption operation, such as modulo
exponentiation or elliptic curve scalar multiplication, in a way that makes it
difficult for an attacker to determine the exponent or multiplier by listening
to a side channel. Rather than performing the operation in a constant time
regardless of the bits, as is done in imperative languages such as C and Rust,
it randomizes the sequence of operations, dividing the number by 2 or 3 at random,
so that the same number can result in different sequences of operations and
the same sequence of operations can result from different numbers.
-}
module Cryptography.RandomLadder
    ( ladderBitsNeeded
    , randomLadder
    ) where
import qualified Data.Sequence as Seq
import Data.Sequence ((><), (<|), (|>), Seq((:<|)), Seq((:|>)))

ladderBitsNeeded :: Int -- ^ The number of bits in the exponent/multiplier.
  -> Int -- ^ The number of bits in range for randomLadder.
ladderBitsNeeded n = round ((fromIntegral n) * 0.78788506 + 9.331)
-- 0.78788506 is (log (644/373))/(log 2),
-- which is pretty close to (log (644/271))/(log 3).
-- 9.331 is (log 644)/(log 2),
-- which allows the last bit to be split close to 373|271.

makeLadder :: Integer -> Integer -> Integer -> Seq.Seq Int
-- makeLadder n random range -> sequence-of-instructions
-- range should be at least n**0.78788506
-- random should be in [0..range)
-- n should be nonnegative
makeLadder (-1) _ _ = error "negative multiplier/exponent"
makeLadder 0 _ _ = Seq.empty
makeLadder 1 _ _ = Seq.singleton 21
makeLadder 2 _ _ = Seq.singleton 32
makeLadder n random range =
  let crit = (range * 373 + 322) `div` 644
      (quo2,rem2) = n `divMod` 2
      (quo3,rem3) = n `divMod` 3
  in if random >= crit
    then let third = makeLadder quo3 (random - crit) (range - crit)
    in
      if rem3 == 0
      then 30 <| third
      else
        if rem3 == 1
        then 31 <| third
        else 32 <| third
    else let half = makeLadder quo2 random crit
    in
      if rem2 == 0
      then 20 <| half
      else 21 <| half

climbLadder :: Seq.Seq Int -> a -> a -> (a -> a -> a) -> a -> a
climbLadder Seq.Empty _ _ _ acc = acc
climbLadder (is :|> 20) gen gen2 (<+>) acc =
  climbLadder is gen gen2 (<+>) (acc <+> acc)
climbLadder (is :|> 21) gen gen2 (<+>) acc =
  climbLadder is gen gen2 (<+>) ((acc <+> acc) <+> gen)
climbLadder (is :|> 30) gen gen2 (<+>) acc =
  climbLadder is gen gen2 (<+>) (acc <+> acc <+> acc)
climbLadder (is :|> 31) gen gen2 (<+>) acc =
  climbLadder is gen gen2 (<+>) ((acc <+> acc <+> acc) <+> gen)
climbLadder (is :|> 32) gen gen2 (<+>) acc =
  climbLadder is gen gen2 (<+>) ((acc <+> acc <+> acc) <+> gen2)

-- | For example, (randomLadder 3 (*) 1 17 8388608 16777216) = 129140163.
-- The number 8388608 determines the sequence of squaring and cubing, but
-- the final result, which is 3^17, does not depend on it.
randomLadder :: a -- ^ The generator of the group, the point being multiplied or the base of exponentiation.
  -> (a -> a -> a) -- ^ The group operation.
  -> a -- ^ The identity element.
  -> Integer -- ^ The exponent or multiplier (must be nonnegative).
  -> Integer -- ^ A random number in [0..range).
  -> Integer -- ^ The range of the random number.
  -> a -- ^ The result of exponentiation or scalar multiplication.
randomLadder gen (<+>) zero n random range =
  climbLadder (makeLadder n random range) gen (gen <+> gen) (<+>) zero

I've run this code with (+) and (*) as the operation, and it works correctly. I haven't tried big-number modulo exponentiation or elliptic curve point multiplication.

I'm new to Haddock and couldn't figure out how to comment the whole module. I'd like to know how clear the code and comments are and also if it would actually foil side-channel attacks.

My code assumes that (<+>) works correctly in expressions like g<+>g, g<+>(-g), and g<+>0, as well as g<+>h where g and h are unrelated. Is this true of actual elliptic-curve implementations?

Code is available on GitHub.

Answer 1

I'm new to Haddock and couldn't figure out how to comment the whole module.

I think the problem is that the module description needs to have some internal structure. See here

I'd like to know how clear the code and comments

The code seems kinda dense. Maybe it's just that I don't understand it and have context, so my eyes inevitably bounce off, I'm not sure. Trying to articulate how I'd make it easier to read, I'd say you're not using newlines and indentation in a way that forefronts the code's structure. For example, the then and else clauses should always be indented more than the controlling if. I also suspect you could improve clarity by using where clauses for a lot of stuff.

As for the comments,

• More consistency would be good. climbLadder has no comments, and makeLadder has a comment but it's not a Haddock comment. Maybe that's on purpose; which would be fine.
• The first things to document about a function are what it's for and how it's used. (How it works may also be commented, but doesn't usually belong in Haddock documentation). randomLadder appears to be the meat of the module, so its documentation should say those two things succinctly upfront. Including an example is often good, but again, try putting it in the format of "in order to do X, write Y".

I'd like to know [...] if it would actually foil side-channel attacks

I haven't worked with the kind of cryptography you're doing here, and have made almost no effort to unpack the math that's relevant here or how your code works, but my intuition is that the strategy of "randomize the sequence of operations, dividing the number by 2 or 3 at random, so that the same number can result in different sequences of operations and the same sequence of operations can result from different numbers" would not be accepted in modern cryptography, at least not without an analysis of how good the protection really was.

The basic problem is that, supposing a relevant side-channel exists, in order for this to provide perfect security, every possible sequence of operations would need to have the same probability of resulting from any possible number, and visa-versa. Anything short of that will leak some information about the number through the side-channel. If you did meet that standard, then I fail to see how this would be better than a constant-time strategy. Alternately, you could quantify the leakage and prove an upper bound for it, in which case your code should have a clearly labeled security parameter and some discussion of how to set it (and your algorithm and proof are probably appropriate for academic publication).