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

2004-04-04 Thread R. A. Hettinga

--- begin forwarded text


To: [EMAIL PROTECTED]
From: Arnold G. Reinhold [EMAIL PROTECTED]
Subject: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate
software
 releases
Sender: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
List-Id: Macintosh Cryptography mac_crypto.vmeng.com
List-Post: mailto:[EMAIL PROTECTED]
List-Help: mailto:[EMAIL PROTECTED]
List-Subscribe: http://www.vmeng.com/mailman/listinfo/mac_crypto,
mailto:[EMAIL PROTECTED]
List-Archive: http://www.vmeng.com/pipermail/mac_crypto/
Date: Sun, 4 Apr 2004 06:17:55 -0500

The cryptographic hash function MD5 has long been used to
authenticate software packages, particularly in the Linux/Unix/open
source community. This has carried over to Apple's OS-X. The MD5 hash
of an entire package is calculated and its value is transmitted
separately from the package. Users who download the package compute
the hash of the copy they received and match that value against the
original.

Putting aside the question of how the the hash value is safely
transmitted, there is a potential attack on this method due to the
128 bit length of the MD5 hash output. If all the individuals having
input to the creation of the original software package are
trustworthy, then 128 bits provides adequate security. Someone trying
to substitute a version of that package containing a malicious
modification (Trojan horse, virus,  backdoor) would have to solve a
128 bit problem to create an infected package that passed the hash
verification. That is considered computationally infeasible, at least
until the advent of quantum computing.

One might think the above argument proves MD5 is sufficient. After
all, if an attacker had an agent working inside the organization that
produced the package, that agent could simply incorporate the
malicious software patch in the original package. However such an
insertion is very risky. A sophisticated software company would
likely have code reviews that would make introduction of the
malicious code difficult. Use of a source control system makes is
easy to track down whoever inserted the malicious change once it is
discovered. The malicious code would be distributed to everyone,
increasing the likelihood of detection. In an open source model, a
defect in source code is particularly hard to hide. The agent risks
being uncovered and and perhaps prosecuted, the organization he works
for risks being identified and the technical means that the malicious
code employed would be compromised.

A safer attack would be for the agent to insert an apparently
innocent modification to the package, with the modification selected
so that the MD5 hash of the package with the malicious code matches
the hash of the officially released package. Since the attacker (or
whomever he is working for) controls the malicious code, calculating
the value of this modification is subject to a meet-in-the-middle
attack and presents presents a 64-bit problem. Solving such a problem
is within the means of a well-funded attacker today* and will become
easier in the future.

The modification could be designed to get past code reviews in a
number of ways. For example, 64 low order bits in a JPEG icon might
be altered. The agent would have to make the last modification to the
software package prior to release and perhaps send a final
pre-release version of the package to someone on the outside who does
the collision calculation, but those are hardly insurmountable
hurdles.  In situations where new releases are relatively frequent,
it may suffice for this attack to succeed only occasionally, allowing
periodic entry into selected systems to recover private keys, for
example.  The attacker merely submits modifications late in the
release cycle and if his happens to be last then the full attack is
mounted.

The obvious solution to this problem is to use a wider hash for
package authentication. For example, SHA-256 would present an
attacker using this approach with a 128-bit problem. Even SHA1 would
be preferable, making such an attack an 80 bit problem.  If both MD5
and SHA1 hashes are provided, the attacker faces the problem of
forging them both. It costs almost nothing to provide a wider hash
along with the MD5 hash whenever a new package is released. It seems
the prudent thing for Apple to do.

Arnold Reinhold


* From: http://www.rsasecurity.com/rsalabs/faq/3-6-6.html

Van Oorschot and Wiener [VW94] have considered a brute-force search
for collisions (see Question 2.1.6) in hash functions, and they
estimate a collision search machine designed specifically for MD5
(costing $10 million in 1994) could find a collision for MD5 in 24
days on average. The general techniques can be applied to other hash
functions.

VW94]
P. van Oorschot and M. Wiener, Parallel collision search with
application to hash functions and discrete logarithms, Proceedings of
2nd ACM Conference on Computer and Communication Security(1994).

