Cipher Book Review, Issue E162

The Theory of Hash Functions and Random Oracles: An Approach to Modern Cryptography
by Arno Mittelbach and Marc Fischlin

Springer Verlag 2021.
First edition, February 2021 ISBN-13: ISBN 978-3-030-63286-1 ISBN 978-3-030-63287-8 (eBook) 798 pages

Reviewed by  Sven Dietrich   07/20/2021 

Are you looking for some light summer reading in these interesting times? Why not consider some hash functions and random oracles for a little twist? Cryptocurrencies are all the rage these days, and their Proofs-of-Work and Proofs-of-Stake are built on hash functions and random oracles.

In 798 pages, Arno Mittelbach and Marc Fischlin provide a great introduction to these narrow(er) topic areas of hash functions and random oracles, two fascinating areas that underlie modern cryptography and other related domains. While this book is not a self-contained cryptography book, it is an in-depth treatise on these two specific areas, giving a solid background in hash functions and at least one of the possible supporting constructs, random oracles. One should note that the hash function controversy started in 2005 with the breaking of fundamental hash function families (e.g. MD5), and eventually led to the creation of the SHA-3 'Keccak' hash function via a global and public effort, which is in use today.

The book covers its titular topics well, splitting them into three major parts: Part I covers Modern Cryptography, Part II discusses Random Oracles, and Part III's grand finale explains Hash Function constructions. There are suggestions for rounding off the rough edges, namely finding textbooks that provide basic knowledge where this book does not, but that only adds to the strength of this book. Each chapter in the three parts contains Chapter Notes and References, Exercises, and a Chapter Bibliography, which allow the reader to go deeper in their discovery.

The first part on Modern Cryptography provides for a quick on-ramp for just the basics. It contains six chapters (not counting the introductory one), covering everything from computability theory, one-way functions, hash functions, and pseudorandomness, and closing with non-cryptographic hash functions. The chapter list is 'Computational Security', 'Pseudorandomness and Computational Indistinguishability', 'Collision Resistance', 'Encryption Schemes', 'Signature Schemes', and 'Non-cryptographic Hashing.'

The second part discusses 'The Random Oracle Methodology' in five chapters. Here the reader learns about one of the basic tools for hash function construction (and for other applications), 'The Random Oracle Model', an important construct in cryptography. The further chapters are 'The Full Power of Random Oracles' with some examples from the literature and applications to blockchain and Proof-of-Work, 'Random Oracle Schemes in Practice' including OAEP for the practitioners among us, some 'Limitations of Random Oracles' for examples applied to key exchanges, and wrapping up with the 'The Random Oracle Controversy' talking about the Random Oracle Uninstantiability.

The third part covers 'Hash Function Constructions' in six chapters. Now equipped with all the necessary theoretical tools (and practical considerations), the reader learns about 'Iterated Hash Functions' including the classical Merkle-Damgard hash function construction, attacks on various hash function schemes, as well as cryptographic sponges, followed by ways of 'Constructing Compression Functions' from various primitives, the catch of 'Iterated Hash Functions in Practice' with the MD5, SHA-1, SHA-2, and SHA-3 hash functions on full display, adding a critical security application with 'Constructions of Keyed Hash Functions' (e.g. improving existing hash functions by keying), the issue of indifferentiability in 'Constructing Random Oracles - Indifferentiability', and wrapping up with Universal Computational Extractors as a way of constructing hash functions in 'Constructing Random Oracles - UCEs.'

Arno Mittelbach and Marc Fischlin did a good job at producing this book with a collection of ideas on the Theory of Hash Functions and Random Oracles, focusing in-depth on these two areas enabling the student, the practitioner, and the researcher, to deepen their knowledge. The book is a great add-on for a modern cryptography course or for 'light summer reading' for those interested in learning more about these two topics.


Sven Dietrich reviews technology and security books for IEEE Cipher. He welcomes your thoughts at spock at ieee dot org