BAT security evaluations

eBATS (ECRYPT Benchmarking of Asymmetric Systems) is a competition for the most efficient public-key systems.

Do users want the smallest, fastest cryptosystems? Not exactly. Users want the smallest, fastest cryptosystems that provide an acceptable security level. There's a tradeoff between security and efficiency: one can reduce time and space by reducing security level.

eBATS measures the time and space consumed by various BATs (Benchmarkable Asymmetric Tools). Users comparing these measurements also want to compare security levels, so BATs are encouraged to document security levels.

BATs can be submitted without security documentation. It's better to have benchmarks first, and figure out the security level later, than to have no benchmarks at all. But do keep in mind that security documentation is important: if you leave it out at first, please try to include it as soon as you can.

BATs can be submitted with rough estimates of security levels. It's better to have rough estimates first, and to have more accurate estimates later, than to have no estimates at all. Sometimes rough estimates are enough to show that one system is considerably more secure than another system with similar efficiency. But sometimes systems are close: please point out (in documentation.pdf) any troublesome points in your estimates, and please try to improve your estimates as soon as you can.

BAT security evaluations should not worry about future improvements in attack methods. We all know that security levels are merely conjectures, and that improved attacks may reduce a system from an acceptable security level to an unacceptable security level. Security evaluations should assume that attackers are limited to today's best attack algorithms.

BAT security evaluations should not worry about future improvements in costs for electronics. We all know that improvements in computer technology are making computations less expensive. Security evaluations should assume that attackers will incur today's costs for computation.

Final BAT security estimates must account for massively parallel computation. This means not just many computers working simultaneously, but also many chips working simultaneously inside one computer, and many computations working simultaneously inside one chip.

With 1000 euros, for example, an attacker can build a computer with several 110-euro FPGAs, each of which can handle 12 parallel high-speed ECM computations using a recently published ECM circuit. This computer is much more cost-effective than a typical Athlon 64 X2 workstation carrying out just two parallel high-speed ECM computations for the same price. Well-funded attackers can do even better with ASICs instead of FPGAs. Of course, computations benefit much less from parallelism if they rely on frequent random access to large amounts of storage.

Don't be afraid to add a note to documentation.pdf asking for help in evaluating attack costs. The SHARCS (Special-purpose Hardware for Attacking Cryptographic Systems) workshops in 2005 and 2006 have featured talks from many people analyzing the cost of cryptanalytic computations.

BAT security estimates against timing attacks must account for high-capacity timing channels. Delaying results until a constant time doesn't stop all timing attacks; for example, hyperthreading attacks see the time for each memory access. A return value of 0 from timingattacks is a strong statement. On the other hand, the distinguishingchance, forgerychance, and cdhchance functions are free to assume that timing is not visible to attackers; many cryptographic applications are offline applications that don't reveal timing to attackers.


This is version 2006.06.14 of the eBATS security-evaluations.html web page. This web page is in the public domain.