Re: This Week's Finds in Mathematical Physics (Week 226)

In article <Pine.LNX.4.61.0602102025360.19201@xxxxxxxxxxxxxxxxxxxxxxxxx>,
<tessel@xxxxxx> wrote:

On Sat, 11 Feb 2006, John Baez mentioned that md5sum was "broken" about a
year ago. I just wanted to add:

1. If I am not mistaken, sha-1 and md5sum are different algorithms (IIRC,
both are known to be insecure).

Yeah, I said SHA-1 and MD5 are different, and I said they were both vulnerable
to collision attacks. MD5 is very vulnerable in practice, while the
vulnerability of SHA-1 is still theoretical: you'd have to have big
computers or lots of time or another clever idea to exploit it.
(Guess who's likely to have all three!)

I gave this reference for MD5:

Magnus Daum and Stefan Lucks, Attacking hash functions by poisoned
messages: "The Story of Alice and Her Boss",
http://www.cits.rub.de/MD5Collisions/

and this one for SHA-1:

SHA hash functions, Wikipedia,
http://en.wikipedia.org/wiki/SHA_hash_functions

The latter has some good links, including this nice review:

Arjen K. Lenstra, Further progress in hashing cryptanalysis,
February 26, 2005, http://cm.bell-labs.com/who/akl/hash.pdf

For more on cryptographic hash functions and their woes, try these:

9) Cryptographic hash function, Wikipedia,
http://en.wikipedia.org/wiki/Cryptographic_hash

Of course, bear in mind that anyone can edit, blah, blah (including
unregistered users, contrary to widely publicized news reports based upon
a fundamental misunderstanding).

Yes, I could have tried to give references to dated versions of
Wikipedia articles, so I could be sure they're good... but I'm an optimist.

These are huge and wonderful philosophico-physico-mathematical questions
with serious practical implications.

You mean the Weyl curvature hypothesis? :-/

Heh, no - I mean stuff like whether there's such a thing as a provably
good cryptographic hash code function, or cipher.

Joel Spencer, The Strange Logic of Random Graphs, Springer 2001

Here's a thought: "Everyone knows" that if on day D, mathematician M is
studying an example of size S in class C, he is more likely to be studying
a "secretly special" representative R than a generic representative G of
size S. Why? Because the secretly special reps show up in disguise in
other areas, and M was probably hacking through the jungle from one of
those places when he got lost and ate a poisoned cache.

Interesting.

Bite me, Brian!

I have no idea what that's a reference to.

Here's some more stuff, from my email correspondence.
It's more related to physics.

I wrote:

Allan Erskine wrote:

I enjoyed week 226! Algorithmic complexity was the area I studied
in... Your readers might find "The Tale of One-way Functions" by
Leonid Levin an enjoyable read:

http://arxiv.org/abs/cs.CR/0012023

Hey, that's great! I'm printing it out now... Levin and I have
argued against Greg Kuperberg and others on sci.physics.research:
we tend to think that quantum computers are infeasible *in principle*.

As for your "shortest proof of this statement has n lines" question,
you may have noticed that Chaitin asks a very similar question about
the shortest proofs that a LISP program is "elegant" (most short) and
proves a strong incompleteness result with an actual 410 + n
character LISP program! Crazy...

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html

Yes. You might like the following related article below.

Best,
jb

It's an old one...

From: b...@xxxxxxxxxxxx (john baez)
Subject: Re: compression, complexity, and the universe
Date: 1997/11/20
Message-ID: <652c5t$62g$1@xxxxxxxxxxxxxxxxxx>#1/1
X-Deja-AN: 291100089
References: <64nsqo$8rg$1@xxxxxxxxxxxxxxxxxx> <346fd86d.1059260@xxxxxxxxxxxxxxxx> <64t2ar$qcs@xxxxxxxxxxxxxxx>
Originator: bunn@pac2
Organization: University of California, Riverside
Newsgroups: sci.physics.research,comp.compression.research

In article <651lm1$q3...@xxxxxxxxxxxxxxxxxx>,
Aaron Bergman <aaron.berg...@xxxxxxxx> wrote:

The smallest number not expressable in under ten words

Hah! This, by the way, is the key to that puzzle I laid out:
prove that there's a constant K such that no bitstring can be
proved to have algorithmic entropy greater than K.

Let me take this as an excuse to say a bit more about this.
I won't give away the answer to the puzzle; anyone who gets
stuck can find the answer in Peter Gacs' nice survey, "Lecture
notes on descriptional complexity and randomness", available at

http://www.cs.bu.edu/faculty/gacs/

In my more rhapsodic moments, I like to think of K as the
"complexity barrier". The world *seems* to be full of incredibly
complicated structures --- but the constant K sets a limit on our
ability to *prove* this. Given any string of bits, we can't rule
out the possibility that there's some clever way of printing it
out using a computer program less than K bits long. The Encyclopedia
Brittanica, the human genome, the detailed atom-by-atom recipe for
constructing a blue whale, or for that matter the entire solar system
--- we are unable to prove that a computer program less than K bits
long couldn't print these out. So we can't firmly rule out the
reductionistic dream that the whole universe evolved mechanistically
starting from a small "seed", a bitstring less than K bits long.
(Maybe it did!)

So this raises the question, how big is K?

It depends on ones axioms for mathematics.

Recall that the algorithmic entropy of a bitstring is defined
as the length of the shortest program that prints it out. For
any finite consistent first-order axiom system A exending the
usual axioms of arithmetic, let K(A) be the constant such that
no bitstring can be proved, using A, to have algorithmic entropy
greater than K(A). We can't compute K(A) exactly, but there's a
simple upper bound for it. As Gacs explains, for some constant c
we have:

K(A) < L(A) + 2 log_2 L(A) + c

where L(A) denotes the length of the axiom system A, encoded as
bits as efficiently as possible. I believe the constant c is
computable, though of course it depends on details like what
universal Turing machine you're using as your computer.

What I want to know is, how big in practice is this upper
bound on K(A)? I think it's not very big! The main problem
is to work out a bound on c.


.

Relevant Pages

  • Re: What is md5sum?
    ... actually no two items in the list share the same MD5 sum. ... If hash functions we create were perfect, we wouldn't be using MD5 - we ... probability of a collision or reversing the function would be negligible ... better than others - and SHA-1 is considered more secure than MD5. ...
    (comp.os.linux.setup)
  • Re: Re-secured Algorithm?
    ... >>MD5 collisions are actually trivial to generate. ... SHA-1 had real collisions in MD5. ... Personal attacks aside I doubt many ...
    (sci.crypt)
  • Re: Crypto Hash functions
    ... crypto-hash functions were "broken". ... MD5: ... SHA-1: wounded but still fighting. ... If you're signing bulk data, probably SHA-256 is your best bet. ...
    (sci.crypt)
  • Crack in Computer Security Code Raises Red Flag
    ... Crack in Computer Security Code Raises Red Flag ... Hash functions generate digital fingerprints, or "hashes," of documents ... SHA-1 is a federal standard promulgated by ... Also worrying cryptographers is a stream of recent hash compromises. ...
    (sci.crypt)
  • Crack in Computer Security Code Raises Red Flag
    ... Crack in Computer Security Code Raises Red Flag ... Hash functions generate digital fingerprints, or "hashes," of documents ... SHA-1 is a federal standard promulgated by ... Also worrying cryptographers is a stream of recent hash compromises. ...
    (alt.computer.security)