Cryptography Reference
In-Depth Information
be protected against their own predictable routine behavior and what that
behavior may reveal to an interested observer.
The sensing contraption was built to measure the electromagnetic
leakage of a specific type of cryptographic algorithms: hash functions.
2
A
fundamental element of the modern cryptographer's toolbox, crypto-
graphic hash functions are essential to the efficiency and security of RSA
digital signatures (see “The Early History” in chapter 4) but are also used
in software protection, version control systems, and identification pro-
tocols. Because of the very high speed such constructions can achieve, the
most widespread hash functions are built according to principles similar
to those of DES, using repeated rounds of basic “bit shaking” operations
of confusion and diffusion.
The efficiency benefits of such functions come with a significant disad-
vantage however. In contrast to public-key algorithms, “It is difficult to say
something concrete about the security of a hash function such as MD4
since it is not 'based' on a well-studied problem such as factoring or the
Discrete Log problem. So, as is the case with DES, confidence in the security
of the system can only be attained over time, as the system is studied and
(one hopes) not found to be insecure.”
3
Indeed, although hash functions
based on number-theoretic problems would be much more amenable to
the mathematical formalization necessary for analysis under the provable
security framework, efforts in that direction have to date mostly resulted
in “an embarrassing history of insecure proposals.”
4
The sensing apparatus depicted in figure 7.1 thus points to what are
perhaps surprising dimensions of the relationship between mathematics
and computing. On the one hand, although mathematical theorems do
not consume energy or leak radiation, their embodiment as algorithms
performed on computers do. On the other hand, there are computer algo-
rithms that have no (elegant and interesting) mathematical representa-
tions and, consequently, about which little can be proven. Thus, though
common references to computers as “universal Turing machines” suggest
they are intimately, fundamentally, mathematical objects, the relationship
is considerably more complex and open-ended than it might appear at first
glance.
5
In this chapter, I explore some of the ways in which the relationship
has been realized in cryptographic models. I begin this exploration with
an account of a controversy familiar to researchers in the field, that
