Subject: RE: [Cfrg] Who agree with building block cipher, hash, MAC with same round function and key schedulel

From: "Blumenthal, Uri" <[email-masked]>
Date: Wed, 2 Aug 2006 10:09:45 -0400

This is what Russians have done. And from what I see, their old
cryptographic school is like their ballet - without competition. :-)
 
Russian cryptographic suite (Encryption, MAC, Hash) is based on
old-but-still-strong block cipher GOST 28147, and their Digital
Signature standard is based on Elliptic Curve Crypto. 
 
Block cipher that Russians base their symmetric key (and keyless - aka
hash) algorithms compares to AES in strengh. Its weaknesses are: 64-bit
block size, and simplistic key schedule. The first weakness is due to
algorithm's age (end of 70-ties?), the second one I suspect to be a
design compromise. Designers sacrificed strong key schedule for greater
key agility. This becomes important when you build hash out of block
cipher.
 
It is illustrative to observe how they approached hash design. Americans
took an idea of block cipher, figured that full strength is not needed
and simplified the heck out of it - and then put together gazillion of
rounds to compensate for the overly simplistic round function. Russians
took a real full-strength block cipher, and considering that full
strength is not needed - truncated the number of rounds. So encrypting
GOST is 32 rounds, while hashing GOST is "only" 16.

________________________________

	From: duo lei [mailto:[email-masked]] 
	Sent: Wednesday, August 02, 2006 2:16 AM
	To: [email-masked]
	Subject: [Cfrg] Who agree with building block cipher, hash,MAC
with same round function and key schedulel

	Dear all:
	
	     In the paper http://eprint.iacr.org/2006/147, titled "New
	Integrated proof Method on Iterated Hash Structure and New
Structures
	", the author give an integrated proof method on security proof
of 
	iterated hash structure. Based on the proof method, one  can
	distinguish the security of Merkel-Damag{\aa}rd structure,
wide-pipe
	hash, double-pipe hash and 3c hash, the paper also give a new
recommend
	structure. 
	
	At last, a new hash called F-hash, MAC called F-MAC and
encryption
	model Called FBC-mode are given,  based on same block cipher
round
	function and key schedule algorithm, which means with a same
block
	cipher round function and key schedule algorithm, we can have a
Hash, 
	MAC and block cipher and Encryption Mode, the proof based
knowledge of
	that was based on security of Feistel structure. The AES with
256 bits
	key and plaintext (called Rijndael) is good selection.

	Who agree with the point of  considering using same round
function and key schedule
	algorithm to build a block cipher, MAC and Hash.
	 
	best regards.
	                       Duo Lei

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Wed, 2 Aug 2006 12:19:29 -0700

HI Uri,

a minor but maybe important comment: the 64-bit block size of the  
GOST cipher seriously limits the amount of text that can be processed  
with a single key before information is leaked out because of attacks  
that use the 'codebook' property.  AES can process lots more text at  
a comparable or greater security level.  The AES limit on the data  
that can be processed is roughly the square of the amount of data  
that GOST can process.

David

On Aug 2, 2006, at 7:09 AM, Blumenthal, Uri wrote:

> Russian cryptographic suite (Encryption, MAC, Hash) is based on old- 
> but-still-strong block cipher GOST 28147, and their Digital  
> Block cipher that Russians base their symmetric key (and keyless -  
> aka hash) algorithms compares to AES in strengh. Its weaknesses  
> are: 64-bit block size, and simplistic key schedule. The first  
> weakness is due to algorithm's age (end of 70-ties?), the second  
> one I suspect to be a design compromise. Designers sacrificed  
> strong key schedule for greater key agility. This becomes important  
> when you build hash out of block cipher.
>
> It is illustrative to observe how they approached hash design.  
> Americans took an idea of block cipher, figured that full strength  
> is not needed and simplified the heck out of it - and then put  
> together gazillion of rounds to compensate for the overly  
> simplistic round function. Russians took a real full-strength block  
> cipher, and considering that full strength is not needed -  
> truncated the number of rounds. So encrypting GOST is 32 rounds,  
> while hashing GOST is "only" 16.
>
>
> Subject: [Cfrg] Who agree with building block cipher, hash,MAC with  
> same round function and key schedulel
>
> Dear all:
>
> Integrated proof Method on Iterated Hash Structure and New Structures
> ", the author give an integrated proof method on security proof of
> distinguish the security of Merkel-Damag{\aa}rd structure, wide-pipe
> At last, a new hash called F-hash, MAC called F-MAC and encryption
> model Called FBC-mode are given,  based on same block cipher round
> function and key schedule algorithm, which means with a same block
> cipher round function and key schedule algorithm, we can have a Hash,
> MAC and block cipher and Encryption Mode, the proof based knowledge of
> that was based on security of Feistel structure. The AES with 256 bits
> Who agree with the point of  considering using same round function  
> and key schedule

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 2 Aug 2006 13:42:59 -0700 (PDT)

