<?xml version="1.0" encoding="iso-8859-1" ?>
<rss version="2.0">
  <channel>
    <title>2010 Reports</title>
    <link>http://eprint.iacr.org/forum/list.php?10</link>
    <description><![CDATA[Discussion forum for Cryptology ePrint Archive reports posted in 2010.
Please put the report number in the subject.

]]></description>
    <language>EN</language>
    <pubDate>Thu, 05 Aug 2010 16:02:52 -0600</pubDate>
    <lastBuildDate>Thu, 05 Aug 2010 16:02:52 -0600</lastBuildDate>
    <category>2010 Reports</category>
    <generator>Phorum 5.1.22</generator>
    <ttl>600</ttl>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,288#msg-288</link>
      <author>hugo</author>
      <description><![CDATA[A few weeks ago, 7-15-2010, in a discussion in the TLS WG mailing list regarding the applicability of the results in this paper to TLS (and practical crypto in general) I posted the following comments
http://www.ietf.org/mail-archive/web/tls/current/msg06705.html

If I am right in my comments (I might have misunderstood the paper's claims) then the paper needs to be revised not to give the impression that its results have any bearing on practical cryptography (as a theoretical issue, in particular in the setting of statistical extractors, this behavior of M-D functions under narrow pipes was already pointed out in the DGGKR paper of Crypto 2004).

Note: I only refer to the general claims of the paper. I have not studied the paper's contents beyond that.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,288#msg-288</guid>
      <pubDate>Thu, 05 Aug 2010 16:02:52 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,284#msg-284</link>
      <author>Vlastimil Klima</author>
      <description><![CDATA[Please excuse our delay. We will write the update and more accurate version of the paper very soon.
Vlastimil Klima]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,284#msg-284</guid>
      <pubDate>Wed, 04 Aug 2010 17:05:38 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,281#msg-281</link>
      <author>marshray</author>
      <description><![CDATA[In many real-world situations an attacker is able to extend the length of messages with chosen text in an attempt to engineer a collision. In these cases, there may be 160 bits of entropy coming in through the chaining values, but the entire message data could be an attacker-supplied constant value for many blocks.

Seems to me that as long as the ratio of (bits of entropy lost to missing preimages) to (log2 of appended constant blocks) remains greater than 2, an attacker seeking to collide messages would find it better to append constant blocks to each candidate message prefix rather than process those same blocks as different messages.

SHA-1 stands today at 2^63 for collision resistance. If this effect &quot;stacks&quot; on top of the other attacks (I don't know that it does) and reduces the collision resistance by a few bits with less than that much extra work, then it could make a real difference as to what year we see the first actual SHA-1 collision.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,281#msg-281</guid>
      <pubDate>Wed, 21 Jul 2010 10:41:20 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,280#msg-280</link>
      <author>Orr</author>
      <description><![CDATA[marshray:

If you enter a random chaining value and a random message to SHA-1's compression function, you put in 512+160 bits of entropy. You would get with very high probability 160 bits of entropy coming out.

If you fix the message to constant, then we expect to lose only ~0.5 bits of entropy, as the underlying block cipher (called SHACAL-1) which is used in a Davies-Meyer mode is invertible (it's a block cipher!).

In other words, you will not be able to measure any entropy loss.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,280#msg-280</guid>
      <pubDate>Wed, 21 Jul 2010 03:37:04 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,279#msg-279</link>
      <author>marshray</author>
      <description><![CDATA[When evaluating the effect of this phenomenon on actual hash designs, it's probably important to look inside the block structure as well. For example, SHA-1:

for i from 0 to 79 // thanks Wikipedia
        if 0 &amp;#8804; i &amp;#8804; 19 then // &quot;round A&quot;
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 &amp;#8804; i &amp;#8804; 39 // &quot;round B&quot;
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 &amp;#8804; i &amp;#8804; 59 // &quot;round C&quot;
            f = (b and c) or (b and d) or (c and d) 
            k = 0x8F1BBCDC
        else if 60 &amp;#8804; i &amp;#8804; 79 // &quot;round D&quot;
            f = b xor c xor d
            k = 0xCA62C1D6
   ...
Sorry for the formatting.

Notice that the two separate rounds A and C are composed of 'and', 'or', and 'not' operations (four times on each state variable). Does this on its own amount to a random function? Rounds B and D are simply 'xor' so we would expect no loss of entropy.

So does SHA-1 experience entropy loss due to missing preimages one time per block, or eight, or somewhere in between? To what degree can this be controlled by an attacker who can extend the input with chosen text?

SHA-256 appears to do some significantly nonlinear operations on two of the eight state variables in each of 64 steps. Does this amount to 16 consecutive random function applications?

This looks like it could knock a few additional bits out of the net effective entropy.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,279#msg-279</guid>
      <pubDate>Tue, 20 Jul 2010 13:22:24 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,278#msg-278</link>
      <author>gligoroski</author>
      <description><![CDATA[Dear Marsh,

From the link you have sent I quote:
&quot;I did some Monte Carlo testing and found that my intuition was mostly wrong. The entropy loss effect is also observable with the Davies-Meyer construction where the chaining value from the previous block is added back into the result from the current block. In fact, under some circumstances, it makes it worse! &quot;

Although your experiments are just Monte Carlo testing - they are interesting and they confirm our initial intuition and feeling (mine and Klima's) that something is not completely OK and not ideally random with narrow-pipe designs.

But I think the research in this area has long way to go until (if ever) any concrete practical results will occur.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,278#msg-278</guid>
      <pubDate>Mon, 19 Jul 2010 14:17:41 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,277#msg-277</link>
      <author>marshray</author>
      <description><![CDATA[Yes, but some of the possible compression functions approximate a random function more closely than others. If we have information that a given construction does not, then we may be obligated not to approximate it as such.

I did some Monte Carlo testing and learned some things :-). Results and code are posted here:
http://www.ietf.org/mail-archive/web/tls/current/msg06719.html

In short:
* Mixing the input chaining value back to the output (D-M) causes the result to more closely approximate a random function (for better or for worse). So MD4-SHA2 do, in fact, experience the entropy reduction effect.
* D-M does convert the worst-case of a completely degenerate compression function (e.g., one which returns the same image every time) into a best case of no entropy loss.
* A pure M-D construction using a random permutation (say AES) for the CF is made worse by randomly mixing into the output.

- Marsh]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,277#msg-277</guid>
      <pubDate>Mon, 19 Jul 2010 13:34:40 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,276#msg-276</link>
      <author>gligoroski</author>
      <description><![CDATA[marshray Wrote:
-------------------------------------------------------
&gt; So the
&gt; 
&gt;     h_(i+1) = h_i + F(h_i, m_i)
&gt; 
&gt; construction used by seems to be credited to
&gt; Davies-Meyer. It's not used in MD2 but is used in
&gt; MD4 (RFC 1186 October 1990), MD5, SHA-1, and
&gt; SHA-2.

Hmm, 
the function 

      h_(i+1) = h_i + F(h_i, m_i) 

has still the form:

      h_(i+1) = compress(h_i, m_i)]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,276#msg-276</guid>
      <pubDate>Sat, 17 Jul 2010 00:37:26 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,274#msg-274</link>
      <author>marshray</author>
      <description><![CDATA[So the

    h_(i+1) = h_i + F(h_i, m_i)

construction used by seems to be credited to Davies-Meyer. It's not used in MD2 but is used in MD4 (RFC 1186 October 1990), MD5, SHA-1, and SHA-2.

However, descriptions of Davies-Meyer seem to be specifically expecting a block cipher for F. As a block cipher is a permutation it would have no missing preimages, so it would not seem that this effect would need compensating.

Perhaps it was an invisible influence, designer's intuition, or we just got lucky?]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,274#msg-274</guid>
      <pubDate>Wed, 14 Jul 2010 22:47:45 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical - models actual M-D accurately?</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,273#msg-273</link>
      <author>marshray</author>
      <description><![CDATA[The model

  h_(i+1) = compress(h_i, m_i)

may be a bit of an oversimplification. Notice that in actual SHA-256 the result of the compression(h_i, m_i) is added into the h_i input chaining values to produce h_(i+1) instead of outright replacing it. I suspect M&amp;D foresaw this issue and built in a resistance to it.

The paper seems to imply that the worst case would be a block message input which mapped every X chaining input to the same Y, destroying all entropy from previous blocks. However, in the actual SHA-256 this would result in the perfect transmission of entropy past that block.

In order for a block to destroy entropy it needs to actively negate the input chaining value. I'm thinking this probability is more like 1/2^256 rather than 1/e?

It is also possible I am misunderstanding something basic here. I admit to being a bit out of my league here. :-)]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,273#msg-273</guid>
      <pubDate>Wed, 14 Jul 2010 19:12:41 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,271#msg-271</link>
      <author>gligoroski</author>
      <description><![CDATA[I am receiving very good comments, suggestions and corrections from Jean-Philippe and Orr - so soon I will post corrected version of the paper.

But Duchman is right: this is more theoretical work and of theoretical importance.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,271#msg-271</guid>
      <pubDate>Fri, 09 Jul 2010 14:47:38 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,270#msg-270</link>
      <author>Orr</author>
      <description><![CDATA[The latest version I've read contains mistakes which are currently are under discussion with the authors (offline).

For example, the claims concerning the lose of entropy if you iterate the compression function 2^20 times is wrong if the message blocks contain a bit of entropy.

So, I would hold your horses concerning the statement &quot;narrow-pipe hash functions can not ever replace random oracles&quot; (for what it's worth, any practical hash function cannot replace random oracles).]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,270#msg-270</guid>
      <pubDate>Fri, 09 Jul 2010 10:05:23 -0600</pubDate>
    </item>
    <item>
      <title>2010/384 is theoretical work - not practical</title>
      <link>http://eprint.iacr.org/forum/read.php?10,264,264#msg-264</link>
      <author>DutchShtull</author>
      <description><![CDATA[Three remarks for this paper:

1. It is nice discovery to show that narrow-pipe hash functions can not ever replace random oracles. From this point of view, wide-pipe hash designs have obvious advantage in SHA-3 contest.

2. The term &quot;practical&quot; in the title of the paper is not well chosen. Observed decreasing of the entropy is of *theoretical* importance, not of practical importance.

3. My impression is that wide-pipe hash designs will not manifest the observed loss of entropy (as narrow-pipe designs do), but this is not clearly stated and explained in the paper.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,264,264#msg-264</guid>
      <pubDate>Thu, 08 Jul 2010 02:24:13 -0600</pubDate>
    </item>
  </channel>
</rss>
