Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question
From: Kristian Gj�steen on 16 Apr 2010 05:47
Maaartin <grajcar1(a)seznam.cz> wrote:
>In order to give a concrete example of how could it work or fail, I'd
>propose the following: Obviously, the function mustn't not be
>commutative, so what do we have? Matrix multiplication, permutation
>composition, quaternions, something else?
>
>So let F(a, b) be the matrix multiplication in GF(256), let h(x) =
>toRegularMatrix(SHA-512(x)), where toRegularMatrix arranges the 512
>bits as a 8x8 matrix of bytes and avoids singular matrixes by adding
>the unity matrix until the result is regular. This really works and
>toRegularMatrix looses no more than 3 bits of information (you need to
>do the addition at most 7 times 'cause the characteristic polynomial
>at most 8 distinct roots). Can anybody find collisions or any relation
>(besides associativity) here?

Let M be the set of message blocks, let G be a group, and let h: M -> G
be a random function. A collision of the form

h(m1) * ... * h(mk) = h(m1') * ... * h(ml')

can be turned into a collision for h(.) or an identity

g1 * ... * gk = g1' * ... * gl'

in the group G for randomly chosen group elements g1, ..., gk, g1',
...., gl'.

In other words, your minimum requirement is for a group G where, given
a bunch of random elements, it is hard to find a relation like the above.

Certainly, G must be large and very non-commutative (in the sense that
it is very unlikely that two random elements do not commute), but that
isn't enough, is it?

--
Kristian Gj�steen
From: Francois Grieu on 16 Apr 2010 07:19
Le 16/04/2010 01:58, Maaartin a �crit :
> On Apr 15, 11:38 pm, Bryan<bryanjugglercryptograp...(a)yahoo.com>
> wrote:
>> Maaartin asked:
>>
>>> Is there any cryptographic associative hash function? I'd like to have
>>> a collision-resistant function, where the input would be a sequence of
>>> fixed-size blocks (of a couple of KB), which would allow to compute
>>> the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
>>> It should work by first computing the hashes of all blocks using a
>>> standard hash function and combining the hashes using an associative
>>> (and non-commutative) operation.
>>
>> Basic answer: What you seem to be specifically looking for, we do not
>> have. Perhaps you were overly specific as to method.
>
> Maybe I was, maybe tree hashing would do the job, and maybe I don't
> need it at all. I'll think about it, but I find the question very
> interesting.
>
>> Cryptographically, associative one-way functions are a public-key
>> concept. Public-key primitives are vastly harder to realize than
>> conventional crypto confusion/diffusion. Any AOWFs we find are likely
>> to be shaped more like RSA than like SHA-256.
>
> That's strange, I saw something like this in the paper and in the
> answer by Francois, but I see no reason why a SHA-like function
> couldn't do.
>
> In order to give a concrete example of how could it work or fail, I'd
> propose the following: Obviously, the function mustn't not be
> commutative, so what do we have? Matrix multiplication, permutation
> composition, quaternions, something else?
>
> So let F(a, b) be the matrix multiplication in GF(256), let h(x) =
> toRegularMatrix(SHA-512(x)), where toRegularMatrix arranges the 512
> bits as a 8x8 matrix of bytes and avoids singular matrixes by adding
> the unity matrix until the result is regular. This really works and
> toRegularMatrix looses no more than 3 bits of information (you need to
> do the addition at most 7 times 'cause the characteristic polynomial
> at most 8 distinct roots). Can anybody find collisions or any relation
> (besides associativity) here?

Collision resistance of this scheme would be broken if given arbitrary
many random RegularMatrix, it was computationaly possible to exhibit two
different ordered subsets having the same product.
I'm not claiming that this is easy. But clearly it is not related to the
strength of SHA-512, or of some well-studied cryptographic problem like RSA.

Francois Grieu
From: Francois Grieu on 16 Apr 2010 16:30
On 15/04/2010 Maaartin wrote;
> Is there any cryptographic associative hash function? I'd like to have
> a collision-resistant function, where the input would be a sequence of
> fixed-size blocks (of a couple of KB), which would allow to compute
> the hash of all subsequences (a[k], a[k+1], ..., a[k+n]) efficiently.
> It should work by first computing the hashes of all blocks using a
> standard hash function and combining the hashes using an associative
> (and non-commutative) operation.
(..)
>
> Let H(a)=h(a) for length(a) = blocksize, and let H(concat(a, b)) =
> F(H(a), H(b)) for any a, b with a length being a multiple of the
> blocksize. This definition is consistent because of the associativity
> of F.
>
>> - some security property holds.
>> Which property ?
>
> I don't know what is achievable. I'd like to have collision-
> resistance, if possible.
>
> Obviously, for a commutative F, collisions would be trivial, but I
> want associativity and no commutativity.


I throw this to see where it falls, take two:

Notation: ^^ is power, ^ is EXclusive OR, % is reminder of euclidean division.

A trusted party publishes n, such that (n,3) is a valid RSA key, that is with n = p*q, p q huge random primes, p%3 = q%3 = 2. Primes p and q are discarded forever.

We define a pseudo-random function h() from blocks a to [0..n-1], e.g. h(a) = (SHA-512(a)*k1) ^ k2 with k1 = floor(n/(2^^513)), k2 = floor(n/3); or better this could be some established deterministic signature padding scheme of block a, e.g. as defined by standard ISO/IEC 9796-2:2002.

We define the set E = N x [0..n-1] of (j,x) with 0<=j, 0<=x<n.

