Interesting papers on HMAC and NMAC

2006-07-10 Thread Perry E. Metzger

Steve Bellovin forwarded me the following links (which he got from
Eric Rescorla). Note the bit at the end about a path to second
preimage attacks:

  On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1

  Jongsung Kim and Alex Biryukov and Bart Preneel and Seokhie Hong

  Abstract. HMAC is a widely used message authentication code and a
  pseudorandom function generator based on cryptographic hash functions
  such as MD5 and SHA-1. It has been standardized by ANSI, IETF, ISO and
  NIST. HMAC is proved to be secure as long as the compression function
  of the underlying hash function is a pseudorandom function. In this
  paper we devise two new distinguishers of the structure of HMAC,
  called {\em differential} and {\em rectangle distinguishers}, and use
  them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0
  and SHA-1. We show how to distinguish HMAC with reduced or full
  versions of these cryptographic hash functions from a random function
  or from HMAC with a random function. We also show how to use our
  differential distinguisher to devise a forgery attack on HMAC. Our
  distinguishing and forgery attacks can also be mounted on NMAC based
  on HAVAL, MD4, MD5, SHA-0 and SHA-1. Furthermore, we show that our
  differential and rectangle distinguishers can lead to second-preimage
  attacks on HMAC and NMAC.

Also of interest, this somewhat earlier paper, which shows that HMAC
can be secure if the underlying hash is merely a pseudorandom function
even if it is not collision resistant:

  New Proofs for NMAC and HMAC: Security Without Collision-Resistance

  Mihir Bellare

  Abstract. HMAC was proved by Bellare, Canetti and Krawczyk [2] to be a
  PRF assuming that (1) the underlying compression function is a PRF,
  and (2) the iterated hash function is weakly
  collision-resistant. However, recent attacks show that assumption (2)
  is false for MD5 and SHA-1, removing the proof-based support for HMAC
  in these cases. This paper proves that HMAC is a PRF under the sole
  assumption that the compression function is a PRF. This recovers a
  proof based guarantee since no known attacks compromise the
  pseudorandomness of the compression function, and it also helps
  explain the resistance-to-attack that HMAC has shown even when
  implemented with hash functions whose (weak) collision resistance is
  compromised. We also show that an even weaker-than-PRF condition on
  the compression function, namely that it is a privacy-preserving MAC,
  suffices to establish HMAC is a MAC as long as the hash function meets
  the very weak requirement of being computationally almost universal,
  where again the value lies in the fact that known attacks do not
  invalidate the assumptions made. 

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

cryptanalysis of Galileo satellite navigation signals

2006-07-10 Thread Steven M. Bellovin
The EU Galileo navigation satellite uses a set of pseudo-random numbers to
secure access to its data.  Galileo is partially investor-funded; part of
the business model is to sell access to the data.  Some researchers at
Cornell took a different approach -- they cryptanalyzed the algorithm...
Better yet, they got an opinion from their university lawyer that the DMCA
didn't apply.  See
for details.

--Steven M. Bellovin,

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

RE: Factorization polynomially reducible to discrete log - known fact or not?

2006-07-10 Thread Charlie Kaufman
I believe this has been known for a long time, though I have never seen the 
proof. I could imagine constructing one based on quadratic sieve.

I believe that a proof that the discrete log problem is polynomially reducible 
to the factorization problem is much harder and more recent (as in sometime in 
the last 20 years). I've never seen that proof either.


-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Ondrej Mikle
Sent: Sunday, July 09, 2006 12:22 PM
Subject: Factorization polynomially reducible to discrete log - known fact or 


I believe I have the proof that factorization of N=p*q (p, q prime) is
polynomially reducible to discrete logarithm problem. Is it a known fact
or not? I searched for such proof, but only found that the two problems
are believed to be equivalent (i.e. no proof).

I still might have some error in the proof, so it needs to be checked by
someone yet. I'd like to know if it is already known (in that case there
would be no reason to bother with it).

   O. Mikle

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

NIST hash function design competition

2006-07-10 Thread Hal Finney
I was registering today for the Crypto conference and discovered that
immediately afterwards, and at the same site in Santa Barbara, CA, NIST
is holding a two-day workshop on hash function design.  The information
is here:

In response to the SHA-1 vulnerability that was announced in Feb. 2005,
NIST held a Cryptographic Hash Workshop on Oct. 31-Nov. 1, 2005 to solicit
public input on its cryptographic hash function policy and standards. NIST
continues to recommend a transition from SHA-1 to the larger approved
hash functions (SHA-224, SHA-256, SHA-384, and SHA-512). In response
to the workshop, NIST has also decided that it would be prudent in
the long-term to develop an additional hash function through a public
competition, similar to the development process for the block cipher in
the Advanced Encryption Standard (AES).

I had not heard that there had been an official decision to hold a new
competition for hash functions similar to AES.  That is very exciting!
The AES process was one of the most interesting events to have occured
in the last few years in our field.

Seemed like one of the lessons of that effort was that, even though it was
successful in terms of attracting the interest and hard work of some of
the top researchers in the field, in the end we have learned considerably
more about Rijndael's vulnerabilities only after the process was over.
Perhaps the intrinsic difficulty of cryptography makes this kind of outcome
inevitable.  But hopefully the hashing competition will learn from the AES
experience and make sure that it takes as much time as it needs to take.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]