Hi Uri,

  GOST takes a 64 bit key. A device was built for less than $1 million
that cracks DES using brute force in less than a day. So why couldn't
a similar one crack GOST in 256 days (or less given Moore's law)? I
find it hard to believe that a piece of hardware can be built for less
that $1 million that could crack AES in that amount of time.

  Can you expound on your statement that GOST "compares to AES in
strength".

  Dan.

---

From: "duo lei" <[email-masked]>
Date: Thu, 3 Aug 2006 13:38:15 +0800

Dear Uri and all:

    The  idea about design hash, MAC and block cipher with same round
function and key schdule algorithm is not new,  but one imporatant thing is
that:
" The Feistel Structure is more like a Hash structure than block cipher
structure, if we fixed the right half inputs, the structure become
uninvertible. If we replace the right half input as key, it become MAC."

   I think that properties are important, and some more discussions are
given in the paper.

                             Duo Lei

On 8/2/06, Blumenthal, Uri <[email-masked]> wrote:
> Russian cryptographic suite (Encryption, MAC, Hash) is based
> on old-but-still-strong block cipher GOST 28147, and their Digital Signature
> standard is based on Elliptic Curve Crypto.
>
> algorithm's age (end of 70-ties?), the second one I suspect to be a design
> compromise. Designers sacrificed strong key schedule for greater key
> agility. This becomes important when you build hash out of block cipher.
>
> took an idea of block cipher, figured that full strength is not needed and
> simplified the heck out of it - and then put together gazillion of rounds to
> compensate for the overly simplistic round function. Russians took a real
> full-strength block cipher, and considering that full strength is not needed
> - truncated the number of rounds. So encrypting GOST is 32 rounds, while
> hashing GOST is "only" 16.
>
>
>  ------------------------------
> *From:* duo lei [mailto:[email-masked]]
> *Sent:* Wednesday, August 02, 2006 2:16 AM
> *To:* [email-masked]
> *Subject:* [Cfrg] Who agree with building block cipher, hash,MAC with same
> round function and key schedulel
>
>
>
>  Dear all:
>
> hash, double-pipe hash and 3c hash, the paper also give a new recommend
> structure.
>
> Who agree with the point of  considering using same round function and key
> schedule

---

From: "Hal Finney" <[email-masked]>
Date: Wed, 2 Aug 2006 14:06:11 -0700

On 8/2/06, David McGrew <[email-masked]> wrote:
> The AES limit on the data that can be processed is
> roughly the square of the amount of data that GOST can process.

... and that would be measured in square-bits?  :-)

Hal

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 3 Aug 2006 07:31:26 -0700

> ... and that would be measured in square-bits?  :-)
Why not?  The quantum computer folks use cube-bits.... :-)

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 3 Aug 2006 07:48:03 -0700

> GOST is 32 rounds, while hashing GOST is "only" 16.
There may also be some interesting social aspects to the design.  GOST
28147's variable S-boxes may make life harder for enemy cryptanalysts.  On
the other hand, specifying the S-box separately for each community of
interest makes it difficult to communicate securely outside of certain
authorized paths -- and that fact might have been of interest to, shall we
say, certain parties...

As for the Americans -- remember how everyone marveled that SHA-0 was
structurally so similar to MD5?  Rivest got it right -- even the NSA
couldn't improve on his basic design.  Or was it that the design was
indeed good, so NSA didn't need to disclose one of its one designs?  After
all, look how much of their art open sector cryptographers had learned
from DES -- no point in making that mistake again...?

---