** SHA1 is available in OS-X as part of openssl. Type openssl  

Re: Do Cryptographers burn?

2004-04-04 Thread Hadmut Danisch
On Sat, Apr 03, 2004 at 11:49:15PM +0100, Dave Howe wrote:
 
 If you mean he gave a false assurance of the security of a product for a
 friend - why would he do that? I can't think of any of my friends who would
 want me to tell them sofware was secure if it wasn't.
...
 I suppose that depends on his integrity and how much his reputation and
 skill would be worth to his employers if it became known that he gave false
 assurances - and it would only be a matter of time before some other
 cryptoanalyst found the fault he found and ignored.


Thanks for the opinions.

Maybe I'll explain a little bit more about the background:

As some already may have heard I'm in a legal dispute with a
german University. I wrote a dissertation in 1998, and the supervisor
announced to give a good rate. I then signed off from the job as an 
assistant effectively to the date of the examination. I didn't know
that the supervisor and another professor had made a plan to implement 
a security infrastrukture for the faculty and to found a company, and
that this plan included that I would do the work in the year after the
examination. When I signed off, they couldn't fulfill the promises
they gave to the faculty, and thus canceled the examination to extort 
me to stay at the university and do the implementation. I refused
to pay that kind of protection money and thus they rejected my 
dissertation with false expertises. 

The advisor's expertise (who claims to be one of the world's top
cryptographers) is just a concatenation of arbitrary nonsense, and
wrong even in the basics of computer science. E.g. he claims that LZ
and MTF would effectively compress just anything. As an example for
the need to distinguish between payload and control information I said
that when phoning, not only speech is to be transmitted, but also
phone numbers and signals about termination of the connection.  He
rated this as completely wrong and giving wrong information, because
phone numbers would be used with today's ISDN Telephones only. As the
reason he gave an obituary in the London Times saying that Donald
Davies had died. Or he blames me for not citing literature that hadn't
been published when I submitted the dissertation. He claims that
rate-distortion theory and shannon encoding allow to pack n+1
independant bits into a single message of n bits (even with small n or
n=1. Just try to do it.). 

The second examiner said the dissertation would be completely wrong
but denied to give any explanation. I filed a lawsuit.

During the law suit, the university had informed me, that they would
never accept me to succeed in the examination. They would abuse a gap
in german examination law: courts are restricted to cancel bad or
wrong examinations, but they cannot give a positive examination
result. All they can do is to sentence the University to repeat the
examination. The University informed me that they had decided that
they do not wish me to work in science and thus I had to accept to
fail in the examination. I would have to modify my dissertation and to
include those mistakes the examiners had falsely claimed in order to
confirm that their rejection was correct. If I do that I would be
allowed to have a second try with a new dissertation and would receive
a bad grade which would keep me out of science. If I do not agree,
they announced to keep me in an endless loop of false
expertises. Every single one will take me years to sue against. I
refused that deal.

I won both at the administration court and the appelate administration
court. The latter one found that the second examiner could never have 
read the largest chapter and didn't even open the pages of the
dissertation. This was already sufficient to cancel the examination 
action. The University then retracted the action to avoid being
sentenced. 

Obviously, this was an extreme disgrace for the University. The 
University had to give a new second expertise. If this expertise could
not confirm what the first expertise said, that the dissertation was
completely wrong, the advisor would face beeing fired, severe
compensation claims, and the ultimate disgrace. 

Within less then two weeks the University managed to get a third rejecting
expertise, this time from a professor outside Germany, who is indeed
known as one of the top cryptographers and a member of the board of
directors of the IACR. I filed a new lawsuit and could easily prove
that this professor had intentionally given a wrong expertise
(obviously to protect the supervisor from legal trouble):

- He wrote the expertise in less than two days. 

- The expertise is less than a page. He does not give any 
  reasons and claims that he cannot be expected to reason his 
  expertise. Reasoning is a strong requirement under german law.

- There is no link between the expertise and the dissertation. 
  He obviously didn't read it.

- He didn't find any single mistake. He just says that everything is
  already known and taken from literature.

