Re: Blowfish Sign Extension implementation risk

From: Thomas Pornin (pornin_at_nerim.net)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 07:38:35 +0000 (UTC)

According to David Wagner <daw-usenet@taverner.cs.berkeley.edu>:
> What if we could design a totally new cipher intended to be more
> resilient against implementation errors -- what might it look like?

Usual approach is to specify the algorithm in a computer-understandable
format and let some sort of compiler turn that into source code.
The description must then be high-level enough to be close to the
mathematical description, and yet give enough information to the
compiler so that a not-too-bad implementation can be produced on a wide
range of architectures.

Some people work on proofs of program correctness: these are automatic
tools that analyze source code in some language, and establish formally
that the source code complies with a formal description such as the
one described above (or point out bugs). Last I heard of it, it can be
made to work quite effectively with some languages (mostly Lisp-like or
SML-like); with more low-level languages like C, there is still some
work to do.

The main problems with that approach are:
-- it has trouble working with some low-level languages, especially
assembly;
-- most smartest optimizations make proofs extremely difficult(*);
-- the problem of correctness is only moved to the problem of making
sure that the program used to verify the proof is itself correct(**).

Needless to say, out-of-shelf tools to generate or verify such proofs
are not yet available(***).

> Are there any generally useful techniques?

As for cryptographic algorithms, one could try to design the algorithm
such that it uses only operations which:
-- can be implemented straightforwardly
-- are unlikely to be implemented in a way which fails rarely

One such design is RC4: it is very simple, and if you get it wrong at
some point, things will diverge very fast. One main reason is that it
uses only 8-bit arithmetics; thus, if an implementation has a bug, that
bug will occur with probability at least 1/256 (well... hopefully). At
the other extreme, try DFC: that algorithm was an AES candidate, and it
used an "a*x+b" transform, where a, b and x were 64-bit values, and the
number obtained was first reduced modulo 2^64+13, then reduced further
modulo 2^64. The reduction was hard to implement correctly if one wanted
speed (no time for a true division) and it was very easy to make bugs
which occurred only once every 2^64 operations or so. Test vectors can
hardly detect that.

Using only simple operations which cannot fail rarely tend to rule out
complex operations such as multiplications, and even 32-bit additions
(carry propagation can be a bit complex with hardware, and thus may
induce faults which occur rarely). The AES is probably quite resilient
to faulty implementations (such implementations are likely to be
detected early with a few test vectors).

        --Thomas Pornin

(*) That is a tautology: if an optimization is simple enough to be
understood by a verifier, it can probably be applied by a compiler
and is not deemed "smart".

(**) To be fair, the same problem exists with all languages other
that straight assembly: the compiler has to produced correct code
from a correct source. And the hardware may fail, too.

(***) If you want to take a look at how far you can go (or more
precisely how far you can fail to go) on the road of verifiability,
see: http://tunes.org/
In brief, ten years of research have lead to a web site, a draft
specification and tons of sentences like: "Reflection is a deep
technical benefit, but also a deep psycho-social requirement, that
allows individual progress despite historical choices by evolution of
the conceptual infrastructure, and community progress despite variety of
individual and unshared backgrounds by unification of infrastructures."

Relevant Pages

  • Re: Algorithms to generate permutations
    ... >>The position on algorithm design, ... > I claim that my government should not insist ... Would this have forced a US national competition? ...
    (sci.crypt)
  • Re: Motion control and RELATIVE position problem
    ... You should be able to wade through the software and figure out how to provide the algorithm with an absolute command instead of a relative command. ... I think Tim Wescott has published a PID algorithm in the past that is relatively easy to port to PICs, ... Partially this is because it's heavily optimized, and the PIC is not amenable to fast, well-structured C code, but partially it's because (in my humble opinion) the guy writing the code didn't really pay attention to maintainability. ... And lest I start a flame war: These are just my opinions, and I may design a PIC into a product tomorrow. ...
    (sci.engr.control)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... and Richard made it clear that he understands the order ... >> of evaluation of a for loop. ... > using strlen but using an Oalgorithm when there is a trivial O ... >> In most other languages the terminating ...
    (comp.programming)
  • Re: Implement ARM cores on a FPGA chip?
    ... directly using FPGA fabrics seems to be the only promising solution. ... Martin indicated that if your algorithm is amenable to breaking it ... to partition your design. ... processing elements are designed for a particular task so that it can ...
    (comp.arch.fpga)
  • Re: Encryption key changing the encryption logic.
    ... >>decides among various elementary crypto operations based on what it sees ... >>adversary knows which key bits select which algorithm and, in practice, N ... > or two rounds of a different block cipher. ... this design is covered under the 1-of-N discussion and your design is ...
    (sci.crypt)