We define F: E x E -> E as F( (j,x), (k,y) ) = ( (j+k), x*(y^^(3^^j))%n )

Unless I err again, F is associative over E.

We define function H() from blocks to E as H(a) = (1,h(a)). F, H are enough to define a proper "associative hash function", with H(a1, a2, .., an) = ( 1 * a1^^3 * a2^^9 * an^^(3^^n) )%n.


I conjecture that the properties that make the RSA signature scheme with padding h() secure are enough to make the "associative hash function" defined by H and F collision-resistant.


Francois Grieu
From: Maaartin on 16 Apr 2010 17:30
I'll comment on the other messages later.

On Apr 16, 10:30 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> I throw this to see where it falls, take two:
>
> Notation: ^^ is power, ^ is EXclusive OR, % is reminder of euclidean division.
>
> A trusted party publishes n, such that (n,3) is a valid RSA key, that is with n = p*q, p q huge random primes, p%3 = q%3 = 2. Primes p and q are discarded forever.
>
> We define a pseudo-random function h() from blocks a to [0..n-1], e.g. h(a) = (SHA-512(a)*k1) ^ k2 with k1 = floor(n/(2^^513)), k2 = floor(n/3); or better this could be some established deterministic signature padding scheme of block a, e.g. as defined by standard ISO/IEC 9796-2:2002.
>
> We define the set E = N x [0..n-1] of (j,x) with 0<=j, 0<=x<n.
>
> We define F: E x E -> E as F( (j,x), (k,y) ) = ( (j+k), x*(y^^(3^^j))%n )
>
> Unless I err again, F is associative over E.

IMHO, it is, but it has its price: Below you need to include the block
count into the hash. This leaks the message length and makes the hash
longer (but not much, since n must be quite huge). But that's fine.

> We define function H() from blocks to E as H(a) = (1,h(a)). F, H are enough to define a proper "associative hash function", with H(a1, a2, .., an) = ( 1 * a1^^3 * a2^^9 * an^^(3^^n) )%n.

You recycled "n", you're using it both as the RSA number and as the
block count. Let me use "k" for the block count and add missing first
pair member:
H(a1, a2, .., ak) = (k, 1 * a1^^3 * a2^^9 * ak^^(3^^k) % n)
Or did I get it wrong?

> I conjecture that the properties that make the RSA signature scheme with padding h() secure are enough to make the "associative hash function" defined by H and F collision-resistant.

I think so, but I know, it doesn't count.
From: Francois Grieu on 17 Apr 2010 03:23
On 16/04/2010 23:30, Maaartin wrote:
> I'll comment on the other messages later.
>
> On Apr 16, 10:30 pm, Francois Grieu<fgr...(a)gmail.com> wrote:
>> I throw this to see where it falls, take two:
>>
>> Notation: ^^ is power, ^ is EXclusive OR, % is reminder of euclidean division.
>>
>> A trusted party publishes n, such that (n,3) is a valid RSA key, that is with n = p*q, p q huge random primes, p%3 = q%3 = 2. Primes p and q are discarded forever.
>>
>> We define a pseudo-random function h() from blocks a to [0..n-1], e.g. h(a) = (SHA-512(a)*k1) ^ k2 with k1 = floor(n/(2^^513)), k2 = floor(n/3); or better this could be some established deterministic signature padding scheme of block a, e.g. as defined by standard ISO/IEC 9796-2:2002.
>>
>> We define the set E = N x [0..n-1] of (j,x) with 0<=j, 0<=x<n.
>>
>> We define F: E x E -> E as F( (j,x), (k,y) ) = ( (j+k), x*(y^^(3^^j))%n )
>>
>> Unless I err again, F is associative over E.
>
> IMHO, it is, but it has its price: Below you need to include the block
> count into the hash. This leaks the message length and makes the hash
> longer (but not much, since n must be quite huge). But that's fine.

Yes. And computing (y^^(3^^j))%n has cost linear with j [ something like O(j * (Log(n)^^s) ) with s<2 ] for someone not knowing the factorization of n.

>> We define function H() from blocks to E as H(a) = (1,h(a)). F, H are enough to define a proper "associative hash function", with H(a1, a2, .., an) = ( 1 * a1^^3 * a2^^9 * an^^(3^^n) )%n.
>
> You recycled "n", you're using it both as the RSA number and as the
> block count.

Ooops.

> Let me use "k" for the block count and add missing first
> pair member:
> H(a1, a2, .., ak) = (k, 1 * a1^^3 * a2^^9 * ak^^(3^^k) % n)
> Or did I get it wrong?

Fortunately you fixed my two errors. At least this time what I meant was clear in my mind, contrary to "take one".

>> I conjecture that the properties that make the RSA signature scheme with padding h() secure are enough to make the "associative hash function" defined by H and F collision-resistant.
>
> I think so, but I know, it doesn't count.

Some 20 years ago, cryptographic schemes used to be accepted as secure on much worse arguments [e.g. ISO 9796(-1)]; then broken. Academic cryptography has grown up to some degree, and applied cryptography is slowly catching up. But I digress.


I wonder what the security becomes if instead of an RSA modulus we use a public prime p with p%3=2. This has the advantage that we can work on the finite set E = [0..p-2] x [0..p-1] with
F( (j,x), (k,y) ) = ( (j+k)%(p-1), x*(y^^((3^^j)%(p-1))%n )
which has much lower asymptotic cost O((Log(p)^^s) ) with s<3.

Francois Grieu
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: If we could factor large numbers quickly, how exactly does everything break?
Next: HTTP and HTTPS sessions question