Â鶹ÊÓƵ

Conference Papers (Selected)

• Compare-by-Hash: A Reasoned Analysis
  John Black

  A paper by Henson criticized the practice of comparing files for equality by comparing their hash digests using a cryptographic hash function. Our paper rebuts her criticisms on several fronts, and offers advice for those planning on employing hash functions in this way.

  This paper appeared in USENIX Annual Technical Conference--Systems and Experience Track, USENIX 2006, Boston, MA, USA, 2006.

• The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function
  John Black

  A series of results are known regarding schemes in the Random-Oracle Model which are "uninstantiable." In other words, schemes which have proofs of security in the Random-Oracle Model but fail to be secure when the oracle is replaced by any concrete function. A natural question arises, are there analogous results in the Ideal-Cipher Model.

  We answer this question in the affirmative, showing a blockcipher-based hash function that is provably secure in the Ideal-Cipher Model, but becomes trivially insecure when the Ideal Cipher is replaced by any blockcipher.

  This paper appeared in Fast Software Encryption -- FSE 2006, Graz, Austria, Mar 2006.

• A Study of the MD5 Attacks: Insights and Improvements 
  John Black, Martin Cochran, and Trevor Highland

  MD5 is a well-known and widely-used cryptographic hash function. It has received renewed attention from researchers subsequent to the recent announcement of collisions found by Wang et al. To date, however, understanding the method used by researchers in this work has been fairly difficult to grasp. In this paper we conduct a study of all attacks on MD5 starting from Wang. We explain the techniques used by her team, give insights on how to improve these techniques, and use these insights to produce an even faster attack on MD5. Additionally, we provide an "MD5 Toolkit" implementing these improvements that we hope will serve as an open-source platform for further research. Our hope is that a better understanding of these attacks will lead to a better understanding of our current collection of hash functions, what their strengths and weaknesses are, and where we should direct future efforts in order to produce even stronger primitives.

  A condensed version of this report appeared in Fast Software Encryption -- FSE 2006, Graz, Austria, Mar 2006.

• An Analysis of the Internet Chess Club
  John Black, Martin Cochran, and Ryan Gardner

  The Internet Chess Club (ICC) is a popular online chess server with more than 30,000 members worldwide including various celebrities and the best chess players in the world. Although the ICC website assures its users that the security protocol used between client and server provides sufficient security for sensitive information to be transmitted (such as credit card numbers), we show this is not true. In particular we show how a passive adversary can easily read all communications with a trivial amount of computation, and how an active adversary can gain virtually unlimited powers over an ICC user. We also show simple methods for defeating the timestamping mechanism used by ICC. For each problem we uncover, we suggest repairs. Most of these are practical and inexpensive.

  A version of this report appeared in IEEE Security and Privacy Magazine, January 2006.
  Another version appeared in the Annual Computer Security Applications Conference--ACSAC 2005, Tucson, AZ, USA, 2005.

• On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
  John Black, Martin Cochran, and Thomas Shrimpton

  Fix a set of keys K. If we build an iterated hash function from any blockcipher whose keys are restricted to K, can this hash function be provably collision-resistant in the ideal cipher model? We answer this question in the negative giving a general information-theoretic attack. We also examine applications to the Tweak Chain Hash (TCH) of Liskov, Rivest, and Wagner and show that TCH cannot be secure under instantiations given in that paper.

  Appeared at Advances in Cryptology -- EUROCRYPT '05, Aarhus, Denmark, 2005.

• Encryption-Scheme Security in the Presence of Key-Dependent Messages
  John Black, Phillip Rogaway, and Thomas Shrimpton

  Is it safe to encrypt and transmit keys? We introduce the notion of key-dependent security and give a symmetric scheme which satisfies the definition and analyze this scheme in the random oracle model.

  Appeared at Selected Areas in Cryptography -- SAC '02, St. John's, Newfoundland, Canada, 2002.

• Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV 
  John Black, Phillip Rogaway, and Thomas Shrimpton

  Preneel, Govaerts, and Vandewalle presented an attack-based analysis of 64 natural ways to make a cryptographic hash function from a block cipher. We revisit their work from a different vantage point and attempt to prove the security of the constructions or demonstrate their insecurity. We show that 20 of the 64 schemes are secure (ie, it is hard to find collisions or to invert a random range point). Proofs are done in the Black-Box Model against information-theoretic adversaries.

  Appeared at Advances in Cryptology -- CRYPTO '02, Santa Barbara, CA, USA, 2002.

• Side-Channel Attacks on Symmetric Encryption Schemes: The Case for Authenticated Encryption
  John Black and Hector Urtubia

  Following an idea of Vaudenay, we consider side-channel attacks based on having an oracle which indicates whether the underlying padding is done correctly or not. We examine several popular and natural padding schemes and show that, under CBC mode encryption, they all succumb to an attack which efficiently recovers the plaintext. We then extend our results to other encryption modes and other side-channels culminating in a recommendation for authenticated encryption as the "proper" notion for symmetric encryption.

  Appeared at 11th USENIX Security Symposium -- USENIX Security '02, San Francisco, USA, 2002.

• A Block-Cipher Mode of Operation for Parallelizable Message Authentication
  John Black and Phillip Rogaway

  PMAC is a new mode of operation for AES (or any block cipher) to provide fast, parallelizable, and provably-secure message authentication. For a sketch on how PMAC works, visit the .

  Appeared at Advances in Cryptology -- EUROCRYPT '02, Amsterdam, The Netherlands, 2002.

