Subject: [TLS] Entropy of SHA-2 and the P_SHA256-based PRF

From: "Brian Smith" <[email-masked]>
Date: Wed, 14 Jul 2010 17:08:37 -0500

Here is an interesting paper regarding the entropy of the output of SHA-2
with a special mention of the TLS 1.2 PRF. If I am understanding correctly,
SHA-2 reduces the entropy of a random input by half the first time it is
applied, and the entropy slowly decreases every time it is applied
thereafter. 

"For illustration we can say that the entropy of E(PRF[1]) = 253.463, but
the entropy of E(PRF[60]) = 250.00."

"Practical consequences of the aberration of narrow-pipe hash designs from
ideal random functions"

Danilo Gligoroski and Vlastimil Klima

http://eprint.iacr.org/2010/384

Regards,

Brian

---

From: Martin Rex <[email-masked]>
Date: Thu, 15 Jul 2010 01:35:41 +0200 (MEST)

> http://eprint.iacr.org/2010/384

A few observations.

Section 4.4 of this paper talks about PBKDF1
("Password based key derivation function 1" from PKCS#5),
and PBKDF1 was defined for MD2 and MD5 by PKCS#5 v1.5 and expanded
to SHA-1 by PKCS#11.

I assume that SHA-256 would more likely be used with PBKDF2
(which may share the relevant properties with PBKDF1
 with respect to the described effect of slow entropy depletion).

I assume that the effect of increased collisions for highly iterated
hashes similarly affect SHA-1 and MD5 password hashes.

I'm wondering whether an approach like this would compensate
the effect:

  Hash( user | pw | iteratedHash( Hash(pw | user | salt) ) )

-Martin

---

From: Marsh Ray <[email-masked]>
Date: Wed, 14 Jul 2010 19:51:35 -0500

On 07/14/2010 05:08 PM, Brian Smith wrote:
> Here is an interesting paper regarding the entropy of the output of
> SHA-2 with a special mention of the TLS 1.2 PRF. If I am understanding
> correctly, SHA-2 reduces the entropy of a random input by half the first
> time it is applied, and the entropy slowly decreases every time it is
> applied thereafter.

If the effect were that dramatic, it would be quite easy to test. Just 
take random samples, append them with long fixed strings, and get 
nonrandom output.

> “For illustration we can say that the entropy of E(PRF[1]) = 253.463,
> but the entropy of E(PRF[60]) = 250.00.”

I believe Merkle and Damgard foresaw this problem and designed the hash 
structure to prevent it.

The paper models each block function as a random mapping of X={0,1}^n to 
Y={0,1}^n (i.e., 256 bits in, 256 bits out, each of the 2^256 mappings 
chosen without regard to the others). From this they infer that the 
probability that any given Y (hash output) does not have a corresponding 
X (input chaining value to generate it) is about 1/e. So for any 256-bit 
hash value you might want to get out of the block, there is a greater 
than 1/3 chance that there exists no chaining input which can produce it 
(for a fixed message input to that block). Since there are 256 bits in 
and 256 bits out, impossible output values imply that entropy is being 
discarded on the way through the function.

They describe SHA-256 as a whole as:
    h_0 = fixed IV
    for i = 0...N-1
        h_(i+1) = blockCompression(h_i, msg_i)
    h_N is the final result

But if you look at (towards the bottom)
http://en.wikipedia.org/wiki/SHA-2
that is not how the block compression functions of SHA-256 are put 
together. There is indeed some complex manipulation of (h_i, m_i) which 
may in fact behave like a random mapping into the variables (a,b...h). 
But this is not returned directly as the result of the block compression 
function, instead it is _added_ back to the h_i input and that sum is 
what is returned as h_(i+1). The effect of this addition is subtle, but 
important.

The worst case for the paper's model would be if there was a block 
message input which mapped every possible X chaining input to the same 
Y: total destruction of all entropy from previous blocks of the message. 
However, in the actual SHA-256 such a degenerate case would actually 
result in the perfect transmission of entropy past that block.

So the tables are turned by that simple addition. If there are 
impossible values of output for a specific block of message data they 
can only preserve whatever entropy comes through the input block. In 
order to actually reduce the entropy propagating from the previous 
block, the block compression function would have to be more likely than 
chance to result in negating the (dynamic) input chaining value in the 
upcoming addition. So assuming* the core input block compression 
function does indeed behave like a selectable random mapping (rather 
than a binary adder) it would require a massively large input block size 
in order for the message input to be able to select a mapping that 
significantly reduced the effective entropy propagating from the 
previous block.

- Marsh

*No attempt is made to show that this is a good assumption :-)

