Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 4 Sep 2015 11:00:33 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: MD5 I() (was: SHA-1 H())

On Thu, Sep 03, 2015 at 06:15:29PM +0300, Solar Designer wrote:
> #define I(x, y, z)	(bitselect(0xffffffffU, (x), (z)) ^ (y))
[...]
> Now that I think of it, the expression is actually very simple and I
> should have been able to arrive at it without a program.  bitselect()
> with the all-ones constant is directly usable to implement OR-NOT. :-)

And now I realize this is inconsistent with:

> SEL     XNOR    ORN     ANDN    COUNT   MD5_I
[...]
> yes     no      yes     yes     177     yes
> yes     no      yes     no      177     yes
> yes     no      no      yes     177     yes
> yes     no      no      no      165     yes

Since one SEL is usable to implement ORN, there should be no increase in
the number of different functions achieved with the addition of ORN to
the instruction set on top of SEL.  Yet the table shows an increase.
I think the same holds for ANDN.  I think the correct number for SEL
alone should thus be at least 177.

This indicates that the program still does not try all combinations.
I think the problem might be that it doesn't try enough constants along
with SELs.  While op() can return constants, uses of op() count towards
the number of operations, which is limited to 2, and there's just one
other place where constants are added (and one more where they might get
copied, but in limited ways).

The program should be re-designed, or some existing tool should be used.
I just felt it'd be quicker and more transparent to write the program
from scratch than to (re)learn how to use an existing tool.

Alexander

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.