- He 

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

2004-04-04 Thread Don Davis
hi, mr. reinhold --

there's stronger reason than the ones you cite,
to distrust md5 as a message-digest.  see these
old sci.crypt threads, and the google-search below,
for discussions of hans dobbertin's 1996 crack
of md5:

http://tinyurl.com/2ox7g

http://tinyurl.com/3x446

http://google.com/search?q=dobbertin+md5num=30

btw, in a phone conversation, dobbertin emphasized
to me that his attack only works when md5 is used
as a message-digest; it doesn't work when md5 is
used with a key to prepare a MAC.  he also mentioned
that while sha-1 may be vulnerable to an attack of
a similar style (because sha-1 is similar in struc-
ture to md5), he himself was forbiddden by german
law to work to cryptanalyze sha-1, because he worked
at that time for the german federal security service,
and so wasn't allowed to attack the USG's standard
ciphers.  now he's at ruhr university (in bochum),
but i don't know whether he's more of a free agent.

- don davis, boston



 To: [EMAIL PROTECTED]
 From: Arnold G. Reinhold [EMAIL PROTECTED]
 Subject: [Mac_crypto] Apple should use SHA! (or stronger) to authenticate
 software
  releases
 Sender: [EMAIL PROTECTED]
 Reply-To: [EMAIL PROTECTED]
 List-Id: Macintosh Cryptography mac_crypto.vmeng.com
 List-Archive: http://www.vmeng.com/pipermail/mac_crypto/
 Date: Sun, 4 Apr 2004 06:17:55 -0500

 The cryptographic hash function MD5 has long been used to
 authenticate software packages, particularly in the Linux/Unix/open
 source community. This has carried over to Apple's OS-X. The MD5 hash
 of an entire package is calculated and its value is transmitted
 separately from the package. Users who download the package compute
 the hash of the copy they received and match that value against the
 original.
...

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


Re: Do Cryptographers burn?

2004-04-04 Thread Dave Howe
Hadmut Danisch wrote:
 - He didn't find any single mistake. He just says that everything is
   already known and taken from literature.
certainly possible - if he didn't know (or deliberately ignored) that it had
been written in 1988 :)
How much of it is *still* new or at least hard to find in the literature?
how much of it would be known *today* out of hand by someone who was
familiar with the state of the art?  If the university had instructed him to
take a look at your work in that context, he may well not have found
anything new or novel in there - because your work had since been
duplicated, and after 16  years I would expect it to have been duplicated
several times.  If he had been instructed to find pre-1987 published work
that duplicated yours, that would be different - but I would assume the
university neglected that direction while instructing him.

 Maybe it's a minority writing false expertises. But it's a majority
 accepting that.
We have the same problem with expert witnesses in court here in the uk -
after a while, prosecutors learn which experts can be relied on to give the
answer they want rather than admit it is a matter of opinion and either case
could be correct - such experts get a lot more work from the prosecution for
their unbiassed opinions than those which gave an unbiassed opinion the
prosecution didn't like (it isn't unknown for the prosecution to approach
three or four experts and take the most favourable return to court)

 So my doubt is not so much about that someone found the magic way to
 factorize. It's about someone intenionally selling snake-oil or
 backdoors and other's keeping their mouth shut and tolerate this as
 they do it here.
no, it isn't.
it is about someone deliberately choosing to concentrate on the worst
aspects of a 16 year old dissertation (almost certainly, that it is 16 years
out of date) and ignoring the context. I am sure if I paid 100 experts to
evaluate *anything* I could find at least one I liked the resulting report
from.
I am not too surprised either - for the reasons I have detailed above. I
know it is hard to have fought this way though the legal system to find the
university has tried to throw money at the problem to make it go away - but
it happens, and I can only assume you will eventually prove it in court.
what you have here is a legal problem with some individuals, that their
employer has chosen to back against a student, and in doing so bent any or
all rules it could to win. This says little about the individual who wrote
the new examination and more about your opponents in the university's legal
team.  BTW is there any way you can find out how many experts were asked
to evaluate your work before they found one whose answer they liked?

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