---

From: Marsh Ray <[email-masked]>
Date: Thu, 15 Jul 2010 00:05:02 -0500

On 07/14/2010 07:51 PM, Marsh Ray wrote:
>
> I believe Merkle and Damgard foresaw this problem and designed the
> hash structure to prevent it.

OK - I no longer believe that.

The M-D construction does not have this feature of merging the 
compression function output with the chaining input. It's normally 
attributed to Davies-Meyer. But D-M seemed to have been expecting a 
proper block cipher which (because there are no missing preimages) would 
not exhibit this effect. So it wouldn't have been put there to compensate.

This non-Merkle-Damgard feature shows up as early as MD4 (RFC 1186 
October 1990), which is the first iterated hash function of the MD family.

- Marsh

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 15 Jul 2010 01:24:20 -0400

Merkle-Damgard iteration does not solve this problem. The Gligorski-Klima
paper's findings apply to all the common M-D instantiations: The MD and
SHA-1/SHA2 families.

However, the loss in entropy has little effect in practical security if by
"practical security" we mean security against computationally bounded
attackers.

For example, under the modeling of the compression functions as random
functions (as done in the Gligorski-Klima paper) one can PROVE that HMAC, in
spite of the entropy reduction, is a secure PRF (i.e., it has been proven
that if the underlying compression function family is pseudorandom then HMAC
is a pseudorandom function; and if one models the compression functions as
random then they are, in particular, also pseudorandom).

So even if there is a loss of statistical entropy, this is something that a
computationally bounded attacker cannot exploit.

This should not come as a surprise. It is very common to have in
cryptography probability spaces with very limited statistical entropy and
yet secure enough for cryptographic purposes. The most common such object
is  a pseudorandom generator PRG (or stream cipher). It takes a seed of
length n and generates, say, 10n bits of output that are pseudorandom.
Clearly, the distribution generated by the PRG contains no more than n bits
of entropy (very small relative to the 10n strings it generates) and yet it
is secure as a PRG. The point is, as before, that in the security of a PRG
we only consider attackers that cannot distinguish the output of the PRG
from random uniform bits using FEASIBLE computation. Yes, a computationally
unlimited attacker (say one working time 2^n) will be able to  distinguish
between uniform and PRG output, but we consider those infeasible.

