Re: New toy: SSLbar

[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]

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

[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: SSL/TLS passive sniffing

[Andy Isaacson]

On Wed, Dec 22, 2004 at 07:43:13PM +0100, Florian Weimer wrote:
> * Victor Duchovni:
> >> The Debian folks have recently stumbled upon a problem in this area:
> >> Generating the ephemeral DH parameters is expensive, in terms of CPU
> >> cycles, but especailly in PRNG entropy.  The PRNG part means that it's
> >> not possible to use /dev/random on Linux, at least on servers.  The
> >> CPU cycles spent on bignum operations aren't a real problem.
> >> 
> >> Would you recommend to switch to /dev/urandom (which doesn't block if
> >> the entropy estimate for the in-kernel pool reaches 0), and stick to
> >> generating new DH parameters for each connection, or is it better to
> >> generate them once per day and use it for several connections?
> >
> > Actually reasoning along these lines is why Lutz Jaenicke implemented
> > PRNGD, it is strongly recommended (at least by me) that mail servers
> > use PRNGD or similar.  PRNGD delivers psuedo-random numbers mixing in
> > real entropy periodically.

That's basically what /dev/urandom does, no?  (Except that it has the
undesirable side-effect of depleting the entropy estimate maintained
inside the kernel.)

> > EGD, /dev/random and /dev/urandom don't produce bits fast enough.
> 
> Is this the only criticism of /dev/urandom (on Linux, at least)?  Even
> on ancient hardware (P54C at 200 MHz), I can suck about 150 kbps out
> of /dev/urandom, which is more than enough for our purposes.  (It's
> not a web server, after all.)

On my PIII/666 running 2.4.26, I get 1.4 MB/sec from /dev/urandom.
Seems plenty fast enough to me.  (Fast, of course, being orthogonal to
secure.)

> I'm slightly troubled by claims such as this one:
> 
>   
> 
> I know that Linux' /dev/random implementation has some problems (I
> believe that the entropy estimates for mouse movements are a bit
> unrealistic, somewhere around 2.4 kbps), but the claim that generating
> session keys from /dev/urandom is a complete no-no is rather
> surprising.

I'm baffled by the post you reference:

Andrew Suffield writes on Mon, 20 Dec 2004 06:11:08 -
> The security of the session is limited by the randomness of the
> weakest key used. If you're going to use /dev/urandom then you might
> as well just not encrypt the session at all. It wouldn't be massively
> less secure, and it would be quite a lot faster.

I *think* what that says is "generating a session key based on entropy
from /dev/urandom is security-equivalent to no encryption at all".
Which is so obviously false that I can't imagine that I'm not
misreading.  I will grant that *if* an attacker can reconstruct the
state of the entropy pool (which in theory is possible if the attacker
can gather N bits of information about the outputs, but would require a
significant advance over the state of the art in cryptanalysis of the
hash function, and probably about 2^N work) then a key generated from it
is insecure.  But the difficulty of extracting that much information
about the entropy pool is enormous, and the challenge of reconstructing
the state, given that information, is ... large.

It would be less work to build a SQUID [1] and snoop the operation of
your ALU from the white van parked across the street from the data
center.

So, I agree with you - while it would be preferable to generate session
keys using the most conservative entropy estimates, it's a perfectly
reasonable engineering compromise to use /dev/urandom.  I'd rather have
Good Enough encryption, universally deployed, than fall for the Purity of
Essence^H^H^H^H^H^H^HRandomness whackos' claims that "Everyone must plug
a Geiger counter into their serial port or We're All Going To Die".

BTW, the Linux kernel guys are actively working on improving the
security of /dev/*random and could benefit from experienced
cryptographers willing to review work and make suggestions.  Check out
the linux-kernel archives for the past few months for subjects
mentioning /dev/urandom and /dev/random.

[1] Superconducting QUantum Interference Device, the Gibsonian gizmo
used by the dolphin in _Johnny Mnemonic_ to extract "80 *Gigabytes*!"
of information from the courier's brain-mounted memory module.

-andy

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

SHA-1 broken, says Schneier

[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]