From: Praveen Gauravaram <[email-masked]>
Date: Fri, 04 Aug 2006 09:17:00 +1000

Hi Duo,

> function and key schdule algorithm is not new,  but one imporatant 
> thing is that:
> " The Feistel Structure is more like a Hash structure than block 
> cipher structure, if we fixed the right half inputs, the structure 
> become uninvertible. If we replace the right half input as key, it 
> become MAC."

If I am following you correctly, the latter part is also not new. Ignore 
my reply if I am missing something from what you said. All dedicated 
hash functions that are based on Merkle-Damgard structure ( MD5, SHA-1 
,SHA-256) are unbalanced Feistel networks (UFN) (left half and right 
half are not of equal size). You can also see the compression functions 
of these hash functions as non-linear feedback shift registers.

Take MD5 for example, it is a 64 round 96:32 UFN meaning 96 bits from 
three registers each of 32 bits sit on one side and the remaining 32 
bits of the other register sit on the other side. Similarly, we can see 
SHA-1 as 80-round 32:128 UFN. Likewise, SHA-256 as a coupling of two 
SHA-1 functions.

A detailed explanation on these concepts was given in a paper titled 
"*Unbalanced Feistel Networks and Block-Cipher Design*" by  Bruce 
Schneier and John Kelsey published in FSE 96.

regards
Praveen

>  
>    I think that properties are important, and some more discussions 
> are given in the paper.
>  
>                              Duo Lei
>  
>
>
> On 8/2/06, *Blumenthal, Uri* <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     on old-but-still-strong block cipher GOST 28147, and their Digital
>     strong key schedule for greater key agility. This becomes
>     important when you build hash out of block cipher.
>      
>     simplistic round function. Russians took a real full-strength
>     block cipher, and considering that full strength is not needed -
>         ------------------------------------------------------------------------
>         *From:* duo lei [mailto:[email-masked]
>         <mailto:[email-masked]>]
>         *To:* [email-masked] <mailto:[email-masked]>
>         *Subject:* [Cfrg] Who agree with building block cipher,
>         hash,MAC with same round function and key schedulel
>
>          
>
>     Dear all:
>
>          In the paper http://eprint.iacr.org/2006/147
>     <http://eprint.iacr.org/2006/147>, titled "New
>     [email-masked] <mailto:[email-masked]>
>------------------------------------------------------------------------
>

---

From: "duo lei" <[email-masked]>
Date: Fri, 4 Aug 2006 13:59:51 +0800

Hi Praveen:

I am wondering why you are saying the later part is also not new.

The previous parts give the distribution of hash structures, the conclusions
are that:

The distribution of output of Merkle-Damagard structured hash and wide-pipe
hash may be not close to uniformly distribution, I have not seen other paper

gives such details.

If in wide-pipe hash, we select the compression function as permutation(for
each message) and $G:\{0,1\}^n\rightarrow \{0,1\}^n$ is un-invertiabe, then
the

structure is perfect, but if the compression function is not a permutation(
for each message), the output distribution of this structure is
unpredictable.

In fact, followed the proof of 3c, we also can give the proof of  $\bigoplus
h_i$ is enough for a good structure, the 3c being good are that the output
of

hash value are near to uniformly distribution, the reason is just because
$\bigoplus h_i$ is near to uniformly distribution.

I referred the conditional probability to my paper, the conditional
probability can give a better understanding of hash structures, some
uncertainty become

certain, which was not seen before.

Graph theory used in hash is not new, but building cluster based on it is
new and interesting, and transforming the finding collision to directed
graph is also interesting topic, in my understanding.

The conditional property can become basic tool in crypto system, but I have
not seen it before.

The game technology is also not new, but related the maximum advantage,
conditional probability and existence of collision are also new and
interesting, in my

understanding.

The ideal of building hash based on Feistel structure is different from MD5
and SHA, for the Feistel structure has much interesting property.

Firstly, the un-invertible property of balanced Feistel structure is as
follows:

let $f_{k)(x)$ is round function of Feistel cipher, then $x\oplus
f_{k_i}(x)$ become un-invertible, so in design of block cipher the $f_k(x)$
being a

permutation or not is not important, the Camellia select the $f(x)$ as
permutation, DES use a one way function.

But why the Feistel structure still invertible, the reason is the output of
left half part and right half part have close relation, so if we omit the
half