Leaving the realm of PRFs abd PRGs, one can ask what is the consequence of
entropy reduction in cryptographic hash functions. One setting where these
questions arise naturally is in designing randomness extractors via such
hash functions (a randomness extractor takes a source with some given
min-entropy and generates an output that is statistically close to uniform).
In this setting, paper [DGHKR'04] already identified the problem, also
pointed out in the Gligorski-Klima paper, that a last fixed (or close to
fixed) block in a M-D construction kills the statistical extraction
properties of the M-D hash functions (with narrow-pipe underlying functions
such as the SHA family). However, [DGHKR'04]  also proves that this is NOT a
problem in the cryptographic extraction setting. That is, if one models the
compression functions as random functions (or, more realistically, as
pseudorandom functions), then  the M-D construction does provide a secure
*computational* extractor. Here, by "computational extractor" one means the
transformation from an entropy source to a distribution that is
computationally indistinguishable from uniform (see [Kra'10]). This results
holds even with a last fixed block.

To summarize: Yes, M-D functions do not behave as perfect random functions
but when used judiciously they provide enough of pseudorandomness for
cryptographic applications (HMAC, extraction, KDF, etc). Of course, if the
underlying compression function is not even a good pseudo-random family then
the constructions based on them may well be insecure -- but the
Gligorski-Klima paper models them as random in which case the weaknesses
pointed out are statistical only but inapplicable to the crypto world of
computationally bounded adversaries. (In particular, of no consequence to
the use of these functions in HMAC, the TLS protocol, etc.)

Hugo

[DGHKR'04] Dodis-Hastad-Gennaro-Krawczyk-Rabin, Crypto 2004.
[Kra10] Krawczyk, Cryptographic Extraction and Key Derivation: The HKDF
Scheme, Crypto'10 (http://eprint.iacr.org/2010/264)

On Wed, Jul 14, 2010 at 7:35 PM, Martin Rex <[email-masked]> wrote:

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Marsh Ray <[email-masked]>
Date: Thu, 15 Jul 2010 01:26:35 -0500

On 07/15/2010 12:24 AM, Hugo Krawczyk wrote:
> Merkle-Damgard iteration does not solve this problem. The
> Gligorski-Klima paper's findings apply to all the common M-D
> instantiations: The MD and SHA-1/SHA2 families.

For Merkle-Damgard:

    H[i+1] = F(H[i], M[i])

We can agree to model F as a random function (mapping {0,1}^n to 
{0,1}^n) and that the e^-1 rate of missing preimages implies a 
significant entropy loss for F.

But MD4-SHA2 are not pure Merkle-Damgard, they are more like
Davies-Meyer:

    H[i+1] = H[i] + F(H[i], M[i])

I think the "H[i] + " in front of F changes everything such that it is 
no longer appropriate to model it as a pure iterated random function. 
The entropy loss is eliminated because it is literally "added back in".

- Marsh

---

From: Marsh Ray <[email-masked]>
Date: Fri, 16 Jul 2010 20:37:07 -0500

> The entropy loss is eliminated because it is literally "added back in".

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!

A pure Merkle-Damgard hash built from a random permutation (e.g., a 
block cipher) would not lose entropy in this way because there are no 
missing preimages. However, if the chaining input is mixed back to the 
output as in the Davies-Meyer, it reintroduces the entropy loss of the 
random function-based hash.

I was correct in thinking that D-M converts the worst-case of a 
completely degenerate compression function (which returns the same image 
every time) into a best case of no entropy loss. Ironically, improving 
the compression function from that point drags the output back down to 
the performance of the random function.

This suggests that the optimal narrow-pipe hash design would be based on 
a pure M-D construction with a block cipher compression function, but I 
assume these points of design were thoroughly researched ages ago.

- Marsh

implementation note: sizeof(XY_type) = 4
implementation note: XY_mask = 0x007FFFFF

----------------------------------------------------------------------
H is a 23-bit iterated hash function of [Merkle-Damgard] construction
using an ideal [random function] for the block compression function C: 
    C : M -> X -> X
     M = {0, 1}^m  (considered fixed)
     X = {0, 1}^23 (8388608 elements)

The padded input message is split into blocks i = 1..N
       h[0] = IV
       h[i] = C(h[i - 1], m[i])
       H = h[n]  (output)

Preimage counts of the block function and their frequency
   0:  3085212  36.7786%
   1:  3087453  36.8053%
   2:  1542686  18.3903%
   3:  513732  6.12416%
   4:  128799  1.5354%
   5:  25759  0.307071%
   6:  4259  0.0507712%
   7:  627  0.00747442%
   8:  76  0.000905991%
   9:  5  5.96046E-05%

Entropy estimates:
    Shannon: 22.1729 bits, a 4% loss
        Min: 19.8301 bits, a 14% loss

----------------------------------------------------------------------
H is a 23-bit iterated hash function of [Merkle-Damgard] construction
using an ideal [random permutation] for the block compression function 
C:     C : M -> X -> X
     M = {0, 1}^m  (considered fixed)
     X = {0, 1}^23 (8388608 elements)

The padded input message is split into blocks i = 1..N
       h[0] = IV
       h[i] = C(h[i - 1], m[i])
       H = h[n]  (output)

Preimage counts of the block function and their frequency
   1:  8388608  100%

Entropy estimates:
    Shannon: 23 bits, a 0% loss
        Min: 23 bits, a 0% loss

----------------------------------------------------------------------
H is a 23-bit iterated hash function of [Davies-Meyer] construction
using an ideal [random function] for the block compression function C: 
    C : M -> X -> X
     M = {0, 1}^m  (considered fixed)
     X = {0, 1}^23 (8388608 elements)

The padded input message is split into blocks i = 1..N
       h[0] = IV
       h[i] = H[i - 1] + C(h[i - 1], m[i])
       H = h[n]  (output)

Preimage counts of the block function and their frequency
   0:  3085773  36.7853%
   1:  3085924  36.7871%
   2:  1543564  18.4007%
   3:  514089  6.12842%
   4:  128881  1.53638%
   5:  25315  0.301778%
   6:  4339  0.0517249%
   7:  636  0.00758171%
   8:  81  0.000965595%
   9:  5  5.96046E-05%
   11:  1  1.19209E-05%

Entropy estimates:
    Shannon: 22.1729 bits, a 4% loss
        Min: 19.5406 bits, a 15% loss

----------------------------------------------------------------------
H is a 23-bit iterated hash function of [Davies-Meyer] construction
using an ideal [random permutation] for the block compression function 
C:     C : M -> X -> X
     M = {0, 1}^m  (considered fixed)
     X = {0, 1}^23 (8388608 elements)

The padded input message is split into blocks i = 1..N
       h[0] = IV
       h[i] = H[i - 1] + C(h[i - 1], m[i])
       H = h[n]  (output)

Preimage counts of the block function and their frequency
   0:  3087177  36.802%
   1:  3084271  36.7674%
   2:  1543368  18.3984%
   3:  514407  6.13221%
   4:  128403  1.53068%
   5:  25938  0.309205%
   6:  4330  0.0516176%
   7:  624  0.00743866%
   8:  80  0.000953674%
   9:  10  0.000119209%

Entropy estimates:
    Shannon: 22.1724 bits, a 4% loss
        Min: 19.8301 bits, a 14% loss

//	mdvsmd.cxx
//
//	Monte Carlo evaluation to compare entropy loss for constant message 
blocks in
//	Merkle-Damgard hash constructions with that of Davies-Meyer.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
#include <stdexcept>
#include <boost/bind.hpp>
#include <boost/foreach.hpp>
#include <boost/function.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/ref.hpp>
#include <boost/integer.hpp>

typedef unsigned char uint8;
using namespace std;

//-	Configurables.

//	Domain of h[i] : X = Y = {0, 1}^n. I.e. count of bits in the chaining 
variables and
//	compression funciton output.
static size_t const XY_domain_n = 23;

enum hf_type_enum { enMerkleDamgard, enDaviesMeyer };
static char const * hf_type_str[] = {
	"Merkle-Damgard",
	"Davies-Meyer" };

enum cf_type_enum { enRandomFunction, enRandomPermutation };
static char const * cf_type_str[] = {
	"random function",
	"random permutation" };

typedef boost::mt19937 rng_type; // Mersenne twister

//	"The smallest, built-in, unsigned integral type with at least N bits."
typedef boost::uint_t<XY_domain_n + 1>::least XY_type;

static size_t XY_cardinality = 1 << XY_domain_n;
static size_t XY_mask = XY_cardinality - 1; // for addition modulo-domain_n

void test(hf_type_enum hf_type, cf_type_enum cf_type);

typedef boost::function<XY_type (XY_type x)> FN_C_type;
void report_entropy_propagation(FN_C_type block_fn, XY_type 
XY_cardinality, rng_type & rng, string const & description);

int main()
{
	cout <<
	"implementation note: sizeof(XY_type) = " << sizeof(XY_type) << "\n"
	"implementation note: XY_mask = 0x" << hex << uppercase << setfill('0') 
<< setw(8) << XY_mask << dec << "\n"
	"\n";

	if ( ! (XY_domain_n <= sizeof(XY_type)*8) )
		throw runtime_error("XY_type too small for full domain");

	for (size_t hft = 0; hft < sizeof(hf_type_str)/sizeof(hf_type_str[0]); 
++hft)
		for (size_t cft = 0; cft < sizeof(cf_type_str)/sizeof(cf_type_str[0]); 
++cft)
			test(hf_type_enum(hft), cf_type_enum(cft));

	return 0;
}

//	Returns a random i :
//		0 <= i < modulo            modulo == 0
//		0 <= i < XY_cardinality    modulo > 0
XY_type random_element(rng_type & rng, XY_type modulo = 0)
{
	XY_type elem = 0;
	if (!modulo)
	{
		//size_t cnt_needed = (sizeof(XY_type) + sizeof(rng_type::result_type) 
- 1)/sizeof(rng_type::result_type);
		size_t cnt_needed = sizeof(XY_type)*8*2;
		while (cnt_needed--)
		{
			elem = (elem << 1) ^ rng();
		}
		elem &= XY_mask;
	}
	else
	{
		XY_type max_mult = (XY_type(~0)/modulo)*modulo;  assert(2 <= max_mult);
		do
			elem = random_element(rng);
		while (! (elem < max_mult) );
		return elem%modulo;
//		if ( ! (modulo <= XY_cardinality) ) throw runtime_error("Doesn't 
make sense");
//		elem = boost::uniform_int<XY_type>(0, modulo - 1)(rng);
	}

	if (elem & ~XY_mask)
		throw runtime_error("Doesn't make sense");

	return elem;
}

//	Function with a mapping of X -> Y implemented as a vector.
struct FN_bare_C
{
	FN_bare_C(vector<XY_type> const & mapping) : mapping_(mapping) { }
	vector<XY_type> const & mapping_;

	XY_type operator () (XY_type x)
	{
		if ( ! (x < mapping_.size()) )
			throw runtime_error("out of range");

		XY_type y = mapping_[x];

		//y |= 7;// make C "less good"

		return y;
	}
};

//	Function with a mapping of X -> Y implemented as a vector.
struct FN_DaviesMeyer_block
{
	FN_DaviesMeyer_block(vector<XY_type> const & mapping) : bareC_(mapping) { }
	FN_bare_C bareC_;

	XY_type operator () (XY_type h_prev)
	{
		XY_type x = h_prev;
		XY_type y = bareC_(x);
		return (h_prev + y) & XY_mask;
//		return y;
	}
};

void test(hf_type_enum hf_type, cf_type_enum cf_type)
{
	string lineSep(70, '-');

	boost::mt19937 rng; // Mersenne twister

	cout <<
	lineSep << "\n"
	"H is a " << XY_domain_n <<"-bit iterated hash function of [" << 
hf_type_str[hf_type] << "] construction\n"
	"using an ideal [" << cf_type_str[cf_type] << "] for the block 
compression function C: \n"
	"    C : M -> X -> X\n"
	"    M = {0, 1}^m  (considered fixed)\n"
	"    X = {0, 1}^" << XY_domain_n << " (" << XY_cardinality << " 
elements)\n"
	"\n"
	"The padded input message is split into blocks i = 1..N\n"
	"      h[0] = IV\n"
	"      h[i] = " <<
	(hf_type == enMerkleDamgard ? "" : hf_type == enDaviesMeyer ?   "H[i - 
1] + " : "WTF?!") <<
	"C(h[i - 1], m[i])\n"
	"      H = h[n]  (output)\n"
	"\n";

	//	Initialize the mapping which defines C.
	vector<XY_type> mapping(XY_cardinality);
	if (cf_type == enRandomFunction)
	{
		for (vector<XY_type>::iterator it = mapping.begin(); it != 
mapping.end(); ++it)
			*it = random_element(rng);
	}
	else if (cf_type == enRandomPermutation)
	{
		XY_type y = 0;
		for (vector<XY_type>::iterator it = mapping.begin(); it != 
mapping.end(); ++it)
			*it = y++;

		if (!mapping.empty())
		for (unsigned int n = 0; n < 10; ++n)
		{
			//	Dumb broken shuffle.
			for (size_t i = 0; i < mapping.size(); ++i)
				swap(mapping[i], mapping[random_element(rng)]);

			//	Shuffle from Durstenfield Fisher-Yates via Wp
			for (size_t i = mapping.size() - 1; i; --i)
				swap(mapping[i], mapping[random_element(rng, i + 1)]);
		}
	}
	else throw runtime_error("wtf");

	//	Dump the mapping if it's not too big
	if (XY_cardinality <= 64)
	{
		cout << "mapping:\n";
		unsigned elem = 0;
		BOOST_FOREACH(XY_type img, mapping)
			cout << "  " << elem++ << " -> " << 0 + img << "\n";
		cout << "\n";
	}

	FN_bare_C bare_C(mapping);
	FN_DaviesMeyer_block dm_block(mapping);

	boost::function<XY_type(XY_type x)> block_fn =
		hf_type == enMerkleDamgard ? bare_C :
		hf_type == enDaviesMeyer ?   dm_block :
		boost::function<XY_type(XY_type x)>();

	report_entropy_propagation(
		block_fn, // boost::function<XY_type(XY_type x)> block_fn
		XY_cardinality, // XY_type XY_cardinality
		rng,
		"block function" ); // string const & description
}

//	Supplied a function of X -> Y, evaluates trials to estimate effective 
entropy.
void report_entropy_propagation(FN_C_type block_fn, XY_type 
XY_cardinality, rng_type & rng, string const & description)
{
	//	Count the number of preimages for each possible image.
	//	Map of image -> preimage frequency.
	vector<size_t> image_cntPreimages(XY_cardinality);
#if 1
	//	One trial for each element.
	for (XY_type element = 0; element < XY_cardinality; ++element)
	{
		XY_type image = block_fn(element);
		++image_cntPreimages[image];
	}
#else
	//	A bunch of random trials.
	for (size_t n = 0; n < max<XY_type>(XY_cardinality*2, 1024*1024); ++n)
	{
		XY_type element = random_element(rng);
		XY_type image = block_fn(element);
		++image_cntPreimages[image];
	}
#endif

	//	Dump the preimage counts if it's not too big
	if (XY_cardinality <= 32)
	{
		cout << "preimage counts:\n";
		for (size_t image = 0; image < image_cntPreimages.size(); ++image)
			cout << "  " << image << " <- qty " << image_cntPreimages[image] << "\n";
		cout << "\n";
	}

	//	Construct a map of preimage count -> frequency of that count's 
occurrence among images in Y.
	typedef map<size_t, size_t> cnt_freqs_type;
	cnt_freqs_type cntPreimages_freqs;
	for (vector<size_t>::const_iterator cit = image_cntPreimages.begin(); 
cit != image_cntPreimages.end(); ++cit)
	{
		size_t cntPreimages = *cit;

		cnt_freqs_type::iterator it = cntPreimages_freqs.find(cntPreimages);
		if (it != cntPreimages_freqs.end())
			++it->second;
		else
			cntPreimages_freqs[cntPreimages] = 1;
	}

	cout << "Preimage counts of the " << description << " and their 
frequency\n";
	BOOST_FOREACH(cnt_freqs_type::value_type pr, cntPreimages_freqs)
		cout << "  " << pr.first << ":  "  << pr.second << "  " << 
(100.0*double(pr.second)/XY_cardinality) << "%\n";

	{
		size_t totalN = 0;
		BOOST_FOREACH(XY_type cnt, image_cntPreimages)
			totalN += cnt;

		double H_shn = 0.0;
		size_t cntPreimages_max = 0;
		BOOST_FOREACH(XY_type cnt, image_cntPreimages)
		{
			if (cnt)
			{
				double p = double(cnt)/totalN;
				H_shn -= p*log2(p);

				if (cntPreimages_max < cnt)
					cntPreimages_max = cnt;
			}
		}

		//cout << "cntPreimages_max=" << cntPreimages_max << "  totalN=" << 
totalN << "\n";

		double p = double(cntPreimages_max)/totalN;
		double H_min = -log2(p);

		cout << "\n"
		"Entropy estimates:\n"
		"   Shannon: " << H_shn << " bits, a " << int(100.0*(XY_domain_n - 
H_shn)/XY_domain_n + 0.5) << "% loss\n"
		"       Min: " << H_min << " bits, a " << int(100.0*(XY_domain_n - 
H_min)/XY_domain_n + 0.5) << "% loss\n"
		"\n";
	}
}