• Ciphers with Arbitrary Finite Domains
  John Black and Phillip Rogaway

  This paper seeks to generate a cipher which works on members taken from an arbitrary finite set. We introduce three methods. The first shows a simple way to encipher the set {0,...,k-1}: we simply encipher these points (using a standard block cipher) and order the outputs. The second enciphers {0,...,k-1} by using a standard block cipher to encipher {0,...,N-1} where N is the next largest power of 2 beyond k; if the encipherment is >= k, we iterate until it is not. The final method uses a variant of the Luby-Rackoff construction and is the most complicated. The security of all methods are rigorously proven.

  Appeared at RSA Data Security Conference, Cryptographer's Track (RSA CT '02), San Jose, CA, USA, 2002.

• 
  Phillip Rogaway, Mihir Bellare, John Black, and Ted Krovetz

  OCB is a new mode of operation for AES (or any block cipher) to provide fast, parallelizable, and provably-secure encryption and message authentication. (PMAC, listed above, provides only the latter.) For a sketch on how OCB works, visit the .

  Appeared at ACM Conference on Computer and Communications Security (CCS '01), Philadelphia, PA, USA, 2001.

• A Suggestion on Handling Arbitrary-Length Messages with the CBC MAC
  John Black and Phillip Rogaway

  This short document recommends the use of the XCBC construction from CRYPTO 2000 as the CBC MAC variant of choice for a standard AES mode of operation. It accepts any message length, has proven security, and is patent-free.

  Appeared at the NIST Symmetric Key Block Cipher Modes of Operation Workshop, Baltimore, MD, 2000.

• 
  John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz and Phillip Rogaway

  We develop the fastest MAC yet devised. Following the Carter-Wegman method, we develop a very fast computer-friendly hash function called NH. NH runs fast on all computers and very fast on SIMD processors such as the Intel Pentium or Motorola Altivec. We then build a full-fledged MAC on top of NH, using several invocations with a Toeplitz shift to decrease the collision rate. The security of the end-product, called UMAC, is rigorously proven in the paper.

  Following the link above will bring you to the UMAC web page; available there are the paper, the spec, and full source code.

  Appeared at Advances in Cryptology -- CRYPTO '99, Santa Barbara, CA, USA, 1999.

• Graph and Hashing Algorithms for Modern Architectures: An Experimental Approach
  John Black, Charles Martel, and Hongbin Qi

  We investigate the performance of various data structures on contemporary architectures, paying particular attention to cache performance. We examine BFS and DFS on small to medium sized random graphs, using various tricks to enhance performance. We also investigate various collision resolution policies for hash tables.

  Appeared at Workshop for Algorithm Engineering (WAE '98), Saarbruecken, Germany, 1998. 

Journal Papers

• The Impossibility of Technology-Based DRM and a Modest Suggestion 
  John Black

  This paper expresses our opinion that technology-based DRM is impossible and what should be done about it. We start off looking at the list of failures that technological solutions to the DRM problem have suffered from, then discuss some of the fundamental issues. Finally, we offer the suggestion that the content providers should perhaps start a media campaign rather than to try and pursue the issue through the courts. This paper is an outgrowth of my panel comments at the Silicon Flatirons Technology conference in 2003.

  Appeared in Journal on Telecommunications and High Technology Law, Volume 3, Issue 2, 2005.

• CBC MACs for Arbitrary Length Messages: The Three-Key Constructions
  John Black and Phillip Rogaway

  This paper starts with the basic CBC MAC. We first give a simpler proof for a variant called EMAC by treating it as an instance of the Carter-Wegman paradigm. We then extend the domain of EMAC (which requires all inputs be a multiple of the block length) to accept any message length, calling this method ECBC. We then incrementally improve ECBC to increase its performance (yielding FCBC and XCBC). The security of each construction is carefully analyzed.

  Appeared in the Journal of Cryptology, Volume 18, Number 2, pp 111-132.

• OCB: A Block-Cipher Mode of Operation for Efficient Authenticated Encryption 
  Phillip Rogaway, Mihir Bellare, and John Black

  We describe a parallelizable mode of operation for authenticity and privacy. OCB is aggressively optimized to a minimum of block-cipher calls, cheap offset calculations which are fast on virtually any computing platform, only one block-cipher key, and it requires only a nonce for initialization (as opposed to a random IV). More info can be found on the 

  Appeared in ACM Transactions on Information and System Security (TISSEC), Volume 6, Issue 3, August, 2003.

Surveys

• Cryptography
  John Black

  A brief introduction and overview of cryptography, focussing on just a few main areas. Written for UNESCO's  an on-line encyclopedia. Appeared March 2004.

• Authenticated Encryption
  John Black

  A survey of the methods for achieving authentication and encryption in the private-key setting. Includes generic composition as well as the several recently-invented methods that provide better efficiency.

  Appears as an entry in Springer's , 2005.

My Thesis

• Message Authentication Codes
  John Black (UC Davis, 2000)

  A gentle introduction to Message Authentication Codes (MACs). Examples, attacks, lots of formalism. Special emphasis on the Carter-Wegman style of MAC. Includes pieces of the UMAC and Three-Key papers, including some material not published anywhere else.