[cap-talk] Dan Bernstein's qmail security lessons paper

[Sandro Magi]

David Wagner wrote:
> 
> That doesn't sound right to me.  Generally bignum libraries support
> "integer arithmetic".  The larger the integer you try to operate on,
> the greater the time and space it takes to complete the operation.
> Some operations on large integers may not complete in a timely manner,
> or may not complete successfully at all (e.g., because they threw a
> OutOfMemory exception).  But that's different in an important way from
> saying that they use modular arithmetic. 

I say there's no semantic difference at all. Consider the signature of
addition for register-sized integers:

val (+): int -> int -> int

This is really a partial function, since it could overflow. We can make
it total as follows:

type Result = Overflow | Success of int
val (+): int -> int -> Result

Consider now BigInt addition:

val (+): BigInt -> BigInt -> BigInt

But this too is a partial function on any realizable machine, as we
could exhaust memory trying to compute it. We can make this addition
function total as follows:

type Result = OutOfMemory | Success of BigInt
val (+): BigInt -> BigInt -> Result

There is an striking symmetry here, and I say that semantically, the
signature of addition is really the same:

type Result = ResourcesExhausted | Success of int
val (+): int -> int -> Result

Overflow is a type of resource exhaustion, or contrarily, memory limits
place an overflow bound on BigInt. Any computable integer conforms to
this semantics. True arbitrary precision integers can only be used in
symbolic computations where they are not realized.

Further, that addition signature is total, so clients *must* deal with
overflow/resource exhaustion, regardless of the underlying implementation.

Sandro