part of output, the structure becomes un-invertible.

Secondly, the MD5 and SHA still use the whole unbalanced Feistel structure,
each step of the compression function is invertible, the un-invertible
property of

the compression functions of those structures were not based on the
un-invertible property of Feistel structure.

Firstly, one of the basic property of balanced Feistel structured block
cipher or L-R structured block cipher is the encryption and decryption with
same structure, the reason of that is the invertible. However, if we only
output the right or left part of output, then the structure become totally
un-invertible,  which is excellent property for hash.

secondly, many attention have been paid on Feistel structure, no weakness
was found on the round function $f_k(x)$ being a permutation or not, and
also plenty  of results have been given about pseudo random property of
Feistel structured, for fixed key. But, one important thing is the hash
require the pseudo random

property on random selected key. What is interesting are that the left half
input and round key of Feistel Cipher have close relation, we can give a
hash

compression function directly from a Feistel Cipher, just assume the left
half input as message and right half input as chaining value and just output
the

right half part of last round output, where we require the key schedule
algorithm being a pseudo random generator like RC6.

Directly followed the forth point, we give a secure hash compression
function, which has provable security, the security proof is just the
security proof of  Feistel structure, many works have been done on about
this part.

So in my view point, the Feistel structure is good structure for block
cipher, where the best advantage is that structure itself is invertible, and
also the

Feistel structure is good structure for hash function, where the best
advantage of this part also the structure(modified) itself is un-invertible.
This property is very interesting property for Feistel structure. And also
we can build MAC, encryption mode, all based on the intestine property of
Feistel  structure.

All my attention is building some secure structure or giving the proof of
known structure based on some known theory. Because I have not seen those
parts

have been done before.

Sincerely

Duo Lei

---

From: "duo lei" <[email-masked]>
Date: Fri, 4 Aug 2006 14:01:32 +0800

The previous parts give the *probability* distribution of hash structures,
the conclusions are that:

On 8/4/06, duo lei <[email-masked]> wrote:
> The previous parts give the distribution of hash structures, the
> conclusions are that:
>
> The distribution of output of Merkle-Damagard structured hash and
> wide-pipe hash may be not close to uniformly distribution, I have not seen
> other paper
>
> gives such details.
>
> If in wide-pipe hash, we select the compression function as
> permutation(for each message) and $G:\{0,1\}^n\rightarrow \{0,1\}^n$ is
> un-invertiabe, then the
>
> structure is perfect, but if the compression function is not a
> permutation( for each message), the output distribution of this structure is
> unpredictable.
>
> In fact, followed the proof of 3c, we also can give the proof of
> $\bigoplus h_i$ is enough for a good structure, the 3c being good are that
> the output of
>
> The conditional property can become basic tool in crypto system, but I
> have not seen it before.
>
> The ideal of building hash based on Feistel structure is different from
> MD5 and SHA, for the Feistel structure has much interesting property.
>
> But why the Feistel structure still invertible, the reason is the output
> of left half part and right half part have close relation, so if we omit the
> half
>
> Secondly, the MD5 and SHA still use the whole unbalanced Feistel
> structure, each step of the compression function is invertible, the
> un-invertible property of
>
> property on random selected key. What is interesting are that the left
> half input and round key of Feistel Cipher have close relation, we can give
> a hash
>
> > > <mailto:[email-masked] >> wrote:
> > >
> > >         *From:* duo lei [mailto: [email-masked]
> > >     < http://eprint.iacr.org/2006/147>, titled "New

---

From: Praveen Gauravaram <[email-masked]>
Date: Fri, 04 Aug 2006 17:05:54 +1000

Thanks Duo for the detailed explanation. As I said I might have missed 
something as I didn't look at the paper.
 From the first glance at the quoted text, I thought you mean UFNs. So 
you can ignore the letter. However, the reference on UFNs could be a 
useful one for your work. I shall send detailed comments when I get a 
chance to look at the paper.
Best wishes,
Praveen

duo lei wrote:

> The previous parts give the *probability* distribution of hash 
> structures, the conclusions are that:
>
>
>
> On 8/4/06, *duo lei* <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hi Praveen:
>
>     wide-pipe hash may be not close to uniformly distribution, I have
>     not seen other paper
>
>     gives such details.
>
>     permutation(for each message) and $G:\{0,1\}^n\rightarrow
>     \{0,1\}^n$ is un-invertiabe, then the
>
>     permutation( for each message), the output distribution of this
>     structure is unpredictable.
>
>     $\bigoplus h_i$ is enough for a good structure, the 3c being good
>     are that the output of
>
>     hash value are near to uniformly distribution, the reason is just
>     because $\bigoplus h_i$ is near to uniformly distribution.
>
>     I referred the conditional probability to my paper, the
>     conditional probability can give a better understanding of hash
>     structures, some uncertainty become
>
>     Graph theory used in hash is not new, but building cluster based
>     on it is new and interesting, and transforming the finding
>     collision to directed graph is also interesting topic, in my
>     understanding.
>
>     The conditional property can become basic tool in crypto system,
>     but I have not seen it before.
>
>     The game technology is also not new, but related the maximum
>     advantage, conditional probability and existence of collision are
>     also new and interesting, in my
>
>     understanding.
>
>     The ideal of building hash based on Feistel structure is different
>     from MD5 and SHA, for the Feistel structure has much interesting
>     property. 
>
>     Firstly, the un-invertible property of balanced Feistel structure
>     is as follows:
>
>     f_{k_i}(x)$ become un-invertible, so in design of block cipher the
>     $f_k(x)$ being a
>
>     permutation or not is not important, the Camellia select the
>     $f(x)$ as permutation, DES use a one way function.
>
>     But why the Feistel structure still invertible, the reason is the
>     output of left half part and right half part have close relation,
>     so if we omit the half
>
>     structure, each step of the compression function is invertible,
>     the un-invertible property of
>
>     the compression functions of those structures were not based on
>     the un-invertible property of Feistel structure.
>
>      
>
>     Firstly, one of the basic property of balanced Feistel structured
>     block cipher or L-R structured block cipher is the encryption and
>     decryption with same structure, the reason of that is the
>     invertible. However, if we only output the right or left part of
>     output, then the structure become totally un-invertible,  which is
>     excellent property for hash.
>
>     secondly, many attention have been paid on Feistel structure, no
>     weakness was found on the round function $f_k(x)$ being a
>     permutation or not, and also plenty  of results have been given
>     about pseudo random property of Feistel structured, for fixed key.
>     But, one important thing is the hash require the pseudo random
>
>     property on random selected key. What is interesting are that the
>     left half input and round key of Feistel Cipher have close
>     relation, we can give a hash
>
>     compression function directly from a Feistel Cipher, just assume
>     the left half input as message and right half input as chaining
>     value and just output the
>
>     right half part of last round output, where we require the key
>     schedule algorithm being a pseudo random generator like RC6.
>
>     Directly followed the forth point, we give a secure hash
>     compression function, which has provable security, the security
>     proof is just the security proof of  Feistel structure, many works
>     have been done on about this part.
>
>     So in my view point, the Feistel structure is good structure for
>     block cipher, where the best advantage is that structure itself is
>     invertible, and also the
>
>     Feistel structure is good structure for hash function, where the
>     best advantage of this part also the structure(modified) itself is
>     un-invertible. This property is very interesting property for
>     Feistel structure. And also we can build MAC, encryption mode, all
>     based on the intestine property of Feistel  structure.
>
>     All my attention is building some secure structure or giving the
>     proof of known structure based on some known theory. Because I
>     have not seen those parts
>
>     have been done before.
>
>     Sincerely
>
>     Duo Lei 
>
>
>
>     On 8/4/06, *Praveen Gauravaram* < [email-masked]
>     <mailto:[email-masked]>> wrote:
>
>         Hi Duo,
>
>> Dear Uri and all:
>>
>         <mailto:[email-masked]>
>> <mailto:[email-masked]
>         <mailto:[email-masked]>>> wrote:
>>
>         <mailto:[email-masked]>
>>         <mailto:[email-masked]
>         <mailto:[email-masked]>>]
>         <mailto:[email-masked] <mailto:[email-masked]>>
>>     < http://eprint.iacr.org/2006/147
>         <http://eprint.iacr.org/2006/147>>, titled "New
>         function
>         <mailto:[email-masked] <mailto:[email-masked]>>