SHA-1 broken, says Schneier

2005-02-16 Thread Andy Isaacson
From Bruce Schneier's weblog:
http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

# SHA-1 has been broken. Not a reduced-round version. Not a simplified
# version. The real thing.
# 
# The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly
# from Shandong University in China) have been quietly circulating a paper
# announcing their results:
# 
# * collisions in the the full SHA-1 in 2**69 hash operations, much
# * less than the brute-force attack of 2**80 operations based on the
# * hash length.
# 
# * collisions in SHA-0 in 2**39 operations.
# 
# * collisions in 58-round SHA-1 in 2**33 operations.
# 
# This attack builds on previous attacks on SHA-0 and SHA-1, and is a
# major, major cryptanalytic result. This pretty much puts a bullet into
# SHA-1 as a hash function for digital signatures (although it doesn't
# affect applications such as HMAC).
# 
# The paper isn't generally available yet. At this point I can't tell if
# the attack is real, but the paper looks good and this is a reputable
# research team.

This appears to be the same research team that published the MD5
collision technique back in August.

-andy

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


Re: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate software releases

2004-04-14 Thread Andy Isaacson
On Mon, Apr 12, 2004 at 06:00:26PM -0700, Joseph Ashwood wrote:
  From: Nicko van Someren [EMAIL PROTECTED]
 
  It's not clear to me that you need all this complexity.  All you need
  if to arrange that the attacker does not know exactly what will be
  signed until it has been signed.  So you append some randomness from a
  good random number source to the end of the file just before you sign
  it, and you're safe.
 
 I'm not quite sure that's a good solution, that random tail provides exactly
 what the attacker needs to make this as easy as possible. Since the random
 tail cannot be know beforehand it cannot be known by the user of the patch.
 If anything this would actually make an attack easier. It is only if the
 random data is from a _bad_ random source that you might actually gain some
 security (a bad source would at the very least have redundancy, internal or
 external, that could be verified by the end user, making it more complex to
 compute valid numbers). Instead it would probably be more useful to include
 the same random number between each file, this should short circuit all but
 the most fatal of hash flaws, but might open up other possibilities (I don't
 have the time right now to prove things about it).

You and Nicko are discussing different attacks.

One attack is Find two patches which have the same MD5.  This falls to
a birthday-paradox attack with 2^64 work, and is somewhat easier if the
patch format includes a random tail.  (The collision attack needs 64
bits of controllable input in the message.)  Short of a compromise of the
developer's machine, it's hard to see how this type of hash collision can
be leveraged into getting a malicious patch distributed as genuine.

Another attack is Submit a carefully sculpted change through normal
channels which results in the new patch having an attacker-determined
hash value.  The work factor is somewhat difficult to estimate, but is
probably a significant multiple higher than 2^64, primarily due to the
more-complex iterator due to having to emulate the workflow of the
developer when computing hash values.  In this attack, the assumption is
that the attacker submits a diff (a very innocuous one, but with a
special structure), which is integrated, and the result is a (binary)
patch which is signed by the developer.  The attacker was able to craft
the diff so as to cause MD5(patchA) to match MD5(patchB) and then
distributes patchB with the signature from patchA.

This second attack is made infeasible by simply appending 64 bits of
randomness to the patch before signing it.  Since the attacker could not
possibly know those bits, so his work required increases by a *power* (I
believe -- haven't done the math carefully) of 64.

These are straightforward extensions of Van Oorschot  Wiener's 1994
paper Parallel Collision Search with Application to Hash Functions and
Discrete Logarithms.

The obvious conclusion is that nobody should be using MD5 any more;
follow the OpenBSD project's lead and distribute SHA1 alongside your MD5
distribution.  Or SHA-256 if you're really paranoid.

 On a related note does anyone happen to know of any useful papers on
 patching, specifically patch integrity/source verification?

I don't see how this is any different from the generic source validation
problem.

-andy

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


Re: New toy: SSLbar

2003-06-25 Thread Andy Isaacson
On Wed, Jun 25, 2003 at 12:02:39PM +0100, Pete Chown wrote:
 On the other hand, once a back door is installed in binary-only 
 software, it is much less likely to be found.  The Interbase back door 
 was only found when the source was opened.

I doubt the truth of this statement.  Certainly, the back door was only
published after the source was opened.  But, just as Matt Blaze found
out when he published his attack on pin-and-tumbler locks, fields other
than computer security do not have a culture of public disclosure.  In
all likelihood the Interbase back door was discovered and carefully
promulgated among the gray- and black-hat communities interested in that
product.

Closed-source is not much of a guarantee in the face of a determined
attacker.  Or in the face of a large number of capable, interconnected,
curious hackers (in the traditional sense of the word).

-andy

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